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