算法基礎(chǔ)第一部分算法簡單概念算法概念復(fù)習(xí)：遞歸時間復(fù)雜度空間復(fù)雜度2023年1月30日算法基礎(chǔ)2什么是算法？算法（Algorithm）：一個計算過程，解決問題的方法2023年1月30日算法基礎(chǔ)3算法輸入輸出復(fù)習(xí)：遞歸遞歸的兩個特點：調(diào)用自身結(jié)束條件看下面幾個函數(shù)：2023年1月30日算法基礎(chǔ)4deffunc1(x):

print(x)

func1(x-1)

deffunc2(x):

ifx>0:

print(x)

func2(x+1)deffunc3(x):

ifx>0:

print(x)

func3(x-1)

deffunc4(x):

ifx>0:

func4(x-1)

print(x)時間復(fù)雜度看代碼：2023年1月30日算法基礎(chǔ)5print('HelloWorld')foriinrange(n):

print('HelloWorld')foriinrange(n):

forjinrange(n):

print('HelloWorld')foriinrange(n):

forjinrange(n):

forkinrange(n):

print('HelloWorld')左面四組代碼，哪組運行時間最短？用什么方式來體現(xiàn)代碼（算法）運行的快慢？時間復(fù)雜度類比生活中的一些事件，估計時間：眨一下眼口算“29+68”燒一壺水睡一覺完成一個項目飛船從地球飛出太陽系2023年1月30日算法基礎(chǔ)6一瞬間/幾毫秒幾秒幾分鐘幾小時幾天/幾星期/幾個月幾年時間復(fù)雜度時間復(fù)雜度：用來評估算法運行效率的一個東西2023年1月30日算法基礎(chǔ)7print('HelloWorld')foriinrange(n):

print('HelloWorld')foriinrange(n):

forjinrange(n):

print('HelloWorld')foriinrange(n):

forjinrange(n):

forkinrange(n):

print('HelloWorld')O(n2)O(n)O(1)O(n3)時間復(fù)雜度那這些代碼呢？2023年1月30日算法基礎(chǔ)8print('HelloWorld')print('HelloPython')print(‘Hello

Algorithm’)foriinrange(n):print('HelloWorld’)

forjinrange(n):

print('HelloWorld')foriinrange(n):

forjinrange(i):

print('HelloWorld')O(3)O(n2+n)O(1/2n2)O(1)O(n2)O(n2)時間復(fù)雜度2023年1月30日算法基礎(chǔ)9那這個代碼呢？whilen>1:

print(n)

n=n//2n=64輸出：64321684226=64log264=6O(log2n)或O(logn)時間復(fù)雜度-小結(jié)時間復(fù)雜度是用來估計算法運行時間的一個式子（單位）。一般來說，時間復(fù)雜度高的算法比復(fù)雜度低的算法快。常見的時間復(fù)雜度（按效率排序）O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)不常見的時間復(fù)雜度（看看就好）O(n!)

O(2n)

O(nn)

…如何一眼判斷時間復(fù)雜度？循環(huán)減半的過程O(logn)幾次循環(huán)就是n的幾次方的復(fù)雜度2023年1月30日算法基礎(chǔ)10空間復(fù)雜度空間復(fù)雜度：用來評估算法內(nèi)存占用大小的一個式子“空間換時間”2023年1月30日算法基礎(chǔ)11列表查找列表查找：從列表中查找指定元素輸入：列表、待查找元素輸出：元素下標(biāo)或未查找到元素順序查找從列表第一個元素開始，順序進行搜索，直到找到為止。二分查找從有序列表的候選區(qū)data[0:n]開始，通過對待查找的值與候選區(qū)中間值的比較，可以使候選區(qū)減少一半。2023年1月30日算法基礎(chǔ)12二分查找2023年1月30日算法基owhighmidmidmid使用二分查找來查找3列表查找-代碼2023年1月30日算法基礎(chǔ)14deflinear_search(data_set,value):

foriinrange(range(data_set)):

ifdata_set[i]==value:

returni

returndefbin_search(data_set,value):

low=0

high=len(data_set)-1

whilelow<=high:

mid=(low+high)//2

ifdata_set[mid]==value:

returnmid

elifdata_set[mid]>value:

high=mid-1

else:

low=mid+1時間復(fù)雜度O(n)O(logn)列表查找：練習(xí)現(xiàn)有一個學(xué)員信息列表（按id增序排列），格式為：修改二分查找代碼，輸入學(xué)生id，輸出該學(xué)生在列表中的下標(biāo)，并輸出完整學(xué)生信息。2023年1月30日算法基礎(chǔ)15[{id:1001,name:"張三",age:20},{id:1002,name:"李四",age:25},{id:1004,name:"王五",age:23},{id:1007,name:"趙六",age:33}]列表排序列表排序?qū)o序列表變?yōu)橛行蛄斜響?yīng)用場景：各種榜單各種表格給二分排序用給其他算法用輸入：無序列表輸出：有序列表2023年1月30日算法基礎(chǔ)16排序low

