使用大 O 符号比较两种算法

Question

我想弄清楚这两种算法中哪一种最慢以及 n 的大小有什么影响。

算法是：

6n^2 + 9

n^2 + 9n

Answer 1

你其实可以证明他们都是O(n²)。这是为什么？

• 如果f(n) = 6n² + 9，则：
• O(f(n)) ∈ O(6n² + 9)，则：
• O(f(n)) ∈ 6 * O(n²) + 9 * O(1)，则：
• O(f(n)) ∈ O(n²)

用类似的方法你可以证明g(n) = n² + 9n又是O(n²)阶的。您还可以比较函数以查看 n 第二个函数需要更多步骤才能完成，然后您会发现第一个函数总是需要 more.

但是，由于它们都是O(n²)，那么你可以假设它们同样是fast/slow，除非你找到一个函数是g(n)的上限并且f(n).

的下限