一、算法引入

如果 a+b+c=1000，且 a^2+b^2=c^2（a,b,c 為自然數(shù)），如何求出所有a、b、c可能的組合?

（1）

import time start_time=time.time() for a in range(0,1001):for b in range(0,1001):for c in range(0,1001):if a+b+c==1000 and a**2+b**2==c**2:print("a,b,c:%d,%d,%d"%(a,b,c)) end_time=time.time() print("times:%d"%(end_time-start_time))

（2）

import time start_time=time.time() for a in range(0,1001):for b in range(0,1001):c=1000-a-bif a**2+b**2==c**2:print("a,b,c:%d,%d,%d"%(a,b,c)) end_time=time.time() print("times:%d"%(end_time-start_time))

? ? ? ?（1）反應(yīng)速度要遠(yuǎn)慢于（2）。算法是計算機(jī)處理信息的本質(zhì)，因為計算機(jī)程序本質(zhì)上是一個算法來告訴計算機(jī)確切的步驟來執(zhí)行一個指定的任務(wù)。算法是獨立存在的一種解決問題的方法和思想。

算法特點

輸入: 算法具有0個或多個輸入

輸出: 算法至少有1個或多個輸出

有窮性: 算法在有限的步驟之后會自動結(jié)束而不會無限循環(huán)，并且每一個步驟可以在可接受的時間內(nèi)完成

確定性：算法中的每一步都有確定的含義，不會出現(xiàn)二義性

可行性：算法的每一步都是可行的，也就是說每一步都能夠執(zhí)行有限的次數(shù)完成

二、時間復(fù)雜度度與大O表示法

import time start_time=time.time() for a in range(0,1001):for b in range(0,1001):for c in range(0,1001):if a+b+c==1000 and a**2+b**2==c**2:print("a,b,c:%d,%d,%d"%(a,b,c)) end_time=time.time() print("times:%d"%(end_time-start_time))

T=1000*1000*1000*2?
T(n)=n^3*2 ?時間復(fù)雜度
g(n)=n^3 ?大O表示法

import time start_time=time.time() for a in range(0,1001):for b in range(0,1001):c=1000-a-bif a**2+b**2==c**2:print("a,b,c:%d,%d,%d"%(a,b,c)) end_time=time.time() print("times:%d"%(end_time-start_time))

T(n)=n^2*（1+Max（0，1））
? ? =n^2*2? ? ? ? ? ?時間復(fù)雜度
g(n)=n^2? ? ? ? ? ? 大O表示法

三、最壞事件復(fù)雜度與計算規(guī)則

? ? ? ?最優(yōu)時間復(fù)雜度、最壞時間復(fù)雜度、平均時間復(fù)雜度。我們主要關(guān)注算法的最壞情況，亦即最壞時間復(fù)雜度。

計算規(guī)則

基本操作，即只有常數(shù)項，認(rèn)為其時間復(fù)雜度為O(1)

順序結(jié)構(gòu)，時間復(fù)雜度按加法進(jìn)行計算

循環(huán)結(jié)構(gòu)，時間復(fù)雜度按乘法進(jìn)行計算

分支結(jié)構(gòu)，時間復(fù)雜度取最大值

判斷一個算法的效率時，往往只需要關(guān)注操作數(shù)量的最高次項，其它次要項和常數(shù)項可以忽略

四、常見時間復(fù)雜度與大小關(guān)系

五、代碼執(zhí)行時間測量模塊timeit

class timeit.Timer(stmt='pass', setup='pass', timer=<timer function>)

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

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

timeit.Timer.timeit(number=1000000)? ? ? ?

測試1000000次的平均耗時

六、Python列表類型不同操作的時間效率

def test1():li=[]for i in range(10000):li.append(i)def test2():li=[]for i in range(10000):li=li+[i]def test3():li=[i for i in range(10000)]def test4():li=list(range(10000))from timeit import Timer timer1=Timer("test1()","from __main__ import test1") print("append:",timer1.timeit(1000))from timeit import Timer timer2=Timer("test2()","from __main__ import test2") print("+:",timer2.timeit(1000))from timeit import Timer timer3=Timer("test3()","from __main__ import test3") print("i for i in range",timer3.timeit(1000))from timeit import Timer timer4=Timer("test4()","from __main__ import test4") print("list(range())",timer4.timeit(1000))

pop最后一個元素的效率遠(yuǎn)遠(yuǎn)高于pop第一個元素

七、Python列表與字典操作的時間復(fù)雜度

（1）list內(nèi)置操作的時間復(fù)雜度

（2）dict內(nèi)置操作的時間復(fù)雜度

八、數(shù)據(jù)結(jié)構(gòu)引入

? ? ? ?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)里面沒有直接定義，需要我們自己去定義實現(xiàn)這些數(shù)據(jù)的組織方式，這些數(shù)據(jù)組織方式稱之為Python的擴(kuò)展數(shù)據(jù)結(jié)構(gòu)，比如棧，隊列等。

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

? ? ? ?即把數(shù)據(jù)類型和數(shù)據(jù)類型上的運算捆在一起，進(jìn)行封裝

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的Python数据结构与算法（第一天）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。