接下來系統(tǒng)的學一下數(shù)據(jù)結構與算法的知識，本章節(jié)是第一部分：數(shù)據(jù)結構與算法的進入與基本概述

第一章：引入概念

【鐵打的算法demo】

先來看到題：

如果 a + b + c = 1000，且 a² + b² = c²（a, b , c 為?然數(shù)），如何求出所有 a、b、c 可能的組合?

方法一：直接干

思路：既然 a + b + c = 1000，說明 a、b、c 都在 0 ~ 1000 之內(nèi)（不考慮負數(shù)），則可以用 for 循環(huán) + if 直接寫代碼

# 導入time，用來計時運行程序所耗時間
import time

start = time.time()

for a in range(1000):
    for b in range(1000):
        for c in range(1000):
            if a ** 2 + b ** 2 == c ** 2 and a + b + c == 1000:
                print('a, b, c：%d, %d, %d' % (a, b, c))

end = time.time()
print('耗時：%fs.'.format(end - start))

運行結果：

a, b, c：0, 500, 500
a, b, c：200, 375, 425
a, b, c：375, 200, 425
a, b, c：500, 0, 500
耗時：251.520628s.

方法二：想想如何優(yōu)化代碼

優(yōu)化一：優(yōu)化 b 的 for 循環(huán) for b in range(1000 - a)

• a b 都在 0 ~ 1000 之內(nèi)，a 循環(huán)范圍是 0 ~ 1000，則循環(huán) b 時可在此基礎上用 1000 - a 即可，沒必要再從 0 到 1000 循環(huán)一遍，因為 a b c 三者之和才只有 1000，如果 a = 500，循環(huán)到 b >= 500 時，會在后面判斷 a ** 2 + b ** 2 == c ** 2 時被過濾掉（從結果看 c 也不能是 0，不符合邏輯），從而造成多余的沒必要的循環(huán)，白白浪費資源，還拉長運行時間

優(yōu)化二：優(yōu)化 c 去掉for循環(huán)，改為 1000 - a - b

• 一共三個數(shù)，在循環(huán)兩個數(shù)后，第三個數(shù)就是 1000 減掉前兩個數(shù)，相比于再 for 循環(huán)一遍，使用它們共同的和減掉前兩個數(shù)得到第三個數(shù)的方式更簡單，且是由 1000 的量級直接降到一個簡單的減法了，還省去了后續(xù)的一個 if 判斷

優(yōu)化后的代碼：

import time

start = time.time()

for a in range(1000):
    for b in range(1000):
        c = 1000 - a - b
        if a ** 2 + b ** 2 == c ** 2:
            print('a, b, c：%d, %d, %d' % (a, b, c))

end = time.time()

print('耗時：%fs.' % (end - start))

運行結果：

a, b, c：0, 500, 500
a, b, c：200, 375, 425
a, b, c：375, 200, 425
a, b, c：500, 0, 500
耗時：0.510947s

發(fā)現(xiàn)執(zhí)行時間明顯縮短了！

1. 算法的概念

算法是計算機處理信息的本質(zhì)，因為計算機程序本質(zhì)上是?個算法來告訴計 算機確切的步驟來執(zhí)??個指定的任務。?般地，當算法在處理信息時，會 從輸?設備或數(shù)據(jù)的存儲地址讀取數(shù)據(jù)，把結果寫?輸出設備或某個存儲地 址供以后再調(diào)?。 算法是獨?存在的?種解決問題的?法和思想。 對于算法??，實現(xiàn)的語?并不重要，重要的是思想。 算法可以有不同的語?描述實現(xiàn)版本（如C描述、C++描述、Python描述 等），我們現(xiàn)在是在? Python 語?進?描述實現(xiàn)。

2. 算法的五?特性

1. 輸?: 算法具有 0 個或多個輸?
2. 輸出: 算法?少有 1 個或多個輸出
3. 有窮性: 算法在有限的步驟之后會?動結束?不會?限循環(huán)，并且每?個步驟可以在可接受的時間內(nèi)完成
4. 確定性：算法中的每?步都有確定的含義，不會出現(xiàn)?義性
5. 可?性：算法的每?步都是可?的，也就是說每?步都能夠執(zhí)?有限的次數(shù)完成

