建堆时间复杂度为什么是NlogN
建堆时间复杂度为什么是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 Nn/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 >=21/4 * log n >= 1/2n/4 * log n >= n/2n/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参考资料https://www.ptt.cc/bbs/Grad-ProbAsk/M.1346930341.A.AD5.htmlhttps://blog.csdn.net/hzh_0000/article/details/80955511https://web.archive.org/web/20200203103511/http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm 哥哥牛逼 yhzc2023 发表于 2023-11-23 22:09
哥哥牛逼
{:4_115:}谢谢哥哥，花了一下午证明就为了这句话！ 哥哥好卷 哥哥好牛逼
页:
[1]