1樓：匿名使用者
樓主，調堆的時間複雜度為logn毋庸置疑，那麼為什麼建堆的時間複雜度不是logn呢，很簡單啊，建堆的時候你看看是不是多次呼叫了調堆的函式呢，那肯定就不只是logn了，如果從底部最後的父節點開始建堆，那麼我們可以大概算一下：
假如有n個節點，那麼高度為h=logn，最後一層每個父節點最多只需要下調1次，倒數第二層最多只需要下調2次，頂點最多需要下調h次，而最後一層父節點共有2^(h-1)個,倒數第二層公有2^(h-2),頂點只有1(2^0)個，所以總共的時間複雜度為s = 1 * 2^(h-1) + 2 * 2^(h-2) + ... + (h-1) * 2^1 + h * 2^0
將h代入後s= 2n - 2 - log2(n)，近似的時間複雜度就是o(n)。
2樓：he**en小太陽
建堆的時候你看看是不是多次呼叫了調堆的函式呢，那肯定就不只是logn了，如果從底部最後的父節點開始建堆，那麼我們可以大概算一下：
假如有n個節點，那麼高度為h=logn，最後一層每個父節點最多只需要下調1次，倒數第二層最多只需要下調2次，頂點最多需要下調h次，而最後一層父節點共有2^(h-1)個,倒數第二層公有2^(h-2),頂點只有1(2^0)個，所以總共的時間複雜度為s = 1 * 2^(h-1) + 2 * 2^(h-2) + ... + (h-1) * 2^1 + h * 2^0 將h代入後s= 2n - 2 - log2(n)，近似的時間複雜度就是o(n)。
堆排序(heapsort)是指利用堆積樹（堆）這種資料結構所設計的一種排序演算法，它是選擇排序的一種。可以利用陣列的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。
大根堆的要求是每個節點的值都不大於其父節點的值，即a[parent[i]] >= a[i]。在陣列的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。
2023年的計算機先驅獎獲得者、斯坦福大學電腦科學系教授羅伯特·弗洛伊德(robert w．floyd）和威廉姆斯(j．williams）在2023年共同發明了著名的堆排序演算法（ heap sort )
堆排序利用了大根堆（或小根堆）堆頂記錄的關鍵字最大（或最小）這一特徵，使得在當前無序區中選取最大（或最小）關鍵字的記錄變得簡單。
3樓：匿名使用者
建堆是自底向上的且序列位於無序狀態，此時除了要選取堆頂元素以外還要保證所有子樹的根與左右結點之間符合堆的標準（根是三個結點中取值最小的（小頂堆，降序）/最大的（大頂堆，升序））。
堆調整是自頂向下的序列處於基本有序狀態。此時只需要關注自頂向下移動路徑上的各個分支是否在交換後依然符合堆的標準。
兩個過程有明顯差別，自然時間複雜度不一樣了。
時間複製度的演算法！？？ 堆排序時間複雜度演算法？ 怎麼算的？
4樓：匿名使用者
這個完全二叉樹的高度為log2n，迴圈為n/2，因此時間複雜度為o(nlog2n)
快速排序，希爾排序和堆排序的平均時間複雜度都是o(nlog2n)，為什麼說快速排序是最快的？
5樓：匿名使用者
快速排序是用遞迴的思想，用棧來儲存資料，它第n趟最多要確定2^n個數的最終位置。它使用的空間是最多的，用空間換取了時間。例如：
6樓：匿名使用者
快排只是內排序演算法啊，而且在內排序中也並不是最快的，只是快排在大多數情況下效果很好，因為一般的無序元素不會是完全或者近似倒序的。
7樓：下個倒角
每種排序都有它的優勢。
時間複雜度問題，請問什麼時候的時間複雜度為log(n), 什麼時候是nlog（n）求大神以c++程式指點
8樓：匿名使用者
堆排序是一種樹形選擇排序，在排序過程中，將a[n]看成是完全二叉樹的順序儲存結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關係來選擇最小的元素。
堆排序是不穩定的。演算法時間複雜度o(nlogn)。
決策樹是一顆二叉樹，每個節點表示元素之間一組可能的排序，它予以京進行的比較相一致，比較的結果是樹的邊。
先來說明一些二叉樹的性質，令t是深度為d的二叉樹，則t最多有2^片樹葉。
具有l片樹葉的二叉樹的深度至少是logl。
所以，對n個元素排序的決策樹必然有n!片樹葉（因為n個數有n!種不同的大小關係），所以決策樹的深度至少是log(n!)，即至少需要log(n!)次比較。
而log(n!)=logn+log(n-1)+log(n-2)+...+log2+log1
>=logn+log(n-1)+log(n-2)+...+log(n/2)
>=(n/2)log(n/2)
>=(n/2)logn-n/2
=o(nlogn)
所以只用到比較的排序演算法最低時間複雜度是o(nlogn)。
時間複雜度的問題，一個時間複雜度的問題
一般來說,標準的分治法合併排序時間複雜度為o n lg n 略小於插入排序的o n n 遞迴式的時間複雜度求解方法比較多,有畫圖分析法,算式求解即類似於 t n f t n 1 的求解方法,還有就是憑經驗猜然後用數學歸納法證明等等,對於你的問題最直觀的方法就是畫圖法,這是一個二叉樹問題,最開始的序列...
求各種查詢和排序的時間複雜度，每種查詢方法的時間複雜度
鈊 煩 薏亂 氣泡排序是穩定的，演算法時間複雜度是o n 2 2.2 選擇排序 selection sort 選擇排序的基本思想是對待排序的記錄序列進行n 1遍的處理，第i遍處理是將l i.n 中最小者與l i 交換位置。這樣，經過i遍處理之後，前i個記錄的位置已經是正確的了。選擇排序是不穩定的，演...
時間複雜度相同的演算法一樣好嗎，氣泡排序演算法的時間複雜度是什麼
大二的猴 如果只分析你上面段程度，顯然方法二做了許多無用功，當然一好。時間複雜度估的是個時間隨規模n增長的趨勢，他倆的趨勢是一樣的。給定規模n，如果方法二能跑，那方法一肯定能跑，只不過比前者多常數倍時間而已，你跑1秒，我不過跑2秒而已，你跑一天，我跑倆天而已，你要跑一年以上，那勸你還是找個更快的演算...