大 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)

Answer 1

没有办法，就是循环：

for each i in given array: 
    total+=i

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

渐近分析测量 time/space 复杂性 与输入大小的关系 ，它不一定显示执行的确切操作数。

要点，O(1) 是常数，不是意味着它只是一 (1) 个操作，而是意味着这个特定的块（需要 O (1))当输入改变时不改变，因此，它与输入没有相关性，所以它具有常数复杂度。

另一方面，

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

正确书写的评论应该是这样的：

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)

Answer 2

TL;DR: 因为大 O 符号用于量化算法，关于它如何随着输入的增加而表现。

I mean if the array size gets bigger the time complexity may get larger right? Also the number in total will get larger and larger, won't it affect the complexity?

你把算法所用的时间和时间复杂度弄错了。

让我们首先阐明什么是当前上下文中的 Big O 表示法。从 (source) 可以读到：

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. (..) In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.

通俗地说，在计算机科学 time-complexity and space-complexity 理论中，可以将 Big O 符号视为算法的一种分类，具有与时间和 space 相关的最坏情况，分别。例如，O(n):

An algorithm is said to take linear time/space, or O(n) time/space, if its time/space complexity is O(n). Informally, this means that the running time/space increases at most linearly with the size of the input (source).

所以对于这段代码：

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

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

IMO 找出这样的复杂度不是很准确：

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)

因为 Big O 表示法 具有一定渐近上限的函数集 ；可以从 source:

中读到

Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.

更准确的是：

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).

Answer 3

Why does the following code for each statement refer to big O constant (here I use 1 for the convention)?

不确定，问写的人。整体运行时间似乎很明显不是 O(1)，所以如果这是他们得出的结论，那他们就错了。如果他们不是有意这么说，那他们写的要么是错误的，要么是令人困惑的。

I mean if the array size gets bigger the time complexity may get larger right?

是的，有可能。事实上，在这里，它会，因为您至少要遍历数组中的元素。数组中的元素越多，循环的迭代次数越多。直截了当。

Also the number in total will get larger and larger, won't it affect the complexity?

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

Answer 4

第二个问题目前没有答案：

Also the number in total will get larger and larger, won't it affect the complexity?

这是非常重要的，通常没有考虑到。

答案是，这取决于你的计算模型。如果底层机器可能在常数时间内~~疯狂地~~任意大数，那么不会，不影响时间复杂度。

然而，现实的机器在固定宽度的值上运行。现代计算机乐于添加 64 位数量。有些可能一次只添加 16 位宽的值。图灵机——它是整个复杂性理论的基础——一次只处理一位。在任何情况下，一旦我们的数字超出寄存器宽度，我们必须考虑到加法所花费的时间与加数中的位数成正比，在本例中为 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)。最后一个等式来自阶乘的斯特林近似。

大 O（常数）时间复杂度

Big O (constant) time complexity

algorithm

complexity-theory

big-o

time-complexity