本篇來學習一些計算時間複雜度相關的概念和規則，然後了解一些常見的時間複雜度。
1.最壞時間複雜度
分析算法時，存在幾種可能的考慮：
算法完成工作最少需要多少基本操作，即最優時間複雜度。
算法完成工作最多需要多少基本操作，即最壞時間複雜度。
算法完成工作平均需要多少基本操作，即平均時間複雜度。
對于最優時間複雜度，其價值不大，因為它沒有提供什麼有用資訊，其反映的隻是最樂觀最理想的情況，沒有參考價值。
對于最壞時間複雜度，提供了一種保證，表明算法在此種程度的基本操作中一定能完成工作。
對于平均時間複雜度，是對算法的一個全面評價，是以它完整全面反映了這個算法的性質。但，另一方面，這種衡量并沒有保證，不是每個計算都能在這個基本操作内完成。而且，對于平均情況的計算機，也會因為應用算法執行個體分布可能并不均勻而難以計算。
是以，我們主要關注算法最壞情況，也就是最壞時間複雜度。
2.時間複雜度的幾條基本計算規則
1.基本操作，即隻有常數項，認為其時間複雜度為O(1)
2.順序結構，時間複雜度按加法進行計算
3.循環結構，時間複雜度按乘法進行計算
4.分支結構，時間複雜度取最大值
5.判斷一個算法的效率時，往往隻需要關注操作數量的最高次項，其他次要項和常數項可以忽略。
6.在沒有特殊說明時，我們所分析的算法的時間複雜度都是指最壞時間複雜度。
3.常見的時間複雜度
看看下面這張表
上面這個表，給了以後計算時間複雜度的一個參考。
4.常見時間複雜度之間關系
這個圖很形象告訴我們常見幾個時間雜度耗時間關系。
5.python中代碼執行時間測量子產品timeit
在python中有一個測量函數執行時間的子產品叫timeit，下面利用這個子產品來測量幾種建立list的效率問題。
先來看看這兩行代碼的含義
time1 = Timer("test1()", "from __main__ import test1") # 調用測量時間子產品的方法
time1.timeit(1000) # 1000指的是測量1000次之後取平均值 # coding:utf-8
from timeit import Timer
def test1():
li = []
for i in range(10000):
li.append(i)
def test2():
li = []
for i in range(10000):
li.insert(0, i)
def test3():
li = [i for i in range(10000)] # 清單生成器方式
def test4():
li = list(range(10000))
time1 = Timer("test1()", "from __main__ import test1")
print("append:", time1.timeit(1000))
time2 = Timer("test2()", "from __main__ import test2")
print("insert:", time2.timeit(1000))
time3 = Timer("test3()", "from __main__ import test3")
print("[i in range(10000)]:", time3.timeit(1000))
time4 = Timer("test4()", "from __main__ import test4")
print("list轉換:", time4.timeit(1000))
運作效果
append: 0.9357269000000001
insert: 20.1958311
[i in range(10000)]: 0.44400420000000196
list轉換: 0.23993809999999982 在清單中，append方法是從尾部添加元素，而insert方法是從頭部插入元素，發現insert比append太慢。其實上面還有一種沒有寫出來就是li = li + [i], 如果i取值10000，這個執行時間差不多要3到4分鐘。
6.python中清單和字典操作時間複雜度
list内置操作時間複雜度
dict内置操作時間複雜度