aaa亚洲精品,粉嫩美鲍国产一区二区,中文字幕AV色久

引入

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

第一次嘗試

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**2+b**2==c**2 and a+b+c == 1000:
                print(a,b,c)
end_time = time.time()
print('elapsed:{}'.format(end_time-start_time))
print('complete!')

從程序中我們可以清晰的看出該程序是三次循環(huán)。
運行結(jié)果：

D:\anaconda\python.exe D:/bilibili大學(xué)/數(shù)據(jù)結(jié)構(gòu)與算法/第一次嘗試.py
0 500 500
200 375 425
375 200 425
500 0 500
elapsed:926.4351501464844
complete!

注意運行時間：926.4351501464844，相當(dāng)于十五分鐘了。
我的電腦cpu不行，這速度我都打完一把王者榮耀了。

算法的提出

算法的概念

算法是計算機(jī)處理信息的本質(zhì)，因為計算機(jī)程序本質(zhì)上是一個算法來告訴計算機(jī)確切的步驟來執(zhí)行一個指定的任務(wù)。一般地，當(dāng)算法在處理信息時，會從輸入設(shè)備或數(shù)據(jù)的存儲地址讀取數(shù)據(jù)，把結(jié)果寫入輸出設(shè)備或某個存儲地址供以后再調(diào)用。
算法是獨立存在的一種解決問題的方法和思想。
對于算法而言，實現(xiàn)的語言并不重要，重要的是思想。
算法可以有不同的語言描述實現(xiàn)版本（如C描述、C++描述、Go語言，Python描述等），我們現(xiàn)在是在用Python語言進(jìn)行描述實現(xiàn)。

算法的五大特性

輸入: 算法具有0個或多個輸入
輸出: 算法至少有1個或多個輸出
有窮性: 算法在有限的步驟之后會自動結(jié)束而不會無限循環(huán)，并且每一個步驟可以在可接受的時間內(nèi)完成
確定性：算法中的每一步都有確定的含義，不會出現(xiàn)二義性
可行性：算法的每一步都是可行的，也就是說每一步都能夠執(zhí)行有限的次數(shù)完成

第二次嘗試

import time

start_time = time.time()
#顯然只有兩次循環(huán)
for a in range(0,1001):
    for b in range(0, 1001):
        c = 1000 - a - b
        if a**2+b**2 == c**2 :
            print(a,b,c)
end_time = time.time()
print('elapsed:{}'.format(end_time-start_time))
print('complete!')

這次的循環(huán)次數(shù)只有兩次，輸出結(jié)果如下：

D:\anaconda\python.exe D:/bilibili大學(xué)/數(shù)據(jù)結(jié)構(gòu)與算法/第二次嘗試.py
0 500 500
200 375 425
375 200 425
500 0 500
elapsed:1.156073808670044
complete!

Process finished with exit code 0

注意運行時間：1.156073808670044，比第一次嘗試的運行時間縮短了不要太多。

針對第一次嘗試和第二次嘗試運行的時間差距，我們有怎樣的思考呢？

算法效率衡量

執(zhí)行時間反應(yīng)算法效率

對于同一問題，我們給出了兩種解決算法，在兩種算法的實現(xiàn)中，我們對程序執(zhí)行的時間進(jìn)行了測算，發(fā)現(xiàn)兩段程序執(zhí)行的時間相差懸殊（926.43秒相比于1.15秒）。
由此我們可以得出結(jié)論：實現(xiàn)算法程序的執(zhí)行時間可以反應(yīng)出算法的效率，即算法的優(yōu)劣。

單靠時間值絕對可信嗎？

假設(shè)我們將第二次嘗試的算法程序運行在一臺配置古老性能低下的計算機(jī)中，情況會如何？很可能運行的時間并不會比在我們的電腦中運行算法一的926.43秒快多少。
單純依靠運行的時間來比較算法的優(yōu)劣并不一定是客觀準(zhǔn)確的！
程序的運行離不開計算機(jī)環(huán)境（包括硬件和操作系統(tǒng)），這些客觀原因會影響程序運行的速度并反應(yīng)在程序的執(zhí)行時間上。那么如何才能客觀的評判一個算法的優(yōu)劣呢？

