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））
