1樓：物理公司的
最差情況下的復
雜度是所有可能的輸入資料所消耗的最大資源，如果最差情況下的複雜度符合我們的要求，我們就可以保證所有的情況下都不會有問題。
某些演算法經常遇到最差情況。比如一個查詢演算法，經常需要查詢一個不存在的值。
也許你覺得平均情況下的複雜度更吸引你，可是平均情況也有幾點問題。第一，難計算，多數演算法的最差情況下的複雜度要比平均情況下的容易計算的多，第二，有很多演算法的平均情況和最差情況的複雜度是一樣的. 第三，什麼才是真正的平均情況？
如果你假設所有可能的輸入資料出現的概率是一樣的話，也是不合理的。其實多數情況是不一樣的。而且輸入資料的分佈函式很可能是你沒法知道。
考慮最好情況的複雜度更是沒有意義。幾乎所有的演算法你都可以稍微修改一下，以獲得很好的最好情況下的複雜度(要看輸入資料的結構，可以是o(1))。怎樣修改呢?
預先計算好某一輸入的答案，在演算法的開始部分判斷輸入，如果符合，給出答案。
2樓：勞雙韶旭
假設陣列長度為n，對於氣泡排序的最壞情況是逆向有序，複雜度為n-1+n-
2+n-
3+...+2+
1=（n-1)(n-1+1)/2=
n(n-1)/2
關於c語言程式設計的時間複雜度
3樓：臨江仙
printf("%d%c",a,c)算是一條語句。
strcmp(svyd,svyy)這個是一條基本計算時間複雜度通常不這麼看。
如果是一個for迴圈，比版如權
for(i = 0; i 算是o(n)，是個線性的。
如果for裡面又一個for，那麼是o(n^2)。
建議看一下資料結構演算法相關的知識。
4樓：匿名使用者
這是一個函式，copy並不是什麼基本運算bai，這些庫du函式你可以看看他們的定義，裡邊還zhi可能有其它的函式。dao你說的基本運算應該是指一條cpu的指令，比如一次加法之類的，這個你學了彙編可能會更瞭解，而其實就算是一條彙編指令他們用的時間也可能不同的，比如乘法比加法慢，這些你學了微機原理應該就知道了。而對於程式設計師來說，時間複雜度是演算法裡的概念，你學了演算法設計就知道了。
快速排序演算法在平均情況下的時間複雜度為 求詳解
5樓：匿名使用者
時間複雜度為o(nlogn) n為元素個數
1. 快速排序的三個步驟：
1.1. 找到序列中用於劃分序列的元素
1.2. 用元素劃分序列
1.3. 對劃分後的兩個序列重複1,2兩個步驟指導序列無法再劃分
所以對於n個元素其排序時間為
t(n) = 2*t(n/2) + n （表示將長度為n的序列劃分為兩個子序列，每個子序列需要t(n/2)
的時間，而劃分序列需要n的時間）
而 t(1) = 1 （表示長度為1的序列無法劃分子序列，只需要1的時間即可）
t(n) = 2^logn + logn * n （n被不斷二分最終只能二分logn次（最優的情況,每次選取
的元素都均分序列））
= n + nlogn
因此t(n) = o(nlogn)
以上是最優情況的推導，因此快速排序在最優情況下其排序時間為o(nlogn),通常平均情況
我們也認為是此值。
在最壞情況下其會退化為氣泡排序，t(n) = t(n - 1) + n (每次選取的元素只能將序列劃分為
一段，即自身是 最小元素或最大元素)
因此t(n) = n * (n-1) / 2 相當於o(n^2)
6樓：匿名使用者
時間複雜度為o（nlogn）n是多少元素
1。快速排序的三個步驟：
1.1。查詢序列用於劃分的序列中的元素
1.2元素劃分的序列
1.3 1,2兩個步驟的過程不斷重複，兩個序列劃分指導序列不能被細分
n個元素的排序條件為t（n）= 2 * t（n / 2個）+ n（表示序列分為兩個子序列中的n的長度，每個子序列需要到t（n / 2個）
時間除以
t（1）= 1（序列的長度不能被劃分為子序列，序列的n個）只需要1罐）
t（n）= 2 ^ logn + logn * n（n為不斷二分法最後只有兩點：logn（最佳，各選擇
平均序列的元素））
= n + nlogn
因此，t（n）= o（nlogn ）
以上是派生的理想情況下，快速排序排序在最佳的情況下，時間為o（nlogn）通常平均
我們也相信，這個值。
在最壞的情況下，它會淪為氣泡排序，t（n）= t（n - 1個）+ n（每次選擇元素序列分為
一些，這是他們自己的元素是最小的或最大的元素）
t（n）= n *（n-1）/ 2，相當於為o（n ^ 2）
7樓：雨的恩惠
正如歸併排序一樣，快速排序也是遞迴的，因此，他的分析需要求解一個遞推公式。我們將對快速排序進行這種分析，假設有一個隨機的樞紐元（不用三數中值分割法），對一些小的檔案也不使用截止範圍。和歸併排序一樣，取t(0)=t(1)=1,快速排序的執行時間等於兩個遞迴呼叫的執行時間加上花費在分割上的限行時間（樞紐元的選取僅花費常數時間）。
我們得到基本的快速排序關係：
t(n)=t(i)+t(n-i-1)+**
其中，i=|s1|是s1中的時間個數。我們還將考查三種情況。
最壞情況的分析：
樞紐元始終是最小元素。此時i=0，如果我們忽略無關緊要的 t(0)-1,那麼遞推關係為
t(n0=t(1)+c(sum+=i;i in (2,n])= o(n^2)
最好情況：
在最好的情況下，樞紐元正好位於中間，t(n)=o(n* log(n))
平均情況的分析：
t(n)=o(n*logn)
《資料結構與演算法分許（c語言描述）》 片段，字太多了，全是公式推導，打了一部分
8樓：郝霞佛念
快速排序時間複雜度下界為o(nlogn)，最壞情況為o(n^2)
快速排序的平均時間複雜度為o(nlogn)。
在最壞的情況下氣泡排序的時間複雜度是什麼
9樓：匿名使用者
氣泡排序的演算法時間複雜度上 最壞情況下 是：
o(n^2 )
氣泡排序是這樣實現的：
首先將所有待排序的數字放入工作列表中。
從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。
重複2號步驟，直至再也不能交換。
氣泡排序的平均時間複雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
快速排序的時間複雜度在最壞情況下是多少？
10樓：匿名使用者
o(n2)最壞
o(nlog2n)平均
11樓：oi淘盡英雄
nlogn （以2為底的）
c語言中什麼情況下跳出while的迴圈
賦值運算子也會返回一個值的 這個值就是賦值運算子左邊的變數賦值後的值，也就是其右邊的表示式的值，只要輸入的不是字元eof，while 裡的判斷條件就是真，因此可以跳出迴圈 跳出while迴圈有以下四種可能 bai1 while expr 的判斷條件du為假時，自zhi動退出循 dao環。即專expr...
下列排序方法中，最壞情況下比較次數最少的是A氣泡排序
最壞情況下比較次數最少的為d 堆排序 a 氣泡排序 需要比較o n 2 次 n n 1 2次 即序列逆序的情況 b 簡單選擇排序，無論是否最壞都需要o n 2 次 n n 1 2次 c 直接插入排序，最壞情況需要比較o n 2 次 n n 1 2次 d 堆排序，無論是否最壞比較o nlog2n 次 ...
氣泡排序在最壞的情況下的比較次數為什麼是n n
氣泡排序如1，2,3,4最好的情況是按完全升級排列，最壞就是數字完全按降序排列 第一次是1 然後1和2,3,4 第2次是2 比較誰比它小交換，於是2和34交換，答案是3421 第3次為3 3和4 最後是4321 這就是最壞情況下的次數3 2 1 6 4 3 2 其實對於n個的話，你要求降低排列，但是...