大O和大欧米茄表示法算法

Question

存在基于比较的排序算法,其在O(n*log(sqrt(n)))中运行.鉴于存在Omega(n(log(n))下界进行排序,这怎么可能呢？

Answer 1

基本上,这个问题要求你证明O(n*log(n))= O(n*log(√n)),这意味着你需要找到一些常数c > 0,这样:O(n*log(n))= O(c*n*log(√n)).记住√n= n ^(1/2)并且log(n ^(1/2))= 1/2*log(n).所以,现在我们有O(n*log(n))= O(1/2*n*log(n)).由于渐近符号忽略常数乘数,我们可以将其重写为O(n*log(n))= O(n*log(n)).瞧,证明有可能.