线性时间算法的总和是线性时间吗？

Question

如果问题显得“傻”，请原谅，因为我对算法时间复杂度还很陌生。

我知道如果我有n个数字并想将它们相加，则需要“n步”，这意味着算法的时间复杂度是O(n)或线性时间。即：随着输入数量n的增加，所需的步骤数量也会线性增加。

如果我编写一个新算法，连续五次执行此求和操作，那么我知道它的时间复杂度是O(5n) = O(n)，仍然是线性 （根据维基百科）。

问题

如果我有10个不同的O(n)时间复杂度的算法（求和、线性时间排序等），并且我在输入的n个数上依次执行它们，那么这是否意味着总体运行时间为O(10n) = O(n)，即线性时间？

- Legendre

Answer 1

是的，对于任何常数k，O(kn)，= O(n)

如果您开始扩大问题并决定将您的10个线性操作基于k（例如k为用户输入数组的长度）成为k个线性操作，则从大O中删除该信息将是不正确的。

- im so confused

Answer 2

从大O的定义开始学习，学会经验法则后再进行“证明”是最好的。

如果你有10个O（n）算法，那么就意味着存在10个常数C1到C10，对于每个算法Ai，执行所需时间小于Ci * n（n足够大）。

因此[*]，对于足够大的n来说，运行所有10个算法所需的时间小于：

C1 * n + C2 * n + ... + C10 * n

=（C1 + C2 + … + C10）* n

所以总时间也是O（n），常数为C1 +…+ C10。

经验法则：常数个O（f（n））函数之和为O（f（n））。

[*]留给读者的证明。提示：有10个不同的“足够”的值要考虑。

- Steve Jessop

---

好回复。谢谢！只能接受一个答案有点可惜。 - Legendre

Answer 3

是的，O(10n) = O(n)。同样，O(C*n) = O(n)，其中C是一个常数。在这种情况下，C等于10。如果C等于n，它可能看起来像O(n^2)，但这是不正确的。因为C是一个常数，它不随n的变化而变化。

另外，请注意，在复杂度的求和中，最高阶或最复杂的部分被视为整体复杂度。在这种情况下，它是O(n) + O(n) ... + O(n)十次。因此，它是O(n)。

- SeattleOrBayArea

---

正如Steve Jessop所指出的那样，这10个单独的常数可能是不同的。此外，说最高阶项被“认为”是总体复杂度可能会稍微有些误导，因为这暗示着这只是一种惯例，而实际上它是由big-Oh的定义在数学上隐含的。 - j_random_hacker

假设一个算法需要时间Dn^2 + En + F，其中D为正数，E和F没有限制。那么设置C = D + E' + F'，其中如果E >= 0，则E'为E，否则为0；F'同理。然后Cn^2 = Dn^2 + E'n^2 + F'n^2，对于任何n >= 1，这都大于等于Dn^2 + En + F，因为每个单独考虑的项都是大于等于的，所以该算法的时间复杂度为O(n^2)，常数为C。 - j_random_hacker

是的，正确的。这是数学上的暗示，而不仅仅是“考虑到”。我的措辞可能有误，但我意思是一样的。感谢您指出。 - SeattleOrBayArea