程序設(shè)計(jì) = 數(shù)據(jù)結(jié)構(gòu) + 算法
基本概念和術(shù)語
- 數(shù)據(jù)：是描述客觀事物的符號少辣，是計(jì)算機(jī)中可以操作的對象耐齐，是能被計(jì)算機(jī)識別厂抽，并輸入給計(jì)算機(jī)處理的符號集合需频。如整型、實(shí)型等數(shù)值類型筷凤，還包括字符及聲音昭殉、圖像、視頻等非數(shù)值類型藐守。
- 數(shù)據(jù)元素：是組成數(shù)據(jù)的挪丢、有一定意義的基本單位，在計(jì)算機(jī)中通常作為整體處理卢厂，也被稱為記錄乾蓬。
- 數(shù)據(jù)項(xiàng)：一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)就是數(shù)據(jù)不可分割的最小單位足淆。
- 數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合巢块，是數(shù)據(jù)的子集。
- 結(jié)構(gòu)：亦指關(guān)系巧号，不同數(shù)據(jù)元素之間不是獨(dú)立的族奢，而是存在特定的關(guān)系，我們將這些關(guān)系稱為結(jié)構(gòu)丹鸿。
- 數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合越走。
邏輯結(jié)構(gòu)與物理結(jié)構(gòu)
我們把數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，邏輯結(jié)構(gòu)是面向問題的靠欢，而物理結(jié)構(gòu)就是面向計(jì)算機(jī)的廊敌，其基本目標(biāo)是將數(shù)據(jù)及其邏輯關(guān)系存儲到計(jì)算機(jī)的內(nèi)存中。
邏輯結(jié)構(gòu)：是指數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關(guān)系门怪。
邏輯結(jié)構(gòu)分為四種：
- 集合結(jié)構(gòu)：集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個(gè)集合外骡澈，他們之間沒有其他關(guān)系。
- 線性結(jié)構(gòu)：線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對一的關(guān)系掷空。
- 樹形結(jié)構(gòu)：樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一種一對多的層次關(guān)系肋殴。
- 圖形結(jié)構(gòu)：圖形結(jié)構(gòu)的數(shù)據(jù)元素是多對多的關(guān)系。
物理結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲形式坦弟。
數(shù)據(jù)元素的存儲結(jié)構(gòu)形式有兩種护锤，分別是順序存儲和鏈接存儲：
- 順序存儲結(jié)構(gòu)：是把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元里，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的（如數(shù)組）酿傍。
- 鏈?zhǔn)酱鎯Y(jié)構(gòu)：是把數(shù)據(jù)元素存放在任意的存儲單元里烙懦，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的赤炒。此時(shí)數(shù)據(jù)元素的存儲關(guān)系并不能反應(yīng)其邏輯關(guān)系氯析，因此需要用一個(gè)指針存放數(shù)據(jù)元素的地址亏较，這樣通過地址就可以找到相關(guān)聯(lián)數(shù)據(jù)元素的位置。
抽象數(shù)據(jù)類型
數(shù)據(jù)類型：是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱掩缓。
抽象：是指抽取出事物具有的普遍性的本質(zhì)宴杀。
抽象數(shù)據(jù)類型（Abstract Data Type, ADT）：是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作。一個(gè)抽象數(shù)據(jù)類型定義了：一個(gè)數(shù)據(jù)對象拾因、數(shù)據(jù)對象中各數(shù)據(jù)元素之間的關(guān)系及對數(shù)據(jù)元素的操作旺罢。至于，一個(gè)數(shù)據(jù)類型到底需要哪些操作绢记，這就只能由設(shè)計(jì)者根據(jù)實(shí)際需要來定扁达。
算法的概念
算法：算法是解決特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列蠢熄，并且每條指令表示一個(gè)或多個(gè)操作跪解。
算法具有五個(gè)基本特性：
- 輸入：算法具有零個(gè)或多個(gè)輸入。
- 輸出：算法至少有一個(gè)或多個(gè)輸出签孔。
- 有窮性：指算法在執(zhí)行有限的步驟之后叉讥，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無限循環(huán)，并且每一個(gè)步驟在可接收的時(shí)間內(nèi)完成饥追。
- 確定性：算法的每一步都具有確定的含義图仓，不會(huì)出現(xiàn)二義性。
- 可行性：算法的每一步都必須是可行的但绕，也就是說每一步都能夠通過執(zhí)行有限次數(shù)完成救崔。
算法設(shè)計(jì)的要求：
- 正確性：指算法至少應(yīng)該具有輸入、輸出和加工處理無歧義性捏顺、能正確反映問題的需求六孵、能夠得到問題的正確答案。
- 可讀性：便于他人閱讀幅骄，讓人理解和交流劫窒。
- 健壯性：當(dāng)輸入數(shù)據(jù)不合法時(shí)，算法也能做出相關(guān)處理拆座，而不是產(chǎn)生異持魑。或莫名其妙的結(jié)果。
- 時(shí)間效率高和存儲量低
算法的 正確 分為四個(gè)層次：
- 沒有語法錯(cuò)誤
- 對于合法的輸入數(shù)據(jù)能夠產(chǎn)生滿足要求的輸出結(jié)果
- 對于非法的輸入數(shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果
- 對于靜心選擇的懂拾，甚至刁難的測試數(shù)據(jù)都有滿足要求的輸出結(jié)果
我們把層次 3 作為一個(gè)算法是否正確的標(biāo)準(zhǔn)煤禽。
函數(shù)的漸進(jìn)增長
函數(shù)的漸進(jìn)增長：給定兩個(gè)函數(shù) f(n) 和 g(n)铐达，如果存在一個(gè)整數(shù) N岖赋，使得對于所有的 n > N，f(n) 總是比 g(n) 大瓮孙，那么唐断，我們說 f(n) 的增長漸進(jìn)快于 g(n)选脊。
通過分析函數(shù)的漸進(jìn)增長，我們有如下推論：
- 與最高次項(xiàng)相乘的常數(shù)不重要
- 最高次項(xiàng)的指數(shù)對于函數(shù)的增長影響最大
- 推斷一個(gè)算法的效率時(shí)脸甘，更應(yīng)該關(guān)注最高階項(xiàng)的階數(shù)
算法的時(shí)間復(fù)雜度
在進(jìn)行算法分析時(shí)恳啥，語句總的執(zhí)行次數(shù) T(n) 是關(guān)于問題規(guī)模 n 的函數(shù)，進(jìn)而分析 T(n) 隨 n 變化情況并確定 T(n) 的數(shù)量級丹诀。算法的時(shí)間復(fù)雜度钝的，也就是算法的時(shí)間度量，記作：T(n) = O(f(n))铆遭。它表示隨問題規(guī)模 n 的增大硝桩，算法執(zhí)行時(shí)間的增長率和 f(n) 的增長率相同，稱作算法的漸進(jìn)時(shí)間復(fù)雜度枚荣，簡稱為時(shí)間復(fù)雜度碗脊。其中 f(n) 是問題規(guī)模 n 的某個(gè)函數(shù)。
這樣用大寫 O()來體現(xiàn)算法時(shí)間復(fù)雜度的記法橄妆，我們稱之為大O記法衙伶。隨著 n 的增大，T(n) 增長最慢的算法為最優(yōu)算法害碾。
推到大 O 階方法
- 用常數(shù) 1 取代運(yùn)行時(shí)間中的所有加法常數(shù)
- 在修改后的運(yùn)行次數(shù)函數(shù)中矢劲，只保留最高階項(xiàng)
- 如果最高階項(xiàng)存在且不是 1，則去除與這個(gè)項(xiàng)相乘的常數(shù)
得到的結(jié)果就是大 O 階慌随。
常見的時(shí)間復(fù)雜度：
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2?) < O(n!) < O(n?)
除非特別指定卧须，我們提到的運(yùn)行時(shí)間都是最壞情況的運(yùn)行時(shí)間。
算法的空間復(fù)雜度
算法的空間復(fù)雜度是通過計(jì)算算法所需的存儲空間實(shí)現(xiàn)儒陨，記作：S(n) = O(f(n))花嘶，其中，n 為問題的規(guī)模蹦漠，f(n) 為語句關(guān)于 n 所占存儲空間的函數(shù)椭员。
若算法執(zhí)行時(shí)間所需要的輔助空間相對于輸入數(shù)據(jù)量而言是個(gè)常數(shù)，則稱此算法為原地工作笛园，空間復(fù)雜度為 O(1)隘击。
對于算法的復(fù)雜度，一般是指時(shí)間復(fù)雜度研铆。
