我們已知python是具有非常多的包一種開源語言，封裝了各種算法。
python典型的數(shù)據(jù)結(jié)構(gòu)為列表/元組/字符串/字典，與C/C++中的數(shù)組(array)/ 棧(stack) /（優(yōu)先）隊列”(queue) / 二叉樹(binary tree)有明顯區(qū)別。
在python官網(wǎng)中指出，列表可以作為棧和隊列使用，但是并未給出特別詳細具體的教程。
在python官網(wǎng)上有關(guān)于list和dict數(shù)據(jù)結(jié)構(gòu)的描述參考，如鏈接所示，但是沒有關(guān)于時間復雜度和空間復雜度的分析。本文是對官網(wǎng)內(nèi)容一個實例化和補充
官網(wǎng)鏈接：https://docs.python.org/zh-cn/3/tutorial/datastructures.html

本文內(nèi)容部分參考：嗶哩嗶哩網(wǎng)站上“自學IT工程師”的“python學習教程之數(shù)據(jù)結(jié)構(gòu)和算法基礎(chǔ)”
具體參考鏈接：https://www.bilibili.com/video/av46256220/?p=6
            https://www.bilibili.com/video/av46256220/?p=7

根據(jù)這一系列的教程，將在系列文章中給出與C語言中的數(shù)據(jù)結(jié)構(gòu)逐一對應(yīng)的python解法

測算一小段代碼的執(zhí)行速度采用timeit這個包，timeit用法參考：https://docs.python.org/3/library/timeit.html
          

常用的參數(shù)定義為：

            
              class timeit.Timer（stmt ='pass'，setup ='pass'，timer = 
              
                ，globals = None ）
              
            
          

用法的簡單示例為：

            
              timeit.Timer('for i in range(10): oct(i)', 'gc.enable()').timeit()
            
          

?

測算生成list的算法效率

            
              from timeit import Timer

def t1():
    li = []
    for i in range(10000):
        li.append(i)

def t2():
    li = []
    for i in range(10000):
        li = li+ [i]

def t3():
    li = [i for i in range(10000)]

def t4():
    li = list(range(10000))

def t5():
    for i in range(10000):
        li.extend([i])

def t6():
    li = []
    for i in range(10000):
        li.insert(0,i)

# 采用timeit測算一小段代碼的運行速度

# 追加操作
timer1 = Timer('t1()','from __main__ import t1')
print('.append: ',timer1.timeit(1000))

# 加操作操作
timer2 = Timer('t2()','from __main__ import t2')
print('+: ',timer2.timeit(1000))

#列表生成器
timer3 = Timer('t3()','from __main__ import t3')
print('[i for i in range]: ',timer3.timeit(1000))

# 列表生成器類似的轉(zhuǎn)換
timer4 = Timer('t4()','from __main__ import t4')
print('list(range()): ',timer4.timeit(1000))

# 擴展操作
timer5 = Timer('t5()','from __main__ import t5')
print('extend: ',timer5.timeit(1000))

#插入操作
timer6 = Timer('t6()','from __main__ import t6')
print('insert :',timer6.timeit(1000))
            
          

            輸出結(jié)果為

          

            
              .append:  0.7118582189999999
+:  114.38965233500001
[i for i in range]:  0.3101561069999974
list(range()):  0.16905038100000525
extend:  1.4377866079999961
insert : 30.547064246999994
            
          

            從以上輸出結(jié)果可以看出，字符串‘+’操作的速度最慢，在循環(huán)次數(shù)多的時間特別明顯，所以盡量避免使用；追加操作和列表生成器的速度相當，建議采納，擴展的速度稍慢，但也可以；插入操作特別是從頭部插入操作，因為后面所有的元素都要向后移動一位，所以速度最慢。
絕大部分情況下，我們更關(guān)注算法的時間復雜度。


除了以上引用到的列表(list)的方法以外，list和dict還有很多內(nèi)置操作，他們的時間復雜度如下所示。

List 內(nèi)置操作的時間復雜度
Operation         Big-O Efficiency
index[]             O(1)
index assignment    O(1)
append              O(1)
pop()               O(1)
pop(i)              O(n)
insert()            O(n)
del operator        O(n)
iteration           O(n)
contains(in)        O(n)
get slice           O(n)
set slice           O(n+k)
reversed            O(n)
concatenate         O(n)
sort                O(nlogn)
multiply            O(nk)

dict 內(nèi)置操作的時間復雜度
operation       Big-O Effeciency
copy                O(n)
get item            O(1)
set item            O(1)
contains(in)        O(1)
iteration           O(1)