時間復(fù)雜度與“大O記法”

我們假定計算機(jī)執(zhí)行算法每一個基本操作的時間是固定的一個時間單位，那么有多少個基本操作就代表會花費多少時間單位。算然對于不同的機(jī)器環(huán)境而言，確切的單位時間是不同的，但是對于算法進(jìn)行多少個基本操作（即花費多少時間單位）在規(guī)模數(shù)量級上卻是相同的，由此可以忽略機(jī)器環(huán)境的影響而客觀的反應(yīng)算法的時間效率。

對于算法的時間效率，我們可以用“大O記法”來表示。

“大O記法”：對于單調(diào)的整數(shù)函數(shù)f，如果存在一個整數(shù)函數(shù)g和實常數(shù)c>0，使得對于充分大的n總有f(n)<=c*g(n)，就說函數(shù)g是f的一個漸近函數(shù)（忽略常數(shù)），記為f(n)=O(g(n))。也就是說，在趨向無窮的極限意義下，函數(shù)f的增長速度受到函數(shù)g的約束，亦即函數(shù)f與函數(shù)g的特征相似。

時間復(fù)雜度：假設(shè)存在函數(shù)g，使得算法A處理規(guī)模為n的問題示例所用時間為T(n)=O(g(n))，則稱O(g(n))為算法A的漸近時間復(fù)雜度，簡稱時間復(fù)雜度，記為T(n)

以上是數(shù)學(xué)問題，類似于高等數(shù)學(xué)的極限，下邊我會根據(jù)具體事例，具體說明。

如何理解“大O記法”

對于算法進(jìn)行特別具體的細(xì)致分析雖然很好，但在實踐中的實際價值有限。對于算法的時間性質(zhì)和空間性質(zhì)，最重要的是其數(shù)量級和趨勢，這些是分析算法效率的主要部分。而計量算法基本操作數(shù)量的規(guī)模函數(shù)中那些常量因子可以忽略不計。
例如，可以認(rèn)為3n^2 和 100n^2屬于同一個量級，如果兩個算法處理同樣規(guī)模實例的代價分別為這兩個函數(shù)，就認(rèn)為它們的效率“差不多”，都為 n^2級。

最壞時間復(fù)雜度

分析算法時，存在幾種可能的考慮：

算法完成工作最少需要多少基本操作，即最優(yōu)時間復(fù)雜度
算法完成工作最多需要多少基本操作，即最壞時間復(fù)雜度
算法完成工作平均需要多少基本操作，即平均時間復(fù)雜度
對于最優(yōu)時間復(fù)雜度，其價值不大，因為它沒有提供什么有用信息，其反映的只是最樂觀最理想的情況，沒有參考價值。

對于最壞時間復(fù)雜度，提供了一種保證，表明算法在此種程度的基本操作中一定能完成工作。對于平均時間復(fù)雜度，是對算法的一個全面評價，因此它完整全面的反映了這個算法的性質(zhì)。但另一方面，這種衡量并沒有保證，不是每個計算都能在這個基本操作內(nèi)完成。而且，對于平均情況的計算，也會因為應(yīng)用算法的實例分布可能并不均勻而難以計算。
因此，我們主要關(guān)注算法的最壞情況，亦即最壞時間復(fù)雜度。

時間復(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ù)雜度都是指最壞時間復(fù)雜度

算法分析(規(guī)模設(shè)置為n)

第一次嘗試的算法核心部分

for a in range(0,1001):
    for b in range(0, 1001):
        for c in range(0, 1001):
            if a**2+b**2==c**2 and a+b+c == 1000:
                print(a,b,c)

