O(n) + O(n) = O(n)？

9 投票

8 回答

11893 浏览

提问于 2025-04-18 12:25

根据Alex Martelli在O'Reilly的《Python in a Nutshell》一书中提到的，复杂度类 O(n) + O(n) = O(n)。所以我相信这个说法，但有点困惑。他解释说，“两个线性函数的和也是一个线性函数。”

根据维基百科的说法，在函数分析中，线性函数是一个线性映射，比如 f(x+y) = f(x) + f(y)。我找到一个似乎更简单的定义，在这里简单地说明，“线性函数是图像是一条直线的函数。”它还包括一些比维基百科上那些看起来更简单的例子。

y = f(x) = a + bx

还有：

y = 25 + 5x

let x = 1
then
y = 25 + 5(1) = 30

let x = 3
then
y = 25 + 5(3) = 40

也许可以合理地期待，两个线性方程的和可以在图上表示为一条直线，这条直线显示出类似于这两条直线的平均值。

所以我理解得对吗？即使在下面的两个函数中，“复杂”的函数处理时间是“简单”函数的三倍，但它们在大O表示法中都是O(n)，因为处理时间的变化在图上会表现为一条直的斜线，而时间差则体现在图形表示中，复杂函数的角度会更陡峭？

from timer import Timer

def complex(it):
    result = []
    for i in it:
        result.append(i)
    result.reverse()
    return result

def simple(it):
    result = list(it)

longlist = list(range(0, 1000000))

with Timer() as t:
    reverse_(longlist)
print "=> elapsed time reverse: %s." % t.secs

with Timer() as t:
    straight(longlist)
print "=> elapsed time straight: %s" % t.secs

平均值算法复杂度处理时间函数分析图形表示大O表示法线性函数线性映射

8 个回答

假设第一个 O(n) 可以用一个方程表示：

y1 = f1(x) = a1 + b1.x

而第二个 O(n) 也可以用一个方程表示：

y2 = f2(x) = a2 + b2.x

通过把这两个方程的两边相加，

y1 + y2 = f1(x) + f2(x) = (a1+a2) + (b1+b2).x

我们可以看到 y1+y2 也是 O(n)。

回答于 2025-04-18 由 Python大师

分享举报

一个好的（也许是最好的）方法是回到大O的数学定义上：

在这里输入图片描述

用简单的话来说：

这两个说法是等价的：

f 是 O(g)

当 n 增加时，f(n) 和 g(n) 的比值趋向于一个非负值。

在我们的例子中，g(n) = n。现在如果我们设定 f(n) = f₁(n) + f₂(n)，并假设 f₁ 和 f₂ 都是 O(n)，那么上面的极限将等于 α = α₁ + α₂，而这个值必须大于或等于零（因为根据定义 α₁ ≥ 0 和 α₂ ≥ 0）。因此，f₁(n) + f₂(n) 也是 O(n)，根据我们的定义。

回答于 2025-04-18 由 Python大师

分享举报

所以即使在下面的两个函数中，“复杂”的函数处理时间是“简单”函数的三倍，但它们在大O表示法中都是O(n)，因为处理时间的变化在图表上看起来像是一条直线，虽然复杂函数的斜率会更陡一些，对吗？

没错。字母O是用来表示一个函数的“阶”的。线性函数都是同一种阶，比如O(n)、O(3n)、O(Cn)都是线性的。

另一方面，O(n^2)、O(n^3)和O(n^C)都是多项式函数（分别是2次、3次和C次）。在处理算法时，我们通常会开始区分O(n^2)和O(n^5)这样的情况，尽管它们都是同一种阶。