algorithm - 这些函数的大 O 复杂度是否正确？

Question

我正在学习算法复杂性，我只是想验证我的理解是否正确。

1) T(n) = 2n + 1 = O(n)

这是因为我们去掉了常量 2 和 1，只剩下 n。因此，我们有 O(n)。

2) T(n) = n * n - 100 = O(n^2)

这是因为我们去掉常量 -100，剩下 n * n，即 n^2。因此，我们有 O(n^2)

我说的对吗？

Answer 1

基本上，您拥有由功能的“主导”因素决定的那些不同级别，从最低的复杂性开始:

• O(1) 如果你的函数只包含常量
• O(log(n)) 如果显性部分在 log 中，ln...
• O(n^p) 如果主要部分是多项式且最高幂是 p(例如 O(n^3) 对于 T(n) = n*(3n^ 2 + 1) -3 )
• O(p^n) 如果占优部分是固定数的 n 次方(例如 O(3^n) 对于 T(n) = 3 + n^ 99 + 2*3^n)
• O(n!) 如果占优部分是阶乘
• 等等...