1? 算法概念

?????軟件 的 最終 成果 都是 以 程序 的 形式 表現(xiàn) 的癣疟， 數(shù)據(jù) 結(jié)構(gòu) 的 各種 操作 都是 以 算法 的 形式 描述 的挣柬。 數(shù)據(jù) 結(jié)構(gòu)、 算法 和 程序 是 密不可分 的睛挚。 三 者 的 關(guān)系 正如 瑞士 蘇黎世 聯(lián)邦 工業(yè) 大學(xué) 著名 計(jì)算機(jī) 科學(xué)家 沃 思（ Wirth） 提出 的 一個(gè) 公式： 數(shù)據(jù) 結(jié)構(gòu)+ 算法= 程序邪蛔。 其中， 算法 是 靈魂扎狱， 它 解決“ 做 什么” 和“ 怎么 做” 的 問題侧到。 在給 出 算法 的 概念 之前， 先 舉 兩個(gè) 例子 來說 明 什么 是 算法淤击。

?例1 　 求 1+ 2+ 3+ 4+…+ 100=匠抗？

?方法 1： 直接 相加， 得出 結(jié)果污抬。?

方法 2：= 100+（ 1+ 99）+（ 2+ 98）+…+（ 49+ 51）+ 50 　 　 　= 50* 100+ 50 　 　 　= 5050?

例2 　 求 1* 2* 3* 4* 5=汞贸？?

最 原始 的 方法： S1： 先 求 1* 2， 得 2印机。 　 　 　 　?

S2： 將 2* 3矢腻， 得 6。

S3： 將 6* 4射赛， 得 24多柑。 　 　 　?

S4： 將 24* 5= 120， 便得 到 最后 的 結(jié)果咒劲。

若 求 1* 2* 3*…* 1000=顷蟆？， 再用 此 方法 就不 可行腐魂。 因?yàn)?需要 999 個(gè) 步驟帐偎， 故要 找 一種 通用 的 方法。 可設(shè) 兩個(gè) 變量蛔屹， 一個(gè) 變量 代表 被乘數(shù)（ p）削樊， 一個(gè) 變量 代表 乘數(shù)（ i）。 S1： 使 p= 1兔毒。 S2： 使 i= 2漫贞。 S3： 使 p* i， 將 p* i= ＞ p育叁。 S4： i+ 1= ＞ i迅脐。 S5： 若 i 不大于 5， 返回 重新 執(zhí)行 S3豪嗽、 S4 和 S5谴蔑； 否則豌骏， 算法 結(jié)束。?

可見隐锭， 算法（ Algorithm） 是對(duì) 特定 問題 求解 步驟 的 一種 描述窃躲， 是 指令 的 有限 序列。 其中 每 一條 指令 表示 一個(gè) 或 多個(gè) 操作钦睡。

2? 算法的特征

算法 的 特征

一個(gè) 算法 應(yīng)該 具有 下列 特性蒂窒。

?① 有 窮 性： 一個(gè) 算法 應(yīng) 包含 有限 的 操作步驟， 而 不能 是 無限 的荞怒。?

② 確定性： 每一 步 應(yīng)是 確定 的洒琢， 而 不應(yīng) 是 含糊 的、 模棱兩可 的挣输， 即 無 二義性纬凤。

?③ 有 輸入： 有零 個(gè) 或 多個(gè) 輸入。

?④ 有 輸出： 有一個(gè) 或 多個(gè) 輸出撩嚼， 算法 的 目的 是 為了“ 解”停士， 求 結(jié)果。 所以完丽， 沒有 輸出 的 算法 是 沒有 意義 的恋技。

?⑤ 有效性（ 可行性）。 算法 中的 每一 步 都應(yīng) 能 有效地 執(zhí)行逻族， 并 得到 確定 的 結(jié)果蜻底， 如 b= 0， 則 表達(dá)式 a/ b 是 不能 有效 執(zhí)行 的聘鳞。

3? 算法 分析

? ? ? ? ? 我們常常說時(shí)間復(fù)雜度薄辅，空間復(fù)雜度，但是涉及到具體的算法分析的時(shí)候不知道怎么去計(jì)算復(fù)雜點(diǎn)的時(shí)間復(fù)雜度抠璃，下面為大家理清一下站楚，參考《數(shù)據(jù)結(jié)構(gòu)》一書

? ? ? ? ? ? ?衡量 算法 優(yōu)劣 最重要的 一點(diǎn) 是 效率 與 低 存儲(chǔ) 量 要求。 算法 效率（ 算法 運(yùn)行 的 時(shí)間） 由 時(shí)間 復(fù)雜度 來 度量搏嗡。 一般窿春， 鑒于 空間（ 內(nèi)存） 較為 充足， 故 把 算法 的 時(shí)間 復(fù)雜度 作為 分析 的 重點(diǎn)采盒。 在 求 時(shí)間 復(fù)雜度 之前旧乞， 先 介紹 頻度 統(tǒng)計(jì)法。

?????????????頻度： 一條 語句 的 頻度 是指 該 語句 被 執(zhí)行 的 次數(shù)磅氨。 而 整個(gè) 算法 的 頻度 是指 算法 中 所有 基本 語句 的 頻度 之和尺栖。

例如：求下面的語句頻度

分析： 該 算法 為 一個(gè) 二重 循環(huán)， 執(zhí)行 次數(shù) 為 內(nèi)烦租、 外 循環(huán) 次數(shù) 相乘延赌， 因此 頻度= n2（2是指數(shù)货徙，不知道怎么打出來，后面如果2在后面的話都表示指數(shù)）皮胡。

