algorithm - 复杂度 O(sqrt(n) * log(sqrt(n))) + O(n) 的大 O 是多少

Question

上述复杂性的大 O 表示法是什么？

是不是O(n)

Answer 1

是的。关键是日志里面的平方根没有区别:

O(sqrt(n) log(sqrt(n))) = O(sqrt(n) 1/2 log(n)) = O(sqrt(n) log(n)).  

有了这个，我们注意到

O(n) = O(sqrt(n)sqrt(n)) > O(sqrt(n)log(n)).  

这是因为无论如何

O(sqrt(n)) > O(log(n)).  

为什么？我们可以取两边的日志来验证，日志里面又出现了一个平方根:

O(log(sqrt(n)) = O(1/2 log(n)) = O(log(n)) > O(log log(n))

所以我们最终可以得出整体结果是O(n)。