3. 算法效率衡量

1. 執(zhí)?時間反應算法效率

對于同?問題，我們給出了兩種解決算法，在兩種算法的實現(xiàn)中，我們對程 序執(zhí)?的時間進?了測算，發(fā)現(xiàn)兩段程序執(zhí)?的時間相差懸殊，由此我們可以得出結論：實現(xiàn)算法程序的執(zhí)?時間可以反映出算法的效率，即算法的優(yōu)劣。

2. 單靠時間值絕對可信嗎？

假設我們將第?次嘗試的算法程序運?在?臺配置古?性能低下的計算機 中，情況會如何？很可能運?的時間并不會?在我們的電腦中運?算法?的 214.583347秒快多少。
單純依靠運?的時間來?較算法的優(yōu)劣并不?定是客觀準確的！
程序的運?離不開計算機環(huán)境（包括硬件和操作系統(tǒng)），這些客觀原因會影 響程序運?的速度并反應在程序的執(zhí)?時間上。那么如何才能客觀的評判? 個算法的優(yōu)劣呢？

3. 時間復雜度與 “?O記法”

我們假定計算機執(zhí)?算法每?個基本操作的時間是固定的?個時間單位，那 么有多少個基本操作就代表會花費多少時間單位。顯然對于不同的機器環(huán)境 ??，確切的單位時間是不同的，但是對于算法進?多少個基本操作（即花 費多少時間單位）在規(guī)模數(shù)量級上卻是相同的，由此可以忽略機器環(huán)境的影 響?客觀的反應算法的時間效率。 對于算法的時間效率，我們可以? “?O記法” 來表示。

“?O記法”：對于單調(diào)的整數(shù)函數(shù) f，如果存在?個整數(shù)函數(shù) g 和實常數(shù) c>0， 使得對于充分?的 n 總有 f(n)<=c*g(n) ，就說函數(shù) g 是 f 的?個漸近函數(shù)（忽略常數(shù)），記為 f(n)=O(g(n))。也就是說，在趨向?窮的極限意義下，函數(shù) f 的增?速度受到函數(shù) g 的約束，亦即函數(shù) f 與函數(shù) g 的特征相似。

時間復雜度：假設存在函數(shù) g，使得算法 A 處理規(guī)模為 n 的問題示例所?時間為 T(n)=O(g(n))，則稱 O(g(n)) 為算法 A 的漸近時間復雜度，簡稱時間復雜度，記為T(n)

4. 如何理解“?O記法”

對于算法進?特別具體的細致分析雖然很好，但在實踐中的實際價值有限。 對于算法的時間性質(zhì)和空間性質(zhì)，最重要的是其數(shù)量級和趨勢，這些是分析算法效率的主要部分。?計量算法基本操作數(shù)量的規(guī)模函數(shù)中那些常量因?可以忽略不計。例如，可以認為 3n² 和 100n² 屬于同?個量級，如果兩個算法處理同樣規(guī)模實例的代價分別為這兩個函數(shù)，就認為它們的效率 “差不多”， 都為 n² 級。

5. 最壞時間復雜度

分析算法時，存在?種可能的考慮：

• 算法完成?作最少需要多少基本操作，即最優(yōu)時間復雜度
• 算法完成?作最多需要多少基本操作，即最壞時間復雜度
• 算法完成?作平均需要多少基本操作，即平均時間復雜度

分析：

• 對于最優(yōu)時間復雜度，其價值不?，因為它沒有提供什么有?信息，其反映的只是最樂觀最理想的情況，沒有參考價值；
• 對于最壞時間復雜度，提供了?種保證，表明算法在此種程度的基本操作中 ?定能完成?作；
• 對于平均時間復雜度，是對算法的?個全?評價，因此它完整全?的反映了這個算法的性質(zhì)。但另???，這種衡量并沒有保證，不是每個計算都能在這個基本操作內(nèi)完成。?且，對于平均情況的計算，也會因為應?算法的實例分布可能并不均勻?難以計算。

