常見時(shí)間復(fù)雜度之間的關(guān)系

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

O（1） ＜ O（logn） ＜ O（n） ＜ O（nlogn） ＜ O（n2） ＜ O（n3） ＜ O（2n） ＜ O（n�。� ＜ O（nn）

Python內(nèi)置類型性能分析timeit模塊

timeit模塊可以用來測試一小段Python代碼的執(zhí)行速度。

class timeit．Timer（stmt＝’pass’， setup＝’pass’， timer＝

Timer是測量小段代碼執(zhí)行速度的類。

stmt參數(shù)是要測試的代碼語句（statment）；

setup參數(shù)是運(yùn)行代碼時(shí)需要的設(shè)置；

timer參數(shù)是一個(gè)定時(shí)器函數(shù)，與平臺(tái)有關(guān)。

timeit．Timer．timeit（number＝1000000）

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

list內(nèi)置操作的時(shí)間復(fù)雜度

dict內(nèi)置操作的時(shí)間復(fù)雜度

數(shù)據(jù)結(jié)構(gòu)

我們?nèi)绾斡肞ython中的類型來保存一個(gè)班的學(xué)生信息？ 如果想要快速的通過學(xué)生姓名獲取其信息呢？

實(shí)際上當(dāng)我們在思考這個(gè)問題的時(shí)候，我們已經(jīng)用到了數(shù)據(jù)結(jié)構(gòu)。列表和字典都可以存儲(chǔ)一個(gè)班的學(xué)生信息，但是想要在列表中獲取一名同學(xué)的信息時(shí)，就要遍歷這個(gè)列表，其時(shí)間復(fù)雜度為O（n），而使用字典存儲(chǔ)時(shí)，可將學(xué)生姓名作為字典的鍵，學(xué)生信息作為值，進(jìn)而查詢時(shí)不需要遍歷便可快速獲取到學(xué)生信息，其時(shí)間復(fù)雜度為O（1）。

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

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

概念

數(shù)據(jù)是一個(gè)抽象的概念，將其進(jìn)行分類后得到程序設(shè)計(jì)語言中的基本類型。如：int，float，char等。數(shù)據(jù)元素之間不是獨(dú)立的，存在特定的關(guān)系，這些關(guān)系便是結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)指數(shù)據(jù)對象中數(shù)據(jù)元素之間的關(guān)系。

Python給我們提供了很多現(xiàn)成的數(shù)據(jù)結(jié)構(gòu)類型，這些系統(tǒng)自己定義好的，不需要我們自己去定義的數(shù)據(jù)結(jié)構(gòu)叫做Python的內(nèi)置數(shù)據(jù)結(jié)構(gòu)，比如列表、元組、字典。而有些數(shù)據(jù)組織方式，Python系統(tǒng)里面沒有直接定義，需要我們自己去定義實(shí)現(xiàn)這些數(shù)據(jù)的組織方式，這些數(shù)據(jù)組織方式稱之為Python的擴(kuò)展數(shù)據(jù)結(jié)構(gòu)，比如棧，隊(duì)列等。

算法與數(shù)據(jù)結(jié)構(gòu)的區(qū)別

數(shù)據(jù)結(jié)構(gòu)只是靜態(tài)的描述了數(shù)據(jù)元素之間的關(guān)系。

高效的程序需要在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上設(shè)計(jì)和選擇算法。

程序 ＝ 數(shù)據(jù)結(jié)構(gòu) ＋ 算法

總結(jié)：算法是為了解決實(shí)際問題而設(shè)計(jì)的，數(shù)據(jù)結(jié)構(gòu)是算法需要處理的問題載體

抽象數(shù)據(jù)類型（Abstract Data Type）

抽象數(shù)據(jù)類型（ADT）的含義是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。即把數(shù)據(jù)類型和數(shù)據(jù)類型上的運(yùn)算捆在一起，進(jìn)行封裝。引入抽象數(shù)據(jù)類型的目的是把數(shù)據(jù)類型的表示和數(shù)據(jù)類型上運(yùn)算的實(shí)現(xiàn)與這些數(shù)據(jù)類型和運(yùn)算在程序中的引用隔開，使它們相互獨(dú)立。
最常用的數(shù)據(jù)運(yùn)算有五種：

插入

刪除

修改

查找

排序