algorithm - 算法大 O 表示法的时间复杂度

Question

我被赋予了以下时间复杂度，并且应该将它们分配给正确的“分类”（大 O 表示法）。

首先：

f(n) = 1000 + log_2(n^(9n))+3*n*log_1000(n^n) -> f in O(n^2*log(n))

第二：

f(n) = 2*n^3+5 * 3^n -> f in O(3^n)

最后但并非最不重要：

f(n) = 2*n^7+5*e^n -> f in O(e^n)

现在我要求验证，因为我真的不确定我是否正确。

标签： algorithmtime-complexitybig-o

Answer 1

f(n) = 1000 + log_2(n^(9n))+3nlog_1000(n^n)

摆脱常量和日志库

=> O(log(n^(n)) + nlog(n^n))

从日志规则

log(a^b) = b*log(a)

=> O(nlog(n) + n*nlog(n))
=> O((n^2)*log(n))

---

f(n) = 2*n^3+5 * 3^n

摆脱常量

=> O(n^3 + 3^n)

指数型胜利

=> O(3^n) 

---

f(n) = 2n^7+5e^n

摆脱常量

=> O(n^7 + e^n)

再次，指数获胜

=> O(e^n)