先看思維導(dǎo)圖：

思維導(dǎo)圖

• 思維導(dǎo)圖有點(diǎn)簡(jiǎn)陋，本著循循漸進(jìn)的思想，這小節(jié)的知識(shí)大多只做了解即可。

• 重點(diǎn)在于算法的代價(jià)及度量?。?！查找資料務(wù)必弄清楚.

零.四個(gè)基本概念

• 問(wèn)題：一個(gè)具體的需求
• 問(wèn)題實(shí)例：針對(duì)問(wèn)題(需求)的具體的例子
• 算法：解決問(wèn)題的過(guò)程，是對(duì)一個(gè)計(jì)算過(guò)程的嚴(yán)格描述
• 程序：程序可以看作是采用計(jì)算裝置能夠處理的語(yǔ)言描述的算法

一.算法的5大性質(zhì)

• 有窮性（算法描述的又窮性）：算法必須用有限長(zhǎng)的描述說(shuō)清楚
• 能行性：算法的每一步都是可行的，也就是說(shuō)，每一步都能通過(guò)執(zhí)行有限次數(shù)完成
• 確定性：別人看了過(guò)后，很清楚的明白，不會(huì)有歧義
• 終止性（行為的有窮性）：指算法在執(zhí)行有限的步驟后，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無(wú)限循環(huán)，并且每一個(gè)步驟在可接受的時(shí)間內(nèi)完成
• 輸入/輸出：算法具有零個(gè)(print("Hello World"))或多個(gè)輸入(輸入?yún)?shù))；算法至少有一個(gè)或多個(gè)輸出

二.算法的描述(最常用的兩種)

• 類(lèi)似編程語(yǔ)言的形式：用類(lèi)似編程語(yǔ)言的形式描述算法的過(guò)程，其中參雜使用一些數(shù)學(xué)符號(hào)和記號(hào)，用于描述算法中一些細(xì)節(jié)和具體操作
• 偽代碼：類(lèi)似于前一方式

三.算法的設(shè)計(jì)模式

• 知道有這六種即可，我也沒(méi)深入了解具體是什么怎么實(shí)現(xiàn)的，知道有這幾種就行，遇到了再掌握吧！

• 算法一般是多種模式的有機(jī)結(jié)合

四.算法的代價(jià)及度量

首先明確，對(duì)于算法的研究，人們主要關(guān)注算法的最壞情況代價(jià)

1. 時(shí)間代價(jià)(時(shí)間復(fù)雜度)

• 測(cè)定運(yùn)行時(shí)間最可靠的方法就是計(jì)算對(duì)運(yùn)行時(shí)間有消耗的基本操作的執(zhí)行次數(shù)

舉個(gè)栗子：對(duì)于同一個(gè)問(wèn)題，算法A要做 2n+3 次操作、算法B要做 3n+1 次操作、算法c要做 2n^2+1 次操作，哪個(gè)算法好？？？

答：很明顯隨著n的增長(zhǎng)(N趨近于無(wú)窮大)，總體來(lái)說(shuō) A<B<C

• 會(huì)用到"大O記法"（針對(duì)不同階的表達(dá)式），定義什么的太麻煩了，直接簡(jiǎn)單的寫(xiě)步驟：

(要知道對(duì)于不同階的表達(dá)式(比如 線性階3n+10 平方階2n^2 2n^2+3n+1) 隨著n的增長(zhǎng)(趨近于無(wú)窮大)，第二種算法趨近于第三種算法，而第1種算法遠(yuǎn)小于其余兩種算法）

(因而得出結(jié)論 對(duì)于不同階的表達(dá)式的比較 算法執(zhí)行次數(shù)表達(dá)式的常數(shù)項(xiàng)和與最高次數(shù)相乘的常數(shù)乃至于次要項(xiàng)都不能起決定作用)

第一步：用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)

第二步：再修改后的運(yùn)算次數(shù)函數(shù)中，只保留最高階項(xiàng)

第三步：如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)

• 下面列出常見(jiàn)的時(shí)間復(fù)雜度

注意，經(jīng)常將log<sub>2</sub>n（以2為底的對(duì)數(shù)）簡(jiǎn)寫(xiě)成logn！！

所消耗的時(shí)間從小到大

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

我們舉個(gè)栗子，推導(dǎo)下對(duì)數(shù)階

count = 1
while count < n:
    count = count * 2 # 這行代碼時(shí)間復(fù)雜度為O(1)</pre>

問(wèn)：上述代碼的時(shí)間復(fù)雜度為多少？

答：由于每次count*2后就會(huì)更接近于n，所以我們就要算 有多少個(gè)2相乘后大于n，使其退出循環(huán)。由2^x = n得到 x = logn.這個(gè)循環(huán)的時(shí)間復(fù)雜度為O(logn)

