以下伪代码的运行时复杂性（big O）是多少？

Question

最近我和我的一个同事就超简单算法的运行时复杂性进行了一场非常非常激烈的辩论。最后我们都同意不同意，但我一直在思考这个问题，这挑战了我对计算机科学基础知识的基本理解，因此我必须对这件事有更多的了解。在

给定以下python，Big-O运行时的复杂性是什么：

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

现在，我马上指出，这只是在O（n）的阶上，也就是线性的。这意味着它依赖于字符串的长度，因此这个循环将随着字符串长度的增长而线性增长。在

我的同事接着说，“不，它是常量，因为我们知道对于我们处理的所有字符串集合（在我们的例子中），max string总是255个字符长（在我们的例子中），他接着说：“因为我们对字符串的字符长度有一个最大的上限，这就导致了O（255），它减少到O（1）。”

不管怎样，我们回到第四位，在45分钟的素描之后，我们都锁定了这个问题。在

在这个循环中，时间循环是什么？如果我们知道上限是1000000个字符，并且所有字符串的集合可以是0到1000000之间的任何地方，那么这个循环显然会显示线性运行时间，这取决于字符串的大小。在

我还问他，如果知道n的上限大小，他是否也认为下面的代码是O（1）。这意味着我们确信此代码只能在255个字符的最大上限上运行：

^{pr2}$

他说这也是常数时间，即使我解释了这是一个O（n^2）算法，并证明了下面的代码会产生一个二次曲线。在

那么，我是否遗漏了一些理论概念，根据理论的发展，上面的任何一个都是正确的？为了明确他的理解，如果不知道n，我是正确的。如果n的上界总是已知的，他就断言这篇文章中的两个算法都具有恒定的运行时复杂性。

我只是想保持我的理智，但如果我错了，我当然可以从中学到一些额外的东西。我的好同事很有说服力。此外，如果任何人有关于这个问题的主题的额外链接或材料，请添加到评论。在

Answer 1

对你来说

我很想说你的朋友错得很轻。这是因为在O（1）运行时间中有相当大的附加常数256。你朋友说死刑是O（256）。因为我们忽略了Big-O中的常数，所以我们把O（256*1）称为O（1）。这个常数对你来说是否可以忽略，这取决于你自己。在

---

我有两个强有力的理由说你是对的：

首先，对于不同的n值，您对O（n）（在第一个代码中）的回答给出了更好的运行时间近似值。例如：

1. 对于长度为4的字符串：您说运行时与4成正比，而您的朋友说它与1（或256）成正比。在
2. 对于长度为255的字符串：你说运行时间与255成正比，而你的朋友又说这是恒定时间。在

很明显，你的答案在任何情况下都更准确，即使他的回答不是完全错误的。在

其次，如果你用你朋友的方法，那么在某种意义上你可以欺骗说，因为没有字符串可以超过你的RAM+磁盘大小，因此所有的处理都在O（1）中。这时，你朋友的推理谬误就显现出来了。是的，他是对的，运行时间（假设1TB硬盘和8GB RAM）是O（（1TB+8GB）*1）=O（1），但在这种情况下，您不能忽略常数的大小。

---

Big-O复杂度并不能说明实际的执行时间，而只是随着n值的增加，运行时间的简单增长率。

Answer 2

将Big-O表示法应用于所有输入都已知的单个场景是可笑的。一个病例没有大O。在

关键是得到任意大的n未知值的最坏情况估计。如果你已经知道确切的答案，你为什么还要浪费时间去估计它呢？在

数学/计算机科学编辑：

Big-O表示法定义为n任意增长：如果g（n）≥c，则f（n）为O（g（n）≥c*f（n），对于所有n大于某些nMin。意思是，你的“对手”可以将c设置为“eleventy quadjillion”，这并不重要，因为对于某个点的“右侧”所有点，“eleventy quadjillion乘以f（n）”的图形将落后于g（n）。。。永远。在

Example: 2ⁿ is less than or equal to n²... for a short segment of the x-axis that includes n = 2, 3, and 4 (at n = 3, 2ⁿ is 8, while n² is 9). This doesn't change the fact that their Big-O relationship is the opposite: O(2ⁿ) is much greater than O(n²), because Big-O says nothing about n values less than nMin. If you set nMin to 4 (thus ignoring the graph to the left of 4), you'll see that the n² line never exceeds the 2ⁿ line.

If your "opponent" multiplies n² by some larger constant c to raise "his" n² line above your 2ⁿ line, you haven't lost yet... you just slide nMin to the right a bit. Big-O says that no matter how big he makes c, you can always find a point after which his equation loses and yours wins, forever.

但是如果你把n限制在右边，你就违反了任何一种Big-O分析的先决条件。在你和你同事的争论中，你们中的一个发明了一个nMax，而另一个则在它右边的某个地方发明了一个nMin——令人惊讶的是，结果毫无意义。在

例如，您展示的第一个算法确实对长度为n的输入进行了工作。。。一般情况下。如果我在构建自己的算法，称之为n次，我将不得不考虑我的二次O（n²）算法。。。同样，在一般情况下。在

但是如果我能证明我永远不会用大于10的输入调用你的算法（这意味着我有更多的信息，因此可以更精确地估计我的算法），用Big-O来估计你的算法的性能，那将是在我所关心的情况下，放弃我所学的关于它的实际行为的知识。我应该用一个适当大的常数来代替你的算法——把my算法从c*n²改为c*10*n。。。这就是cbiger*n。我可以说我的算法是线性的，因为在这个例子中，你的算法的图永远不会超过这个常量。这不会改变算法的Big-O性能，因为Big-O并不是针对这样的约束情况定义的。在

总而言之：总的来说，您展示的第一个算法在Big-O标准下是线性的。在一个约束的情况下，最大输入是已知的，用Big-O术语来描述它是一个错误。在一个约束的情况下，当讨论其它算法的大O行为时，它可以被某个常数值合法地代替，但这并不能说明第一个算法的大O行为。在

结论：当nMax足够小时，O（Ackermann（n）工作良好。非常非常小。。。在

Answer 3

你俩都是对的。在

第一个算法的运行时在其输入大小上是线性的。但是，如果它的输入是固定的，那么它的运行时也是固定的。在

大O是关于测量一个算法在其输入改变时的行为。如果输入永远不变，那么大O就没有意义了。在

另外：O（n）表示复杂度的上界是n。如果你想表示一个紧界，那么更精确的表示法是Θ（n）（θ表示法）。在