1樓：匿名使用者
快速排序最好的情況是每次把上一次的陣列平均分成兩個子陣列。設陣列總數一共為n，如果把這n個數每次分成2半最後每個陣列只包含一個元素，假設要分k次，則2的k次方=n，解得k=log2 n（log以2為底對n取對數）.也就是說要分log2 n次，而每次都是處理n個資料。
所以總的時間複雜度為o（n*log2 n）。
2樓：匿名使用者
第一趟要遍歷整個陣列複雜度為n很好理解，接下來的log2n實際上和二分法查詢規律差不多，每次的規模減半，設計算次數為x，則n = 2^x，所以x = log2n。
電腦程式設計中快速排序的時間複雜度n log n 是n*log(n)還是什麼
3樓：匿名使用者
問題中兩者選擇的答案是相同的，且是正確的，n log n 即等於n*log(n)，其中*代表乘，預設底數為
2.快速排序的複雜度為log以2為底，n^2的對數，也就是o（n^2），如排序10個數，最壞的情況就是o（10^2）=o(100)≈33
4樓：
快速排序的平均複雜度是在n*log2(n)也就是nlog(n)，在資訊學中nlog(n)的底數預設為2。至於說快速排序10個數的時間複雜度，是沒辦法計算的，這個還是和這10個數的初始順序有關。只能說排序10個數的平均複雜度在10*log2(10)，如果這個10個序列差勁，複雜度也有可能是o(10^2)。
（快速排序的最壞情況下的時間複雜度是o(n^2)）
5樓：匿名使用者
複雜度的表示式裡面只看冪級不看具體底數，log n跟log2n是一回事，感覺你有些概念不清的樣子，時間複雜度的n就表示演算法處理的數字個數，快速排序的時間複雜度就是n log n，快速排序10個數的時間複雜度也還是n log n，你可以說n=10，但是時間複雜度的表示式裡面要求把具體的輸入個數用n表示，因為這樣才能反映出演算法在輸入個數增加的時候執行時間相應增加的程度，也就是「時間複雜度」這個概念本身想說明的問題。
6樓：謙謙知臨
資料結構中logn一般表示2為底數，如果不是的話，才會明確標明。
快速排序，希爾排序和堆排序的平均時間複雜度都是o(nlog2n)，為什麼說快速排序是最快的？
7樓：匿名使用者
快速排序是用遞迴的思想，用棧來儲存資料，它第n趟最多要確定2^n個數的最終位置。它使用的空間是最多的，用空間換取了時間。例如：
8樓：匿名使用者
快排只是內排序演算法啊，而且在內排序中也並不是最快的，只是快排在大多數情況下效果很好，因為一般的無序元素不會是完全或者近似倒序的。
9樓：下個倒角
每種排序都有它的優勢。
這個程式為什麼時間複雜度是log2n呢 請各位指教
10樓：匿名使用者
2的log n次方等於n，i=i*2中的數字2就代表log中的底，如果i=i*3，那麼底就是3。意思就是i要經過logn次迴圈運算才能達到停止條件，也就是i>n
快速排序的時間複雜度為n*log n,請教一下n是代表什麼，麻煩講通俗一點，不要百度照搬
11樓：90李鵬
不知道你的數學基礎如何，我簡單描述一下。
前提定義
待陣列的元素個數為n
背景介紹
何為快速排序？是否寫過快速排序的**？至少這個你需要事先有所知道，要不然也僅僅是停留在記憶的層面，而不理解它為n*lgn的原因。
快速排序演算法：
主要分為以下三個部分
1，partittion
2，quicksort前一部分
3，quicksort後一部分
簡單說來就是，partition從要排序的陣列中選取一個樞紐，例如即為pivot，然後將陣列中比pivot小的元素放到它的左邊，將比pivot大的元素放到它的右邊（如果是遞增排序的話）。因此根據時間複雜度的概念，這個partition的時間複雜度為n，這裡的n就是你partition方法處理的資料長度。
為何partition的時間複雜度為n？
看你的問題，既然問到了n，我就解釋一下partition為什麼會是n的時間複雜度。paritition方法選取樞紐，這個一般拿陣列元素的第一個即可，這個不需要任何的迴圈操作，直接取值即可，換句話說這個時間複雜度是1，然後需要遍歷陣列，將比pivot大的元素放到右邊，比pivot小的元素放到左邊，這個至少要遍歷整個陣列，然後對每一個元素進行操作決定是否移動，處理一個元素的時間複雜度為1，現在有n個元素要處理，故而parition方法的時間複雜度為n。
為何快速排序的時間複雜度為n*lgn?
根據背景介紹中的演算法描述，可以寫出如下的遞推公式：
f(n) = 2 * f(n/2) + n
對上述函式進行解釋如下：
f(n)代表對n個元素進行排序處理所花費的時間（當然只是一個抽象的時間概念）
根據演算法描述的三步，第一步partition就是等式右邊的n，第二步和第三步中的quicksort就是等式右邊的2 * f(n/2)。為什麼是n/2 ? 這個應該很容易理解，partition將陣列分成兩部分，下面的quicksort分別排序前一部分和後一部分，此處我們假設這個拆分是完全等分的，也就是說前一部分和後一部分都是n/2。
對上述等式進行時間複雜度的運算如下：
f(n) = 2 * f(n/2) + n = 2 * ( 2 * f(n/4) + n/2 ) + n
= 4 * f(n/4) + 2 * n
希望你能看出這個推導，就是直接的代入而已，下面我不再繼續了，可以看出每一次它等式右邊就多出了一個n， 由於每次操作是進行除以2的操作，故而最多進行lgn，也就是說最終的運算結果： f(n) = k* f(1) + lgn*n。
好了，囉囉嗦嗦.
c高手，順序儲存中的折半查詢的時間複雜度怎麼是 o(log2n) ？（書上有點看不懂 **）
12樓：似風幻雨
n+1/n就是常數，取無窮大時就是常數級的，所以o(n)=c*log2(n+1)-1;現在可以看出來量級是log2n這個級別了；時間複雜度就是看量級，常數的約去不看就是了
11、在基於排序碼比較的排序演算法中，（ ）演算法的最壞情況下的時間複雜度不高於o(nlog2n)。 a. 起泡排序 b.
13樓：謝浩
排序抄方法 最壞時間複雜度
bai 最好時間複雜du度 平均時間複雜度zhi
直接插入 o(n2) o(n) o(n2)
簡單選擇 o(n2) o(n2) o(n2)
起泡排序dao o(n2) o(n) o(n2)
快速排序 o(n2) o(nlog2n) o(nlog2n)
堆排序 o(nlog2n) o(nlog2n) o(nlog2n)
歸併排序 o(nlog2n) o(nlog2n) o(nlog2n)
在最壞的情況下，下列排序方法中時間複雜度最小的是（）a.氣泡排序 b.快速排序 c.插入排序d.堆排序
14樓：匿名使用者
答案是d，堆排序。
選項中的四種排序方法的最壞時間複雜度、最好時間複雜度 、平均時間複雜度分別為：
a、氣泡排序： o(n2) 、o(n) 、o(n2)。
b、快速排序： o(n2) 、o(nlog2n)、 o(nlog2n)。
c、插入排序： o(n2)、 o(n) 、o(n2)。
d、堆排序： o(nlog2n)、 o(nlog2n)、 o(nlog2n)。
所以，在最壞情況下，氣泡排序時間複雜度=快速排序時間複雜度=插入排序時間複雜度= o(n2)>堆排序時間複雜度= o(nlog2n)。答案選d。
15樓：匿名使用者
排序方法 最壞時間複雜度 最好時間複雜度
平均時間複雜度
直接插入 o(n2) o(n) o(n2)
簡單選擇 o(n2) o(n2) o(n2)
起泡排序 o(n2) o(n) o(n2)
快速排序 o(n2) o(nlog2n) o(nlog2n)
堆排序 o(nlog2n) o(nlog2n) o(nlog2n)
歸併排序 o(nlog2n) o(nlog2n) o(nlog2n)
所以選d
為什麼快速排序比堆排序快呢？
16樓：琳瓏的林
因為推排抄中有大量無效的操作，比如將最末尾元素移動到堆首，必須要有後續操作再移動此時堆首的元素，這樣會增加資料的無序度；但是快排不一樣，快排沒有無用操作，每一次交換都會使資料更加有序。而且堆排是跳躍訪問，快排是區域性順序訪問，這兩者的速度實際上是不一樣的，當資料量增大差距就明顯了
17樓：東邪簫醉
一般情bai況下，快速排序效du率要高於堆排序zhi。因為堆dao排序的常數較大（不過也
內是1～2之間容吧）。
快速排序的平均時間複雜度是o(1.39nlogn)。一般來說，除非有需要絕對保證不能出現o(n^2)的要求，不使用堆排。
堆排序需要有效的隨機存取。
18樓：匿名使用者
你去看看c語言自帶的sort 排序函式吧，藐視也是快排，建議你去看看什麼是分攤準則，在小資料的情況下，選擇快排比較好，不是 什麼完爆不完爆的問題 大哥
19樓：哈孤
資料結構我不大記得了，不過實際使用是用快速排序的話可能是開發人員的喜歡，歷史版本的統一，或者是以硬體換速度吧。
快速排序演算法在平均情況下的時間複雜度為求詳解
時間複雜度為o nlogn n為元素個數 1.快速排序的三個步驟 1.1.找到序列中用於劃分序列的元素 1.2.用元素劃分序列 1.3.對劃分後的兩個序列重複1,2兩個步驟指導序列無法再劃分 所以對於n個元素其排序時間為 t n 2 t n 2 n 表示將長度為n的序列劃分為兩個子序列，每個子序列需...
快速排序方法的時間複雜度為on2nn
1 對於你的問題簡單解釋如下 理論計算機研究中，衡量演算法一般從兩個方面分析 時間複雜度和空間複雜度。空間複雜度跟時間複雜度是類似的，下面簡單解釋一下時間複雜度 對於一個資料規模為n的問題，解決該問題的演算法所用時間可以用含有n的函式t n 來表示。對於絕大多數情況，我們只需要瞭解演算法的一般效能而...
資料結構快速排序問題，C語言資料結構 快速排序的問題
由於你傳遞的l是值傳遞，在快速排序內部出現了一個名字一樣的區域性變數，只是區域性變數被排序了，並不是傳入的變數被排序，可以採用傳地址的方式解決，或者不定義形參，直接採用全域性變數。我使用前者幫你實現了 再者，快速排序 有點問題，幫你修改了下 include include define maxsiz...