B三人組：冒泡排序選擇排序插入排序快速排序排序NB二人組：堆排序歸并排序沒什么人用的排序：基數(shù)排序希爾排序桶排序排序Low

B三人組大家自己能想到怎么完成一次排序嗎？冒泡排序選擇排序插入排序算法關(guān)鍵點：有序區(qū)無序區(qū)2023年1月30日算法基礎(chǔ)17冒泡排序思路首先，列表每兩個相鄰的數(shù)，如果前邊的比后邊的大，那么交換這兩個數(shù)……會發(fā)生什么？2023年1月30日算法基礎(chǔ)18754638291012345678冒泡排序代碼2023年1月30日算法基礎(chǔ)19defbubble_sort(li):

foriinrange(len(li)-1):

forjinrange(len(li)-i-1):

ifli[j]>li[j+1]:

li[j],li[j+1]=li[j+1],li[j]時間復(fù)雜度：O(n2)冒泡排序-優(yōu)化2023年1月30日算法基礎(chǔ)20defbubble_sort_1(li):

foriinrange(len(li)-1):

exchange=False

forjinrange(len(li)-i-1):

ifli[j]>li[j+1]:

li[j],li[j+1]=li[j+1],li[j]

exchange=True

ifnotexchange:

return如果冒泡排序中執(zhí)行一趟而沒有交換，則列表已經(jīng)是有序狀態(tài)，可以直接結(jié)束算法。選擇排序思路一趟遍歷記錄最小的數(shù)，放到第一個位置；再一趟遍歷記錄剩余列表中最小的數(shù)，繼續(xù)放置；……問題是：怎么選出最小的數(shù)？2023年1月30日算法基礎(chǔ)21選擇排序代碼時間復(fù)雜度：O(n2)2023年1月30日算法基礎(chǔ)22defselect_sort(li):

foriinrange(len(li)-1):

min_loc=i

forjinrange(i+1,len(li)):

ifli[j]<li[min_loc]:

min_loc=j

ifmin_loc!=i:

li[i],li[min_loc]=li[min_loc],li[i]插入排序思路列表被分為有序區(qū)和無序區(qū)兩個部分。最初有序區(qū)只有一個元素。每次從無序區(qū)選擇一個元素，插入到有序區(qū)的位置，直到無序區(qū)變空。2023年1月30日算法基礎(chǔ)23574631298插入排序代碼時間復(fù)雜度：O(n2)優(yōu)化空間：應(yīng)用二分查找來尋找插入點（并沒有什么卵用）2023年1月30日算法基礎(chǔ)24definsert_sort(li):

foriinrange(1,len(li)):

tmp=li[i]

j=i-1

whilej>=0andtmp<li[j]:

li[j+1]=li[j]

j=j-1

li[j+1]=tmp小結(jié)——排序LOW

B三人組冒泡排序插入排序選擇排序時間復(fù)雜度：O(n2)空間復(fù)雜度：O(1)練習(xí)：嘗試自己寫一遍這三種排序方式的代碼對于前面給出的學(xué)生信息列表，使用冒泡排序?qū)ζ溥M行升序排序2023年1月30日算法基礎(chǔ)25快速排序快速排序：快好寫的排序算法里最快的快的排序算法里最好寫的2023年1月30日算法基礎(chǔ)26快速排序思路快排思路：取一個元素p（第一個元素），使元素p歸位；列表被p分成兩部分，左邊都比p小，右邊都比p大；遞歸完成排序。2023年1月30日算法基礎(chǔ)27574631298123456789214356798排序前：目標(biāo)：P歸位：算法關(guān)鍵點：整理遞歸快速排序代碼——第一步defquick_sort(data,left,right):

ifleft<right:

mid=partition(data,left,right)

quick_sort(data,left,mid-1)

quick_sort(data,mid+1,right)2023年1月30日算法基礎(chǔ)28怎么寫partition函數(shù)2023年1月30日算法基礎(chǔ)29574631298574631298214356798快速排序代碼——第二步defpartition(data,left,right):

tmp=data[left]

