algorithm - 算法对输入的大小是线性的 (O(n))，但是如果输入大小是指数的怎么办

Question

讲师说，算法的复杂性通常是根据其输入大小来衡量的。

所以，当我们说一个算法是线性的，那么即使你给它一个 2^n 的输入大小（比如说 2^n 是二叉树中的节点数），算法仍然与输入大小成线性关系？

以上似乎是导师的意思，但我很难在脑海中转动它。如果你给它一个 2^n 的输入，它是某个参数“n”的指数，然后称这个输入为“x”，那么，当然，你的算法与 x 是线性的。但在内心深处，它不是仍然是“n”的指数吗？说它与 x 成线性关系有什么意义？

标签： algorithmtime-complexitycomplexity-theory

Answer 1

如果算法具有线性时间复杂度，那么无论输入的大小如何，它都是线性的。无论是固定大小的输入，二次还是指数。

显然，在固定大小的数组、二次或指数上运行该算法将花费不同的时间，但复杂度仍然是O(n).

---

也许这个例子会帮助你理解，在一个大小为 16 的数组上运行合并排序是否意味着合并排序是O(1)因为它需要不断的操作来对该数组进行排序？答案是不。