3.1??時(shí)間 復(fù)雜度

? ??????在 剛才 提到 的 算法 頻度 中， n 稱為 問題 的 規(guī)模（ 通常用 正 整數(shù) n 表示）赏迟。 當(dāng) n 不斷 變化 時(shí)屡贺， 語句 頻度 也會(huì) 不斷 變化。 但 有時(shí) 我們 想知道 它 變化 時(shí) 呈現(xiàn) 什么 規(guī)律锌杀。 為此甩栈， 我們 引入 時(shí)間 復(fù)雜度 概念。 或者說 時(shí)間 復(fù)雜度 是 問題 規(guī)模 的 函數(shù)糕再。 但 算法 的 時(shí)間 復(fù)雜度 考慮 的 只是 對(duì) 問題 規(guī)模 n 的 增長率量没， 難以 精確 計(jì)算 出 語句 頻度， 只需 求出 它 關(guān)于 n 的 增長率 或 階（ 數(shù)量級(jí)） 即可突想。

? ??????一般 情況下殴蹄， 算法 中 基本 操作 重復(fù) 執(zhí)行 的 次數(shù) 是 問題 規(guī)模 n 的 某個(gè) 函數(shù) f（ n）， 記作 T（ n）= O（ f（ n））猾担。

其中袭灯， T（ n） 表示 時(shí)間 復(fù)雜度， 大寫字母 O 為 英文 Order（ 即 數(shù)量級(jí)） 單詞 的 第一個(gè) 字母绑嘹。

例如稽荧，

語句 x= x+ 1 執(zhí)行 次數(shù) 關(guān)于 n 的 增長率 為 n2， 故 它的 時(shí)間 復(fù)雜度 T（ n）= O（ n2）工腋。

可能這個(gè)比較簡單姨丈，下面看看復(fù)雜點(diǎn)的時(shí)間復(fù)雜度

求出 下列 算法 段 的 時(shí)間 復(fù)雜度。

分析可知：（1）? ? T（ n）= O（1） 常數(shù)級(jí)

(2)? ?T(n) = O(n)

第三段代碼（3）? ①的頻度是n-1(因?yàn)閗<n,沒有等于)? ? ? ②的頻度是T（n） = （n-1）* (2n +1) =?2n2- n- 1? ?則 該 程序 段 的 時(shí)間 復(fù)雜度 T（ n）= n- 1+ 2n2- n- 1= O（ n2）擅腰。

第 4 段 代碼 是 三層 for 循環(huán)蟋恬， 故 時(shí)間 復(fù)雜度 為 O（ n3）。

第 5 段 代碼 中的 語句 ① 的 頻度 是 1惕鼓， 語句 ② 的 頻度 設(shè)為 f（ n）筋现， 則有 2 f（ n） ≤ n， 即 f（ n） ≤ log2n箱歧， 取 最大值 f（ n）= log2n矾飞。 故 該 程序 段 的 時(shí)間 復(fù)雜度 T（ n）= 1+ log2n= O（ log2n）。很多人可能不理解2 f（ n） ≤ n是怎么得來的呀邢，大家可以把n設(shè)置為10洒沦，帶入去計(jì)算一下，你會(huì)發(fā)現(xiàn)?2 f（ n） ≤ n? 總會(huì)成立价淌。

總結(jié)： 在各 種 不同 算法 中申眼， 若 程序 的 運(yùn)行 時(shí)間 不隨 著 問題 規(guī)模 n 的 增加 而 增長瞒津， 即使 算法 中有 上千 條 語句， 其 執(zhí)行 時(shí)間 也不 過 是一 個(gè) 較大 的 常數(shù)括尸， 此類 算法 的 時(shí)間 復(fù)雜度 仍是 O（ 1）巷蚪。 另外， 在 頻度 不相 同時(shí)濒翻， 時(shí)間 復(fù)雜度 有可能 相同屁柏， 如 T（ n）= n2+ 3n+ 4 與 T（ n）= 4n2+ 2n+ 1 的 頻度 不同， 但 時(shí)間 復(fù)雜度 相同有送， 都為 O（ n2）淌喻。 按 數(shù)量級(jí) 遞增 排列， 常見 的 時(shí)間 復(fù)雜度 有 常數(shù) 階 O（ 1）雀摘、 對(duì)數(shù) 階 O（ log2n）裸删、 線性 階 O（ n）、 線性 對(duì)數(shù) 階 O（ nlog2n）阵赠、 平方 階 O（ n2）涯塔、 立方 階 O（ n3）… k 次方 階 O（ nk）、 指數(shù) 階 O（ 2n）清蚀。 隨著 問題 規(guī)模 n 的 不斷 增大伤塌， 上述 時(shí)間 復(fù)雜度 不斷 增大， 算法 的 執(zhí)行 效率 降低轧铁。

3.2 空間復(fù)雜度

????????????一個(gè) 程序 需要 的 空間 即 存儲(chǔ) 量每聪， 包括 輸入 數(shù)據(jù) 所占 空間、 程序 本身 所占 空間 和 輔助 變量 所占 空間齿风。 我們 一般 是 討論 算法 占用 的 輔助 存儲(chǔ) 空間药薯， 即 空間 復(fù)雜度 是對(duì) 一個(gè) 算法 在 運(yùn)行 過程中 臨時(shí) 占用 的 存儲(chǔ) 空間 大小 的 量度。 一般 也作 為 問題 規(guī)模 n 的 函數(shù)救斑， 以 數(shù)量級(jí) 形式 給出童本， 記作： S（ n）= O（ g（ n））