按复杂度排序大O-复杂度函数

Question

我试图按大O复杂度排序以下函数，从低复杂度到高复杂度：

100n, 2^n , 2^log^3 n , log^n, n^100 , log log n, 2^n^2, n^log n , n^√n , 2^2^n

在这里，所有的日志都是2基的。

我已经命令他们跟着走。这个大O-复杂度的顺序正确吗？

log n 
100n 
log log n
2^n
n^100
n^√n
n^log n
2^log^3 n
2^n^2
2^2^n

Answer 1

正确的顺序是：

log log n 
log n
100n
n^100
n^log n
n^√n
2^log^3 n
2^n
2^n^2
2^2^n

当比较两种功能时，

(由于日志都是基2)，因此，possible

• substitute

1. 就像对n => 2^100、2^2^10等应用“log”的次数一样，在双方=>中应用“log”的次数是很大的。