算法导论3.2-5
lg(lg * n)与lg * (lgn)哪个渐近更大些?
先看lg * n怎么定义的。lg * n=min{i>=0:lg(i)n<=1}
假设一个比宇宙原子总数目10^80还要大的数2^65536.
根据多重对数函数定义知道:
当i=1时,第一次lg得 lg2^65536=65536//书中规定log2=lg
当i=2时,第二次lg得 lg65536=lg2^16=16
当i=3时,第三次lg得 lg16=lg2^4=4
当i=4时,第三次lg得 lg4=lg2^2=2
当i=5时,第三次lg得 lg2=lg2^1=1符合定义。
所以lg *2^65536=5 符合书中结论。
n=0,1,2,4时,lg(lg * n)=lg*(lgn)
n>=16时,lg(lg * n)<lg*(lgn)成立。
例如:设n=2^65536;
再看lg(lg * n)=lg5=2.3
而lg*(lgn)=lg*65536=4
所以lg(lg * n)<lg*(lgn)。
由以上分析可知:
先进行多重取对数所得的值,然后再进行对这个值再取对数。(lg(lg * n))
要比 先对此数取一次对数,然后再进行多重对数运算的渐近小(lg*(lgn))