大一下-數(shù)算sessdsa-02algoana數(shù)據(jù)結(jié)構(gòu)與算法Python02

〉本章目標(biāo)〉算法分析大O表示法例子：“變位詞”判斷問題〉

Python數(shù)據(jù)結(jié)構(gòu)的性能列表List字典Dictionary地球與空間科學(xué)學(xué)院//2015本章目標(biāo)〉

了解算法分析的重要性〉

能夠采用“大O”表示法來描述算法執(zhí)行時間〉

了解Python列表和字典類型中通用操作執(zhí)行時間的“大O”級別；〉

了解Python數(shù)據(jù)類型的具體實現(xiàn)對算法分析的影響；〉

了解如何對簡單Python程序進(jìn)行執(zhí)行時間檢測。地球與空間科學(xué)學(xué)院//2015算法分析〉

如何對比兩個程序？看起來不同，但解決同一個問題的程序，哪個“更好”？〉

程序和算法的區(qū)別算法是對問題解決的分步描述程序則是采用某種編程語言實現(xiàn)的算法，同一個算法通過不同的程序員采用不同的編程語言，能產(chǎn)生很多程序〉來看一段程序，完成從1到n的累加，輸出總和設(shè)置累計變量=0從1到n循環(huán)，逐次累加到累計變量返回累計變量def

sumOfN(n):theSum

=

0for

i

in

range(1,n+1):theSum

=

theSum

+

ireturn

theSumprint(sumOfN(10))地球與空間科學(xué)學(xué)院//2015算法分析〉

再看第二段程序，是否感覺怪怪的？但實際上本程序功能與前面那段相同這段程序失敗之處在于：變量命名有無用的

代碼〉

比較程序的“好壞”，有

因素代碼風(fēng)格、可讀性等等〉

本課程中，

主要感的是算法本身特性〉

算法分析主要就是從計算資源消耗的角度來評判和比較算法更高效利用計算資源，或者更少占用資源的算法，就是好算法從這個角度，前述兩段程序?qū)嶋H上是基本相同的，它們都采用了一樣的算法來解決累計求和問題def

foo(tom):fred

=

0for

bill

in

range(1,tom+1):barney

=

billfred

=

fred

+

barneyreturn

fredprint(foo(10))地球與空間科學(xué)學(xué)院//2015說到代碼風(fēng)格和可讀性〉

為什么Python的語句塊強(qiáng)制縮進(jìn)是好的？語句塊功能和視覺效果〉

蘋果公司的一個低級Bug造成SSL連接驗證被跳過2014.2.22修正iOS7.0.6〉

不像看起來那樣運(yùn)行〉

還有下面這樣地球與空間科學(xué)學(xué)院//2015數(shù)據(jù)結(jié)構(gòu)與算法（Pytho）計算資源指標(biāo)〉

那么何為計算資源？〉

一種是算法解決問題過程中需要的

空間或內(nèi)存但

空間受到問題自身數(shù)據(jù)規(guī)模的變化影響要區(qū)分哪些

空間是問題本身描述所需，哪些是算法占用，不容易〉

另一種是算法的執(zhí)行時間可以對程序進(jìn)行實際運(yùn)

試，獲得真實的運(yùn)行時間〉

Python中有一個time模塊，可以獲取計算機(jī)系統(tǒng)當(dāng)前時間在算法開始前和結(jié)束后分別記錄系統(tǒng)時間，即可得到運(yùn)行時間>>>

import

time>>>

time.time()1426317539.975>>>

print

time.time.

doc

time()

->

floating

point

numberReturn

the

current

time

in

seconds

since

the

Epoch.Fractions

of

a

second

may

be

present

if

the

systemclock

provides

them.1970/1/1

00:00:00地球與空間科學(xué)學(xué)院//2015運(yùn)行時間檢測〉

累計求和程序的運(yùn)行時間檢測增加了總運(yùn)行時間函數(shù)返回一個元組tuple包括累計和，以及運(yùn)行時間（秒）〉

在交互窗口連續(xù)運(yùn)行5次看看1到10,000累加每次運(yùn)行約需0.0019秒import