因此，我們主要關注算法的最壞情況，亦即最壞時間復雜度。

6. 時間復雜度的?條基本計算規(guī)則

1. 基本操作，即只有常數(shù)項，認為其時間復雜度為 O(1)
2. 順序結構，時間復雜度按加法進?計算
3. 循環(huán)結構，時間復雜度按乘法進?計算
4. 分?結構，時間復雜度取最?值
5. 判斷?個算法的效率時，往往只需要關注操作數(shù)量的最?次項，其它次要項和常數(shù)項可以忽略
6. 在沒有特殊說明時，我們所分析的算法的時間復雜度都是指最壞時間復雜度

7. 空間復雜度

類似于時間復雜度的討論，?個算法的空間復雜度S(n)定義為該算法所耗費 的存儲空間，它也是問題規(guī)模n的函數(shù)。
漸近空間復雜度也常常簡稱為空間復雜度。
空間復雜度(SpaceComplexity) 是對?個算法在運?過程中臨時占?存儲空間??的量度。
算法的時間復雜度和空間復雜度合稱為算法的復雜度。

4. 算法分析

第?次嘗試的算法核?部分

for a in range(0, 1001):
	for b in range(0, 1001):
		for c in range(0, 1001):
			if a**2 + b**2 == c**2 and a+b+c == 1000:
				print("a, b, c: %d, %d, %d" % (a, b, c))

時間復雜度：T(n) = O(n*n*n) = O(n3)

第?次嘗試的算法核?部分

for a in range(0, 1001):
	for b in range(0, 1001 - a):
		c = 1000 - a - b if a**2 + b**2 == c**2:
			print("a, b, c: %d, %d, %d" % (a, b, c))

時間復雜度： T(n) = O(n*n*(1+1)) = O(n*n) = O(n2)

由此可?，我們嘗試的第?種算法要?第?種算法的時間復雜度好多的。

5. 常?時間復雜度

注意，經(jīng)常將 log₂n（以 2 為底的對數(shù)）簡寫成 logn

常?時間復雜度之間的關系為：

所消耗的時間從?到?：

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

6. Python內(nèi)置類型性能分析

1. timeit 模塊

timeit 模塊可以?來測試??段 Python 代碼的執(zhí)?速度

class timeit.Timer(stmt=‘pass’, setup=‘pass’, timer=<timer function>)

參數(shù)說明：

• Timer 是測量?段代碼執(zhí)?速度的類
• stmt 參數(shù)是要測試的代碼語句（statment）
• setup 參數(shù)是運?代碼時需要的設置
• timer 參數(shù)是?個定時器函數(shù)，與平臺有關

timeit.Timer.timeit(number=1000000)

• Timer 類中測試語句執(zhí)?速度的對象?法。number 參數(shù)是測試代碼時的測試次數(shù)，默認為 1000000 次。?法返回執(zhí)?代碼的平均耗時，?個 float 類型的秒數(shù)

2. list 的操作測試

1. 添加元素的四種方式效率比較

from timeit import Timer

def t1():
    l = []
    for i in range(1000):
        l = l + [i]

def t2():
    l = []
    for i in range(1000):
        l.append(i)

def t3():
    l = [i for i in range(1000)]

def t4():
    l = list(range(1000))

timer1 = Timer("t1()", "from __main__ import t1")
print("concat", timer1.timeit(number=1000), "s")
timer2 = Timer("t2()", "from __main__ import t2")
print("append", timer2.timeit(number=1000), "s")
timer3 = Timer("t3()", "from __main__ import t3")
print("comprehension", timer3.timeit(number=1000), "s")
timer4 = Timer("t4()", "from __main__ import t4")
print("list_range", timer4.timeit(number=1000), "s")

'''
concat 1.0436126479980885 s
append 0.08462878499994986 s
comprehension 0.03660322499490576 s
list_range 0.014424725006392691 s
'''

2. 刪除元素的兩種方式效率比較

• 從結果可以看出，pop 最后?個元素的效率遠遠?于 pop 第?個元素