時間復(fù)雜度：
T（n） = O(n * n * n * (1 + 1)）
根據(jù)時間復(fù)雜度的規(guī)則，我們只取同等數(shù)量級（也就是極限法則），忽略常數(shù)項和次要項
故T（n） = O(n^3）
同理我們看看第二次嘗試。

第二次嘗試的算法核心部分

for a in range(0,1001):
    for b in range(0, 1001):
        c = 1000 - a - b
        if a**2+b**2 == c**2 :
            print(a,b,c)

時間復(fù)雜度：
T（n） = O(n * n * (1 + 1 + 1)）
根據(jù)時間復(fù)雜度的規(guī)則，我們只取同等數(shù)量級（也就是極限法則），忽略常數(shù)項和次要項
故T（n） = O(n^2）

由此可見，我們嘗試的第二種算法要比第一種算法的時間復(fù)雜度好多的。

常見時間復(fù)雜度

注意，經(jīng)常將log2n（以2為底的對數(shù)）簡寫成logn

常見時間復(fù)雜度之間的關(guān)系

所消耗的時間從小到大

練習(xí)：時間復(fù)雜度練習(xí)( 參考算法的效率規(guī)則判斷 )
O(5)
O(2n + 1)
O(n2+ n + 1)
O(3n3+1)
對應(yīng)的答案分別為：O(1) ，O(n) ，O(n2) ，O(n3)

Python內(nèi)置類型性能分析

timeit模塊

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

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

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

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

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

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

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

list的操作測試


def test_1():
    li = []
    for i in range(1000):
        li = li + [i]#兩個列表相加才是列表，故[i]
def test_2():
    li = []
    for i in range(1000):
        li += [i]#道理同上
def test_3():
    li = []
    for i in range(1000):
        li.append(i)
def test_4():
    li = []
    li = [i for i in range(1000)]
def test_5():
    li = []
    li = list(range(1000))
def test_6():
   li = []
   for i in range(1000):
      li.extend([i])
   #extend()能接收列表和可遍歷的對象，append()只能接收單個元素
def test_7():
   li = []
   for i in range(1000):
      li.insert(0,i)

import timeit

t_1 = timeit.Timer('test_1()','from __main__ import test_1')
print('li = li + [i] uses {} seconds'.format(t_1.timeit(1000)))
print('li += [i] uses {} seconds'.format(timeit.Timer('test_2()','from __main__ import test_2').timeit(1000)))
print('li.append(i) uses {} seconds'.format(timeit.Timer('test_3()','from __main__ import test_3').timeit(1000)))
print('[i for i in range(1000)] uses {} seconds'.format(timeit.Timer('test_4()','from __main__ import test_4').timeit(1000)))
print('li = list(range(1000)) uses {} seconds'.format(timeit.Timer('test_5()','from __main__ import test_5').timeit(1000)))
print('li.extend([i]) uses {} seconds'.format(timeit.Timer('test_6()','from __main__ import test_6').timeit(1000)))
print('li.insert(i) uses {} seconds'.format(timeit.Timer('test_7()','from __main__ import test_7').timeit(1000)))

輸出結(jié)果：

D:\anaconda\python.exe D:/bilibili大學(xué)/數(shù)據(jù)結(jié)構(gòu)與算法/list運算時間比較.py
li = li + [i] uses 1.1192282000000002 seconds
li += [i] uses 0.06146549999999995 seconds
li.append(i) uses 0.06267580000000006 seconds
[i for i in range(1000)] uses 0.025689500000000143 seconds
li = list(range(1000)) uses 0.010555199999999987 seconds
li.extend([i]) uses 0.09602200000000005 seconds
li.insert(i) uses 0.37362589999999996 seconds

Process finished with exit code 0

對比一下結(jié)果，除了li = li + [i] 我不推薦使用，其他也還行?。?br> 具體分別請參考：https://www.cnblogs.com/chenshichenyin/p/9363830.html

pop操作測試

import timeit
x = list(range(2000))
# print(x.pop(0))
# print(x.pop(-1))
print('x.pop(0) uses {} seconds'.format(timeit.Timer('x.pop(0)','from __main__ import x').timeit(1000)))
print('x.pop(-1) user {} seconds'.format(timeit.Timer('x.pop(-1)','from __main__ import x').timeit(1000)))
#x.pop(0)是從開頭開始刪除
#x.pop(-1)是從后面開始

執(zhí)行結(jié)果：

D:\anaconda\python.exe D:/bilibili大學(xué)/數(shù)據(jù)結(jié)構(gòu)與算法/pop函數(shù)測試.py
x.pop(0) uses 0.0002253000000000116 seconds
x.pop(-1) user 7.419999999999649e-05 seconds

Process finished with exit code 0

注意x.pop(-1)的運行用時最后是e-05

測試pop操作：從結(jié)果可以看出，pop最后一個元素的效率遠(yuǎn)遠(yuǎn)高于pop第一個元素
可以自行嘗試下list的append(value)和insert(0,value),即一個后面插入和一個前面插入？？？

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

針對上述表格，簡要做一些說明：

Operation	Big-O Eifficiency	Interpretation
index x[ ]	O(1)	x=[1,2,3,4]，問你x [1]，x[2]等于什么
index assignment	O(1)	賦值，x = [1,2,3,4,5]，x[2]=8，x=[1, 2, 8, 4, 5]
append	O(1)	就是在隊尾追加元素
pop()	O(1)	相當(dāng)于尾部往外彈出元素，也就是從尾部取出元素
pop(i)	O(n)	指定位置彈出元素，考慮最壞復(fù)雜度，也就是i 在頭部，從頭部彈出元素，n為列表長度，故為O(n)
insert(i,item)	O(n)	標(biāo)識在哪個位置上插入元素，最壞是在頭部插入元素，相當(dāng)于遍歷了一遍，故也是O(n)
del operator	O(n)	刪除要一個一個元素的刪除
iteration	O(n)	這個就是迭代，類似于for循環(huán)
contains (in)	O(n)	利用 in 查看元素是否在列表內(nèi)，肯定要遍歷一下
get slice [x:y]	O(k)	取切片，首先定位到x的位置，這是O（1）然后x+k = y,故我們可以理解k的意思了
del slice	O(n)	刪除一個切片后，后面的部分會前移，考慮最壞是切掉第一個元素，故為O(n)
set slice	O(n+k)	步驟是先刪除列表中即講被替換的部分，是O(n)，然后將切片的內(nèi)容加進(jìn)去，就是k個元素，所以為O（n+k）
reverse	O(n)	是列表反向輸出
concatenate	O(k)	相當(dāng)于兩個列表相加，第二個列表有k個元素
sort	O(nlogn)	排序有關(guān)，暫且不說
multiply	O(nk)	一個列表乘一個常數(shù)k

主要要理解索引，隊尾追加，彈出，插入，查找

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

針對上述表格，簡要做一些說明:

Operation	Big-O Eifficiency	Interpretation
copy	O(n)	復(fù)制，把字典中所有元素再生成一遍，故O(n)
get item	O(1)	通過鍵，獲取值
set item	O(1)	設(shè)置字典
delete tem	O(1)	刪除字典鍵
contains(in)	O(1)	包含在字典中不需要遍歷
iteration	O(n)	迭代

數(shù)據(jù)結(jié)構(gòu)

我們?nèi)绾斡肞ython中的類型來保存一個班的學(xué)生信息？如果想要快速的通過學(xué)生姓名獲取其信息呢？
實際上當(dāng)我們在思考這個問題的時候，我們已經(jīng)用到了數(shù)據(jù)結(jié)構(gòu)。列表和字典都可以存儲一個班的學(xué)生信息，但是想要在列表中獲取一名同學(xué)的信息時，就要遍歷這個列表，其時間復(fù)雜度為O(n)，而使用字典存儲時，可將學(xué)生姓名作為字典的鍵，學(xué)生信息作為值，進(jìn)而查詢時不需要遍歷便可快速獲取到學(xué)生信息，其時間復(fù)雜度為O(1)。
我們?yōu)榱私鉀Q問題，需要將數(shù)據(jù)保存下來，然后根據(jù)數(shù)據(jù)的存儲方式來設(shè)計算法實現(xiàn)進(jìn)行處理，那么數(shù)據(jù)的存儲方式不同就會導(dǎo)致需要不同的算法進(jìn)行處理。我們希望算法解決問題的效率越快越好，于是我們就需要考慮數(shù)據(jù)究竟如何保存的問題，這就是數(shù)據(jù)結(jié)構(gòu)。
在上面的問題中我們可以選擇Python中的列表或字典來存儲學(xué)生信息。列表和字典就是Python內(nèi)建幫我們封裝好的兩種數(shù)據(jù)結(jié)構(gòu)。

概念

數(shù)據(jù)是一個抽象的概念，將其進(jìn)行分類后得到程序設(shè)計語言中的基本類型。如：int，float，char等。數(shù)據(jù)元素之間不是獨立的，存在特定的關(guān)系，這些關(guān)系便是結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)指數(shù)據(jù)對象中數(shù)據(jù)元素之間的關(guān)系。
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ù)結(jié)構(gòu)的區(qū)別