timedef

sumOfN2(n):start

=

time.time()theSum

=

0for

i

in

range(1,n+1):theSum

=

theSum

+

iend

=

time.time()return

theSum,end-start>>>for

i

in

range(5):print("Sum

is

%d

required

%10.7f

seconds"%sumOfN2(10000))Sumis50005000required0.0018950secondsSumis50005000required0.0018620secondsSumis50005000required0.0019171secondsSumis50005000required0.0019162secondsSumis50005000required0.0019360seconds地球與空間科學(xué)學(xué)院//2015運(yùn)行時間檢測〉

如果累加到100,000？看起來運(yùn)行時間增加到10,000的10倍>>>for

i

in

range(5):print("Sum

is

%d

required

%10.7f

seconds"%sumOfN2(100000))Sumis5000050000required0.0199420secondsSumis5000050000required0.0180972secondsSumis5000050000required0.0194821secondsSumis5000050000required0.0178988secondsSumis5000050000required0.0188949seconds〉

進(jìn)一步累加到1,000,000？運(yùn)行時間又是100,000的10倍了>>>for

i

in

range(5):print("Sum

is

%d

required

%10.7f

seconds"%sumOfN2(1000000))Sumis500000500000required0.1948988secondsSumis500000500000required0.1850290secondsSumis500000500000required0.1809771secondsSumis500000500000required0.1729250secondsSumis500000500000required0.1646299seconds地球與空間科學(xué)學(xué)院//2015第二種無迭代的累計算法〉

利用求和公式的無迭代算法〉

采用同樣的方法檢測運(yùn)行時間10,000;

100,000;

1,000,00010,000,000;

100,000,000def

sumOfN3(n):return

(n*(n+1))/2print(sumOfN3(10))Sumis50005000

required

0.00000095

secondsSumis5000050000

required

0.00000191

secondsSumis500000500000

required

0.00000095

secondsSumis50000005000000

required

0.00000095

secondsSumis5000000050000000

required

0.00000119

seconds〉

需要關(guān)注的兩點這種算法的運(yùn)行時間比前種都短很多運(yùn)行時間與累計對象n的大小沒有關(guān)系（前種算法是倍數(shù)增長關(guān)系）〉

新算法運(yùn)行時間幾乎與需要累計的數(shù)目無關(guān)地球與空間科學(xué)學(xué)院//2015運(yùn)行時間檢測的分析〉

觀察一下第一種迭代算法包含了一個循環(huán)，可能會執(zhí)行

語句這個循環(huán)運(yùn)行次數(shù)跟累加值n有關(guān)系，n增加，循環(huán)次數(shù)也增加〉

但關(guān)于運(yùn)行時間的實際檢測，有點問題關(guān)于編程語言和運(yùn)行環(huán)境〉

同一個算法，采用不同的編程語言編寫，放在不同的機(jī)器上運(yùn)行，得到的運(yùn)行時間會不一樣〉

有時候會大不一樣比如把非迭代算法放在老舊機(jī)器上跑，甚至可能慢過新機(jī)器上的迭代算法〉

所以

需要更好的方法來衡量算法的運(yùn)行時間這個指標(biāo)與具體的機(jī)器、程序、運(yùn)行時段，與編譯器都無關(guān)地球與空間科學(xué)學(xué)院//2015數(shù)據(jù)結(jié)構(gòu)與算法（Pytho）大O表示法（Big-O）〉

分析SumOfN的賦值語句數(shù)量對于“問題規(guī)?！眓賦值語句數(shù)量T(n)=1+n〉

一個算法所實施的操作數(shù)量或者步驟數(shù)可以作為獨立于具體程序或機(jī)器的度量指標(biāo)哪種操作跟算法的具體實現(xiàn)無關(guān)？需要一種通用的基本操作來作為運(yùn)行步驟的計量單位〉

賦值語句是一個合適的選擇一條賦值語句同時包含了（表達(dá)式）計算和（變量）兩個基本資源仔細(xì)觀察程序設(shè)計語言特性，除了與計算資源無關(guān)的定義語句之外，主要就是三種控制流語句和賦值語句，而控制流僅僅起了組織賦值語句的作用，并不實施處理。def

sumOfN(n):theSum

=

theSum

+

ireturn

theSumprint(sumOfN(10))1theSum

=

0nfor

i

in

range(1,n+1):1地球與空間科學(xué)學(xué)院//2015大O表示法（Big-O）〉

問題規(guī)模影響算法執(zhí)行時間n個自然數(shù)累計求和的算法中，需要累計的自然數(shù)個數(shù)合適作為問題規(guī)模的指標(biāo)前100,000個自然數(shù)求和對比前1,000個自然數(shù)求和，算是同一問題的更大規(guī)模算法分析的目標(biāo)是要找出問題規(guī)模會怎么影響一個算法的執(zhí)行時間〉

數(shù)量級函數(shù)（Order

of

Magnitude

function）基本操作數(shù)量函數(shù)T(n)的精確值并不是特別重要，重要的是T(n)中起決定性因素的主導(dǎo)部分用動態(tài)的眼光看，就是當(dāng)問題規(guī)模增大的時候，T(n)中的一些部分會蓋過其它部分的貢獻(xiàn)數(shù)量級函數(shù)描述了T(n)中隨著n增加而增加速度最快的部分稱作“大O”表示法，記作O(f(n))，其中f(n)表示T(n)中的主導(dǎo)部分地球與空間科學(xué)學(xué)院//2015確定運(yùn)行時間數(shù)量級大O的方法〉

例1：T(n)=1+n當(dāng)n增大時，常數(shù)1在最終結(jié)果中顯得越來越無足輕重所以可以去掉1，保留n作為主要部分，運(yùn)行時間數(shù)量級就是O(n)〉

例2：T(n)=5n2+27n當(dāng)n很小時，常數(shù)1005其決定性作用但當(dāng)n越來越大，n2項就越來越重要，其它兩項對結(jié)果的影響則越來越小同樣，n2項中的系數(shù)5，對于n2的增長速度來說也影響不大所以可以在數(shù)量級中去掉27n

，以及系數(shù)5的部分，確定為O(n2)〉

有時候，決定運(yùn)行時間的不僅僅是問題規(guī)模，某些具體數(shù)據(jù)也會影響算法的運(yùn)行時間分為最好、

和平均情況，平均狀況體現(xiàn)了算法的主流性能對算法的分析要看主流，而不被某幾種特定的運(yùn)行狀況所迷惑地球與空間科學(xué)學(xué)院//2015常見的大O數(shù)量級函數(shù)〉

通常當(dāng)n較小時，難以確定其數(shù)量級〉

當(dāng)n增長到較大時，容易看出其主要變化量級f(n)名稱1常數(shù)log

n對數(shù)n線性n

log

n對數(shù)線性n2平方n3立方2n指數(shù)地球與空間科學(xué)學(xué)院//2015從代碼分析確定執(zhí)行時間數(shù)量級函數(shù)〉

代碼賦值語句可以分為4個部分T(n)=3+3n2+2n+1=3n2+2n+4〉

僅保留最高階項n2，去掉所有系數(shù)〉

數(shù)量級為O(n2)a=5b=6c=10for

i

in

range(n):for

j

inrange(n):x

=

i

*

iy

=

j

*

jz

=

i

*

jfor

k

in

range(n):w

=

a*k

+

45v

=

b*bd

=

33地球與空間科學(xué)學(xué)院//2015隨堂作業(yè)2-1〉

寫兩個Python函數(shù)，功能為找到列表中最小數(shù)別用list.sort()〉

要求函數(shù)1將每個數(shù)與其它所有數(shù)比較，運(yùn)行時間數(shù)量級為O(n2)〉

要求函數(shù)2數(shù)量級為O(n)〉

3種提交方法電腦/

：從課程 找到作業(yè)提交表單直接輸入代碼提交：寫在紙上（包括學(xué)號 ）拍照，從

表單上傳附件提交紙質(zhì)：直接交紙質(zhì)版（包括學(xué)號

）〉表單

見

“chbpku”菜單“教學(xué)課程”->“數(shù)據(jù)結(jié)構(gòu)與算法”defmin1(lst):defmin2(lst):地球與空間科學(xué)學(xué)院//2015“變位詞”判斷問題〉

“變位詞”判斷問題可以很好地展示不同數(shù)量級的算法〉

問題描述所謂“變位詞”是指兩個詞之間存在組成字母的重新排列關(guān)系如：heart和earth，python和typhon為了簡單起見，假設(shè)參與判斷的兩個詞僅由小寫字母構(gòu)成，而且長度相等〉

解題目標(biāo)：寫一個bool函數(shù)，以兩個詞作為參數(shù)，返回真假，表示這兩個詞是否變位詞地球與空間科學(xué)學(xué)院//2015解法1：逐字檢查〉

解法思路為將字符串1中的字符逐個到字符串2中檢查是否存在，存在就“打勾”標(biāo)記（防止重復(fù)檢查），如果每個字符都能找到，則兩個詞是變位詞，只要有1個字符找不到，就不是變位詞〉

程序技巧實現(xiàn)“打勾”標(biāo)記：將字符串2對應(yīng)字符設(shè)為None由于字符串是不可變類型，需要先 到列表中p

y

t

h

o

nt

y

p

h

o

n地球與空間科學(xué)學(xué)院//2015數(shù)據(jù)結(jié)構(gòu)與算法（Pytho）def

anagramSolution1(s1,s2):alist

=

list(s2)pos1

=

0stillOK

=

Truewhile

pos1

<

len(s1)

and

stillOK:pos2

=

0found

=Falsewhile

pos2

<

len(alist)

and

not

found:if

s1[pos1]

==

alist[pos2]:found

=

Trueelse:pos2

=

pos2

+

1if

found:alist[pos2]

=

Noneelse:stillOK

=

Falsepos1

=

pos1

+

1return

stillOKprint(anagramSolution1('abcd','dcba'))解法1：逐字檢查-程序代碼s2到列表循環(huán)s1的每個字符在s2列表逐個對比找到，打勾未找到，失敗地球與空間科學(xué)學(xué)院//2015解法1：逐字檢查-算法分析〉

問題規(guī)模：詞中包含的字符個數(shù)n〉

主要部分在于兩重循環(huán)〉

外重循環(huán)要遍歷字符串1每個字符，將內(nèi)層循環(huán)執(zhí)行n次〉

而內(nèi)重循環(huán)在字符串2中查找字符，每查找一個字符的操作次數(shù)，分別是1、2、3……n中的一個，而且各不相同〉

所以總執(zhí)行次數(shù)是1+2+3+……+n〉

可知其數(shù)量級為O(n2)地球與空間科學(xué)學(xué)院//2015解法2：排序比較〉

解題思路為：將兩個字符串都按照字母順序排好序，再逐個字符對比是否相同，如果相同則是變位詞p

y

t

h

o

nt

y

p

h

o

nh

n

o

p

t

yh

n

o

p

t

y排序地球與空間科學(xué)學(xué)院//2015解法2：排序比較def

anagramSolution2(s1,s2):alist1

=

list(s1)

alist2

=

list(s2)alist1.sort()alist2.sort()pos

=

0matches

=

Truewhile

pos

<

len(s1)

and

matches:ifalist1[pos]==alist2[pos]:pos

=

pos

+

1else:matches

=

Falsereturn

matchesprint(anagramSolution2('abcde','edcba'))print(anagramSolution1('abcd','dcba'))分別都排序逐個對比地球與空間科學(xué)學(xué)院//2015解法2：排序比較-算法分析〉

粗看上去，本算法只有一個循環(huán)，最多執(zhí)行n次，數(shù)量級應(yīng)該是O(n)〉

但循環(huán)前面的兩個sort并不是無代價的〉

如果查詢下后面的章節(jié)，會發(fā)現(xiàn)排序算法采用不同的解決方案，其運(yùn)行時間數(shù)量級差不多是O(n2)或者O(n

log

n)，大過循環(huán)的O(n)〉

所以本算法中其決定性作用的步驟是排序步驟〉

本算法的運(yùn)行時間數(shù)量級就等于排序過程的數(shù)量級O(n

log

n)地球與空間科學(xué)學(xué)院//2015解法3：

法〉法解題思路為：窮盡所有可能組合〉

對于變位詞問題來說，

法具體是，將字符串1中出現(xiàn)的字母進(jìn)行全排列，再查看字符串2是否出現(xiàn)在全排列列表中〉

這里最大的

是產(chǎn)生字符串1所有字母的全排列，根據(jù)組合數(shù)學(xué)的〉結(jié)論，如果n個字符進(jìn)行全排列，其所有可能的字符串個數(shù)為n!已知n!的增長速度甚至超過2n例如，對于20個字符長的詞來說，將產(chǎn)生20!=2,432,902,008,176,640,000

個候選詞如果每秒鐘處理一個候選詞的話，需要77,146,816,596年（百億）的時間來做完所有的匹配?！?/p>

結(jié)論：

法恐怕不能算是個好算法地球與空間科學(xué)學(xué)院//2015解法4：計數(shù)比較〉

最后一個算法解題思路為：對比兩個字符串中每個字母出現(xiàn)的次數(shù)，如果26個字母出現(xiàn)的次數(shù)都相同的話，這兩個字符串就一定是變位

詞〉

具體做法：為每個字符串設(shè)置一個26位的計數(shù)器，先檢查每個字符串，在計數(shù)器中設(shè)定好每個字母出現(xiàn)的次數(shù)〉

計數(shù)完成后，進(jìn)入比較階段，看兩個字符串的計數(shù)器是否相同，如果相同則輸出是變位詞的結(jié)論地球與空間科學(xué)學(xué)院//2015def

anagramSolution4(s1,s2):c1

=

[0]*26c2

=

[0]*26for

i

in

range(len(s1)):pos

=

ord(s1[i])-ord('a')c1[pos]

=

c1[pos]

+

1for

i

in

range(len(s2)):pos

=

ord(s2[i])-ord('a')c2[pos]

=

c2[pos]

+

1j

=

0stillOK

=

Truewhile

j<26

and

stillOK:if

c1[j]==c2[j]:j

=

j

+

1else:stillOK

=

Falsereturn

stillOKprint(anagramSolution4('apple','pleap'))解法4：計數(shù)比較-程序代碼分別都計數(shù)計數(shù)器比較地球與空間科學(xué)學(xué)院//2015解法4：計數(shù)比較-算法分析〉

計數(shù)比較算法中有3個循環(huán)迭代，但不象解法1那樣存在嵌套循壞前兩個循環(huán)用于對字符串進(jìn)行計數(shù)，操作次數(shù)等于字符串長度n第3個循環(huán)用于計數(shù)器比較，操作次數(shù)總是26次〉

所以總操作次數(shù)T(n)=2n+26，其數(shù)量級為O(n)，這是一個線性數(shù)量級的算法，是4個變位詞判斷算法中性能最優(yōu)的?！?/p>

值得注意的是，本算法依賴于兩個長度為26的計數(shù)器列表，來保存字符計數(shù)，這相比前3個算法需要

的

空間由于僅限于26個字母構(gòu)成的詞，本算法對空間額外的需求并不明顯，但如果考慮由大字符集構(gòu)成的詞（如中文具有上萬不同字符），情況就會有所改變?！?/p>

犧牲

空間來換取運(yùn)行時間，或者相反，這種在時間空間之間的取舍和權(quán)衡，在選擇問題解法的過程中經(jīng)常會出現(xiàn)。地球與空間科學(xué)學(xué)院//2015隨堂作業(yè)2-2〉

判斷下列代碼段的大O級別A.

O(n) B.

O(n^2) C.

O(log

n)

D.

O(n^3)〉

Q1：〉

Q2：〉

Q3：test

=

0for

i

in

range(n):for

j

inrange(n):test

=

test

+

i

*

jtest

=

0for

i

in

range(n):test

=

test

+

1for

j

in

range(n):test

=

test

-

1i

=

nwhile

i

>

0:k

=

2

+

2i

=

i

//

2地球與空間科學(xué)學(xué)院//2015Python數(shù)據(jù)結(jié)構(gòu)的性能〉

前面

了解了“大O表示法”以及對不同的算法的評估〉

下面來

下Python兩種內(nèi)置數(shù)據(jù)結(jié)構(gòu)上

的大O數(shù)量級列表List和字典Dictionary這是兩種重要的Python數(shù)據(jù)結(jié)構(gòu)，后面的課程會用來實現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)通過運(yùn)行試驗來確定其 的運(yùn)行時間數(shù)量級〉

對比List和Dictionary類型索引添加刪除更新正查反查其它List連續(xù)整數(shù)iappendextendinsertpopremove*a[i]=va[i]a[i:j]index(v)count(v)reversesortDict不可變類型值kb[k]=vpopb[k]=vb[k]copy無has_keyupdate地球與空間科學(xué)學(xué)院//2015List數(shù)據(jù)結(jié)構(gòu)〉

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

（interface）的實現(xiàn)方法有很多，如何選擇具體采用哪種實現(xiàn)方法？〉

總的方案就是，讓最常用的操作性能最好，犧牲不太常用的操作80/20準(zhǔn)則：80%的功能其使用率只有20%〉來看一些常用的List操作〉

最常用的是：按索引取值和賦值（v=

a[i],

a[i]=

v）由于列表的隨機(jī)

特性，這兩個操作執(zhí)行時間與列表大小無關(guān)，均為O(1)〉

另一個是列表增長，可以選擇append()和

add

()lst.append(v)，執(zhí)行時間是O(1)lst=lst+[v]，執(zhí)行時間是O(n+k)，其中k是被加的列表長度如何選擇具體方法，決定了程序的性能地球與空間科學(xué)學(xué)院//20154種生成前n個整數(shù)列表的方法〉

第

法是用循環(huán)連接列表（+）方式生成〉

然后是用append()方法來添加元素生成〉

接著用列表推導(dǎo)式（List

Comprehension）來做〉

最后是range函數(shù)調(diào)用轉(zhuǎn)成列表列表推導(dǎo)式地球與空間科學(xué)學(xué)院//2015地球與空間科學(xué)學(xué)使用timeit模塊對函數(shù)計時〉

對于每個函數(shù)具體的執(zhí)行時間，timeit模塊提供了一種在一致的運(yùn)行環(huán)境下可以反復(fù)調(diào)用并計時的機(jī)制〉

timeit計時的使用方法首先創(chuàng)建一個Timer對象，需要兩個參數(shù)，第一個是需要反復(fù)運(yùn)行的語句，第二個是為了建立運(yùn)行環(huán)境而只需要運(yùn)行一次的“安裝語句”然后調(diào)用這個對象的timeit方法，其中可以指定反復(fù)運(yùn)行多少次，計時完畢后返回以秒為單位的時間4種生成前n個整數(shù)列表的方法計時〉看到，4種方法運(yùn)行時間差別很大列表連接（concat）最慢，List

range最快，速度相差近200倍。append也要比concat快得多另外， 注意到列表推導(dǎo)式速度是append兩倍的樣子〉

當(dāng)然，如果仔細(xì)分析，嚴(yán)格來說，上述時間除了具體列表操作的耗時，應(yīng)該還包括函數(shù)調(diào)用的時間在內(nèi)。但函數(shù)調(diào)用花銷的時間是常數(shù)可以通過調(diào)用空函數(shù)來確定并從上述時間減除掉函數(shù)調(diào)用時間地球與空間科學(xué)學(xué)院//2015List基本操作的大O數(shù)量級〉〉

右表是List基本操作的數(shù)量級注意到pop這個操作pop()從列表末尾移除元素，O(1)pop(i)從列表中部移除元素，O(n)〉

原因在于Python所選擇的實現(xiàn)方法從中部移除元素的話，要把移除元素后面的元素全部向前挪位一遍這個看起來有點笨拙但后面章節(jié)會看到這種實現(xiàn)方法能夠保證列表按索引取值和賦值的操作很快，達(dá)到O(1)這也算是一種對常用操作和不常用操作的折衷方案地球與空間科學(xué)學(xué)院//2015list.pop的計時試驗〉

為了驗證表中的大O數(shù)量級，

把兩種情況下的pop操作來實際計時對比，相對同一個大小的list，分別調(diào)用pop()和pop(0)〉

并對不同大小的list做計時試驗，

期望的結(jié)果是pop()的時間不隨list大小變化，pop(0)的時間隨著list變大而變長〉

首先

看對比對于長度2百萬的列表，執(zhí)行1000次pop()時間是0.0007秒pop(0)時間是0.8秒相差1000倍地球與空間科學(xué)學(xué)院//2015list.pop的計時試驗〉通過改變列表的大小來測試兩個操作的增長趨勢地球與空間科學(xué)學(xué)院//2015list.pop的計時試驗〉

通過將試驗數(shù)據(jù)畫成圖表，可以看出增長趨勢pop()是平坦的常數(shù)pop(0)是線性增長的趨勢〉

其中散落的點是誤差導(dǎo)致系統(tǒng)中其它進(jìn)程調(diào)度資源占用等地球與空間科學(xué)學(xué)院//2015Dictionary數(shù)據(jù)結(jié)構(gòu)〉

字典與列表不同，它可以根據(jù)關(guān)鍵碼（key）來找到數(shù)據(jù)項，而列表是根據(jù)位置（index）來找到數(shù)據(jù)項〉

后面的課程會介紹字典的幾種不同實現(xiàn)方法〉

最常用的取值get

item和賦值set

item操作，其性能為O(1)〉

另一個重要操作是判斷字典中是否存在某個關(guān)鍵碼（key），這個性能也是O(1)〉

某些罕見的情況下性能會劣化set/get/contains

->

O(n)后面課程講到實現(xiàn)的時候會分析地球與空間科學(xué)學(xué)院//2015List和Dictionary的in操作對比〉

設(shè)計一個性能試驗來驗證List中檢索一個值，以及Dictionary中檢索一個值的計時對比生成一個包含連續(xù)值的List和一個包含連續(xù)關(guān)鍵碼Key的Dictionary用隨機(jī)數(shù)來檢驗，采用同一個操作符in

來判斷。地球與空間科學(xué)學(xué)院//2015List和Dictionary的in操作對比〉

可見字典的執(zhí)行時間與字典規(guī)模大小無關(guān)，是常數(shù)〉

而列表的執(zhí)行時間則隨著列表的規(guī)模加大而線性上升Python〉

Python

的算法復(fù)雜度

：plexity院//2015大地球與空間科隨堂作業(yè)2-3〉

Q4:下面哪個List操作不是O(1)?list.pop(0)list.pop()list.append()list[10]以上都是O(1)〉chbpku和課程

有提交 （作業(yè)2-3）〉

Q5：下面哪個字典操作是O(1)？'x'

in

mydictdel

mydict['x']mydict['x']

==

10mydict['x']=

mydict['x']+

1以上都是O(1)地球與空間科學(xué)學(xué)院//2015Python小知識：特殊方法〉

Python有很多內(nèi)置的語句、函數(shù)和操作符，可以用在不同的類型中print

a，可以在輸出終端顯示不同類型變量的字符串形式del

a，可以銷毀對象a；del

lst[2]，可以刪除列表第3個元素len(a)，返回列表、元組或字典類型變量所包含元素的個數(shù)

int(a),float(a)，轉(zhuǎn)換整數(shù)、浮點數(shù)、字符串為整數(shù)或浮點數(shù)

a+b，可以返回整數(shù)和、浮點數(shù)和、字符串的連接、列表的連接

a*b，可以返回整數(shù)乘積、浮點數(shù)乘積、字符串重復(fù)、列表的重復(fù)〉

這些語句、函數(shù)和操作符，同樣也可以用于用戶自定義的類這些內(nèi)置的語句函數(shù)和操作符，應(yīng)用到用戶自定義的類，會產(chǎn)生什么呢？比如 定義了一個類Color，