x = list(range(2000000))
pop_zero = Timer("x.pop(0)", "from __main__ import x")
print("pop_zero", pop_zero.timeit(number=1000), "s")
y = list(range(2000000))
pop_end = Timer("y.pop()", "from __main__ import y")
print("pop_end", pop_end.timeit(number=1000), "s")

'''
pop_zero 0.9256400320009561 s
pop_end 9.138700261246413e-05 s
'''

3. list 內(nèi)置操作的時間復雜度

4. dict 內(nèi)置操作的時間復雜度

7. 數(shù)據(jù)結構

我們?nèi)绾?Python中的類型來保存?個班的學?信息？ 如果想要快速的通過學?姓名獲取其信息呢？

實際上當我們在思考這個問題的時候，我們已經(jīng)?到了數(shù)據(jù)結構。列表和字 典都可以存儲?個班的學?信息，但是想要在列表中獲取?名同學的信息時，就要遍歷這個列表，其時間復雜度為 O(n)，?使?字典存儲時，可將學?姓名作為字典的鍵，學?信息作為值，進?查詢時不需要遍歷便可快速獲取到學?信息，其時間復雜度為 O(1)。

我們?yōu)榱私鉀Q問題，需要將數(shù)據(jù)保存下來，然后根據(jù)數(shù)據(jù)的存儲?式來設計 算法實現(xiàn)進?處理，那么數(shù)據(jù)的存儲?式不同就會導致需要不同的算法進?處理。我們希望算法解決問題的效率越快越好，于是我們就需要考慮數(shù)據(jù)究竟如何保存的問題，這就是數(shù)據(jù)結構。

在上?的問題中我們可以選擇 Python 中的列表或字典來存儲學?信息。列表和字典就是 Python 內(nèi)建幫我們封裝好的兩種數(shù)據(jù)結構。

1. 概念

數(shù)據(jù)是?個抽象的概念，將其進?分類后得到程序設計語?中的基本類型。 如：int，float，char 等。數(shù)據(jù)元素之間不是獨?的，存在特定的關系，這些關系便是結構。

數(shù)據(jù)結構指數(shù)據(jù)對象中數(shù)據(jù)元素之間的關系。 Python 給我們提供了很多現(xiàn)成的數(shù)據(jù)結構類型，這些系統(tǒng)??定義好的，不需要我們??去定義的數(shù)據(jù)結構叫做 Python 的內(nèi)置數(shù)據(jù)結構，?如列表、元 組、字典。?有些數(shù)據(jù)組織?式，Python 系統(tǒng)??沒有直接定義，需要我們??去定義實現(xiàn)這些數(shù)據(jù)的組織?式，這些數(shù)據(jù)組織?式稱之為 Python 的擴展數(shù)據(jù)結構，?如棧，隊列等。

2. 算法與數(shù)據(jù)結構的區(qū)別

數(shù)據(jù)結構只是靜態(tài)的描述了數(shù)據(jù)元素之間的關系。
?效的程序需要在數(shù)據(jù)結構的基礎上設計和選擇算法。

程序 = 數(shù)據(jù)結構 + 算法
總結：算法是為了解決實際問題?設計的，數(shù)據(jù)結構是算法需要處理的問題載體

3. 抽象數(shù)據(jù)類型(Abstract Data Type)

抽象數(shù)據(jù)類型(ADT) 的含義是指?個數(shù)學模型以及定義在此數(shù)學模型上的? 組操作。即把數(shù)據(jù)類型和數(shù)據(jù)類型上的運算捆在?起，進?封裝。引?抽象 數(shù)據(jù)類型的?的是把數(shù)據(jù)類型的表示和數(shù)據(jù)類型上運算的實現(xiàn)與這些數(shù)據(jù)類 型和運算在程序中的引?隔開，使它們相互獨?。

最常?的數(shù)據(jù)運算有五種：文章來源地址http://www.zghlxwxcb.cn/news/detail-437270.html

• 插?
• 刪除
• 修改
• 查找
• 排序

到了這里，關于數(shù)據(jù)結構與算法1：引入概念的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！