whileleft<right:

whileleft<rightanddata[right]>=tmp:

right-=1

data[left]=data[right]

whileleft<rightanddata[left]<=tmp:

left+=1

data[right]=data[left]

data[left]=tmp

returnleft2023年1月30日算法基礎(chǔ)30還不理解partition函數(shù)？defpartition(data,left,right):

tmp=data[left]

whileleft<right:

whileleft<rightanddata[right]>=tmp:

right-=1

data[left]=data[right]

whileleft<rightanddata[left]<=tmp:

left+=1

data[right]=data[left]

data[left]=tmp

returnleft2023年1月30日算法基礎(chǔ)31574631298跟著我右手左手一個慢動作右手左手慢動作重播快速排序-如何效率快速排序真的比冒泡排序快嗎？為什么快了？快了多少？問題最壞情況遞歸2023年1月30日算法基礎(chǔ)32快速排序-練習(xí)如果想將列表進行降序排序，應(yīng)該修改哪些符號？還是對于剛才那個學(xué)生信息表，修改快速排序代碼，使其能夠進行排序。2023年1月30日算法基礎(chǔ)33堆排序前傳——樹與二叉樹簡介樹是一種數(shù)據(jù)結(jié)構(gòu)比如：目錄結(jié)構(gòu)樹是一種可以遞歸定義的數(shù)據(jù)結(jié)構(gòu)樹是由n個節(jié)點組成的集合：如果n=0，那這是一棵空樹；如果n>0，那存在1個節(jié)點作為樹的根節(jié)點，其他節(jié)點可以分為m個集合，每個集合本身又是一棵樹。一些概念根節(jié)點、葉子節(jié)點樹的深度（高度）樹的度孩子節(jié)點/父節(jié)點子樹2023年1月30日算法基礎(chǔ)34特殊且常用的樹——二叉樹二叉樹：度不超過2的樹（節(jié)點最多有兩個叉）2023年1月30日算法基礎(chǔ)35兩種特殊二叉樹滿二叉樹完全二叉樹2023年1月30日算法基礎(chǔ)36二叉樹的存儲方式鏈?zhǔn)酱鎯Ψ绞巾樞虼鎯Ψ绞剑斜恚└腹?jié)點和左孩子節(jié)點的編號下標(biāo)有什么關(guān)系？0-1

1-3

2-5

3-7

4-9父節(jié)點和右孩子節(jié)點的編號下標(biāo)有什么關(guān)系？0-2

1-4

2-6

3-8

4-10比如，我們要找根節(jié)點左孩子的左孩子2023年1月30日算法基礎(chǔ)37987210563498765012430123456789i

–

2i+1i

–

2i+2二叉樹小結(jié)二叉樹是度不超過2的樹滿二叉樹與完全二叉樹（完全）二叉樹可以用列表來存儲，通過規(guī)律可以從父親找到孩子或從孩子找到父親2023年1月30日算法基礎(chǔ)38堆排序堆大根堆：一棵完全二叉樹，滿足任一節(jié)點都比其孩子節(jié)點大小根堆：一棵完全二叉樹，滿足任一節(jié)點都比其孩子節(jié)點小2023年1月30日算法基礎(chǔ)39堆排序2023年1月30日算法基礎(chǔ)409872105634大根堆：1264975386小根堆：堆這個玩意…2023年1月30日算法基礎(chǔ)412976105384假設(shè)：節(jié)點的左右子樹都是堆，但自身不是堆當(dāng)根節(jié)點的左右子樹都是堆時，可以通過一次向下的調(diào)整來將其變換成一個堆。堆排序過程建立堆得到堆頂元素，為最大元素去掉堆頂，將堆最后一個元素放到堆頂，此時可通過一次調(diào)整重新使堆有序。堆頂元素為第二大元素。重復(fù)步驟3，直到堆變空。2023年1月30日算法基礎(chǔ)42構(gòu)造堆2023年1月30日算法基礎(chǔ)436812703954挨個出數(shù)2023年1月30日算法基礎(chǔ)449872105634堆排序代碼2023年1月30日算法基礎(chǔ)45defsift(data,low,high):

i=low

j=2*i+1

tmp=data[i]

whilej<=high:

ifj<highanddata[j]<data[j+1]:

j+=1

iftmp<data[j]:

data[i]=data[j]

i=j

j=2*i+1

else:

break

data[i]=tmpdefheap_sort(data):

n=len(data)