數(shù)據(jù)結(jié)構(gòu)只是靜態(tài)的描述了數(shù)據(jù)元素之間的關(guān)系。
高效的程序需要在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上設(shè)計和選擇算法。
程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法
總結(jié)：算法是為了解決實際問題而設(shè)計的，數(shù)據(jù)結(jié)構(gòu)是算法需要處理的問題載體

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

抽象數(shù)據(jù)類型(ADT)的含義是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。即把數(shù)據(jù)類型和數(shù)據(jù)類型上的運算捆在一起，進(jìn)行封裝。引入抽象數(shù)據(jù)類型的目的是把數(shù)據(jù)類型的表示和數(shù)據(jù)類型上運算的實現(xiàn)與這些數(shù)據(jù)類型和運算在程序中的引用隔開，使它們相互獨立。

最常用的數(shù)據(jù)運算有五種：

插入
刪除
修改
查找
排序

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

引入算法概念+時間復(fù)雜度

引入算法概念+時間復(fù)雜度

引入

第一次嘗試

算法的提出

算法的概念

算法的五大特性

第二次嘗試

算法效率衡量

執(zhí)行時間反應(yīng)算法效率

單靠時間值絕對可信嗎？

時間復(fù)雜度與“大O記法”

對于算法的時間效率，我們可以用“大O記法”來表示。

