以下伪代码的运行时复杂度(大O)是多少？

Question

我最近与我的同事就一个超简单算法的运行时复杂性进行了非常非常激烈的辩论.最后我们都同意不同意,但正如我一直在考虑的那样,它挑战了我对计算机科学基础的基本理解,因此我必须对这个问题有更多的了解.

鉴于以下python,Big-O运行时复杂性是什么:

for c in "How are you today?":
    print c

现在,我立刻喊出这只是O(n)又名线性的顺序.这意味着它取决于字符串的长度,因此这个循环将随着字符串长度的增长而线性增长.

我的同事随后说:"不,它是常数,因为我们知道对于我们正在处理的所有字符串集合(在我们的例子中),最大字符串总是255个字符长(在我们的例子中),因此它必须是常量. " 他接着说:"因为我们在字符串的字符长度上有一个最大上限,这导致O(255)减少到O(1)."

无论如何,我们回到了第四,在我们两个人画了草图的45分钟后,我们都死在这个问题上.

我的问题是在一个恒定时间循环之上的循环是什么世界或什么数学系统？如果我们知道我们的上限是1,000,000个字符,并且所有字符串的集合可以是从0到1,000,000的任何地方,那么这个循环显然会表现出线性运行时间,具体取决于字符串的大小.

我还问他,如果n的上限大小已知,他是否还认为以下代码是O(1).这意味着我们确定这段代码只会在255个字符的最大上限上运行:

s = "How are you today?"
for c in s:
    for d in s:
        print c+d

他说这也是恒定时间....即使在我解释这是一个O(n ^ 2)算法并证明以下代码将产生二次曲线.

那么,我是否缺少一些理论概念,其中任何一个都是真的,这取决于理论如何发展？ 只是要清楚他的理解是,如果不知道n,我是正确的.如果n的上限总是已知的,那么他断言这篇文章中的两个算法都具有恒定的运行时复杂性.

只是想保持我的理智,但也许如果我错了,肯定会有一些额外的学习,我可以从中受益.我的好同事非常有说服力.此外,如果任何人有关于此问题的主题的其他链接或材料,请添加评论.

Answer 1

将Big-O表示法应用于已知所有输入的单个场景是荒谬的.这里是没有大O的一个案例.

重点是得到n的任意大的未知值的最坏情况估计.如果您已经知道确切的答案,为什么在地球上你会浪费时间去估算它？

Mathy /计算机科学编辑:

大O符号被定义为ñ生长任意大:F(Ñ)为O(克(Ñ))如果g(Ñ)≥ Ç*F(Ñ),对于任何恒定Ç,对于所有Ñ大于一些NMIN.意思是,你的"对手"可以将c设置为"十一 - 四十亿"并且没关系,因为对于某些点"向右"的所有点nMin,"十一 - 四十亿次f(n)" 的图形将永远滞后于g(n)......

实施例:2 ^Ñ是小于或等于ñ ² ...为x轴的短片段,其包括Ñ = 2,3和4(在Ñ = 3,2 ^Ñ为8,而Ñ ²是9 ).这并没有改变他们的Big-O关系相反的事实:O(2 ⁿ)远大于O(n ²),因为Big-O 没有说n值小于nMin.如果你将nMin设置为4(因此忽略4左边的图形),你会看到n ²行从不超过2 ⁿ线.

如果你的"对手"乘ñ ²通过一些较大的常数ç提高"他的" ň ²线上方2 ^ñ线,你还没有失去尚未...你只是滑动NMIN向右一点.大O说,不管他做多大Ç,你可以随时找到一个点之后,他的方程失去和你赢了,永远.

但是,如果你限制ñ在右边,你已经违反了任何一种大O分析的先决条件.在你与同事的争论中,你们中的一个人发明了一个nMax,然后另一个人将nMin设置在它的右边 - 惊讶的是,结果是荒谬的.

例如,在一般情况下,您展示的第一个算法确实对n长度为n的输入进行了操作.如果我正在构建我自己的算法n次调用它,我将不得不考虑我的二次O(n ²)算法......在一般情况下.

但是,如果我能证明我永远不会用大于10的输入调用你的算法(这意味着我有更多的信息,因此可以更准确地估计我的算法),使用Big-O来估计你的算法的性能就会丢掉什么在我关心的情况下,我了解了它的实际行为.我应该用一个适当大的常数替换你的算法---将我的算法从c*n ²改为c*10*n ......这只是cBigger*n.我可以诚实地声称我的算法是线性的,因为在这种情况下,你的算法的图形永远不会超过那个常数值.这对于算法的Big-O性能没有任何改变,因为Big-O没有为像这样的约束情况定义.

总结: 通常,您展示的第一个算法是Big-O标准的线性算法.在一个约束的情况下,最大输入是已知的,用Big-O术语来说它是错误的.在一个受约束的情况下,在讨论其他算法的Big-O行为时,它可以合理地被一些常量值替换,但这绝对没有说明第一个算法的Big-O行为.

总结:O(Ackermann(n))在nMax足够小时工作正常.非常非常小......