foriinrange(n//2-1,-1,-1):

sift(data,i,n-1)

foriinrange(n-1,-1,-1):

data[0],data[i]=data[i],data[0]

sift(data,0,i-1)歸并排序假設(shè)現(xiàn)在的列表分兩段有序，如何將其合成為一個有序列表這種操作稱為一次歸并。2023年1月30日算法基礎(chǔ)46253178694一次歸并代碼defmerge(li,low,mid,high):

i=low

j=mid+1

ltmp=[]

whilei<=midandj<=high:

ifli[i]<=li[j]:

ltmp.append(li[i])

i+=1

else:

ltmp.append(li[j])

j+=1

whilei<=mid:

ltmp.append(li[i])

i+=1

whilej<=high:

ltmp.append(li[j])

j+=1

li[low:high+1]=ltmp2023年1月30日算法基礎(chǔ)47有了歸并怎么用？分解：將列表越分越小，直至分成一個元素。一個元素是有序的。合并：將兩個有序列表歸并，列表越來越大。2023年1月30日算法基礎(chǔ)48歸并排序defmergesort(li,low,high):

iflow<high:

mid=(low+high)//2

mergesort(li,low,mid)

mergesort(li,mid+1,high)

merge(li,low,mid,high)2023年1月30日算法基礎(chǔ)49時間復(fù)雜度：O(nlogn)空間復(fù)雜度：O(n)快速排序、堆排序、歸并排序-小結(jié)三種排序算法的時間復(fù)雜度都是O(nlogn)一般情況下，就運行時間而言：快速排序<歸并排序<堆排序三種排序算法的缺點：快速排序：極端情況下排序效率低歸并排序：需要額外的內(nèi)存開銷堆排序：在快的排序算法中相對較慢2023年1月30日算法基礎(chǔ)50希爾排序思路希爾排序是一種分組插入排序算法。首先取一個整數(shù)d1=n/2，將元素分為d1個組，每組相鄰量元素之間距離為d1，在各組內(nèi)進行直接插入排序；取第二個整數(shù)d2=d1/2，重復(fù)上述分組排序過程，直到di=1，即所有元素在同一組內(nèi)進行直接插入排序。希爾排序每趟并不使某些元素有序，而是使整體數(shù)據(jù)越來越接近有序；最后一趟排序使得所有數(shù)據(jù)有序。2023年1月30日算法基礎(chǔ)51574631298d=4d=2d=1希爾排序defshell_sort(li):

gap=len(li)//2

whilegap>0:

foriinrange(gap,len(li)):

tmp=li[i]

j=i-gap

whilej>=0andtmp<li[j]:

li[j+gap]=li[j]

j-=gap

li[j+gap]=tmp

gap/=22023年1月30日算法基礎(chǔ)52時間復(fù)雜度： O((1+τ)n)

O(1.3n)排序-小結(jié)排序方法時間復(fù)雜度穩(wěn)定性代碼復(fù)雜度最壞情況平均情況最好情況冒泡排序O(n2)O(n2)O(n)穩(wěn)定簡單直接選擇排序O(n2)O(n2)O(n2)不穩(wěn)定簡單直接插入排序O(n2)O(n2)O(n2)穩(wěn)定簡單快速排序O(n2)O(nlogn)O(nlogn)不穩(wěn)定較復(fù)雜堆排序O(nlogn)O(nlogn)O(nlogn)不穩(wěn)定復(fù)雜歸并排序O(nlogn)O(nlogn)O(nlogn)穩(wěn)定較復(fù)雜希爾排序O(1.3n)不穩(wěn)定較復(fù)雜2023年1月30日算法基礎(chǔ)53排序-贈品1現(xiàn)在有一個列表，列表中的數(shù)范圍都在0到100之間，列表長度大約為100萬。設(shè)計算法在O(n)時間復(fù)雜度內(nèi)將列表進行排序。2023年1月30日算法基礎(chǔ)54贈品1-計數(shù)排序創(chuàng)建一個列表，用來統(tǒng)計每個數(shù)出現(xiàn)的次數(shù)。2023年1月30日算法基礎(chǔ)55defcount_sort(li,max_num):

count=[0foriinrange(max_num+1)]

fornuminli:

count[num]+=1

i=0

fornum,minenumerate(count):

forjinrange(m):

li[i]=num

i+=1排序-贈品2現(xiàn)在有n個數(shù)（n>10000），設(shè)計算法，按大小順序得到前10大的數(shù)。應(yīng)用場景：榜單TOP

102023年1月30日算法基礎(chǔ)56贈品2-堆的應(yīng)用（了解）解決思路：取列表前10個元素建立一個