python - O(n) + O(n) = O(n)？

Question

根据 O'Reilly 的 Python in a Nutshell 中的 Alex Martelli，复杂度类 O(n) + O(n) = O(n)。所以我相信。但是我很困惑。他解释说:“N 的两个线性函数之和也是 N 的线性函数。”

根据 wikipedia ，在泛函分析中，线性函数是一个线性映射，例如 f(x+y) = f(x) + f(y)。找到了一个似乎更简单的定义 here简单地说，“线性函数是图形为直线的函数。”它包含更多示例，这些示例看起来不像维基百科文章那样深奥。

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

Answer 1

正确，O(n) + O(n) = O(n)。

更具体地说，O(n) + O(n) = 2 * O(n)，但由于 Big O 只关心趋于无穷大的函数，因此任何线性都表示为 O(n)。