Question

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

Answer 1

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)。

Answer 2

这个是基于关键字比较在最坏情况下的最好时间复杂度，计算过程：
因为一次比较可以区分数据的两个状态，n个数据的初始排列可能为n!，用完全二叉树来看，n!个叶子的高度为O(log2(n!))~O(nlog2n)

Answer 3

O(log2(n!))~O(nlog2n)并不相似吧，他两的阶数不同，右侧等同于O(log2（n∧n）)，幂指不等同于阶乘吧！