處女座-算法視頻二

算法基礎(chǔ)第一部分算法簡(jiǎn)單概念算法概念復(fù)習(xí)：遞歸時(shí)間復(fù)雜度空間復(fù)雜度2023年1月30日算法基礎(chǔ)2什么是算法？算法（Algorithm）：一個(gè)計(jì)算過(guò)程，解決問(wèn)題的方法2023年1月30日算法基礎(chǔ)3算法輸入輸出復(fù)習(xí)：遞歸遞歸的兩個(gè)特點(diǎn)：調(diào)用自身結(jié)束條件看下面幾個(gè)函數(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)時(shí)間復(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')左面四組代碼，哪組運(yùn)行時(shí)間最短？用什么方式來(lái)體現(xiàn)代碼（算法）運(yùn)行的快慢？時(shí)間復(fù)雜度類比生活中的一些事件，估計(jì)時(shí)間：眨一下眼口算“29+68”燒一壺水睡一覺(jué)完成一個(gè)項(xiàng)目飛船從地球飛出太陽(yáng)系2023年1月30日算法基礎(chǔ)6一瞬間/幾毫秒幾秒幾分鐘幾小時(shí)幾天/幾星期/幾個(gè)月幾年時(shí)間復(fù)雜度時(shí)間復(fù)雜度：用來(lái)評(píng)估算法運(yùn)行效率的一個(gè)東西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)時(shí)間復(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)時(shí)間復(fù)雜度2023年1月30日算法基礎(chǔ)9那這個(gè)代碼呢？whilen>1:

print(n)

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

O(2n)

O(nn)

…如何一眼判斷時(shí)間復(fù)雜度？循環(huán)減半的過(guò)程O(píng)(logn)幾次循環(huán)就是n的幾次方的復(fù)雜度2023年1月30日算法基礎(chǔ)10空間復(fù)雜度空間復(fù)雜度：用來(lái)評(píng)估算法內(nèi)存占用大小的一個(gè)式子“空間換時(shí)間”2023年1月30日算法基礎(chǔ)11列表查找列表查找：從列表中查找指定元素輸入：列表、待查找元素輸出：元素下標(biāo)或未查找到元素順序查找從列表第一個(gè)元素開(kāi)始，順序進(jìn)行搜索，直到找到為止。二分查找從有序列表的候選區(qū)data[0:n]開(kāi)始，通過(guò)對(duì)待查找的值與候選區(qū)中間值的比較，可以使候選區(qū)減少一半。2023年1月30日算法基礎(chǔ)12二分查找2023年1月30日算法基owhighmidmidmid使用二分查找來(lái)查找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時(shí)間復(fù)雜度O(n)O(logn)列表查找：練習(xí)現(xiàn)有一個(gè)學(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(wú)序列表變?yōu)橛行蛄斜響?yīng)用場(chǎng)景：各種榜單各種表格給二分排序用給其他算法用輸入：無(wú)序列表輸出：有序列表2023年1月30日算法基礎(chǔ)16排序low

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

