計算機算法設(shè)計與分析(第4版)[王曉東][電子教案]第1章(已修改)
2025-08-21 15:33 本頁面
【正文】 計算機算法設(shè)計與分析（第 4版） 王曉東 編著 電子工業(yè)出版社 第 1章 算法概述 學(xué)習要點 : ? 理解算法的概念。 ? 理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系。 ? 掌握算法的計算復(fù)雜性概念。 ? 掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。 ? 掌握用 C++語言描述算法的方法。 算法 (Algorithm) ? 算法是指解決問題的一種方法或一個過程。 ? 算法是若干指令的有窮序列，滿足性質(zhì)： ? (1)輸入 ：有外部提供的量作為算法的輸入。 ? (2)輸出 ：算法產(chǎn)生至少一個量作為輸出。 ? (3)確定性 ：組成算法的每條指令是清晰，無歧義的。 ? (4)有限性 ：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時間也是有限的。 程序 (Program) ? 程序是算法用某種程序設(shè)計語言的具體實現(xiàn)。 ? 程序可以不滿足算法的性質(zhì) (4)。 ? 例如操作系統(tǒng)，是一個在無限循環(huán)中執(zhí)行的程序，因而不是一個算法。 ? 操作系統(tǒng)的各種任務(wù)可看成是單獨的問題，每一個問題由操作系統(tǒng)中的一個子程序通過特定的算法來實現(xiàn)。該子程序得到輸出結(jié)果后便終止。 問題求解 (Problem Solving) 證明正確性 分析算法 設(shè)計程序 理解問題 精確解或近似解 選擇數(shù)據(jù)結(jié)構(gòu) 算法設(shè)計策略 設(shè)計算法 算法復(fù)雜性分析 ? 算法復(fù)雜性 = 算法所需要的計算機資源 ? 算法的時間復(fù)雜性 T(n)； ? 算法的空間復(fù)雜性 S(n)。 ? 其中 n是問題的規(guī)模（輸入大?。? 算法的時間復(fù)雜性 ? （ 1） 最壞情況 下的時間復(fù)雜性 ? Tmax(n) = max{ T(I) | size(I)=n } ? （ 2） 最好情況 下的時間復(fù)雜性 ? Tmin(n) = min{ T(I) | size(I)=n } ? （ 3） 平均情況 下的時間復(fù)雜性 ? Tavg(n) = ? 其中 I是問題的規(guī)模為 n的實例， p(I)是實 例 I出現(xiàn)的概率。 ? ? nIsize ITIp)( )()(算法漸近復(fù)雜性 ? T(n) ?? , as n?? 。 ? (T(n) t(n) )/ T(n) ?0 ， as n??。 ? t(n)是 T(n)的漸近性態(tài)，為算法的漸近復(fù)雜性。 ? 在數(shù)學(xué)上， t(n)是 T(n)的漸近表達式，是 T(n)略去低階項留下的主項。它比 T(n) 簡單。 漸近分析的記號 ? 在下面的討論中，對所有 n， f(n) ? 0， g(n) ? 0。 ? （ 1） 漸近上界記號 O ? O(g(n)) = { f(n) | 存在正常數(shù) c和 n0使得對所有 n? n0有：0 ? f(n) ? cg(n) } ? （ 2） 漸近下界記號 ? ? ? (g(n)) = { f(n) | 存在正常數(shù) c和 n0使得對所有 n? n0有：0? cg(n) ? f(n) } ? （ 3） 非緊上界記號 o ? o(g(n)) = { f(n) | 對于任何正常數(shù) c0， 存在正數(shù)和 n0 0使得對所有 n? n0有： 0 ? f(n)cg(n) } ? 等價于 f(n) / g(n) ?0 ， as n??。 ? （ 4） 非緊下界記號 ? ? ? (g(n)) = { f(n) | 對于任何正常數(shù) c0， 存在正數(shù)和 n0 0使得對所有 n? n0有： 0 ? cg(n) f(n) } ? 等價于 f(n) / g(n) ?? ， as n??。 ? f(n) ? ? (g(n)) ? g(n) ? o (f(n)) ? （ 5） 緊漸近界記號 ? ? ? (g(n)) = { f(n) | 存在正常數(shù) c1,c2和 n0使得對所有 n? n0有： c1g(n) ? f(n) ? c2g(n) } ? 定理 1： ? (g(n)) = O (g(n)) ? ? (g(n)) 漸近分析記號在等式和不等式中的意義 ? f(n)= ?(g(n))的確切意義是： f(n) ? ?(g(n))。 ? 一般情況下，等式和不等式中的漸近記號 ?(g(n))表示?(g(n))中的某個函數(shù)。 ? 例如： 2n2 + 3n + 1 = 2n2 + ?(n) 表示 ? 2n2 +3n +1=2n2 + f(n)，其中
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1