C 语言快速排序最好情况时间复杂度为什么是 nlog2n ?(菜鸟在线)

Question

书上是这么写的:

快速排序的最好情况是每次待定的枢轴记录都将待排序列分成两个独立的长度
几乎相等的子序列，即第一趟快速排序的范围是n个记录，第二趟快速排序的范围是
两个长度各为n/2的子序列，第三趟快速排序的范围是4个长度各为（n/2)/2的子序列。
依次类推，整个算法时间的复杂度为O(nlog2n)

还是不理解，哪个高手能帮我解决这个问题，详细点,多谢了

Answer 1

快速排序最好的情况是每次把上一次的数组平均分成两个子数组。设数组总数一共为n，如果把这n个数每次分成2半最后每个数组只包含一个元素，假设要分k次，则2的k次方=n，解得k=log2 n（log以2为底对n取对数）.也就是说要分log2 n次，而每次都是处理n个数据。所以总的时间复杂度为O（n*log2 n）。

Answer 2

第一趟要遍历整个数组复杂度为n很好理解，接下来的log2n实际上和二分法查找规律差不多，每次的规模减半，设计算次数为x，则n = 2^x，所以x = log2n。