算法的官方定義
- 算法（Algorithm）
- 一個(gè)有限指令集
- 接受一些輸入（有些情況下不需要輸入）
- 產(chǎn)生輸出
- 一定在有限步驟之后終止
- 每一條指令必須
- 有充分明確的目標(biāo)，不可以有歧義
- 計(jì)算機(jī)能處理的范圍之內(nèi)
- 描述應(yīng)不依賴于任何一種計(jì)算機(jī)語(yǔ)言以及具體的實(shí)現(xiàn)手段
/* 偽代碼描述 */
void SelectionSort (int List[], int N)
{ 將N個(gè)整數(shù)List[0]...List[N-1]進(jìn)行非遞減排序；
從List[i]到List[N-1]中找最小元，并將其位置賦給MinPosition；
將未排序部分的最小元換到有序部分的最后位置；
}
}
/* C語(yǔ)言實(shí)現(xiàn) */
void SelectionSort (int List[], int N)
{ /* 將N個(gè)整數(shù)List[0]...List[N-1]進(jìn)行非遞減排序 */
for (i=0; i<N; i++){
MinPosition = ScanForMin(List, i, N-1);
/* 從List[i]到List[N-1]中找最小元，并將其位置賦給MinPosition；*/
Swap(List[i], List[MinPosition]);
/* 將未排序部分的最小元換到有序部分的最后位置； */
}
}
# Python語(yǔ)言實(shí)現(xiàn)
def selection_sort(lt, n):
for i in range(n):
min_position = scan_for_min(lt, i, n-1)
swap(lt[i], lt[min_position])
抽象 ——
List到底是數(shù)組還是鏈表（雖然看上去像數(shù)組）？
Swap用函數(shù)還是用宏去實(shí)現(xiàn)？
什么是好的算法
通常通過(guò)下面兩個(gè)指標(biāo)衡量算法的好壞
空間復(fù)雜度S(n)
根據(jù)算法寫成的程序在執(zhí)行時(shí)占用存儲(chǔ)單元的長(zhǎng)度。這個(gè)長(zhǎng)度往往與輸入數(shù)據(jù)的規(guī)模有關(guān)。空間復(fù)雜度過(guò)高的算法可能導(dǎo)致使用的內(nèi)存超限，造成程序非正常中斷。
時(shí)間復(fù)雜度T(n)
根據(jù)算法寫成的程序在執(zhí)行時(shí)耗費(fèi)時(shí)間的長(zhǎng)度。這個(gè)長(zhǎng)度往往也與輸入數(shù)據(jù)的規(guī)模有關(guān)。時(shí)間復(fù)雜度過(guò)高的低效算法可能導(dǎo)致我們?cè)谟猩甓嫉炔坏竭\(yùn)行結(jié)果。
0101-例2-空間復(fù)雜度
/* c語(yǔ)言實(shí)現(xiàn) */
void PrintN (int N)
{if (N){
PrintN(N - 1);
printf("%dn", N);
}
return;
}
# python語(yǔ)言實(shí)現(xiàn)
def print_n(n: int):
if n:
print_n(n - 1)
print(n)
首先內(nèi)存記錄PrintN(100000)的狀態(tài)，但由于是遞歸調(diào)用，會(huì)繼續(xù)記錄PrintN(99999)的狀態(tài)，由于繼續(xù)在遞歸調(diào)用，會(huì)繼續(xù)記錄PrintN(99998)的狀態(tài)，……因此內(nèi)存占用超限。
0101-例3-時(shí)間復(fù)雜度
方法1
f(x)=a
0
+a
1
x+?+a
n−1
x
n−1
+a
n
x
n
f(x)=a0+a1x+?+an−1xn−1+anxn
對(duì)于上述的多項(xiàng)式，我們可以使用以下代碼實(shí)現(xiàn)：
/* c語(yǔ)言實(shí)現(xiàn) */
double f(int n, double a[], double x)
{int i;
double p = a[0]
for (i=1; i<=n; i++)
p += (a[i] * pow(x, i)); /* pow會(huì)執(zhí)行i次乘法 */
return p;
}
# python語(yǔ)言實(shí)現(xiàn)
def f(n: int, a_list: list, x: float):
p = a_list[0]
for i in range(1, n):
p += (a_list[i] * pow(x, i))
return p
時(shí)間復(fù)雜度：
(1+2+?+n)=(n
2
+n)/2
T(n)=C
1
n
2
+C
2
n
(1+2+?+n)=(n2+n)/2T(n)=C1n2+C2n
方法2
但是上述的方法極其復(fù)雜，我們可以對(duì)多項(xiàng)式進(jìn)行如下化簡(jiǎn)：
f(x)=a
0
+x(a
1
+(x(?(a
n−1
+x(a
n
))?))
f(x)=a0+x(a1+(x(?(an−1+x(an))?))
/* c語(yǔ)言實(shí)現(xiàn) */
double f(int n, double a[], double x)
{int i;
double p = a[n];
for (i=n; i>0; i--)
p = a[i-1] + x*p; /* 一次乘法 */
return p
}
# python語(yǔ)言實(shí)現(xiàn)
def f(n: int, a_list: list, x: float):
p = a_list[n]
for i in range(0,n,-1):
p = a_list[i-1] + x*p
return p
時(shí)間復(fù)雜度：
(1+1+?+1)n次
T(n)=Cn
(1+1+?+1)n次T(n)=Cn
綜上：在分析一般算法的效率時(shí)，我們經(jīng)常關(guān)注下面兩種復(fù)雜度
- 最壞情況復(fù)雜度 T
- worst
- (n)
- Tworst(n)
- 平均復(fù)雜度 T
- avg
- (n)
- Tavg(n)
由于平均復(fù)雜度的計(jì)算難度遠(yuǎn)遠(yuǎn)大于最壞情況復(fù)雜度，因此通?？紤]最快情況復(fù)雜度，即T
worst
(n)≥T
avg
(n)
Tworst(n)≥Tavg(n)
算法復(fù)雜度的漸進(jìn)表示
對(duì)于算法的復(fù)雜度，沒(méi)有必要求出一個(gè)精確值，只需要粗略的知道算法的增長(zhǎng)趨勢(shì)即可。
- T(n)=O(f(n))
- T(n)=O(f(n))表示存在常數(shù)C>0,n
- 0
- >0
- C>0,n0>0使得當(dāng)n≥n
- 0
- n≥n0時(shí)有T(n)≤Cf(n)
- T(n)≤Cf(n)
- T(n)=Ω(g(n))
- T(n)=Ω(g(n))表示存在常數(shù)C>0,n
- 0
- >0
- C>0,n0>0使得當(dāng)n≥n
- 0
- n≥n0時(shí)有T(n)≥Cg(n)
- T(n)≥Cg(n)
- T(n)=Θ(h(n))
- T(n)=Θ(h(n))表示同時(shí)有T(n)=O(h(n))
- T(n)=O(h(n))和T(n)=Ω(h(n))
- T(n)=Ω(h(n))
分析算法效率時(shí)，我們總是希望找到O
O時(shí)最大的上界；找到Ω
Ω時(shí)最小的下界。
下面三張圖表示算法復(fù)雜度為不同函數(shù)時(shí)對(duì)應(yīng)的耗時(shí)：
綜上：一個(gè)專業(yè)的程序，設(shè)計(jì)了一個(gè)O(N
2
)
O(N2)的算法，應(yīng)該本能的想到是否能把他改進(jìn)為O(Nlog
N
)
O(NlogN)的算法。
算法復(fù)雜度分析小竅門
- 若兩段算法分別有復(fù)雜度T
- 1
- (n)=O(f
- 1
- (n))
- T1(n)=O(f1(n))和T
- 2
- (n)=O(f
- 2
- (n))
- T2(n)=O(f2(n))，則
- T
- 1
- (n)+T
- 2
- (n))=max(O(f
- 1
- (n)),O(f
- 2
- (n)))
- T1(n)+T2(n))=max(O(f1(n)),O(f2(n)))
- T
- 1
- (n)×T
- 2
- (n))=max(O(f
- 1
- (n)×f
- 2
- (n))
- T1(n)×T2(n))=max(O(f1(n)×f2(n))
- 若T(n)
- T(n)是關(guān)于n
- n的k
- k階多項(xiàng)式，那么T(n)=Θ(n
- k
- )
- T(n)=Θ(nk)
- 一個(gè)for循環(huán)的時(shí)間復(fù)雜度等于循環(huán)次數(shù)乘以循環(huán)體代碼的復(fù)雜度
- if-else結(jié)構(gòu)的復(fù)雜度取決于if的條件判斷復(fù)雜度和兩個(gè)分支部分的復(fù)雜度，總體復(fù)雜度取三者中最大
