logo标签列表

以下伪代码的运行时间复杂度（大O）是什么？

pythonalgorithmbig-otime-complexity
6

最近，我和同事就一段非常简单的算法的运行时复杂度进行了一场激烈的辩论。最终我们都认为自己是对的，但我一直在思考这个问题，这挑战了我对计算机科学基础的理解，因此我需要进一步了解这个问题。

假如给出以下Python代码，请问它的大O运行时复杂度是多少：

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

现在，我立即指出这只是O(n)即线性级别。这意味着它取决于字符串的长度，因此随着字符串长度的增加，该循环将呈线性增长。
我的同事接着说：“不，它是常数，因为我们知道对于所有字符串集合（在我们的情况下），最大字符串长度始终为255个字符（在我们的情况下），因此它必须是常数。”他接着说：“因为我们对字符串的最大上限长度有一个上限，这导致O(255)，这可以简化为O(1)。”
无论如何，我们来回争论了45分钟，经过我们两人画草图后，我们都陷入了僵局。
我的问题是，在哪个世界或哪种数学系统中，上面的循环是一个常数时间循环？如果我们知道我们的上限是100万个字符，并且所有字符串集合的大小可以从0到100万不等，那么这个循环显然会根据字符串的大小而呈现线性运行时间。
我还问他，如果已知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的上限总是已知的，则他断言此帖子中的两个算法都具有恒定的运行时间复杂度。
只是想保持清醒，但也许如果我错了，肯定还有一些额外的学习可以获益。我的好同事非常有说服力。此外，如果有人对这个问题有特定的链接或材料，请添加到评论中。
2
根据你描述的他认为所有问题都可以简化为O(1)的想法，似乎他并不理解大O符号的实际含义。如果你试图向他解释了45分钟，而他仍然坚称自己对此有着完美的理解，那么看起来你面临的是一个不同的问题。 - TigerhawkT3
2
选择一个n的值并不能立即将任何算法转化为O(1)。 - TigerhawkT3
2
@TigerhawkT3，选择的不是N的值，而是C的值 - 这与N是*独立的。该值在前提条件中给出，因此我可以自由选择它。讨论Big-O的正确方法是考虑N-> Infinity。虽然挂钟时间确实遵循预期模式，但它超出了技术定义。 - user2864740
1
@TigerhawkT3 Big-O的定义是f(n) = O(g(n))，意味着存在正常数c和k，使得对于所有n≥k，0 ≤ f(n) ≤ cg(n)。在这种情况下，虽然有点学究气，但合理的论点是n < 256。正确的“答案”是敲打某人的头并告诉他们停止困难 - 并让有限的磁带机（计算机）代表一个理想的无限磁带系统，消除限制，以便可以有用地分析函数的执行时间。（通过“没有最大整数”来进行争论可能是有益的...） - user2864740
2
我投票关闭此问题，因为它似乎是在纯数学问题而不是特定于编程的问题（它恰好在Python的上下文中被问到是无关紧要的，因为主题（大O符号）和接受的答案都是纯数学的）。更好的网站可能是计算机科学网站（目前处于测试版），数学溢出或程序员。 - TylerH
显示剩余5条评论
4个回答
11

将Big-O符号应用于所有输入都已知的单个场景是荒谬的。对于单独一个情况，不存在Big-O符号。

整个意义在于获取任意大、未知值的最坏情况估计。如果您已经知道确切的答案，为什么要浪费时间进行估算呢？

数学/计算机科学编辑：

Big-O符号的定义是随着n的增长而变得任意大：如果对于任何常数c，对于所有大于某个nMin的n，g(n)≥c*f(n),那么就可以说 f(n)是O(g(n))，这意味着您的"对手"可以将c设置为"eleventy-quadjillion"，但它并不重要，因为对于"g(n)"曲线右侧的所有点，"eleventy-quadjillion乘以f(n)"的图形将永远落后于g(n)。