B三人組大家自己能想到怎么完成一次排序嗎？冒泡排序選擇排序插入排序算法關(guān)鍵點(diǎn)：有序區(qū)無(wú)序區(qū)2023年1月30日算法基礎(chǔ)17冒泡排序思路首先，列表每?jī)蓚€(gè)相鄰的數(shù)，如果前邊的比后邊的大，那么交換這兩個(gè)數(shù)……會(huì)發(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]時(shí)間復(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í)行一趟而沒(méi)有交換，則列表已經(jīng)是有序狀態(tài)，可以直接結(jié)束算法。選擇排序思路一趟遍歷記錄最小的數(shù)，放到第一個(gè)位置；再一趟遍歷記錄剩余列表中最小的數(shù)，繼續(xù)放置；……問(wèn)題是：怎么選出最小的數(shù)？2023年1月30日算法基礎(chǔ)21選擇排序代碼時(shí)間復(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ū)和無(wú)序區(qū)兩個(gè)部分。最初有序區(qū)只有一個(gè)元素。每次從無(wú)序區(qū)選擇一個(gè)元素，插入到有序區(qū)的位置，直到無(wú)序區(qū)變空。2023年1月30日算法基礎(chǔ)23574631298插入排序代碼時(shí)間復(fù)雜度：O(n2)優(yōu)化空間：應(yīng)用二分查找來(lái)尋找插入點(diǎn)（并沒(méi)有什么卵用）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三人組冒泡排序插入排序選擇排序時(shí)間復(fù)雜度：O(n2)空間復(fù)雜度：O(1)練習(xí)：嘗試自己寫(xiě)一遍這三種排序方式的代碼對(duì)于前面給出的學(xué)生信息列表，使用冒泡排序?qū)ζ溥M(jìn)行升序排序2023年1月30日算法基礎(chǔ)25快速排序快速排序：快好寫(xiě)的排序算法里最快的快的排序算法里最好寫(xiě)的2023年1月30日算法基礎(chǔ)26快速排序思路快排思路：取一個(gè)元素p（第一個(gè)元素），使元素p歸位；列表被p分成兩部分，左邊都比p小，右邊都比p大；遞歸完成排序。2023年1月30日算法基礎(chǔ)27574631298123456789214356798排序前：目標(biāo)：P歸位：算法關(guān)鍵點(diǎ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怎么寫(xiě)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跟著我右手左手一個(gè)慢動(dòng)作右手左手慢動(dòng)作重播快速排序-如何效率快速排序真的比冒泡排序快嗎？為什么快了？快了多少？問(wèn)題最壞情況遞歸2023年1月30日算法基礎(chǔ)32快速排序-練習(xí)如果想將列表進(jìn)行降序排序，應(yīng)該修改哪些符號(hào)？還是對(duì)于剛才那個(gè)學(xué)生信息表，修改快速排序代碼，使其能夠進(jìn)行排序。2023年1月30日算法基礎(chǔ)33堆排序前傳——樹(shù)與二叉樹(shù)簡(jiǎn)介樹(shù)是一種數(shù)據(jù)結(jié)構(gòu)比如：目錄結(jié)構(gòu)樹(shù)是一種可以遞歸定義的數(shù)據(jù)結(jié)構(gòu)樹(shù)是由n個(gè)節(jié)點(diǎn)組成的集合：如果n=0，那這是一棵空樹(shù)；如果n>0，那存在1個(gè)節(jié)點(diǎn)作為樹(shù)的根節(jié)點(diǎn)，其他節(jié)點(diǎn)可以分為m個(gè)集合，每個(gè)集合本身又是一棵樹(shù)。一些概念根節(jié)點(diǎn)、葉子節(jié)點(diǎn)樹(shù)的深度（高度）樹(shù)的度孩子節(jié)點(diǎn)/父節(jié)點(diǎn)子樹(shù)2023年1月30日算法基礎(chǔ)34特殊且常用的樹(shù)——二叉樹(shù)二叉樹(shù)：度不超過(guò)2的樹(shù)（節(jié)點(diǎn)最多有兩個(gè)叉）2023年1月30日算法基礎(chǔ)35兩種特殊二叉樹(shù)滿二叉樹(shù)完全二叉樹(shù)2023年1月30日算法基礎(chǔ)36二叉樹(shù)的存儲(chǔ)方式鏈?zhǔn)酱鎯?chǔ)方式順序存儲(chǔ)方式（列表）父節(jié)點(diǎn)和左孩子節(jié)點(diǎn)的編號(hào)下標(biāo)有什么關(guān)系？0-1

1-3

2-5

3-7

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

1-4

2-6

3-8

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

–

2i+1i

–

