算法導論中文版答案課后第三章

第三章函數(shù)的增長的時間確實比較緊，請大家原諒（如果迫切需要解答請不我聯(lián)系，另外，結(jié)識一點正在學習算法的仁兄，把算法導論（學算法的都會看這本書吧）的讀書筆記完善，并且盡量減少錯誤。我的讀書筆記原版是用Word2007+Aurora（MikTex的一個工具word版本筆記發(fā)給你的。記號：

，存在正常 ，使對所有 ，有，存在正常數(shù) ，使對所有 ，有，存在正常數(shù) ，使對所有 ，有，對任意正常數(shù)，存在常 ，使對所有 ，有數(shù)，存在常數(shù) ，有fgabab3.1-1： 不都是漸近非負函數(shù)。利 記號的基本定義來證。要使只要存在正常 ，當n足夠大時2.這里輪換對稱，假設 恒成立 ，使n足夠大成立，故3.1-2：證明對任意實常數(shù)a和b，其 ，要使取取時在中 中故存在正常數(shù)使，即在中 中故存在正常數(shù)使，即3.1-3：解釋為什么“算法A的運行時間至少是”這句話是無意義的。3.1-4：成立嗎？成立嗎？1.，c3.1-5：證明定理條件一：存在正常數(shù)，使存在正常數(shù)：3.1-6證明一個算法的運行時間是當且僅當其情況運行時間是，且最佳情況運行時間是。3.1-7：證明是空集簡單的說明如下（可以用基本定義進行嚴格證明3.1-8nmnm以以丌同的速率，互相獨立地趨于無窮。對給定的函數(shù)，為函集存在正整數(shù) ，使對所有 ，有給出對應的和的定義存在正整數(shù) ，使對所 ，。存在正整數(shù) ，使對所 ，。對任意實 和整對于一個d次的漸近正多項式，有若對于某個常數(shù)有，則稱函數(shù)有多項式界1任意正的多項式函數(shù)都比多項對數(shù)函數(shù)增長得快。 ，，性質(zhì)第i個那契數(shù)等于和最接近的整數(shù)所以那契數(shù)以指數(shù)形式增長 和是單調(diào)遞增的函數(shù)，則和也是單調(diào)遞 和是非負的，那么也是單調(diào)遞增的。時，，1.，故是單調(diào)遞增函數(shù)2.是單調(diào)遞增函數(shù)且故是單調(diào)遞增函數(shù)。故是單調(diào)遞增函數(shù)（3.5（3.18a.對于足夠大的n，一定 ，對數(shù)函數(shù)是單調(diào)遞增函數(shù)，所以 b.b. ， 時取取故存在正常數(shù)， 時 3.2-4：函數(shù)是否是多項式有界？函數(shù)呢多項式有界條件利用3.2-5？假設（i個，所以在漸近上更大些3.2-6：用歸納法證明：第i個那契數(shù)滿足等其中是黃金分割律，是共軛數(shù)。i=1，iiii3.2-7：證明：對 ，第個那契數(shù)滿足顯然成立。故 為一個n的d次多項式，其 ，令k為一個常數(shù)。利用漸若 ，則 若 ，則 ，則 ，則 ，則假設i足夠大， a), 即可b), 即可c) 即可d)nc（可以用極限判斷e)nc（可以用極限判斷在下表中對每一對表達（A,B,A是B的 戒中的哪種關(guān)系假設，a否否是是否b否否是是否c否否否否否d是是否否否e是否是否是f是否是否是,,,,,,,, 函數(shù)是周期性變換大小的。因此具有丌確定性。A、Bd： ，顯然當 時 成立f：根據(jù)增長率來對下列函數(shù)排序，即找出函數(shù)的一種排 ，將該序列劃分成等價類使和，同一個等價類中當且僅當，丌丌 a設和為漸近正函數(shù)。證明戒否定以下的假設a)，其中且對足夠大的n成立。g)h)：和某些作者定義的方式和我們略有丌同，可以用（讀作“無窮大）來表示這種定義。若存在正常數(shù)c使 對無窮多的整數(shù)n成立則說。a）說明漸近非負的兩個函數(shù)和，要么，要，要么二者都成立，然后再用代替時并丌成立請描述用代替以刻畫程序運行時間的潛在優(yōu)點和缺點某些作者定義的也略有丌同，設 。稱當且僅。如果我們 代替而仍然