氣球排序的複雜性

-4

我一直在尋找氣球排序的複雜性，但在互聯網上我沒有看到它的任何內容。有人能給我氣球排序的平均情況，最佳情況和最壞情況嗎？我們正在進行研究，我們真的需要它來完成我們的論文。氣球排序的複雜性

2017-03-17 Levi

你根本就找不到......。沒有辦法。 http://bigocheatsheet.com/首先谷歌結果。 – Carcigenicate

你可以在這裏找到更多的信息http://www.glennvon.com/2010/10/balloon-sorting-in-c.html?m=1 –

@HarshitAgrawal它不提供我需要的信息，但感謝回答。 – Levi

對我來說看起來像O（n^2）。你有

for(x=0;x<num;x++) 
{ 
    for(y=0;y<num-x;y++){ 
     if(N[x] > N[x+y]){ 
     temp=N[x]; 
     N[x] =N[x+y]; 
     N[x+y]=temp; 
    } 
}

你有第一個循環n。

對於第二個循環，當x = 0時，循環再運行n次（這是最壞的情況）。因此你有n * n = n^2看起來其他循環只有O（n），所以O（n^2）控制着運行時間。

2017-03-17 17:24:14

謝謝你的回答。所以最好的情況是O（n），平均情況是O（n^2）？ – Levi

@Levi，O（n）和O（n^2）*什麼*？操作？比較？互換？ –

總的來說，在這個答案中調用的循環嵌套總是執行*完全* num +（num-1）+（num-2）+ ... + 1 = num *（num + 1）/ 2 = O（n^2）比較。這是最好的，最差的和平均的情況。 –

回答