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

Question

根据O'Reilly的Python in a Nutshell中的Alex Martelli所说的复杂性类O(n) + O(n) = O(n).所以我相信它.但我很困惑.他解释说,"N的两个线性函数之和也是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

也许可以公平地预期两个线性方程的总和可以在图上表示为直线,其显示类似于代表每一个的直线之间的平均值的东西.

所以我理解正确,即使在以下两个函数中,"复杂"函数的处理时间是"简单"函数的三倍,它们每个函数都以big-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).

Answer 2

该陈述是正确的,因为添加两个线性函数也是线性函数.以这两个为例:

y = 6*x + 10
y = 20*x + 2

将它们添加到一起就可以得到:

y = 26*x + 12

这也是一个线性函数!这适用于任何两个线性函数.

y = A*x + B
y = C*x + D
-----------
y = (A+C)*x + (B+D)

Answer 3

因此,即使在以下两个函数中,"复杂"函数的处理时间是"简单"函数的三倍,它们每个函数都以大O符号表示为O(n),因为处理时间的弧度将是在图/图上用直线对角线表示,即使更复杂函数的角度更锐利？

是.使用字母O是因为它指的是函数的顺序.线性函数是相同的顺序,O(n),O(3n),O(Cn)都是线性的.

在另一方面,O(n^2),O(n^3),和O(n^C)都是多项式函数(,3度2,C).(与算法交易时)在这里,我们经常不开始做喜欢的事物之间的区别O(n^2)和O(n^5)-尽管它们都是同一个数量级.

并且O(2^n),O(3^n)并且O(C^n)是指数级的.您通常不希望编写具有指数复杂性(或更糟)的算法.

Answer 4

一个好的(最好的？)方法是参考big-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).