數(shù)據(jù)結(jié)構(gòu)與算法c(4)(已修改)
2024-10-30 15:42 本頁(yè)面
【正文】 第二章 程序設(shè)計(jì)基本策略與方法 遞歸、逐步求精、分治是基本的算法（程序）設(shè)計(jì)策略與方法。許多復(fù)雜問(wèn)題，使用它們都可迎刃而解。這幾種策略與方法在后面要經(jīng)常使用，這里先介紹它們的基本思想，進(jìn)一步的例子將在后面的章節(jié)中見(jiàn)到。做為基礎(chǔ)，我們先介紹算法的概念 算法的基本概念 一、算法的概念 ? 一個(gè) 算法 是規(guī)則的有窮序列，它為解決某一特定類型的問(wèn)題規(guī)定了一個(gè)運(yùn)算過(guò)程，并且具有下列特性： ? 有窮性：一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束。 ? 確定性：算法的每一步必須是確切定義的，對(duì)于每種情況，有待執(zhí)行的每種動(dòng)作必須嚴(yán)格地和清楚地規(guī)定。 ? 可行性：算法應(yīng)該是可行的，這意味著算法中所有有待實(shí)現(xiàn)的運(yùn)算都是基本的，即它們都可由相應(yīng)的基本計(jì)算裝置所理解，并可通過(guò)有窮次運(yùn)算即可完成。 ? 輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，它們是在算法所需的初始量或被加工的對(duì)象的表示。這些輸入取自特寫(xiě)的對(duì)象集合。 ? 輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，它們是與輸入有特定關(guān)系的量 二 、什么是“好”的算法 通常，從下列幾個(gè)方面衡量算法的優(yōu)劣： ? 正確性 。也稱有效性，是指算法能滿足具體問(wèn)題的要求。亦即對(duì)任何合法的輸入，算法都會(huì)得出正確的結(jié)果。 可讀性 。指算法被理解的難易程度。人們現(xiàn)在常把算法的可讀性放在比較重要的位置，主要是因?yàn)榛逎y懂的算法不易交流、推廣使用，也難以修改、擴(kuò)展與調(diào)試，而且可能隱藏較多的錯(cuò)誤?？勺x性實(shí)質(zhì)上強(qiáng)調(diào)的是：越簡(jiǎn)單的東西越美。 ? 健壯性（魯棒性） 。是指對(duì)非法輸入的抵抗能力。它強(qiáng)調(diào)的是，如果輸入非法數(shù)據(jù)，算法應(yīng)能加以識(shí)別并做出處理，而不是產(chǎn)生誤動(dòng)作或陷入癱瘓。 ? 時(shí)間復(fù)雜度與空間復(fù)雜度 。時(shí)間復(fù)雜度是指算法的運(yùn)行的時(shí)間消耗，同一個(gè)問(wèn)題，不同的算法可能有不同的時(shí)間復(fù)雜度。 算法時(shí)間復(fù)雜度與空間復(fù)雜度 ? 簡(jiǎn)單地講，算法的時(shí)間復(fù)雜度是指算法的運(yùn)行的時(shí)間消耗的大小，但這里的“運(yùn)行”，是指抽象的運(yùn)行，并不是指在具體機(jī)上的運(yùn)行。一個(gè)算法在具體計(jì)算機(jī)上的運(yùn)行速度，不僅取決于算法本身，而且與目標(biāo)計(jì)算機(jī)（運(yùn)行算法的計(jì)算機(jī)）的速度有關(guān)，如果算法是用非目標(biāo)指令（如匯編語(yǔ)言、高級(jí)語(yǔ)言等）描述的，則運(yùn)行速度還與描述語(yǔ)言的編譯器所生成的目標(biāo)代碼的質(zhì)量（或解釋器本身的質(zhì)量）有關(guān)。 ? 算法的時(shí)間復(fù)雜度指算法自身的抽象運(yùn)行的時(shí)間消耗，與運(yùn)行算法的目標(biāo)計(jì)算機(jī)及描述算法的工具無(wú)關(guān) 一 、相關(guān)因素 算法的時(shí)間復(fù)雜度與下列因素有關(guān)： ? 問(wèn)題性質(zhì)：有的問(wèn)題比較復(fù)雜，而有的比較簡(jiǎn)單； ? 問(wèn)題規(guī)模：同一問(wèn)題，同一算法，其處理的對(duì)象的規(guī)模不同，則耗時(shí)也不同； ? 算法性質(zhì)：同一問(wèn)題，不同的解決方法，效率也不同。 一個(gè)算法的時(shí)間復(fù)雜度通常用函數(shù)描述（時(shí)間復(fù)雜度函數(shù)）。時(shí)間復(fù)雜度函數(shù)通?？梢悦枋鰹檩斎胍?guī)模的函數(shù)。輸入規(guī)?？梢允禽斎肓炕蜉敵隽?，或兩者之和，也可以是某種測(cè)度（如數(shù)組維數(shù)、圖的邊數(shù)等），它可用一個(gè)或多個(gè)量代表 下面舉一個(gè)簡(jiǎn)單的例子。 [例 ] 考慮計(jì)算三次多項(xiàng)式 ax3 + bx2 + cx + d 一種直接的計(jì)算方法是： s=a*x*x*x + b*x*x + c*x + d。 該算法共執(zhí)行 6次乘法， 3次加法。 考察另一種解法： s=a。 s=s*x+b。 s=s*x+c。 s=s*x+d。 該算法共進(jìn)行 3次乘法， 3次加法。顯然該算法的計(jì)算量少于前一種方法，盡管其看上去較復(fù)雜。第二種算法基于的原理是逐步提取共因子： a*x*x*x + b*x*x + c*x + d = (ax+b)x2 + cx + d =((ax+b)x + c)x + d 二、復(fù)雜度的漸近表示 常用的上界函數(shù)有 log(n), nm, an, n! 下面給出幾種常見(jiàn)的函數(shù)的比較關(guān)系：即當(dāng) n充分大時(shí)，下列關(guān)系成立： O(a) O(log n) O(n) O( n) O(n2) ... O(nm) O(an) O(n!) O(nn) 這里， n為自變量， a和 m為常數(shù) 定理 21 若 A(n) = amnm + … +a1n + a0 是關(guān)于 n的一個(gè) m次多項(xiàng)式，則 A(n)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1