数组排序的最少时间复杂度O(nlog2n)怎么计算的?

如题所述

for(int j=1; j<=n; j*=2)


这个循环最终执行的次数假设为x,则x次的时候j=2^x 。


当j>n时停止执行,于是2^x>n ,则可以认为该循环一共执行了log2(n)次。


所以该循环的时间复杂度为o(log2(n)),简记为o(log n) ,忽略掉2的底数

方法:

1、首先,看外循环for(i=0;i<n;i++),按照i++的递加速度,直到这个循环退出,一共是n次。


2、再看内部循环,for(j=1;j<n;j*=2),这个内部循环的累加速度是j=j*2,假设循环x次之后,这个循环退出,2^x>n===》x=log2(n)。

3、如果把两个循环合在一起看,也就是一共循环了n个x次,也就是log2(n)。



温馨提示:答案为网友推荐,仅供参考
第1个回答  2013-09-25
这个是基于关键字比较在最坏情况下的最好时间复杂度,计算过程:
因为一次比较可以区分数据的两个状态,n个数据的初始排列可能为n!,用完全二叉树来看,n!个叶子的高度为O(log2(n!))~O(nlog2n)本回答被网友采纳
第2个回答  2018-09-28
O(log2(n!))~O(nlog2n)并不相似吧,他两的阶数不同,右侧等同于O(log2(n∧n)),幂指不等同于阶乘吧!