1樓：謝浩
排序抄方法 最壞時間複雜度
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)
設序列長度為n,在最壞的情況下,時間複雜度為o(log2n)的演算法是什麼
2樓：匿名使用者
二分法二分法的基本思想如下：
假設資料是按升序排序的，對於給定值x，從序列的中間位置開始比較，如果當前位置值等於x，則查詢成功；若x小於當前位置值，則在數列的前半段中查詢；若x大於當前位置值則在數列的後半段中繼續查詢，直到找到為止。
由於是陣列是預先排序好的，所以可以採用折半查詢的方式，每次拋掉待查詢部分的一半
這樣，長度為n的陣列，只需要log2n次查詢即可，2是對數的底。
例如，長度為7的陣列，最多只需要3次就可以找到o(log2n)只是表示是log2n同一數量級，因為有個取整的問題，而且也有可能在查詢過程中就已經找到（也就是某個折半查詢點正好是待查詢資料），這樣o(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），這個o是什麼，還有能解釋一下這個資料是
7樓：風箏
o是表示bai最大近似的意思（
du個人理解），書上嚴格zhi定義我忘了，dao假如說時間複雜度是o（n）的話，專一般屬
情況下語句塊的執行次數就是n。
快排在有序情況下複雜度退化到o（n~2），因為快排每次都是選定一個軸值，把資料按軸值分成兩部分，這個軸值一般取第一個資料，當有序情況下，每次需要排序的資料都在軸值的一邊，總共要拍n次
陣列排序的最少時間複雜度o(nlog2n)怎麼計算的？
8樓：匿名使用者
for(int j=1; j<=n; j*=2)這個迴圈最終執行的次數假設為x，則x次的時候j=2^x 。
當j>n時停止執行，於是2^x>n ，則可以認為該迴圈一共執行了log2(n)次。
所以該迴圈的時間複雜度為o(log2(n))，簡記為o(log n) ，忽略掉2的底數。
方法：1、首先，看外迴圈for（i=0；i2、再看內部迴圈，for（j=1；jn===》x=log2(n)。
3、如果把兩個迴圈合在一起看，也就是一共迴圈了n個x次，也就是log2(n)。
9樓：匿名使用者
這個是基於關鍵字比較在最壞情況下的最好時間複雜度，計算過程：
因為一次比較可以區分資料的兩個狀態，n個資料的初始排列可能為n!，用完全二叉樹來看，n!個葉子的高度為o(log2(n!))~o(nlog2n)
10樓：wx越前龍馬
o(log2(n!))~o(nlog2n)並不相似吧，他兩的階數不同，右側等同於o(log2（n∧n）)，冪指不等同於階乘吧！
在下列排序演算法中，哪演算法的時間複雜度與初始排序無關
在下列排序演算法中，哪一個演算法的時間複雜度與初始排序無關 a.插入排序 b.起泡排序 c.快速排序 d.選擇排序 在下列排序演算法中，哪一個演算法的時間複雜度與初始排序無關 d不管原陣列是什麼樣子，每一次你都要遍歷一邊剩餘的數來選取最大 最小值 演算法的時間複雜度與初始排序無關的都有什麼排序 常見...
資料結構中幾種常見內部排序方法的比較
內容來自使用者 cngdzjl 資料結構各種排序方法的綜合比較 結論 排序方法 平均時間 最壞時間 輔助儲存 簡單排序 o n2 o n2 o 1 快速排序 o nlogn o n2 o logn 堆排序 o nlogn o nlogn o 1 歸併排序 o nlogn o nlogn o n 基數...
快速排序演算法在平均情況下的時間複雜度為求詳解
時間複雜度為o nlogn n為元素個數 1.快速排序的三個步驟 1.1.找到序列中用於劃分序列的元素 1.2.用元素劃分序列 1.3.對劃分後的兩個序列重複1,2兩個步驟指導序列無法再劃分 所以對於n個元素其排序時間為 t n 2 t n 2 n 表示將長度為n的序列劃分為兩個子序列，每個子序列需...