• 由于python程序是算法的實(shí)現(xiàn)，所以不得不考慮python程序的計(jì)算代價(jià)

• 有點(diǎn)懵 看不明白也沒(méi)關(guān)系，我也看不明白，等學(xué)完用python語(yǔ)言程序?qū)崿F(xiàn)后就自然而言明白了。

2. 空間代價(jià)(空間復(fù)雜度)

時(shí)間復(fù)雜度指運(yùn)行時(shí)間的需求，空間復(fù)雜度指空間需求。現(xiàn)目前，不必考慮。所以不準(zhǔn)備怎么了解，先放放。

五.數(shù)據(jù)結(jié)構(gòu)及分類(lèi)

1. 組成

• 數(shù)據(jù)：是描述客觀事物的符號(hào)，是計(jì)算機(jī)可以操作的對(duì)象，是能被計(jì)算機(jī)識(shí)別并輸出給計(jì)算機(jī)處理的符號(hào)集合
• 數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，在不混淆的情況下，數(shù)據(jù)=數(shù)據(jù)對(duì)象
• 數(shù)據(jù)元素：是組成數(shù)據(jù)的一定意義的基本單位，在計(jì)算機(jī)中通常作為整體處理
• 數(shù)據(jù)項(xiàng)：是數(shù)據(jù)不可分割的最小單位，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成

數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或者多種特定關(guān)系的數(shù)據(jù)元素的集合.由邏輯結(jié)構(gòu)和物理結(jié)構(gòu).

2. 邏輯結(jié)構(gòu)

• 邏輯結(jié)構(gòu)是指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的相互關(guān)系

• 邏輯結(jié)構(gòu)包括：集合結(jié)構(gòu)、序列結(jié)構(gòu)(一對(duì)一)、層次結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)(一對(duì)多)、圖結(jié)構(gòu)(多對(duì)多)

3. 物理結(jié)構(gòu)

• 物理結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式

  • 順序存儲(chǔ)結(jié)構(gòu)：把數(shù)據(jù)元素存放在地址連續(xù)的存儲(chǔ)單元里
  • 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：把數(shù)據(jù)元素存放在任意的存儲(chǔ)單元里，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的

• 那么我們不得不討論下計(jì)算機(jī)內(nèi)存對(duì)象的表示，以及python變量的引用語(yǔ)義

  • 計(jì)算機(jī)內(nèi)存對(duì)象表示

內(nèi)存是CPU可以直接訪問(wèn)的存儲(chǔ)設(shè)備，與其對(duì)應(yīng)的是外存(磁盤(pán)、光盤(pán)、磁帶等)

內(nèi)存的基本結(jié)構(gòu)是線性排列的一批存儲(chǔ)單元(存儲(chǔ)單元具有唯一的編號(hào)，稱(chēng)為單元地址或簡(jiǎn)稱(chēng)地址)。每個(gè)單元的大小相同，可以保存一個(gè)單位大小的數(shù)據(jù).
舉個(gè)例子：目前常見(jiàn)的64位操作系統(tǒng)，一次可以讀取8個(gè)單元的數(shù)據(jù)，現(xiàn)在由一個(gè)float64的數(shù)據(jù)，我們可以得知float64 = 8字節(jié) = 8個(gè)單元 = 64位二進(jìn)制數(shù)

當(dāng)一個(gè)對(duì)象不再使用的時(shí)候，存儲(chǔ)管理系統(tǒng)會(huì)設(shè)法回收其占用的存儲(chǔ)，以便于用于存儲(chǔ)其它對(duì)象

對(duì)于一個(gè)組合對(duì)象，其中包含了一組元素，這些元素被安排到了一組連續(xù)的存儲(chǔ)單元里，我們現(xiàn)在知道其起始地址位P，每個(gè)元素的大小相等為a，那么我們可以得知第K個(gè)元素的地址 loc(k) = p + k*a;

還有一種情況，每個(gè)元素的大小不相等，那么我們就可以計(jì)算這類(lèi)對(duì)象里的各個(gè)元素相對(duì)于起始地址的相對(duì)位置，稱(chēng)為元素的存儲(chǔ)偏移量

• python變量的引用語(yǔ)義

python語(yǔ)言是引用語(yǔ)義，C語(yǔ)言是值語(yǔ)義。簡(jiǎn)單來(lái)說(shuō)，有一個(gè)值3.1415存儲(chǔ)在內(nèi)存的中，地址為p，那么 a = 3.1415,a變量里保存的是p，同樣的我們?cè)侔?.1415賦值給b，b變量里保存的同樣是p，a和b的同時(shí)指向了3.1415這一數(shù)據(jù)所在的地址，即a和b變量的存儲(chǔ)區(qū)里保存的都是p。而C語(yǔ)言是吧變量的值直接保存在變量的存儲(chǔ)區(qū)里。