algorithm - 算法中的大 O 复杂度

Question

我想对条款进行排序，使每个条款都是下一个条款的大 O

√n√logn

√n log⁡( n^30)

n/〖(logn)〗^2

〖16〗^(log√n)

谁能帮忙找到顺序？

Answer 1

claim :16*log(sqrt(n))在O(n/(log(n))^2) .

根据 Wikipedia 中的定义, f(x)在O(g(x))比较 lim sup abs(f(x)/g(x)) < infinity对于 n 接近无穷大。如果存在极限，lim sup 变为 lim，并使用 l'Hospital 的规则(假设满足先决条件，参见 Wikiepdia)，我们有:

lim abs(f(x)/g(x)) = lim ((8*log(n))/n) * log(n) * log(n)
= lim (8*(log(n))^3)/n = lim (24*(log(n))^2)/n 
= lim (48*log(n))/(n^2) = lim (24/n^3) = 0

在这里，我应用了 3 次 l'Hopstial 规则来摆脱 (log(n))^3。因此，lim 存在，因此等于 lim sup，根据定义，声明如下。