在算法时间复杂度上，总是O(1)优于O(n)？
我在问如果我有一个算法需要O(100) -> O(1)时间复杂度，我有一个算法需要O(n)来解决，但是如果我知道它的最大值是50，那么我可以决定最坏的情况是O(50)，所以在这样的情况下，O(1)算法或第二个O(n)算法是最好的选择？因此，如果是第二个，我们是否总是可以告诉O(1)比O(n)更好？
回答 2
Stack Overflow用户
发布于 2019-12-05 15:54:47
当然，不是；并不总是这样。大O只是一种渐近行为，这就是为什么
O(1) == O(0.001) == O(50) == O(100) == O(C) # where C is any positive constantO(n)也是如此
O(n) == O(0.001n) == O(100n) == O(C * n) # where C is any positive constant想象两个带定时的算法
t1 = 1e100 (seconds) = O(1)
t2 = n (seconds) = O(n)对于无限的n (渐近行为)，第一种算法比第二种算法更好，但对于所有现实世界的情况(小n)，t2更可取。仅仅伸缩是不够的：
t1 = 1000 (seconds)
t2 = 100 * n (seconds)
t3 = n + 1e100 * log(n) (seconds)算法3具有更好的伸缩性(1与100：n与100 * n)，但1e100 * log(n) term使其无法在现实世界中完成。
因此，在一般情况下，应该比较函数而不是O
t1 = 100 (seconds)
t2 = n (seconds)在这里，如果是n <= 50，那么t2是更好的选择(而对于n > 1000，我们有完全相反的选择)
Stack Overflow用户
发布于 2019-12-06 01:30:21
两种算法：
100n -> O(n)
10n² -> O(n²)当n< 10时，二次时间算法更好。当n> 10时，线性时间算法更好。
还有一些实际的用例。快速排序算法(avg: O(n log(N)通常在给定数据集合足够小的情况下使用插入排序(avg: O(n²))。
https://stackoverflow.com/questions/59189272
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号