最近，我和一位同事就 super 简单算法的运行时复杂性进行了非常非常激烈的辩论。最后，我们俩都同意不同意，但是由于我一直在思考，这挑战了我对计算机科学基础知识的基本理解，因此，我必须对此事有更多的了解。
给定以下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之间的任何位置，则此循环显然将显示线性运行时间，具体取决于字符串的大小。
我还问他是否还认为以下代码为O(1)(如果知道n的上限大小)。这意味着我们确定该代码将只能在最大上限(例如255个字符)上运行:
s = "How are you today?"
for c in s:
for d in s:
print c+d
他说，这也是恒定时间...。即使在我解释了这是O(n ^ 2)算法并证明以下代码将产生二次曲线之后，也是如此。
那么，我是否错过了一些理论概念，根据理论的发展情况，以上任何一项都是正确的？ 为了清楚起见，他的理解是，如果n未知，我是正确的。如果始终知道n的上限，则他断言这篇文章中的两种算法都具有恒定的运行时复杂性。
只是想保持自己的理智，但也许如果我错了，我肯定会从中受益。我的好，好同事很有说服力。另外，如果有人对此问题的主题有其他链接或 Material ，请添加到评论中。
最佳答案
将Big-O表示法应用到所有输入均已知的单个场景中是荒谬的。单个案例没有Big-O。
关键是要获得n 的任意大未知值的最坏情况估计。如果您已经知道确切的答案，那么为什么您会在地球上浪费时间进行估算呢？
Mathy/计算机科学编辑:
Big-O表示法定义为n任意大:如果g(n)≥c * f(n)，则f(n)为O(g(n))，对于任何常数c，对于所有大于某个nMin的n， 。意思是，您的“对手”可以将c设置为“四十亿”，这并不重要，因为对于某个点nMin的“向右”的所有点，“四十亿乘以f(n)”的图永远低于g(n)...永远
但是，如果在右边限制n，则违反了任何类型的Big-O分析的先决条件。在与同事的争论中，你们中的一个人发明了一个nMax，然后另一个人将nMin设置在它的右侧某处---令人惊讶的是，结果是荒谬的。
例如，在一般情况下，您显示的第一个算法确实对长度为n ...的输入确实完成了n次工作。如果我正在构建自己的算法，该算法将其调用n次，那么在一般情况下，我将不得不考虑使用二次O(n2)算法。
但是，如果我能证明我绝不会以大于10的输入调用您的算法(这意味着我有更多信息，因此可以更精确地估算我的算法)，那么使用Big-O估算您的算法的性能就可以避免在我关心的情况下，我了解了它的实际行为。相反，我应该用一个适当的大常数替换您的算法---将我的算法从c * n2更改为c * 10 * n ...，这就是cBigger * n。老实说，我的算法是线性的，因为在这种情况下，您的算法图永远不会超过该常数。这不会改变算法的Big-O性能，因为Big-O并未针对此类约束情况进行定义。
总结:一般来说，您显示的第一个算法是按照Big-O标准线性的。在受限的情况下，最大输入是已知的，用Big-O术语来谈论它是完全错误的。在受约束的情况下，当讨论其他算法的Big-O行为时，可以合理地用某个常数替换它，但这绝对没有说第一个算法的Big-O行为。
结论:当nMax足够小时，O(Ackermann(n))可以正常工作。非常非常小...
关于python - 以下伪代码的运行时复杂度(大O)是多少？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32793881/