|
建堆时间复杂度为什么是NlogN 首先有一个数组，长度为N，全部插入到堆中 复杂度是NlogN，今天朋友问的时候突然产生怀疑了 插入第一个是log1，第二个是log2，最后一个是logN 那么最后的结果应该是log(N!)，根据经验可知log(N!)=NlogN 但是为什么？ 于是决定抽空认真研究一下 首先可知复杂度为 log1 + log2 + log3 + log4 + ... + log n 因为 log(a*b) = log(a) + log(b) 所以 log1 + log2 + log3 + log4 + ... + log n = log(1 * 2 * 3 *.... n) = log(n!) 首先确定n的上界 log1 + log2 + log3 + log4 + ... + log n <= log n + log n + log n + log n + ... + log n =n*log n 接下来将n分为两个n/2，同时不计入前部分n/2，只计算后半部分的n/2得出 log(n!) >= log (n/2) + log (n/2 +1) + log (n/2 +2) + log (n/2 +3) + .... + log (n) 将所有的项都替换为最小项也就是n/2，得出 log(n!) >= log (n/2) + log (n/2) + log (n/2) + log (n/2) + .... + log (n/2) = n/2 * log (n/2) 根据公式 log (M/N) = log M - log N n/2 * log (n/2) = n/2 * (log n - log 2) 而log 2 = 1，可得 n/2 * (log n - log 2) = n/2 * (log n - 1) = n/2 * log n - n/2 得出 log(n!) >= n/2 * log n - n/2 我们想要证明它大于n log n的倍数，由于n/2 * log n - n/2 小于 n/2 * log n 我们需要选择一个小于1/2的倍数，例如1/4，为了证明 n/2 * log n - n/2 >= n/4 * log n 我们假设n>=4，则可得出 log n >=2 1/4 * log n >= 1/2 n/4 * log n >= n/2 n/4 * log n - n/2 = 0 左右各加n/4 * log n可得 n/2 * log n - n/2>= n/4 * log n 由于 log(n!) >= n/2 * log n - n/2 则 log(n!) >= n/4 * log n 则可得出 n/4 * log n <= log(n!) <= n log n 时间复杂度可以约去系数，由此可得时间复杂度上log(N!)=N log N 可得堆插入时间复杂度为NlogN
参考资料 | 
置顶卡
沉默卡
照妖镜
谢谢哥哥，花了一下午证明就为了这句话！