如何理解“大O記法”

最壞時間復(fù)雜度

時間復(fù)雜度的幾條基本計算規(guī)則

算法分析(規(guī)模設(shè)置為n)

常見時間復(fù)雜度

常見時間復(fù)雜度之間的關(guān)系

Python內(nèi)置類型性能分析

timeit模塊

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

list的操作測試

pop操作測試

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

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

數(shù)據(jù)結(jié)構(gòu)

概念

算法與數(shù)據(jù)結(jié)構(gòu)的區(qū)別

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

最常用的數(shù)據(jù)運算有五種：

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

引入算法概念+時間復(fù)雜度

引入

第一次嘗試

算法的提出

算法的概念

算法的五大特性

第二次嘗試

算法效率衡量

執(zhí)行時間反應(yīng)算法效率

單靠時間值絕對可信嗎？

時間復(fù)雜度與“大O記法”

對于算法的時間效率，我們可以用“大O記法”來表示。

如何理解“大O記法”

最壞時間復(fù)雜度

時間復(fù)雜度的幾條基本計算規(guī)則

算法分析(規(guī)模設(shè)置為n)

常見時間復(fù)雜度

常見時間復(fù)雜度之間的關(guān)系

Python內(nèi)置類型性能分析

timeit模塊

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

list的操作測試

pop操作測試

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

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

數(shù)據(jù)結(jié)構(gòu)

概念

算法與數(shù)據(jù)結(jié)構(gòu)的區(qū)別

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

最常用的數(shù)據(jù)運算有五種：

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

單靠時間值絕對可信嗎？

對于算法的時間效率，我們可以用“大O記法”來表示。