2i+2二叉樹(shù)小結(jié)二叉樹(shù)是度不超過(guò)2的樹(shù)滿二叉樹(shù)與完全二叉樹(shù)（完全）二叉樹(shù)可以用列表來(lái)存儲(chǔ)，通過(guò)規(guī)律可以從父親找到孩子或從孩子找到父親2023年1月30日算法基礎(chǔ)38堆排序堆大根堆：一棵完全二叉樹(shù)，滿足任一節(jié)點(diǎn)都比其孩子節(jié)點(diǎn)大小根堆：一棵完全二叉樹(shù)，滿足任一節(jié)點(diǎn)都比其孩子節(jié)點(diǎn)小2023年1月30日算法基礎(chǔ)39堆排序2023年1月30日算法基礎(chǔ)409872105634大根堆：1264975386小根堆：堆這個(gè)玩意…2023年1月30日算法基礎(chǔ)412976105384假設(shè)：節(jié)點(diǎn)的左右子樹(shù)都是堆，但自身不是堆當(dāng)根節(jié)點(diǎn)的左右子樹(shù)都是堆時(shí)，可以通過(guò)一次向下的調(diào)整來(lái)將其變換成一個(gè)堆。堆排序過(guò)程建立堆得到堆頂元素，為最大元素去掉堆頂，將堆最后一個(gè)元素放到堆頂，此時(shí)可通過(guò)一次調(diào)整重新使堆有序。堆頂元素為第二大元素。重復(fù)步驟3，直到堆變空。2023年1月30日算法基礎(chǔ)42構(gòu)造堆2023年1月30日算法基礎(chǔ)436812703954挨個(gè)出數(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)在的列表分兩段有序，如何將其合成為一個(gè)有序列表這種操作稱為一次歸并。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有了歸并怎么用？分解：將列表越分越小，直至分成一個(gè)元素。一個(gè)元素是有序的。合并：將兩個(gè)有序列表歸并，列表越來(lái)越大。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時(shí)間復(fù)雜度：O(nlogn)空間復(fù)雜度：O(n)快速排序、堆排序、歸并排序-小結(jié)三種排序算法的時(shí)間復(fù)雜度都是O(nlogn)一般情況下，就運(yùn)行時(shí)間而言：快速排序<歸并排序<堆排序三種排序算法的缺點(diǎn)：快速排序：極端情況下排序效率低歸并排序：需要額外的內(nèi)存開(kāi)銷堆排序：在快的排序算法中相對(duì)較慢2023年1月30日算法基礎(chǔ)50希爾排序思路希爾排序是一種分組插入排序算法。首先取一個(gè)整數(shù)d1=n/2，將元素分為d1個(gè)組，每組相鄰量元素之間距離為d1，在各組內(nèi)進(jìn)行直接插入排序；取第二個(gè)整數(shù)d2=d1/2，重復(fù)上述分組排序過(guò)程，直到di=1，即所有元素在同一組內(nèi)進(jìn)行直接插入排序。希爾排序每趟并不使某些元素有序，而是使整體數(shù)據(jù)越來(lái)越接近有序；最后一趟排序使得所有數(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時(shí)間復(fù)雜度： O((1+τ)n)

O(1.3n)排序-小結(jié)排序方法時(shí)間復(fù)雜度穩(wěn)定性代碼復(fù)雜度最壞情況平均情況最好情況冒泡排序O(n2)O(n2)O(n)穩(wěn)定簡(jiǎn)單直接選擇排序O(n2)O(n2)O(n2)不穩(wěn)定簡(jiǎn)單直接插入排序O(n2)O(n2)O(n2)穩(wěn)定簡(jiǎ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排序-贈(zèng)品1現(xiàn)在有一個(gè)列表，列表中的數(shù)范圍都在0到100之間，列表長(zhǎng)度大約為100萬(wàn)。設(shè)計(jì)算法在O(n)時(shí)間復(fù)雜度內(nèi)將列表進(jìn)行排序。2023年1月30日算法基礎(chǔ)54贈(zèng)品1-計(jì)數(shù)排序創(chuàng)建一個(gè)列表，用來(lái)統(tǒng)計(jì)每個(gè)數(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排序-贈(zèng)品2現(xiàn)在有n個(gè)數(shù)（n>10000），設(shè)計(jì)算法，按大小順序得到前10大的數(shù)。應(yīng)用場(chǎng)景：榜單TOP

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