1樓：匿名使用者
計算複雜性目前主要用計算所消耗的資源數量來量度。由於演算法在計算時所消耗的資源與問題規模有關，所以通常用遞增函式來估計。另外，對具體問題例項，演算法的資源消耗量是不同的，通常可以估計出最壞、最好和平均三種情形下對資源消耗的數量。
對上述三者作時間複雜性分析的具體做法如下：以順序查詢為例，最壞情況是指需要搜尋完所有的資料；最好情況是指搜尋的第一個資料就是所要的資料；平均情況是指所獲得的資料按其實際分佈而言，平均需要查詢比較的次數。
如果一個演算法在平均情況下的計算時間複雜性為 ,則該演算法在最壞情況下所需的計算時間為 。
2樓：匿名使用者
什麼問題啊，平均計算複雜性是n，還是logn？問題沒問清楚吧
比如快速排序在平均情況下複雜性為o(nlogn)，最壞情況下複雜性為o(n2)
要看具體演算法了吧
c語言，程式設計 演算法 最壞情況下的時間複雜度可以與平均情況的時間複雜度相 10
3樓：物理公司的
最差情況下的復
雜度是所有可能的輸入資料所消耗的最大資源，如果最差情況下的複雜度符合我們的要求，我們就可以保證所有的情況下都不會有問題。
某些演算法經常遇到最差情況。比如一個查詢演算法，經常需要查詢一個不存在的值。
也許你覺得平均情況下的複雜度更吸引你，可是平均情況也有幾點問題。第一，難計算，多數演算法的最差情況下的複雜度要比平均情況下的容易計算的多，第二，有很多演算法的平均情況和最差情況的複雜度是一樣的. 第三，什麼才是真正的平均情況？
如果你假設所有可能的輸入資料出現的概率是一樣的話，也是不合理的。其實多數情況是不一樣的。而且輸入資料的分佈函式很可能是你沒法知道。
考慮最好情況的複雜度更是沒有意義。幾乎所有的演算法你都可以稍微修改一下，以獲得很好的最好情況下的複雜度(要看輸入資料的結構，可以是o(1))。怎樣修改呢?
預先計算好某一輸入的答案，在演算法的開始部分判斷輸入，如果符合，給出答案。
4樓：勞雙韶旭
假設陣列長度為n，對於氣泡排序的最壞情況是逆向有序，複雜度為n-1+n-
2+n-
3+...+2+
1=（n-1)(n-1+1)/2=
n(n-1)/2
快速排序演算法在平均情況下的時間複雜度為 求詳解
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)。
求高手幫忙做一套演算法分析的題目。做好之後再加100。
9樓：118硬幣
我表示昨晚一個通宵，從分治開始一直看到回溯……幸好只考了一題的分支限界~
壓力好大啊~
10樓：借過
老師 我是來圍觀的
11樓：
老師 好人做到底 把題發來吧
12樓：匿名使用者
老師的id亮了，圍觀圍觀
13樓：匿名使用者
膜拜沙莎姐~~~去年我們也是這樣，貌似我剛過......
14樓：匿名使用者
看樣子沙莎老師的課程試卷沒什麼改動呀。。。。。。
同學你這樣子讓莎莎老師以後都不敢透題了，你這是害了中南大學電腦科學與技術專業所有學弟，強烈譴責！
你也傷害沙莎老師了。再次譴責！
15樓：
廣告位招租。。。膜拜沙莎老師
16樓：壞壞難
哎，哥們，速度採納老師的回答吧
17樓：匿名使用者
路過，上網找答案，沒想到這裡居然如此火爆。沙莎老師都在。熱鬧啊！！！
18樓：匿名使用者
跪求沙老師庇護保佑。不能掛我。
19樓：匿名使用者
圍觀沙莎老師，膜拜老師，老師你要給力啊，不能掛啊不能掛~~
20樓：匿名使用者
此貼必將入選2023年中南十大網路事件 o(∩_∩)o~
21樓：匿名使用者
同求啊，不然莎莎才會很生氣。。。
22樓：匿名使用者
現在的學生們越來越聰明瞭。明天的考試不會很難的，但是題不一定都在這裡面，只要你們聽了課，好好複習就能過。
23樓：匿名使用者
哎 這樣不好啊 莎莎會知道的
24樓：匿名使用者
求答案啊,不然明天怎麼辦...樓上的哥們要給力啊
25樓：匿名使用者
傻傻灰常灰常生氣，後果灰常灰常嚴重！
不用rand()，如何產生亂數？
26樓：匿名使用者
亂數是不重複的隨機數嗎？
很多演算法的每一個計算步驟都是固定的，而在下面我們要討論的概率演算法，允許演算法在執行的過程中隨機選擇下一個計算步驟。許多情況下，當演算法在執行過程中面臨一個選擇時，隨機性選擇常比最優選擇省時。因此概率演算法可在很大程度上降低演算法的複雜度。
概率演算法的一個基本特徵是對所求解問題的同一例項用同一概率演算法求解兩次可能得到完全不同的效果。這兩次求解問題所需的時間甚至所得到的結果可能會有相當大的差別。一般情況下，可將概率演算法大致分為四類:
數值概率演算法，蒙特卡羅（monte carlo）演算法，拉斯維加斯（las vegas）演算法和舍伍德（sherwood）演算法。
數值概率演算法常用於數值問題的求解。這類演算法所得到的往往是近似解。而且近似解的精度隨計算時間的增加不斷提高。
在許多情況下，要計算出問題的精確解是不可能或沒有必要的，因此用數值概率演算法可得到相當滿意的解。
蒙特卡羅演算法用於求問題的準確解。對於許多問題來說，近似解毫無意義。例如，一個判定問題其解為「是」或「否」，二者必居其一，不存在任何近似解答。
又如，我們要求一個整數的因子時所給出的解答必須是準確的，一個整數的近似因子沒有任何意義。用蒙特卡羅演算法能求得問題的一個解，但這個解未必是正確的。求得正確解的概率依賴於演算法所用的時間。
演算法所用的時間越多，得到正確解的概率就越高。蒙特卡羅演算法的主要缺點就在於此。一般情況下，無法有效判斷得到的解是否肯定正確。
拉斯維加斯演算法不會得到不正確的解，一旦用拉斯維加斯演算法找到一個解，那麼這個解肯定是正確的。但是有時候用拉斯維加斯演算法可能找不到解。與蒙特卡羅演算法類似。
拉斯維加斯演算法得到正確解的概率隨著它用的計算時間的增加而提高。對於所求解問題的任一例項，用同一拉斯維加斯演算法反覆對該例項求解足夠多次，可使求解失效的概率任意小。
舍伍德演算法總能求得問題的一個解，且所求得的解總是正確的。當一個確定性演算法在最壞情況下的計算複雜性與其在平均情況下的計算複雜性有較大差別時，可以在這個確定演算法中引入隨機性將它改造成一個舍伍德演算法，消除或減少問題的好壞例項間的這種差別。舍伍德演算法精髓不是避免演算法的最壞情況行為，而是設法消除這種最壞行為與特定例項之間的關聯性。
本文簡要的介紹一下數值概率演算法和舍伍德演算法。
首先來談談隨機數。隨機數在概率演算法設計中扮演著十分重要的角色。在現實計算機上無法產生真正的隨機數，因此在概率演算法中使用的隨機數都是一定程度上隨機的，即偽隨機數。
產生隨機數最常用的方法是線性同餘法。由線性同餘法產生的隨機序列a1,a2,...,an滿足
a0=d
an=(ban-1+c)mod m n=1,2.......
其中,b>=0, c>=0, d>=m。d稱為該隨機序列的種子。
下面我們建立一個隨機數類radomnumber，該類包含一個由使用者初始化的種子randseed。給定種子之後，既可產生與之相應的隨機數序列。randseed是一個無符號長整型數，既可由使用者指定也可由系統時間自動產生。
const unsigned long maxshort=65536l;
const unsigned long multiplier=1194211693l;
const unsigned long adder=12345l;
class randomnumber
; randomnumber::randomnumber(unsigned long s)
unsigned short randomnumber::random(unsigned long n)
double randomnumber::frandom(void)
函式random在每次計算時，用線性同餘式計算新的種子。它的高16位的隨機性較好，將randseed右移16位得到一個0-65535之間的隨機整數然後再將此隨機整數對映到0-n-1範圍內。
對於函式frandom,先用random(maxshort)產生一個0-(maxshort-1之間的整型隨機序列)，將每個整型隨機數除以maxshort，就得到[0，1）區間中的隨機實數。
下面來看看數值概率演算法的兩個例子：
1.用隨機投點法計算π
設有一半徑為r的圓及其外切四邊形，如圖所示。向該正方形隨機投擲n個點。設落入圓內的點在正方形上均勻分佈，因而所投入點落入圓內的概率為 πr^2/4r^2，所以當n足夠大時，k與n之比就逼近這一概率，即π/4。
由此可得使用隨機投點法計算π值的數值概率演算法。具體實現時，只需要在第一次象限計算即可。
double darts(int n)
return 4*k/double(n);
} 再簡單舉個舍伍德演算法的例子。
我們在分析一個演算法在平均情況下的計算複雜性時，通常假定演算法的輸入資料服從某一特定的概率分佈。例如，在輸入資料是均勻分佈時，快速排序演算法所需的平均時間是o(n logn)。但是如果其輸入已經基本上排好序時，所用時間就大大增加了。
此時，可採用舍伍德演算法消除演算法所需計算時間與輸入例項間的這種聯絡。
在這裡，我們用舍伍德型選擇演算法隨機的選擇一個陣列元素作為劃分標準。這樣既能保證演算法的線性時間平均效能又避免了計算擬中位數的麻煩。非遞迴的舍伍德型演算法可描述如下：
template
type select(type a, int l, int r, int k)
if(j-l+1==k)
return pivot;
a[l]=a[j];
a[j]=pivot;
if(j-l+1
type select(type a, int n, int k)
平時我們一般開始考慮的是一個有著很好平均效能的選擇演算法，但在最壞情況下對某些例項演算法效率較低。這時候我們用概率演算法，將上述演算法改造成一個舍伍德型演算法，使得該演算法對任何例項均有效。
不過在有些情況下，所給的確定性演算法無法直接改造成舍伍德型演算法。這時候就可以藉助隨機預處理技術，不改變原有的確定性演算法，僅對其輸入進行隨機洗牌，同樣可以得到舍伍德演算法的效果。還是剛才的例子，換一種方法實現：
template
void shuffle(type a, int n) }
在基於排序碼比較的排序演算法中演算法的最壞情況下的
排序抄方法 最壞時間複雜度 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 nlogn n為元素個數 1.快速排序的三個步驟 1.1.找到序列中用於劃分序列的元素 1.2.用元素劃分序列 1.3.對劃分後的兩個序列重複1,2兩個步驟指導序列無法再劃分 所以對於n個元素其排序時間為 t n 2 t n 2 n 表示將長度為n的序列劃分為兩個子序列，每個子序列需...
氣泡排序在最壞的情況下的比較次數為什麼是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個的話，你要求降低排列，但是...