时间复杂度为什么是O(nlgn)

Question

O(lgn)的解释是:将一个数据集分成两半,然后将分开的每一半再分成两半,依此类推O(nlgn)的解释是:将一个数据集分成两半,然后将分开的每一半再分成两半,依此类推,在此过程中同时遍历每一半数据O(lgn)我可以理解,但我不理解为什么在此过程中同时遍历每一半数据就得乘以n,这个n怎么算出来的?谁能举个简单又实际的例子?

Answer 1

以快速排序为例，第i轮中，数据集已被分为2^(i-1)块，在选定这么多个pivot之后，要遍历所有n个元素才能把所有2^(i-1)个块分为2^i块，这个过程一共要做log(n)次，可不就是n*log(n)？
                            

Answer 2

把n的问题看成一棵二叉树。
logN算法就是从root找到一个叶子结点，复杂度为树高，也就是logN。
NlogN算法则是从root找到每一个叶子结点，复杂度为树高*叶子结点个数，也就是logN*N
建议找本书看严格的证明