數(shù)據(jù)結(jié)構(gòu)與算法 筆記
數(shù)據(jù)
- 描述客觀事物的符號(hào)宦言，是計(jì)算機(jī)中可以操作的對(duì)象，是能被計(jì)算機(jī)識(shí)別商模，并輸入給計(jì)算處理的符號(hào)集合奠旺。
- 可以輸入到計(jì)算機(jī)中
- 能被計(jì)算機(jī)程序處理
數(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ù)對(duì)象
- 是性質(zhì)相同的數(shù)據(jù)元素的集合稽寒，是數(shù)據(jù)的子集。
數(shù)據(jù)結(jié)構(gòu)
- 是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合趟章。
邏輯結(jié)構(gòu)與物理結(jié)構(gòu)
邏輯結(jié)構(gòu)
- 是指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的相互關(guān)系杏糙。?分為以下四種
集合結(jié)構(gòu)： 集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個(gè)集合外，它們之間沒(méi)有其他關(guān)系蚓土。
線性結(jié)構(gòu)： 線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對(duì)一的關(guān)系
樹形結(jié)構(gòu)： 樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一種一對(duì)多的層次關(guān)系
圖形結(jié)構(gòu)： 圖形結(jié)構(gòu)的數(shù)據(jù)元素是多對(duì)多的關(guān)系
物理結(jié)構(gòu)(存儲(chǔ)結(jié)構(gòu))
- 是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式
- 數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)形式有兩種：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)
- 順序存儲(chǔ)結(jié)構(gòu)： 是把數(shù)據(jù)元素存放在地址連續(xù)的存儲(chǔ)單元里宏侍，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的
- 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：是把數(shù)據(jù)元素存放在任意的存儲(chǔ)單元里，這組存儲(chǔ)單元可以是連續(xù)的蜀漆，也可以是不連續(xù)的谅河。
抽象數(shù)據(jù)類型
數(shù)據(jù)類型: 是指一組性質(zhì)相同的 值 的 集合 及在此集合上的一些操作的總稱。
抽象：是指抽取事物具有的普遍性的本質(zhì)。
抽象數(shù)據(jù)類型: 是指一個(gè) 數(shù)學(xué)模型 及定義在該模型上的 一組操作绷耍。
抽象的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性
抽象數(shù)據(jù)類型提現(xiàn)了程序設(shè)計(jì)中問(wèn)題分解吐限、抽象和信息隱藏的特性。
算法
算法是解決特定問(wèn)題求解步驟的描述褂始，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列诸典，并且每條指令表示一個(gè)或多個(gè)操作
算法的特性
- 輸入輸出: 算法具有零個(gè)或多個(gè)輸入；算法至少有一個(gè)或多個(gè)輸出
- 有窮性: 指算法在執(zhí)行有限的步驟之后崎苗，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無(wú)限循環(huán)狐粱，并且每一個(gè)步驟在可接受的時(shí)間內(nèi)完成。
- 確定性: 算法的每一步驟都具有確定的含義胆数，不會(huì)出現(xiàn)二義性肌蜻。
- 可行性: 算法的每一步都必須是可行的，也就是說(shuō)必尼，每一步都能夠通過(guò)執(zhí)行有限次數(shù)完成宋欺。
算法設(shè)計(jì)的要求
-
正確性: 算法的正確性是指算法至少應(yīng)該具有輸入、輸出和加工處理無(wú)歧義性胰伍、能正確反映問(wèn)題的需求齿诞、能夠得到問(wèn)題的正確答案。 分為以下四個(gè)層次
- 算法程序沒(méi)有語(yǔ)法錯(cuò)誤 層次1
- 算法程序?qū)τ诤戏ㄝ斎霐?shù)據(jù)能夠產(chǎn)生滿足要求的輸出結(jié)果骂租。層次2
- 算法程序?qū)τ诜欠ǖ妮斎霐?shù)據(jù)能夠得出滿足規(guī)格說(shuō)明的結(jié)果 層次3（標(biāo)準(zhǔn)）
- 算法程序?qū)τ诰倪x擇的祷杈，甚至刁難的測(cè)試數(shù)據(jù)都有滿足要求的輸出結(jié)果。 層次4
可讀性：算法設(shè)計(jì)的另一目的是為了便于閱讀渗饮、理解和交流 （重要標(biāo)志）
健壯性?: 當(dāng)輸入數(shù)據(jù)不合法時(shí)但汞，算法也能做出相關(guān)處理，而不是產(chǎn)生異郴フ荆或莫名其妙的結(jié)果
時(shí)間效率高和存儲(chǔ)量低: 設(shè)計(jì)算法應(yīng)該滿足時(shí)間效率高和存儲(chǔ)量低的需求
算法效率的度量方法
- 事后統(tǒng)計(jì)方法: 這種方法主要是通過(guò)設(shè)計(jì)好的測(cè)試程序和數(shù)據(jù)私蕾，利用計(jì)算機(jī)計(jì)時(shí)器對(duì)不同算法編制的程序的運(yùn)行時(shí)間進(jìn)行比較，從而確定算法效率的高低 (有很大缺陷)
- 事前分析估算方法: 在計(jì)算機(jī)程序編制前胡桃，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算踩叭。
-
高級(jí)程序語(yǔ)言編寫的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間取決于
- 算法采用的策略、方法 (根本)
- 編譯產(chǎn)生的代碼質(zhì)量 (軟件支持)
- 問(wèn)題的輸入規(guī)模
- 機(jī)器執(zhí)行指令的速度 (硬件性能)
所以一個(gè)程序的運(yùn)行時(shí)間翠胰，依賴于算法的好壞和問(wèn)題的輸入規(guī)模容贝。所謂問(wèn)題輸入規(guī)模是指輸入量的多少
最終，在分析程序的運(yùn)行時(shí)間時(shí)之景，最重要的是把程序看成是獨(dú)立于程序設(shè)計(jì)語(yǔ)言的算法或一系列步驟
函數(shù)的漸近增長(zhǎng)：給定兩個(gè)函數(shù)f(n)和g(n),如果存在一個(gè)整數(shù)N斤富，使得對(duì)于所有的n?>N,f(n)總是比g(n)大，那么锻狗，我們說(shuō)f(n)的增長(zhǎng)漸近快于g(n)满力。
判斷一個(gè)算法的效率時(shí)焕参，函數(shù)中的常數(shù)和其他次要項(xiàng)常常可以忽略油额，而更應(yīng)該關(guān)注主項(xiàng)(最高階項(xiàng))的階數(shù)
與高次項(xiàng)相乘的常數(shù)并不重要
某個(gè)算法龟糕，隨著n的增大，它會(huì)越來(lái)越優(yōu)于另一算法悔耘，或者越來(lái)越差于另一算法。
