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

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

I mean if the array size gets bigger the time complexity may getlarger 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 limitingbehavior of a function when the argument tends towards a particularvalue or infinity. (..) In computer science, big O notation is used to classify algorithmsaccording to how their run time or space requirements grow as theinput size grows.

非正式地，在计算机科学领域 time-complexity和 space-complexity理论上，可以将 Big O 符号视为分别具有与时间和空间有关的特定最坏情况的算法的分类。例如，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 表示法表示 set of functions具有一定的渐近上限；正如人们可以从 source 中读到的那样:

Big O notation characterizes functions according to their growthrates: different functions with the same growth rate may berepresented 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)。