【正文】 ?⑸ 是賦值語(yǔ)句 ， 與問(wèn)題規(guī)模無(wú)關(guān) ， 時(shí)間復(fù)雜度為常數(shù)階O(1)， 即 T5(n)=O(1)； ?對(duì)于第 ⑷ 條語(yǔ)句 ， T4(n)=O(n)， 它與第 ⑸ 條語(yǔ)句是循環(huán)關(guān)系應(yīng)該用乘法準(zhǔn)則 ， 即 T4(n)*T5(n)=O(1*n)=O(n)； ?對(duì)于第 ⑶ 條語(yǔ)句 T3(n)=O(1)， 它與第 ⑷ 、 ⑸ 是順序結(jié)構(gòu)應(yīng)該用求和準(zhǔn)則 ， 即 T3(n)+T4(n)* T5(n)=O(max(1,n))=O(n)； ?第 ⑵ 條語(yǔ)句其 T2(n)=O(n)， ⑶ 到 ⑸ 是它的循環(huán)體適用乘法準(zhǔn)則 ， 故有 T2(n)*(T3(n)+T4(n)*T5(n))=O(n*n)=O(n2)； ?第 ⑴ 條語(yǔ)句的耗時(shí) T1(n)=O(n)， ⑵ 到 ⑸ 是它的循環(huán)體適用乘法準(zhǔn)則 ， 所以有 T1(n)*(T2(n)*(T3(n)+T4(n)*T5(n)))=O(n* n2)=O(n3)。 ?實(shí)際上 ， 算法或程序的執(zhí)行時(shí)間不僅依賴于所求解問(wèn)題的規(guī)模 ， 還與它所處理的數(shù)據(jù)的狀態(tài)有關(guān) 。 空間復(fù)雜度 ?衡量一個(gè)算法優(yōu)劣的另一個(gè)因素是空間代價(jià) ， 即執(zhí)行由算法轉(zhuǎn)化的程序時(shí)所占用存儲(chǔ)空間的大小 。 ? 算法或程序中的輸入和輸出數(shù)據(jù)所占用的存儲(chǔ)空間 。 這部分空間是與算法本身密切相關(guān)的 ， 因算法設(shè)計(jì)的不同而異 ，是我們討論算法的空間代價(jià)時(shí)所要著重討論的方面 。 空間復(fù)雜度和時(shí)間復(fù)雜度一樣 ，也是用相對(duì)于問(wèn)題規(guī)模函數(shù)的漸近階形式給出 ， 如 O(1)、 O(n)等 。 算法的設(shè)計(jì)與評(píng)價(jià) 評(píng)價(jià)算法的標(biāo)準(zhǔn) 算法的環(huán)路復(fù)雜度 算法的時(shí)空效率 常見(jiàn)的算法設(shè)計(jì)方法 常見(jiàn)的算法設(shè)計(jì)方法 ?為了獲得有效的算法 ， 必須了解一些解題的基本思想和方法 。 然而 ， 作為探尋問(wèn)題求解思路的基本思想和方法 ， 對(duì)于任何算法設(shè)計(jì)都是有用的 。 它的 基本思想 是： ?首先根據(jù)求解問(wèn)題的部分條件確定答案的大致范圍 ， 即列舉出解的所有可能的情況； ?然后在此范圍內(nèi)對(duì)所有可能的情況逐一驗(yàn)證 ， 若某個(gè)情況經(jīng)過(guò)驗(yàn)證符合問(wèn)題條件則為一個(gè)解 ， 若全部情況驗(yàn)證后均不符合題目條件則問(wèn)題無(wú)解 ， 從而得出求解問(wèn)題的完整解 。 ?窮舉法的 特點(diǎn) 是算法簡(jiǎn)單 ， 但有時(shí)運(yùn)算量大效率較低 。 ?迭代法的 基本思想 是 ， 由一個(gè)量的原值求出它的新值 ， 不斷地再用新值替代原值求出它的下一個(gè)新值 ，直到得到滿意的解 。 ?迭代法主要用于那些很難用或無(wú)法用解析法求解的一類計(jì)算問(wèn)題 ， 如高次方程和超越方程等；使得復(fù)雜問(wèn)題的求解過(guò)程 ， 轉(zhuǎn)化為相對(duì)較簡(jiǎn)單的迭代算式的重復(fù)執(zhí)行過(guò)程 ， 用數(shù)值方法求出問(wèn)題的近似解 。 ?這種迭代方法稱作 逼近迭代 ， 如著名的牛頓迭代法就是這種逼近迭代方法 。 例如計(jì)算s=1+2+3+… +1000， 可選取迭代公式 s+i→s 和迭代初值0（ 即 0→s ） 。 ?遞推過(guò)程往往表現(xiàn)為迭代 ， 即由一些量的原值推出它的新值 ， 不斷地用新值替代原值推出下一個(gè)新值 ，直到推出最終結(jié)果 ， 新值與原值之間的關(guān)系用遞推公式表示 。 如 Fibonacci數(shù)列的通項(xiàng)公式為 ?顯而易見(jiàn) ， 找出這個(gè)通項(xiàng)公式不易 ， 利用它計(jì)算 F(n)也相當(dāng)費(fèi)力 。 ?如果一個(gè)過(guò)程 直接 或 間接 地調(diào)用它自身 ， 則稱該過(guò)程是 遞歸 的；直接調(diào)用自身稱作 直接遞歸 ， 間接調(diào)用自身則稱作 間接遞歸 。 這個(gè)最簡(jiǎn)單的問(wèn)題即為遞歸終止條件 ， 也稱作遞歸出口 。 遞歸法和遞推法比較 ?遞歸和遞推是既有區(qū)別又有聯(lián)系的兩個(gè)概念 。 ?一般地說(shuō) ， 一個(gè)遞推算法總可以轉(zhuǎn)換為一個(gè)遞歸算法 。 遞歸法和遞推法比較（續(xù)） ?然而 ， 利用遞歸方法分析和設(shè)計(jì)算法可使難度大幅度降低 ， 且程序設(shè)計(jì)語(yǔ)言中一般都提供遞歸機(jī)制；利用遞歸過(guò)程描述問(wèn)題求解算法不僅非常自然 ， 而且算法的正確性證明要比相應(yīng)的非遞歸算法容易得多；另外有成熟的方法和技術(shù) ， 可以很方便地把遞歸算法改寫(xiě)為非遞歸算法 。 ?回溯法是算法設(shè)計(jì)中的一種基本策略 ， 它通過(guò)對(duì)問(wèn)題的分析找出一個(gè)解決問(wèn)題的線索 ， 然后沿這個(gè)線索逐步試探 。 ?在那些涉及到尋找一組解的問(wèn)題或者滿足某些約束條件的最優(yōu)解的問(wèn)題中 ， 許多都可以用回溯法來(lái)求解 。 ?貪婪法也稱作貪心算法 ， 它是通過(guò)一系列的選擇來(lái)得到問(wèn)題的一個(gè)解 。 ?換句話說(shuō) ， 貪婪法并不從整體最優(yōu)上加以考慮 ， 它做出的選擇只是在某種意義上的局部最優(yōu)選擇 ， 但希望算法得到的最終結(jié)果也是整體最優(yōu)的 。 ?在一些情況下 ， 即使貪婪算法不能得到整體最優(yōu)解 ， 其最終結(jié)果卻是最優(yōu)解的很好近似 。 ?使用分治法時(shí) ， 往往要按問(wèn)題的輸入規(guī)模來(lái)衡量問(wèn)題的大??；當(dāng)要求解問(wèn)題的輸入規(guī)模相當(dāng)大時(shí) ， 應(yīng)選擇適當(dāng)策略將輸入劃分成若干子集合得到一組子問(wèn)題 ， 在求出各子問(wèn)題的解之后用適當(dāng)?shù)姆椒ò阉鼈兒喜⒊烧麄€(gè)問(wèn)題的解 ， 分治法便應(yīng)用成功了 。 第 1章 算法與程序 算法的基本概念 算法的表示 算法的設(shè)計(jì)與評(píng)價(jià) 算法與程序 算法與程序 ?算法與程序是密切相關(guān)的兩個(gè)概念 。 算法與程序 程序的基本概念 問(wèn)題求解與實(shí)現(xiàn)策略 程序調(diào)試與查錯(cuò)策略 程序設(shè)計(jì)方法概述 程序的基本概念 ?在低級(jí)語(yǔ)言中 ， 程序表現(xiàn)為一組指令和有關(guān)數(shù)據(jù)； ?在高級(jí)語(yǔ)言中 ， 程序表現(xiàn)為一組說(shuō)明和語(yǔ)句 。 ?衡量一個(gè)程序的質(zhì)量 ， 除了對(duì)程序結(jié)構(gòu)進(jìn)行靜態(tài)考察外 ， 還必須考察其執(zhí)行過(guò)程 。 程序的特征 ?程序描述解決某一問(wèn)題的特定任務(wù)與功能 ， 回答“ 解決什么問(wèn)題 ” 或 “ 做什么 ” 的問(wèn)題 。 ?程序的執(zhí)行者是計(jì)算機(jī) 。 ?程序的運(yùn)行是自動(dòng)完成的 。 算法與程序 程序的基本概念 問(wèn)題求解與實(shí)現(xiàn)策略 程序調(diào)試與查錯(cuò)策略 程序設(shè)計(jì)方法概述 解決一個(gè)實(shí)際問(wèn)題的一般過(guò)程 ?明確問(wèn)題要求 。 ?算法設(shè)計(jì) 。 ?調(diào)試程序 。 ?編寫(xiě)程序文檔 。 沒(méi)有文檔資料對(duì)于軟件的維護(hù)會(huì)帶來(lái)許多困難 ， 即使是設(shè)計(jì)者自己也不例外 。 實(shí)現(xiàn)策略 ?在拿到一個(gè)設(shè)計(jì)問(wèn)題之后 ， 有兩種不同的方法可供選擇： ?一種是自頂向下逐步求精細(xì)化； ?一種是自底向上逐步堆砌積累 。 ?結(jié)構(gòu)化程序設(shè)計(jì)提倡自頂向下逐步求精細(xì)化的分析設(shè)計(jì)方法 ， 從求解問(wèn)題本身到得出一系列基本操作逐層次展開(kāi)細(xì)化 ， 是一種將問(wèn)題求解方法由抽象逐步到具體化的過(guò)程 。 算法與程序 程序的基本概念 問(wèn)題求解與實(shí)現(xiàn)策略 程序調(diào)試與查錯(cuò)策略 程序設(shè)計(jì)方法概述 程序調(diào)試 ?程序調(diào)試 是開(kāi)發(fā)過(guò)程中最艱巨的腦力勞動(dòng) 。 ?現(xiàn)有的調(diào)試技術(shù)有如下三類： ?輸出存儲(chǔ)器內(nèi)容 。 ?在程序中插入打印語(yǔ)句 ， 調(diào)試結(jié)束后要將為了調(diào)試而插入的語(yǔ)句刪掉 。 調(diào)試工具可以提供程序動(dòng)態(tài)行為的有關(guān)信息 ， 但不需要修改源程序 。 調(diào)試策略 ?試探法 ?回溯法 ?對(duì)分查找法 ?歸納法 。 ?演繹法 。 查錯(cuò)策略 ?查錯(cuò)策略主要有兩種： 黑盒子測(cè)試 和 白盒子測(cè)試 ?如果 已知 產(chǎn)品的 功能 ， 可以測(cè)試它的每一個(gè)功能是否都達(dá)到了預(yù)期的要求 ， 這種方法叫 黑盒子測(cè)試 。 ?無(wú)論使用哪一種方法 ， 對(duì)程序的 窮舉測(cè)試 是不可能的 ， 我們所能做到的是通過(guò)有限的測(cè)試盡可能多地發(fā)現(xiàn)錯(cuò)誤 。 查錯(cuò)的 關(guān)鍵在于設(shè)計(jì)好測(cè)試用例 ， 即確定一組最有可能發(fā)現(xiàn)某個(gè)或某類錯(cuò)誤的測(cè)試數(shù)據(jù)的設(shè)計(jì) 。 它是一種白盒子測(cè)試技術(shù) 。 ?等價(jià)類劃分 。 ?邊界值分析 。 ?圖形技術(shù) 。 ?測(cè)試的目的是為了發(fā)現(xiàn)錯(cuò)誤 ， 而糾錯(cuò)則是確定錯(cuò)誤在程序中的確切位置和性質(zhì)并改正它 。 算法與程序 程序的基本概念 問(wèn)題求解與實(shí)現(xiàn)策略 程序調(diào)試與查錯(cuò)策略 程序設(shè)計(jì)方法概述 程序設(shè)計(jì)方法概述 ?程序是軟件的重要組成部分 ， 程序設(shè)計(jì)是軟件開(kāi)發(fā)的重要方面 。 ?程序設(shè)計(jì)方法學(xué)主要研究涉及用于指導(dǎo)程序設(shè)計(jì)工作的原理和原則 ， 研究基于這些原理和原則的具體設(shè)計(jì)方法和技術(shù) ， 研究各種方法的共性和理論基礎(chǔ) 。 如結(jié)構(gòu)化程序設(shè)計(jì)方法 ， 它不僅要求編出的程序結(jié)構(gòu)良好 ， 而且要求程序設(shè)計(jì)過(guò)程是結(jié)構(gòu)化 、 層次式 、 逐層降低抽象級(jí)別的 。 如子例程方法 、 協(xié)同例程方法