例子：2的n次方小于等于n的2次方......对于包含n=2、3和4的x轴的短线段（当n=3时，2的n次方为8，而n的2次方为9）。这并不改变它们大O关系的事实：O(2的n次方)比O(n的2次方)要大得多，因为大O并不涉及小于nMin的n值。如果将nMin设置为4（从而忽略4左侧的图形），你会发现n的2次方线永远不会超过2的n次方线。
如果您的“对手”通过将n的2次方乘以一些较大的常数c来提高他的n的2次方线，以使其超过您的2的n次方线，则您还没有输...您只需将nMin稍微向右移一点即可。大O表示无论他让c有多大，您都可以始终找到一个点，在该点之后，他的方程式输掉了，而您的方程式永远赢得胜利。
但是，如果您在右侧限制n，则违反了任何类型的大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行为没有任何影响。
最后：O(Ackermann(n))在nMax足够小的情况下运行良好。非常非常小...
我同意这个观点，并向他提出了这一点，大O表示法为我们提供了一个框架，可以根据输入的大小来比较算法。 - Ralph Caraveo
2
荒谬是正确的。对于特定有限的N值，也可以选择有限的C（在该点上运行时间为有限的墙钟时间）。 大O表示法的要点是描述N -> 无穷大。 - user2864740
@user2864740：说得好，这恰好总结了我正在打字时你所做的巨大编辑。 - Kevin J. Chase
虽然我认为这篇帖子收到的所有回复都有值得学习的好东西，但我认为这个特定的答案捕捉到了我希望向我的朋友解释细节的本质。很棒的东西。 - Ralph Caraveo
2

在您的情况下...

我倾向于说，您的朋友是有点错误的。这是因为在O(1)运行时间中有一个相当大的附加常数256。你的朋友说执行时间是O(256)。因为我们在大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)，但在这种情况下你不能忽略你的常数大小。

大O复杂度并不告诉实际执行时间，而只是随着n的值增加，运行时间增长的简单速率。

我认为你不能说他是正确的（即他的同事是错误的），因为他的估计更好。Landau符号是理论计算机科学（最初是数学...），它们使用无限存储器。而且因为大O是一个上界，所以当O（1）起作用时，O（n）也可以起作用。我会考虑这个是O（1），因为255相当小。有很多情况下，255被认为是小的，而不是大的。 - Sbls
@Sbls：这就是为什么我在我的回答中说，决定常数是否可以忽略取决于他们。第一段，最后一行。 - displayName
1
我认为你们两个都是正确的。
第一个算法的运行时间与其输入的大小成线性关系。然而，如果其输入是固定的，则其运行时间也是固定的。
大O表示法主要用于度量算法的行为随着其输入的变化而变化。如果输入永远不会改变，那么大O表示法就没有意义。
另外：O(n)表示复杂度的上限为N。如果要表示严格的界限，则更精确的符号是Θ(n)（theta符号）。
就像我之前说的，输入并不是固定的。它可能是0-255，那么这个仍然成立吗？ - Ralph Caraveo
1
但是上限是固定的。例如，将两个数字相加在技术上是O（n），其中n是两个数字中位数的数量。但实际上，我们通常认为它是O（1），因为我们使用的数字类型具有固定的最大位数上限（32或64）。这有意义吗？ - Daniel Pryden
我同意，如果输入是固定的...运行时间也是固定的。但是，在对完全相同的输入比较两种算法时，你永远不会说它们都是O(1)。你不能忽略指数。 - Ralph Caraveo
1
哦，我完全同意。你是正确的。你的同事提出了一个技术上正确的观点，但在某种情况下它变得毫无意义。无论如何，在你所描述的问题约束条件下，大O表示法都不是比较可能解决方案的有用框架。 - Daniel Pryden
1
您们两个都有一定道理，但是您比同事更正确。（编辑：不对。经过进一步思考，您是正确的，您的同事是错误的。请参见我下面的评论。）问题真正的关键不在于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)。
1
重新阅读了您的帖子后，我必须撤回我的声明，即您们两个都是正确的。您的同事是错误的。由于您正在处理不同的字符串，因此s是算法的输入。您知道N可以达到多大的上限是无关紧要的，这与O(N)分析有关；重要的是随着N的增长，O(N^2)的增长速度比O(N)快得多。N具有255的上限并不改变这个事实，这只意味着在这种特殊情况下，您可能可以使用O(N^2)算法。 - rmunn
原帖明确说明了N的最大尺寸。因此，可以选择一个C使其成为O(1)，因为Big-O（受学术启发）仅讨论上限，但在有限的极限处被截断；因此，虽然挂钟时间肯定会受到输入大小的影响（甚至根据预期曲线），但可以确定最大值（常数）。 - user2864740
这并不能成为一个O(1)算法。想象一下，有人用一个O(n^2)算法输入用户名，你问他“如果有人用户名有一百万个字符怎么办？”他回答：“我们限制它只能有20个字符。”你是告诉他“好吧，O(n^2)算法也可以”，还是告诉他“实际上这是一个O(1)算法”？ - TigerhawkT3
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接