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

也许可以期望两个线性方程的和能够在图表上被表示为一条直线，该直线会显示出类似于代表每一个方程的直线之间的平均值。

那么我是否正确理解即使在下面这两个函数中，“复杂”函数需要处理的时间是“简单”函数的三倍，它们在大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

- MikeiLL

---

你的问题是什么？ - jonrsharpe

据我所知，大O表示法在那个规模上并不太关心精度。它主要用于比较O(n)与O(log n)与O(3^n)等的差异。 - Jon Surrell

在大O分析中，通常情况下会忽略常数项和系数。 - alvonellos

Answer 1

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

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

- bryce

---

啊，这进一步澄清了一些。 - MikeiLL

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)

- Mark Ransom

---

谢谢！我希望你不介意我添加一个链接，展示公式的图形表示。 - MikeiLL

为什么要在方程左侧添加 y？你有两个不同的线性函数 f_1(x) = a*x + b 和 f_2(x) = c*x + d。这两个函数的和是 f(x) = f_1(x) + f_2(x) = (a + c)*x + (b + d)。假设左侧的 y 对于两个函数来说是相同的是错误的，因此没有任何意义将它们加到 2*y 上。 - Sven Marnach

@SvenMarnach 当然你是对的。我会编辑它；但这不影响结论。 - Mark Ransom

Answer 3

即使在下面的两个函数中，“complex”函数的处理时间是“simple”函数的三倍，它们在大O符号表示法中都是O(n)，因为处理时间的弧线会在图表上用一条直线对应，即使更复杂的函数的角度会更尖吗？

是的。字母O被使用是因为它指的是一个函数的阶。线性函数具有相同的阶，O(n)，O(3n)，O(Cn)都是线性的。

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

而O(2^n)，O(3^n)和O(C^n)则是指数级别的。通常不要编写具有指数级别复杂度（或更糟）的算法。

- David Titarenco

---

我一直在努力理解什么是多项式函数，这很有帮助。谢谢。 - MikeiLL

Answer 4

一个好的（最好的？）方法是回顾一下大O符号的数学定义：

这两个说法等价：

- f是O(g) - 随着n的增加，f(n)与g(n)的比值趋向于非负值。

在我们的例子中，g(n)=n。现在假设f(n)=f1(n)+f2(n)，并且假设f1和f2都是O(n),则上面的极限将等于α=α1+α2,它本身必须大于或等于零（因为根据定义α1≥0且α2≥0）。因此，f1(n)+f2(n)也是O(n)，按照我们的定义。

- arshajii

---

因此，“=”绝对是符号滥用。 - user824425

@Rhymoid +1。最好改成O(f) = O(g)以确保一切安全。 - luk32

带有希腊符号的语句让我感到困惑。我也不太理解 g(x) = x 是从哪里来的。X 是一个值，对吧？我们是指 g(x) 的结果（值）等于 x 吗？ - MikeiLL

@arshajii 在第二个语句中，n被lim所“绑定”或“量化”，因此它的含义是清晰的。但在f(n) \in O(g(n))中，n没有明确的含义。O(.)接受一个函数并产生一组函数；通过f(n)，你实际上只是指函数f（再次滥用符号 ;))。 - user824425

这里应该使用“极限上确界”而不是“极限”。f对g的极限不一定存在。 - Sven Marnach

Answer 5

假设第一个 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)。

- R Sahu

Answer 6

是的，这是因为Big-O符号不是用于计算绝对运行时间，而是用于描述随着输入增长算法的行为。

换句话说，如果您有一个在O(3n)和O(n)下运行的算法，并且您以任何方式增加n，它们都会运行更长时间。

它只是给出一个概念，即某个算法在增加输入的某一点上是否会超越另一个算法。

当然，在数学上，可以使用定义证明一切。

- luk32

Answer 7

是的，只要图表上的线是直线，函数就是O(n)，不管角度如何。当你可以说“这个函数对于每个输入项需要x秒钟”时，函数需要线性时间。在这种情况下，x可能是三、九或一百万，但它仍然是一个线性函数。

- TheSoundDefense

Answer 8

已经有很多好的答案了，但我还没有看到从这个角度的答案。O(x) + O(y) 的总和是 O(x) 和 O(y) 中最差的一个。在这种情况下，由于它们都是线性的，例如 x = C1n 和 y = C2n，其中 C1 > C2。因此，x 支配了 O() 函数，而大O将是 O(C1n) => O(n)。

- Fallen

---

我认为你的意思是，无论哪个函数代表最坏情况，都会决定大O符号，对吗？你能翻译和/或举例说明C1n和C2n吗？ - MikeiLL

C1和C2只是两个常量。 - Fallen