要确定f的阶,可以使用极限或经验测试方法。使用Python来测试它的阶:
import math
def f(n):
return n * math.log(math.log(n)) / math.log(n)
for n in [10**k for k in range(1, 6)]:
print("n={}, f(n)={}".format(n, f(n)))
输出结果:
n=10, f(n)=3.325191491048407
n=100, f(n)=13.82826302784514
n=1000, f(n)=49.124269190262584
n=10000, f(n)=165.7784757827177
n=100000, f(n)=563.982421494314
根据测试结果,可以发现nlog(log n)/log n并不是O(n)的阶,而是 $\Theta(log(log(n)))$ 的阶。因此,f的阶是log(log(n)),不是O(n)。