有没有什么情况下你更喜欢O(log n)时间复杂度而不是O(1)时间复杂度?还是O(n)到O(log n)
你能举个例子吗?
有没有什么情况下你更喜欢O(log n)时间复杂度而不是O(1)时间复杂度?还是O(n)到O(log n)
你能举个例子吗?
当前回答
简单地说:因为系数(与该步骤的设置、存储和执行时间相关的成本)在较小的大o问题中比在较大的大o问题中要大得多。Big-O只是算法可伸缩性的一个衡量标准。
考虑以下来自黑客词典的例子,提出了一个依赖于量子力学的多重世界解释的排序算法:
用量子过程随机排列数组, 如果数组没有排序,毁灭宇宙。 所有剩下的宇宙现在都被排序了(包括你所在的宇宙)。
(来源:http://catb.org/ esr /术语/ html / B / bogo-sort.html)
注意,这个算法的大O是O(n),它击败了迄今为止在一般项目上的任何已知排序算法。线性阶跃的系数也很低(因为它只是一个比较,而不是交换,是线性完成的)。事实上,类似的算法可以用于在多项式时间内解决NP和co-NP中的任何问题,因为每个可能的解(或没有解的可能证明)都可以使用量子过程生成,然后在多项式时间内验证。
然而,在大多数情况下,我们可能不想冒多重世界可能不正确的风险,更不用说实现步骤2的行为仍然是“留给读者的练习”。
其他回答
总有一个隐藏常数,在O(log n)算法中可以更低。因此,在实际生活数据中,它可以更快地工作。
还有空间问题(比如在烤面包机上运行)。
还有开发人员的时间问题——O(log n)可能更容易实现和验证1000倍。
当n很小时,O(1)总是很慢。
简单地说:因为系数(与该步骤的设置、存储和执行时间相关的成本)在较小的大o问题中比在较大的大o问题中要大得多。Big-O只是算法可伸缩性的一个衡量标准。
考虑以下来自黑客词典的例子,提出了一个依赖于量子力学的多重世界解释的排序算法:
用量子过程随机排列数组, 如果数组没有排序,毁灭宇宙。 所有剩下的宇宙现在都被排序了(包括你所在的宇宙)。
(来源:http://catb.org/ esr /术语/ html / B / bogo-sort.html)
注意,这个算法的大O是O(n),它击败了迄今为止在一般项目上的任何已知排序算法。线性阶跃的系数也很低(因为它只是一个比较,而不是交换,是线性完成的)。事实上,类似的算法可以用于在多项式时间内解决NP和co-NP中的任何问题,因为每个可能的解(或没有解的可能证明)都可以使用量子过程生成,然后在多项式时间内验证。
然而,在大多数情况下,我们可能不想冒多重世界可能不正确的风险,更不用说实现步骤2的行为仍然是“留给读者的练习”。
以下是我的观点:
有时,当算法在特定的硬件环境中运行时,会选择较差的复杂度算法来代替较好的算法。假设我们的O(1)算法非顺序地访问一个非常大的固定大小数组的每个元素来解决我们的问题。然后将该阵列放在机械硬盘驱动器或磁带上。
在这种情况下,O(logn)算法(假设它按顺序访问磁盘)变得更有利。
对于安全应用程序来说,这经常是这样的情况,我们希望设计算法缓慢的问题,以阻止某人过快地获得问题的答案。
这里有几个我能想到的例子。
Password hashing is sometimes made arbitrarily slow in order to make it harder to guess passwords by brute-force. This Information Security post has a bullet point about it (and much more). Bit Coin uses a controllably slow problem for a network of computers to solve in order to "mine" coins. This allows the currency to be mined at a controlled rate by the collective system. Asymmetric ciphers (like RSA) are designed to make decryption without the keys intentionally slow in order to prevent someone else without the private key to crack the encryption. The algorithms are designed to be cracked in hopefully O(2^n) time where n is the bit-length of the key (this is brute force).
在CS的其他地方,快速排序在最坏的情况下是O(n²),但在一般情况下是O(n*log(n))。因此,在分析算法效率时,“大O”分析有时并不是您唯一关心的事情。