算法復(fù)習(xí)
1.insert_sort
# -*-coding:UTF-8 -*-
a=input()
b=list(a) # 將其變?yōu)榱斜?lenth=len(b)
print(b,lenth)
for i in range(1,lenth):
key=b[i]
j=i-1
while(j>=0 and b[j]>key):
b[j+1]=b[j]
j-=1
b[j+1]=key
print(b)
備注：
1.input讀取輸入污筷，默認(rèn)為字符串
2.list能直接將其按照字符轉(zhuǎn)換為列表宴合，否則分割用split()進(jìn)行應(yīng)有的切割
3.算法最好時間復(fù)雜度為O(n)效诅，最差為O(n2)彼绷，平均為O(n2)
4.算法思想為外層循環(huán)n-1次余爆，從1開始，每次與前面的所有進(jìn)行比較硕舆，一直知道比他小的數(shù)
2.遞歸之整數(shù)劃分問題
# -*- coding:UTF-8 -*-
def equationCount(n,m):
if (n==1 or m==1):
return 1
elif n<m:
return equationCount(n,n)
elif n==m:
return 1+equationCount(n,n-1)
else:
return equationCount(n-m,m)+equationCount(n,m-1)
a = int(input())
print(equationCount(a,a))
算法整體思想分為4部分
f(n,m)=1 ,n=1,m=1 秽荞，n=1的時候為{1}，m=1時為{1,1,1,1,....}
f(n,m)=f(n,n),n>m時抚官，最大的只能為n
f(n,m)=1+f(n,n-1)蚂会，n=m時，除去一個{n}的劃分耗式，剩下所有小于n的劃分
f(n,m)=f(n,m-1)+f(n-m,m),n>m>1時，n!=m時趁猴，,分為劃分中包含m和不包含m
包含m刊咳，則剩下的所有數(shù)字和為n-m,最大值不超過m，不包含m,可能最大值為m-1儡司，則遞歸計算為f(n,m-1)
備注:輸入默認(rèn)為字符
3.hanoi問題
def hanoi(n,a,b,c):
if(n>0):
hanoi(n-1,a,c,b)
move(a,b)
hanoi(n-1,c,b,a)
算法思想為：
將n-1個從a移到c通過b
移動最后1個娱挨，從a到b
將n-1個從c移到b，通過a
4.分治法基本步驟
? divided_and_conquer(P){
? if(|P|<=n0) adhoc(P);//解決小規(guī)模問題
? divide P into smaller subinstance p1,p2...pk//分解問題
? for(i=1,i<k,i++)
? yi=divide_and_conquer(Pi)//遞歸解決子問題
? return merge(y1,y2,....yk)捕犬，//合并子問題解跷坝，得到最后的解}
T(n)=O(1) n=1
=kO(n/m)+f(n)，n>1
主定理公式:n^logmk+ kjf(n/mj)
f(n) < nlogba
也就是 f(n) = O(nlogba - e ) 碉碉，e > 0為任意小的常數(shù)
或者說柴钻，f(n) 比 nlogba變化的慢，慢ne
那么垢粮，T(n) ? Q (nlogba)f(n) > nlogba
也就是 f(n) = W(nlogba +e ) 贴届，e > 0為任意小的常數(shù)
或者說，f(n) 比 nlogba變化的快，快ne
那么毫蚓， T(n) ? Q(f(n))
f(n) = nlogba
也就是兩項的數(shù)量級相當(dāng)占键，就給這個數(shù)量級乘上一個lg n
T(n) ? Q(nlogba * lg n)
可以簡單地說，遞歸方程的右側(cè)的兩項元潘，哪項變化的塊畔乙，T(n)就屬于哪項的數(shù)量級
5.二分搜索算法
def binaraysearch(a,x):
l=0
r=len(a)-1
while(r>=1):
m=int((l+r)/2)
if(x==a[m]):
return m
elif x>a[m]:
l=m+1
else:
r=m-1
return -1
a=input()
a=list(a)
x=input()
print(binaraysearch(a,x))
最壞時間復(fù)雜度O(logn)
6.大整數(shù)乘法
參考博客：1.整數(shù)劃分問題（遞歸法）
?????2.主項定理Master Method ——算法復(fù)習(xí)筆記
