以下伪代码的运行时复杂度（大 O）是多少？
What is the runtime complexity (big O) of the following pseudocode?
我最近与我的一位同事就一个超级简单算法的运行时复杂性进行了一场非常非常激烈的辩论。最后我们都同意不同意，但由于我一直在思考这个问题，它挑战了我对计算机科学基础知识的基本理解，因此我必须对此事有更多的了解。
给定以下 python，Big-O 运行时复杂度是多少：
for c in "How are you today?":
print c
现在，我立即大声说这只是 O(n) 的量级，也就是线性的。这意味着它取决于字符串的长度，因此此循环将随着字符串长度的增长而线性增长。
然后我的同事说，"No, it's constant because we know that for the set of all strings we are dealing with (in our case), the max string is always 255 characters long (in our case), therefore it must be constant."他接着说"because we have a max upper-bound on character length of the string this results in O(255) which reduces to 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 的上限总是已知的，他断言此 post 上的两个算法都具有恒定的运行时复杂度。
只是想保持理智，但如果我错了，我肯定可以从中受益的一些额外学习。我的好同事非常有说服力。另外，如果有人有其他链接或 material 关于这个问题的特定主题，请添加到评论中。
我认为你们都是对的。
第一个算法的运行时间与其输入大小成线性关系。但是，如果它的输入是固定的，那么它的运行时间也是固定的。
Big O 就是衡量算法随着输入变化 的行为。如果输入永远不变，那么Big O就没有意义了。
另外：O(n) 表示复杂度的 上限 为 N。如果要表示 紧界 那么更精确的表示法是 Θ(n)（theta 表示法）。
将 Big-O 符号应用于所有输入已知的单个场景是荒谬的。 没有一个案例没有Big-O。
重点是获得任意大的最坏情况估计，未知值n。如果你已经知道确切的答案，为什么还要浪费时间去估计呢？
Mathy / 计算机科学编辑：
Big-O 表示法定义为 n 增长任意大：f(n) 是 O(g(n)) 如果 g(n) ≥ c * f(n ), 对于任何常数 c, for all n 大于一些 nMin。意思是，您的 "opponent" 可以将 c 设置为 "eleventy-quadjillion" 并且没关系，因为对于某个点的所有点 "to the right" nMin，"eleventy-quadjillion times f(n)" 的图形将永远滞后于 g(n)...。
Example: 2n is less than or equal to n2... for a short segment of the x-axis that includes n = 2, 3, and 4 (at n = 3, 2n is 8, while n2 is 9). This doesn't change the fact that their Big-O relationship is the opposite: O(2n) is much greater than O(n2), 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 n2 line never exceeds the 2n line.
If your "opponent" multiplies n2 by some larger constant c to raise "his" n2 line above your 2n 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... 在一般情况下案件。如果我正在构建自己的算法并调用它 n 次，我将不得不考虑我的二次 O(n2 ) 算法...同样，在一般情况下。
但如果我能证明我永远不会用大于 10 的输入调用你的算法（意味着我有更多信息，因此可以更准确地估计我的算法） ，在我关心的情况下，使用 Big-O 来估计你的算法的性能会丢弃我所了解的关于它的 actual 行为的知识。我应该用一个适当大的常数替换你的算法---从 c * n[=76= 更改 my 算法]2 到 c * 10 * n... 这只是 cBigger * n。老实说，我的算法是线性的，因为 在这种情况下 ，你的算法图永远不会超过该常数值。这将改变没有关于你的算法的 Big-O 性能，因为 Big-O 没有为像这样的受限情况定义。
总结：总的来说，按照 Big-O 标准，您展示的第一个算法是线性的。在 约束情况 中，最大输入是已知的，用 Big-O 术语来谈论它是完全错误的。在受限的情况下，在讨论 其他一些算法 的 Big-O 行为时，它 可以 合法地替换为某个常数值，但这绝对是与第一个算法的 Big-O 行为无关。
结论：O(Ackermann(n)) 在 nMax 足够小的情况下工作正常。非常非常小了...
从某种意义上说，你们都对，但你比你的同事更正确。 （编辑： 不。进一步思考，你是对的，你的同事是错误的。请参阅下面我的评论。）真正的问题不是 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).
你的情况...
我很想说你的朋友是软弱的错误。这是因为在 O(1) 运行 时间 中 相当大的附加常量 256。你的朋友说执行是 O(256)。因为我们忽略了 Big-O 中的常量，所以我们简单地将 O(256 * 1) 称为 O(1)。由您决定这个常数对您是否可以忽略不计。
我有两个充分的理由说你是对的：
首先，对于 n 的各种值，您的 O(n) 答案（在第一个代码中）给出了 运行ning 时间的更好近似值。例如：
- 对于长度为 4 的字符串： 你说 运行-时间与 4 成正比，而你朋友说它与 1（或 256）成正比。
- 对于长度为 255 的字符串： 你说 运行ning 时间与 255 成正比，而你的朋友又说它是常数时间。
显然，你的回答在每种情况下都更准确，即使他的回答并非完全错误。
其次，如果你按照你朋友的方法去做，那么在某种意义上你可以作弊并说因为没有字符串可以超过你的 RAM + 磁盘大小，因此所有处理都在 O(1) 中。那就是你朋友推理的谬误变得明显的时候。 是的，运行宁时间（假设 1TB 硬盘和 8GB RAM）是 O((1TB + 8GB) *1) = O(1)，他是对的，但你不能忽略这种情况下常量的大小。
Big-O 复杂度并不能说明实际的执行时间，而只是简单地说明 运行ning 时间随着 n 值的增加而增长的速度。
我最近与我的一位同事就一个超级简单算法的运行时复杂性进行了一场非常非常激烈的辩论。最后我们都同意不同意，但由于我一直在思考这个问题，它挑战了我对计算机科学基础知识的基本理解，因此我必须对此事有更多的了解。
给定以下 python，Big-O 运行时复杂度是多少：
for c in "How are you today?":
print c
现在，我立即大声说这只是 O(n) 的量级，也就是线性的。这意味着它取决于字符串的长度，因此此循环将随着字符串长度的增长而线性增长。
然后我的同事说，"No, it's constant because we know that for the set of all strings we are dealing with (in our case), the max string is always 255 characters long (in our case), therefore it must be constant."他接着说"because we have a max upper-bound on character length of the string this results in O(255) which reduces to 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 的上限总是已知的，他断言此 post 上的两个算法都具有恒定的运行时复杂度。
只是想保持理智，但如果我错了，我肯定可以从中受益的一些额外学习。我的好同事非常有说服力。另外，如果有人有其他链接或 material 关于这个问题的特定主题，请添加到评论中。
我认为你们都是对的。
第一个算法的运行时间与其输入大小成线性关系。但是，如果它的输入是固定的，那么它的运行时间也是固定的。
Big O 就是衡量算法随着输入变化 的行为。如果输入永远不变，那么Big O就没有意义了。
另外：O(n) 表示复杂度的 上限 为 N。如果要表示 紧界 那么更精确的表示法是 Θ(n)（theta 表示法）。
将 Big-O 符号应用于所有输入已知的单个场景是荒谬的。 没有一个案例没有Big-O。
重点是获得任意大的最坏情况估计，未知值n。如果你已经知道确切的答案，为什么还要浪费时间去估计呢？
Mathy / 计算机科学编辑：
Big-O 表示法定义为 n 增长任意大：f(n) 是 O(g(n)) 如果 g(n) ≥ c * f(n ), 对于任何常数 c, for all n 大于一些 nMin。意思是，您的 "opponent" 可以将 c 设置为 "eleventy-quadjillion" 并且没关系，因为对于某个点的所有点 "to the right" nMin，"eleventy-quadjillion times f(n)" 的图形将永远滞后于 g(n)...。
Example: 2n is less than or equal to n2... for a short segment of the x-axis that includes n = 2, 3, and 4 (at n = 3, 2n is 8, while n2 is 9). This doesn't change the fact that their Big-O relationship is the opposite: O(2n) is much greater than O(n2), 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 n2 line never exceeds the 2n line.
If your "opponent" multiplies n2 by some larger constant c to raise "his" n2 line above your 2n 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... 在一般情况下案件。如果我正在构建自己的算法并调用它 n 次，我将不得不考虑我的二次 O(n2 ) 算法...同样，在一般情况下。
但如果我能证明我永远不会用大于 10 的输入调用你的算法（意味着我有更多信息，因此可以更准确地估计我的算法） ，在我关心的情况下，使用 Big-O 来估计你的算法的性能会丢弃我所了解的关于它的 actual 行为的知识。我应该用一个适当大的常数替换你的算法---从 c * n[=76= 更改 my 算法]2 到 c * 10 * n... 这只是 cBigger * n。老实说，我的算法是线性的，因为 在这种情况下 ，你的算法图永远不会超过该常数值。这将改变没有关于你的算法的 Big-O 性能，因为 Big-O 没有为像这样的受限情况定义。
总结：总的来说，按照 Big-O 标准，您展示的第一个算法是线性的。在 约束情况 中，最大输入是已知的，用 Big-O 术语来谈论它是完全错误的。在受限的情况下，在讨论 其他一些算法 的 Big-O 行为时，它 可以 合法地替换为某个常数值，但这绝对是与第一个算法的 Big-O 行为无关。
结论：O(Ackermann(n)) 在 nMax 足够小的情况下工作正常。非常非常小了...
从某种意义上说，你们都对，但你比你的同事更正确。 （编辑： 不。进一步思考，你是对的，你的同事是错误的。请参阅下面我的评论。）真正的问题不是 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).
你的情况...
我很想说你的朋友是软弱的错误。这是因为在 O(1) 运行 时间 中 相当大的附加常量 256。你的朋友说执行是 O(256)。因为我们忽略了 Big-O 中的常量，所以我们简单地将 O(256 * 1) 称为 O(1)。由您决定这个常数对您是否可以忽略不计。
我有两个充分的理由说你是对的：
首先，对于 n 的各种值，您的 O(n) 答案（在第一个代码中）给出了 运行ning 时间的更好近似值。例如：
- 对于长度为 4 的字符串： 你说 运行-时间与 4 成正比，而你朋友说它与 1（或 256）成正比。
- 对于长度为 255 的字符串： 你说 运行ning 时间与 255 成正比，而你的朋友又说它是常数时间。
显然，你的回答在每种情况下都更准确，即使他的回答并非完全错误。
其次，如果你按照你朋友的方法去做，那么在某种意义上你可以作弊并说因为没有字符串可以超过你的 RAM + 磁盘大小，因此所有处理都在 O(1) 中。那就是你朋友推理的谬误变得明显的时候。 是的，运行宁时间（假设 1TB 硬盘和 8GB RAM）是 O((1TB + 8GB) *1) = O(1)，他是对的，但你不能忽略这种情况下常量的大小。
Big-O 复杂度并不能说明实际的执行时间，而只是简单地说明 运行ning 时间随着 n 值的增加而增长的速度。