大 O（常数）时间复杂度

Question

为什么下面的代码中每个语句都使用大O常量（这里我使用1作为惯例）？

我的意思是，如果数组大小变大，时间复杂度可能会变大，对吗？而且总数会越来越大，不会影响复杂度吗？

伪代码：

def find_sum(given_array)
    total = 0 # refers to O(1)
    for each i in given array: #O(1) 
      total+=i #O(1)
    return total #O(1)

- Yan Skywalker

---

每次对一个数组的操作时间复杂度应该是O(n)，其中n为该数组的大小。 - Hans Kesting

如果你的问题是为什么这些注释是正确的，那么答案是它们是错误的。如果你的问题是为什么有人写了这些注释，那么你就得问问他们了。 - kaya3

@HansKesting 可能更准确的是 Θ(n)，不是吗？ - dreamcrash

@dreamcrash 我不得不查一下大O符号，但确实如此 - 它不仅是一个上界，而且是“相等的”。 - Hans Kesting

Answer 1

TL;DR：因为大O符号用于量化算法，涉及其在输入增加时的行为。

引用块中的提问者误将算法所花费的时间与时间复杂度混淆了。

让我们从澄清当前上下文中“大O符号”是什么开始。从（source）中可以读到：

大O符号是一种描述函数在参数趋向特定值或无穷大时的极限行为的数学符号。在计算机科学中，大O符号用于根据输入大小来分类算法，以了解它们运行时间或空间需求如何随着输入规模的增长而增长。

在计算机科学的时间复杂度和空间复杂度理论中，人们通常将Big O符号视为一种关于最坏情况下时间和空间的算法分类方法。例如，O(n)表示线性时间/空间：

算法的时间/空间复杂度为O(n)，即称其为具有线性时间/空间复杂度。简单来说，这意味着运行时间/空间随着输入规模的增加而最多呈线性增长。

因此，对于以下代码：

def find_sum(given_array)
    total = 0
    for each i in given array:
      total+=i 
    return total 

复杂度为O(n)，因为随着输入的增加，复杂度呈线性而不是常数增长。更准确地说是Θ(n)。

我认为这种方式并不是非常精确地确定复杂度。

def find_sum(given_array)
    total = 0 # refers to O(1)
    for each i in given array: #O(1) 
      total+=i #O(1)
    return total #O(1)

由于大O符号表示具有一定渐近上限的函数集合；正如您可以从source中读到的那样：

“大O符号根据它们的增长速度对函数进行表征：相同增长速度的不同函数可以使用相同的O符号表示。”

更准确的说法是：

def find_sum(given_array)
    total = 0 # takes c1 time 
    for each i in given array: 
      total+=i # takes c2 time 
    return total # takes c3 time 

因此，时间复杂度将是 c1 + n * c2 + c3，可以简化为 n。由于该函数的下限和上限相同，因此我们可以使用 Θ(n) 代替 O(n)。

- dreamcrash

Answer 2

到目前为止，没有回答第二个问题：

总数也会变得越来越大，这不会影响复杂度吗？

这是非常重要的问题，通常被忽略。

答案取决于你的计算模型。如果底层机器可以在恒定时间内添加任意大的数字，那么不，它不会影响时间复杂度。

然而，现实中的机器是以固定宽度的值进行操作的。现代计算机可以愉快地添加64位数量。有些机器一次只能添加16位宽度的值。图灵机——整个复杂性理论的基础——每次只处理1位。无论如何，一旦我们的数字超过寄存器宽度，我们必须考虑加法所需的时间与加数的位数成正比，而在这种情况下，加数的位数是 log(i)（或者 log(total)，但由于 total 的增长速度为 i*(i-1)/2，其位宽约为 log(i*i) = 2 log(i)）。

有了这个想法，注释如下：

  total+=i # O(log i)

更为谨慎。现在循环的复杂度

for each i in given array:
  total+=i # O(log(i))

sum[1..n] log(i) = log(n!) ~ n log(n)。最后一个等式来自于阶乘的 Stirling 近似。

- user58697

Answer 3

以下代码为什么每个语句都引用大O常数（这里我使用1作为惯例）？

不确定，请问编写代码的人。显然，总运行时间不是O（1），因此如果他们得出这个结论，那么他们是错误的。如果他们没有这个意思，那么他们所写的要么是错误的，要么是令人困惑的。

我的意思是，如果数组大小变得更大，时间复杂度可能会变得更大，对吗？

是的，可能会。实际上，在这里，它会，因为您至少正在迭代数组中的元素。数组中的元素越多，循环次数就越多。简单明了。

此外，总数也会变得越来越大，这不会影响复杂性吗？

这是一个有趣的见解，答案取决于您如何构思数字的表示方式。如果您有固定长度的数字表示（32位无符号整数、双精度浮点数等），那么加法是一个常数时间操作。如果您有可变长度的表示（例如大整数库或手动执行算法），则添加的复杂性取决于所使用的加法方法，但必然随着数字大小的增加而增加（对于常规的带进位加法，可能存在上限对数界）。实际上，对于可变长度的表示，您的复杂性至少应包括与数组中数字的大小（最大或平均值）相关的某些参数；否则，运行时可能会被添加数字而不是循环所主导（例如，两个1000^1000位整数的数组几乎会花费所有时间来添加而不是循环）。

- Patrick87

Answer 4

这个循环没有办法：

for each i in given array: 
    total+=i

将在O(1)时间内运行。即使输入的大小n为1，渐近分析仍然会表明它以O(n)而不是O(1)运行。

渐近分析测量时间/空间复杂度与输入大小的关系，并不一定显示执行的确切操作数。

指出O(1)是常数，并不意味着它只有一个(1)操作，而是意味着这个特定的块(它需要O(1))不随输入变化而改变，因此它具有恒定的复杂度。

另一方面，O(n)表示复杂度取决于n，并且根据输入n的变化而变化。当输入大小和运行时间具有1对1的相关性时，O(n)是线性关系。

正确编写的注释应该像这样：

def find_sum(given_array)
    total = 0 #this is O(1), it doesn't depend on input
    for each i in given array: #this is O(n), as loop will get longer as the input size gets longer 
      total+=i #again, O(1)
    return total #again, O(1)

- Giorgi Tsiklauri

---

描述大O符号时，这个答案包含了一些常见的错误。O(1)并不意味着随着输入变化时间不会改变，而是指操作需要有一个有限的时间。O(n)并非线性关系，它是一个最终会受到通过原点的一条直线限制的函数。此外，并非所有的O(n)函数都取决于n，例如f(n)=1就是O(n)。 - Paul Hankin

f=O(g) 的定义是存在 n0 和 c，使得当 n≥n0 时，|f(n)| ≤ |cg(n)|。例如，对于函数 f(n) = n mod 1000000，它是 O(1)，但不是常数函数，并且确实取决于 n。以直观的语言描述，O(1) 意味着“被一个常数所限制”，而不是“渐近为常数”。在实际应用中，我们通常使用非正式的复杂度概念，但在解答问题时，为了避免混淆那些试图更加严谨地理解该主题的人们，准确描述细节会更有帮助。 - Paul Hankin