常見時間復雜度之間的關系

所消耗的時間從小到大

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

Python內置類型性能分析timeit模塊

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

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

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

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

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

timer參數(shù)是一個定時器函數(shù)，與平臺有關。

timeit．Timer．timeit（number＝1000000）

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

list內置操作的時間復雜度

dict內置操作的時間復雜度

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

我們如何用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內建幫我們封裝好的兩種數(shù)據(jù)結構。

概念

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

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

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

數(shù)據(jù)結構只是靜態(tài)的描述了數(shù)據(jù)元素之間的關系。

高效的程序需要在數(shù)據(jù)結構的基礎上設計和選擇算法。

程序 ＝ 數(shù)據(jù)結構 ＋ 算法

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

抽象數(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ù)運算有五種：

插入

刪除

修改

查找

排序