1最壞情況分析

❶ 設計求解下列問題的的類C語言演算法，並分析其最壞情況時間復雜性及其量級。 (數據結構導論的題目) 大家快來

(1)
void findEle(int[] a, int n, int key) {
for (int i=0; i<n; i ++) {
if (key == a[i]) {
printf( "%d\n", i+1);
return ;
}
}
printf("0\n");
return;
}
演算法的復雜度為: O(n)，最壞為n。
(2)
void findMaxMin(int a[], int n, int &max, int &maxNext) {
if (n ==0 || a == 0) return; //輸入的數組為空
if (n==1) { max = maxNext = a[0]; return;} //數組的長度為1， max 和maxNext 都設為a[0]

if (a[1] > a[0] ) { max = a[1]; maxNext=a[0];}
else { max = a[0]; maxNext = a[1];}

for(int i=2; i<n; i ++) {
if (a[i] > max) {maxNext= max; max = a[i]; } //-----a
else if (a[i] > maxNext) { maxNext = a[i];}
}
return;
}

演算法的復雜度： O(n). 最壞情況： 2n (當輸入的數組是一個排好序的升序的數組時，循環的每一步都要執行語句a進行數據交換。

❷ 1.為什麼要分析最壞情況下的演算法時間復雜性

哈哈，這個問題問得好，我記得我也問過老師這個問題，結果老師的答案是程序就是要看最差的時間，而且最差時間比較容易計算出來。比如說遍歷一個二叉樹，計算平均時間相當復雜，是2（1+1/n）ln n ，約等於1.38log n。需要一個求和，公式相當復雜（詳見《數據結構:思想與實現》高教版204頁）

所以，只用最壞了。好計算。

❸ 為何說不要迴避最壞的情況

卡瑞爾是一個很聰明的工程師，他開創了空氣調節器製造業，現在是位於紐約州瑞西的著名卡瑞爾公司的負責人。我所知道的解決憂慮困難的最好辦法，是我和卡瑞爾先生在紐約的工程師俱樂部吃中飯的時候親自從他那裡學到的。

「年輕的時候，」卡瑞爾先生說，「我在紐約州水牛城的水牛鋼鐵公司做事。我必須到密蘇里州水晶城的匹茲堡玻璃公司——一座花費好幾百萬美金建造的工廠，去安裝二架瓦斯清潔機，目的是清除瓦斯里的雜質，使瓦斯燃燒時不至於有損引擎。這種清潔瓦斯的方法是新的方法，以前只試過一次——而且當時的情況很不相同。我到密蘇里州水晶城工作的時候，很多事先沒有想到的困難都發生了。經過一番調整之後，機器可以使用了，可是成績並不能好到我們所保證的程度。

「我對自己的失敗非常吃驚，覺得好像是有人在我頭上重重地打了一拳。我的胃和整個肚子都開始扭痛起來。有好一陣子，我憂慮得簡直沒有辦法睡覺。

「最後，我的常識告訴我憂慮並不能夠解決問題，於是我想出了一個不需要憂慮就可以解決問題的辦法，結果非常有效。我這個排除憂慮的辦法已經使用了30多年。這個辦法非常簡單，任何人都可以使用。其中共有三個步驟：

「第一步，我毫不害怕而誠懇地分析整個情況，然後找出萬一失敗可能發生的最壞的結果。沒有人會把我關起來，或者把我槍斃，這一點說得很准。不錯，很可能我會丟掉差事，也可能我的老闆會把整個機器拆掉，使投進去的2萬美元泡湯。

「第二步，找出可能發生的最壞的情況之後，我就讓自己在必要的時候能夠接受它。我對自己說，這次失敗，在我的紀錄上會是一個很大的污點，可能我會因此而丟差事。但即使真是如此，我還是可以另外找到一份差事。至於我的那些老闆，他們也知道我們現在是在試驗一種清除瓦斯新法，如果這種實驗要花他們2萬美元，他們還付得起。他們可以把這筆賬算在研究費用上，因為這只是一種實驗。

「發現可能發生的最壞情況，並讓自己能夠接受之後，有一件非常重要的事情發生了。我馬上輕松下來，感受到幾天以來所沒經驗過的一份平靜。

「第三步，從這以後，我就平靜地把我的時間和精力，拿來試著改善我在心理上已經接受的那種最壞情況。

「我努力找出一些辦法，讓我減少我們目前面臨的2萬美元損失。我做了幾次實驗，最後發現，如果我們再多花5000美元，加裝一些設備，我們的問題就可以解決。我們照這個辦法去做之後，公司不但沒有損失2萬美元，反而賺了1 5萬美元。

「如果當時我一直擔心下去的話，恐怕永遠不可能做到這一點。因為憂慮的最大壞處，就是會毀了我集中精神的能力。在我們憂慮的時候，思想會到處亂轉，而喪失所有作決定的能力。然而，當我們強迫自己面對最壞的情況，而在精神上接受它之後，就能夠衡量所有可能的情形，使我們處在一個可以集中精力解決問題的地位。

「我剛才所說的這件事，發生在很多很多年以前，因為這種做法非常好，我就一直使用著。結果呢，我的生活里幾乎完全不再有煩惱了。」

為什麼威利·卡瑞爾的萬能公式這么有價值，這么實用呢？從心理學上來講，它能夠把我們從那個巨大的灰色雲層里拉下來，讓我們不再因為憂慮而盲目地摸索，它可以使我們的雙腳穩穩地站在地面上，而我們也都知道自己的確站在地面上。如果我們腳下沒有結實的土地，又怎麼能希望把事情想通呢？

應用心理學之父威廉·詹姆斯教授，已經去世38年了，可是如果他今天還活著，聽到這個面對最壞情況的公式的話，也一定會大表贊同。我怎麼知道的呢？因為他曾經告訴他的學生說：「你要願意承擔這種情況，因為能接受既成的事實，就是克服隨之而來的任何不幸的第一個步驟。」

林語堂在他的《生活的藝術》里也談到同樣的概念。「心理的平靜，」這位中國哲學家說，「……能接受最壞的情況，在心理上，就能讓你發揮出新的能力。」

這就對了，一點也不錯。在心理上就能讓你發揮出新的能力。當我們接受了最壞的情況之後，我們就不會再損失什麼，而這也就是說，一切都可以得回來。「在面對最壞的情況之後，」威利·卡瑞爾告訴我們說，「我馬上就輕松下來，感到一種好幾天來沒有經歷過的平靜。然後，我就能思想了。」

很有道理，對不對？可是還有成千上萬的人，為憤怒而毀了他們的生活。因為他們拒絕接受最壞的情況，不肯由此以求改進，不願意在災難中盡可能地救出點東西來。他們不但不重新構築他們的財富，卻參與了「和經驗所作的一次冷酷而激烈的斗爭」——終於變成我們稱之為憂鬱症的那種頹喪的情緒的犧牲者。

這套消除憂慮的萬靈公式，曾經使一個帶著棺材航海旅行的垂死病人胖了90磅。這是艾爾·漢里的故事。那是1948年11月17日，他在波士頓史帝拉大飯店親口告訴我的故事：

「1929年，」他說，「因為我常常發愁，得了胃潰瘍。有一天晚上，我的胃出血了，被送到芝加哥西比大學的醫學院附設醫院里。我的體重從175磅降到90磅。我的病嚴重到使醫生警告我，連頭都不許抬。三個醫生中，有一個是非常有名的胃潰瘍專家。他們說我的病是『已經無葯可救了』。我只能吃蘇打粉，每小時吃一大匙半流質的東西，每天早上和每天晚上都要有護士拿一條橡皮管插進我的胃裡，把裡面的東西洗出來。

「這種情形過了好幾個月……最後，我對自己說：『你睡吧，漢里，如果你除了等死之外沒有什麼別的指望了，不如好好利用你剩下的這一點時間。你一直想在你死以前環游世界，所以如果你還想這樣做的話，只有現在就去做了。』

「當我對那幾位醫生說，我要環游世界，我自己會一天洗兩次胃的時候，他們都大吃一驚。不可能的，他們從來都沒有聽說這種事。他們警告我說』，如果我開始環游世界，我就只有葬在海里了。『不，我不會的。』我回答說，『我已經答應過我的親友，我要葬在尼布雷斯卡州我們老家的墓園里，所以我打算把我的棺材隨身帶著。』

「我去買了一具棺材，把它運上船，然後和輪船公司安排好，萬一我去世的話，就把我的屍體放在冷凍艙里，一直到回老家的時候。我開始踏上旅程，心裡只想著奧瑪開儼的一首詩。

啊，在我們零落為泥之前，

豈能辜負，不拼作一生歡，

物化為泥，永寂黃泉下，

沒酒、沒弦、沒歌伎，而且沒明天。

「我從洛杉磯上了亞當斯總統號的船向東方航行的時候，就覺得好多了，漸漸地不再吃葯，也不再洗胃。不久之後，任何食物都能吃了——甚至包括許多奇奇怪怪的當地食品和調味品。這些別人都說我吃了一定會送命的。幾個禮拜過去之後，我甚至可以抽長長的黑雪茄，喝幾杯老酒。多年來我從來沒有這樣享受過。我們在印度洋上碰到季風，在太平洋上遇到台風。這種事情要是害怕，也會讓我躺進棺材裡的，可是我卻從這次冒險中得到很大的樂趣。

「我在船上和他們玩游戲、唱歌、交新朋友，晚上聊到半夜。到了中國和印度之後，我發現我回去之後要料理的私事，跟在東方所見到的貧窮與飢餓比起來，簡直像是天堂跟地獄之比。我中止了所有無聊的擔憂，覺得非常的舒服。回到美國之後，我的體重增加了90磅，幾乎完全忘記了我曾患過胃潰瘍。我這一生中從沒有覺得這么舒服。我回去後一天也沒再病過。」

艾爾·漢里告訴我，他發現他是在下意識里應用了威利·卡瑞爾征服憂慮的辦法。

讓我們看看其他人怎樣利用威利·卡瑞爾的萬靈公式，來解決他們自己的問題。下面就是一個例子。這是以前我的一個學生——目前他是一名紐約油商——所做過的事情：

「有人勒索我，」他說，「我不相信會有這種事情——我不相信這種事情會發生在電影以外的現實生活里——可是我真的是被勒索了。事情是這樣的：我主管的那個石油公司，有好幾輛運油的卡車和好些司機。在那段時期，物價管理委員會的條例是很嚴格的，我們所能送給每一個顧客的油量也都有限制。我起先不知道事情的真相，好像有一些運貨員減少我們固定顧客的油量，把偷下來的賣給一些他們的顧客。

「有一天，有個自稱政府調查員的人來看我，跟我索要紅包。他說，他掌握我們運貨員舞弊的證據。並以此要挾說，如果我不答應的話，他要把證據轉交給地方檢察官。這時候，我才發現公司有這種非法的買賣。

「當然，我知道我沒有什麼好擔心的——至少跟我個人無關。但是我也知道法律規定，公司應該為員工的行為負責。還有，萬一案子打到法院去，上了報紙，這種壞名聲就會毀了我的生意。我對自己的生意非常驕傲——我父親在24年前為此打下了基礎。

「我生病了，三天三夜吃不下睡不著。我一直在那件事情裡面打轉。我是該付那筆錢——5000美金，還是該跟那個人說，你愛怎麼干就怎麼干吧？我一直決定不下，每天晚上都在噩夢中度過。

「在事情發生後的某一個禮拜天的晚上，我碰巧拿起一本叫做《如何不再憂慮》的小書，這是我去聽卡耐基公開演說時拿到的。我讀到威利·卡瑞爾的故事，裡面說：『面對最壞的情況。』於是我問自己：『如果我不肯付錢，那個勒索者把證據交給地檢處的話，可能發生的最壞情況是什麼呢？』

「答案是：『毀了我的生意——最壞就是如此。我不會被送進監獄。可能發生的，只是我會被這件事毀了。』

「於是我對自己說：『好了，生意即使毀了，但我心理上可以接受這點，接下去又會怎樣呢？』

「嗯，我的生意毀了之後，也許得去另外找份工作。這也不壞，我對石油知道得很多——有幾家大公司可能會樂意僱用我……我開始覺得好過多了。三天三夜之後，我的那份憂慮開始消散了。我的情緒終於穩定了下來……而意外地，我居然能夠開始思考了。

「我清醒地看出第三步——改善最壞的情況。就在我想解決方法的時候，一個全新的局面展現在我的面前：如果我把整個情況告訴我的律師，他可能會幫我找到一條我一直沒有想到的路子。這乍聽起來很笨，因為我起先一直沒有想到這一點——我原先一直沒有好好思想，只是一味在擔心。我打定了主意，第二天清早就去見我的律師，接著我上了床，安安穩穩地睡了一覺。

「事情的結果如何呢？第二天早上，我的律師叫我去見地方檢察官，把真實情形告訴他。我照他的話做了。當我說出原委之後，出乎意外地聽到地方檢察官說，這種勒索的案子已經持續好幾個月了，那個自稱是『政府官員』的人，實際上是警方通緝犯。當我為了是否該把5000美金交給那個職業罪犯而擔心了三天三夜之後，聽到這番話，真是鬆了一大口氣。

「這次的經歷給我上了永難忘懷的一課。現在，每當面臨會使我憂慮的難題時，我就把所謂的『威利·卡瑞爾的老公式』派上用場。」

——引自延邊人民出版社《人性的優點全集》

❹ 設計求解下列問題的類C語言演算法，並分析其最壞情況時間復雜性及其量級。 1.在數組A（1..n）中查找

思路：
最壞情況比較次數
最好情況比較次數
求出平均比較次數
算出基本運算次數
得出時間復雜度 f(n)=O(g(n))

❺ 分別舉一個印象最差最不成功最成功的廣告案例,分析原因。

肯德基的所有廣告。嘩眾取寵、立意滑稽、毫無美感。

❻ 設計求解下列問題的演算法，並分析其最壞情況的時間復雜度及其量級。

intlocate(dataytpeA[1..n],dateytpek)
{i=n;
while((I<=n)&&(A[i]!=k))I++;
if(I<=n)return(i);
elsereturn(o);}
當查找不成功時，總是比較n+1次，所以，最壞時間復雜性為n+1。其量T（n）=O(n).
（2）VoidCZ_max(datatypeA[n],x,y)
{x=A[1];y=A[1];
for(I=2;I<=n;I++)
if(x<A[i]
{y=x;x=A[i];}
elseif(y<A[i]y=A[i];
}
若經條件判斷語句為標准操作，則最壞情況時間復雜度為n-1，其量級為T（n）=O（n）

❼ 冒泡排序在最壞的情況下的比較次數為什麼是n(n-1)/2

冒泡排序如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個的話，升序的數字；最壞的情況就是如此：次數為：n-1+n-2.........+1=n*(n-1)/2

比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。

針對所有的元素重復以上的步驟，除了最後一個。持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

(7)1最壞情況分析擴展閱讀：

冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。

所以，如果兩個元素相等，是不會再交換的；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序演算法。

❽ 作業 使用O分析比較名次排序、選擇 排序、冒泡排序、插入排序最好 和最壞情況下的時間復雜性。

最壞情況下：直接選擇排序：每次都要執行交換，總移動次數為（n-1)次交換 O(n) 冒泡排序：每比較一次都要進行一次交換 ，移動次數為 3n(n-1)/2 O(n2) 直接插入排序：n2/4 O(n2) 堆排序： O(nlog2n）所以，應該選D

❾ 演算法分析中，為什麼分析最壞情況而不是平均情況

哈哈，這個問題問得好！我記得我也問過老師這個問題，結果老師的答案是程序就是要看最差的時間，而且最差時間比較容易計算出來。比如說遍歷一個二叉樹，計算平均時間相當復雜，是2（1+1/n）ln n ，約等於1.38log n。需要一個求和，公式相當復雜（詳見《數據結構：思想與實現》高教版204頁） 所以，只用最壞了。好計算

❿ 設計求解下列問題的類C語言演算法，並分析其最壞情況時間復雜性及其量級。（1），在數組A[1...n]中查找值為

演算法如下： void max(datatype A[],datatype m,datatype sm) //datatype為C語言標准數據類型 { int i; m=sm=A[1];//m存放最大值，sm存放次最大值 for(i=2;i＜=n;++i) if(A[i]＞m) { sm=m;m=A[i]; } else if(A[i]＞sm) sm=A[i]; } 為了得到最大值和次最大值，必須經過n-1次循環，所以最壞的時間復雜度為n-1，即O(n)。