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

所消耗的時間從小到大

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參數是要測試的代碼語句（statment）；

setup參數是運行代碼時需要的設置；

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

timeit．Timer．timeit（number＝1000000）

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

list內置操作的時間復雜度

dict內置操作的時間復雜度

數據結構

我們如何用Python中的類型來保存一個班的學生信息？ 如果想要快速的通過學生姓名獲取其信息呢？

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

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

在上面的問題中我們可以選擇Python中的列表或字典來存儲學生信息。列表和字典就是Python內建幫我們封裝好的兩種數據結構。

概念

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

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

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

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

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

程序 ＝ 數據結構 ＋ 算法

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

抽象數據類型（Abstract Data Type）

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

插入

刪除

修改

查找

排序