我最近和我的一个同事就一个超级简单算法的运行时复杂度进行了非常非常激烈的辩论。最后我们都同意保留不同意见，但我一直在思考这个问题，它挑战了我对计算机科学基础的基本理解，因此我必须对这件事有更多的了解。
给定以下python, Big-O运行时复杂度是多少:
for c in "How are you today?":
print c
现在，我立刻指出这是O(n)的阶也就是线性的。这意味着它依赖于字符串的长度，因此这个循环将随着字符串长度的增长而线性增长。
我的同事接着说:"不，它是常量，因为我们知道对于我们正在处理的所有字符串的集合(在我们的情况下)，最大字符串长度总是255个字符(在我们的情况下)，因此它必须是常量。"他接着说:"因为我们对字符串的字符长度有一个最大上限，所以结果是0(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的上界总是已知的，他断言这篇文章中的两种算法都具有恒定的运行时复杂度。
只是想保持我的理智，但也许如果我错了，肯定会有一些额外的学习我可以从中受益。我的好同事非常有说服力。另外，如果有人有关于这个问题的其他链接或材料，请在评论中添加。
将Big-O符号应用于已知所有输入的单一场景是荒谬的。是没有大o。
整个要点是得到任意大的，未知的n值的最坏情况估计。如果你已经知道了确切的答案，为什么还要浪费时间去估计它呢?
Big-O符号定义为n任意增大:f(n)是O(g(n))如果g(n) ≥ c * f (n ),为任意常数c , 为 n 大于一些 nMin 。也就是说，你的"对手"可以将c设置为"1eventy - quadjlion"，这并不重要，因为对于某些点nMin的所有"右侧"点，"1eventy - quadjlion乘以f(n)"的图形将滞后于g(n)。永远。
例子:2 <一口> n 是 <</em>或 n <一口> 2> = 2,3和4的x轴短段(在n = 3,2 n为8，而n2为9)。这并不能改变它们的大O关系是相反的事实:O(2n2)比O(n2)大得多，因为大O告诉关于n小于nMin的值没有。如果将nMin设置为4(从而忽略4左边的图形)，您将看到n2行永远不会超过2n行。
如果你的"对手"将n2乘以某个更大的常数c，使"他的"n2线高于你的2n线，你还没有输……你只要把nMin向右滑动一点。大o说不管他的方程c有多大，你总能找到一个点，在这个点之后他的方程失效，而你的方程永远有效。
但是，如果你把n限制在右边，你就违反了任何大o分析的先决条件。在你和同事的争论中，你们中的一个人发明了nMax，然后另一个人发明了nMin在它右边的某个地方——令人惊讶的是，结果是荒谬的。
例如，你展示的第一个算法确实对长度n的输入做了关于n的工作…一般情况下。如果我要构建自己的算法，调用它n次，我将不得不考虑我的二次O(n2)算法…同样，在一般情况下。 但是，如果我可以证明我永远不会在输入大于10的情况下调用你的算法(这意味着我有更多的信息，因此可以更精确地估计我的算法)，使用大0来估计你的算法的性能将会扔掉我所了解的实际行为，在我关心的情况下。我应该用一个合适的大常数来代替你的算法——把我的算法从c * n2改成c * 10 * n…也就是cBigger * n。我可以诚实地说我的算法是线性的，因为在这种情况下，你的算法的图永远不会超过这个常数值。这将改变没有关于你的算法的大o性能，因为大o不是为这样的约束情况定义的。总结:一般来说，，你展示的第一个算法是按大0标准线性的。在约束的情况下，其中最大输入是已知的，用大0术语来谈论它是一个错误。在约束的情况下，当讨论的大0行为时，可以用某个常数值合法地替换，但这绝对不能说明第一个算法的大0行为。
综上所述，当nMax足够小时，O(Ackermann(n))可以很好地工作。非常非常小……在你的情况下…
我很想说你的朋友有点错。这是因为在O(1)运行时间中有相当大的附加常数256。你的朋友说执行是0(256)。因为我们忽略了大0中的常数，我们简单地称0(256 * 1)为O(1)你可以决定这个常数对你来说是否可以忽略。我有两个强有力的理由说你是对的:
首先，对于n的各种值，您的答案O(n)(在第一段代码中)给出了更好的运行时间近似值。例如:
- 对于长度为4的字符串:你说运行时间正比于4，而你的朋友说它正比于1(或256)。
- 对于长度为255的字符串:你说运行时间与255成正比，而你的朋友又说它是常数时间。
显然，你的答案在任何情况下都更准确，尽管他的答案并不是完全错误的。
其次，如果你采用你朋友的方法，那么在某种意义上你可以欺骗说，因为没有字符串可以超过你的RAM +磁盘大小，因此所有的处理都在O(1)中。这时你朋友推理的谬误就显现出来了。是的，他是对的，运行时间(假设1TB硬盘和8GB内存)是0 ((1TB + 8GB) *1) = 0(1)，但在这种情况下，您根本不能忽略常量的大小。
Big-O复杂度并没有告诉我们实际的执行时间，而只是告诉我们随着n值的增加，运行时间的简单增长率。
我觉得你都是对的。
第一个算法的运行时间与输入的大小呈线性关系。但是，如果它的输入是固定的，那么它的运行时间也是固定的。
大O是关于在输入变化时测量算法的行为。如果输入没有改变，那么大O是没有意义的。
也:O(n)意味着复杂度的上界是n。如果你想表示紧界，那么更精确的表示法是Θ(n) (theta表示法)。
你们在某种程度上都是对的，但你比你的同事更对。(编辑:不。仔细想想，你是对的，你的大学是错的。请看下面我的评论。)问题不在于N是否已知，而在于N能否改变。s是你算法的输入吗?那么它就是O(N)或者O(N^2)你知道这个特定输入的N的值，但是不同的输入会有不同的值，所以知道这个输入的N是无关的。
这是你们两种方法的不同之处。您将这段代码视为如下所示:
def f(s):
for c in s:
print c
f("How are you today?")
但是你的同事是这样对待它的:
def f(some_other_input):
for c in "How are you today?":
print c
f("A different string")
在后一种情况下，for循环应该被认为是O(1)，因为不会随着不同的输入而改变。对于前一种情况，算法为O(N)。