时间复杂度or“假溢出”

巴巴鲁

一个程序，重要的是时间复杂度还是什么？
比如说一个队列，如果定义结构体，会出现假溢出的情况（时间复杂度o(1)）
但是改进一下，不用考虑“假溢出”了，但时间复杂度会变成O(n)
请问需不需要改进，回答好的另外有奖励
@愷龍 @永恒的蓝色梦想  @乐乐学编程 @昨非

巴巴鲁

@小甲鱼的铁粉

i6720

进来看看 学学

小甲鱼的铁粉

我觉得看情况吧，根据实际的情况选择是牺牲空间还是牺牲时间，还是得看实际的要求

一抹心尘

等待大佬

乐乐学编程

我还没学到 “时间复杂度” 和 “空间复杂度”

愷龍

没有绝对的空间和时间都能兼顾，在平时我们要么会牺牲时间来节约空间，要么一牺牲空间来节约时间，我可以可以通过一些算法来使得时间和空间达到最大的利用，使得相互的牺牲达到一种相对最好的平衡。

斌小白

同等

wzdr

没有看懂

hornwong

不太明白

心驰神往

看大佬们

巴巴鲁

愷龍 发表于 2020-10-29 07:08
没有绝对的空间和时间都能兼顾，在平时我们要么会牺牲时间来节约空间，要么一牺牲空间来节约时间，我可以可 ...

确实，也不知道有没有一种算法兼顾时间和空间

巴巴鲁

乐乐学编程 发表于 2020-10-29 02:35
我还没学到 “时间复杂度” 和 “空间复杂度”

其实就是一个定义

noti

进来看看，有没有送渔币

小摩的滴滴滴

币币

赚小钱

1. 个人理解，应该将 “假溢出” 视为程序的 Bug，因此，有 bug 的程序无论多快都是纸老虎
2. 运行在一般计算机上的一般程序，随着项目发展，应按照 make it works -> make it right -> make it fast 的顺序设计，编写代码
3. 在对性能没有极致要求的时候，代码的可阅读性是最重要的，没有之一
4. 当需要优化性能时，多数情况考虑优化时间复杂度，若算法方面没有质变，则一般采用空间换时间的方案，空间靠花钱
5. 其他特殊情况特殊处理，比如小霸王游戏机卡

巴巴鲁

赚小钱 发表于 2020-11-2 16:22
1. 个人理解，应该将 “假溢出” 视为程序的 Bug，因此，有 bug 的程序无论多快都是纸老虎
2. 运行在一般 ...

既然栈和队列是特殊的数组，那我觉得一些简单的应用完全可以用数组来解决，虽然会提升时间复杂度，但是不会出现“假溢出”
数据结构那本书，我看都是用结构体来做的

赚小钱

巴巴鲁 发表于 2020-11-2 21:18
既然栈和队列是特殊的数组，那我觉得一些简单的应用完全可以用数组来解决，虽然会提升时间复杂度，但是不 ...

首先，我没看过你说的那本书，不清楚你所谓的数据结构是什么意思。

我推测是定义了某种类似于 struct Queue 的数据类型。如果推测无误，那我是赞同这种定义数据类型的编码方式，且远优于直接使用数组。

因为，用户，或者说开发者只想要的是一种支持先进先出的线性数据结构，具体到使用上表现为 queue.push queue.pop 两个函数，至于是使用数组，还是链表，还是双向链表，亦或是循环链表什么的，谁又会关心呢？

而且，还是那句话，你所谓的假溢出完全是一个 bug ，与你直接用数组做队列，还是将数组封装到一个叫做 Queue 的结构体中，完全没有关系。

然后说一下你的表述问题，无论是栈还是队列都不能被称作特殊的数组。
一般的数据结构或者算法教材会称作线性表，链表。这两者都是空间维度的概念，即逻辑上相邻的元素的空间关系。而队列与栈是对元素操作的规则定义。以上四个概念有一个共同点，他们都是一维空间。因此，栈与队列的实现方式是基于线性表或者链表。

接着，我不清楚你为何会说数组会增加时间复杂度。不用数组还能有什么呢，链表吗？双指针它不香吗，再不行加一个实际长度也是好的呀。

最后，还是看一些正统的教材吧，那种能帮你区分线性表链表与栈队列的教材，如果是英文教材就更好了。
在学习数据结构与算法设计的同时，最好也学习下程序设计，比如面向对象编程，或者设计模式。然后你就会发现用结构体是理所当然的方法。

祝，编程快乐，不需要解决太多的 bug。

i6720

好好学习学习

象棋爱好者

领鱼币