Chapter02 算法分析

参考书本： Data Structure and Algorithm Analysis in C

参考课程： 浙江大学-数据结构 陈越姥姥

几个概念： Def： T(N) <= cf(N) 记为 T(N) = O(f(N)) T(N) >= cf(N) 记为 T(N) = Ω(f(N))

在算法分析中，比较函数值的大小是没有意义的，于是比较它们的相对增长率（relative rate of growth)

注意： 不要将低阶项或常数放入大O。不要写T(N) = O( 2N² ) 或 T(N) = O( N²+ N )， 这两种的正确写法都是T( N ) = O ( N² )。

法则：如果一个算法用的常数时间O( 1 )将问题的大小削减为其一部分（通常是1/2），那么该算法就是O( logN )的。另一方面，如果只减少了一个常数（问题减少1）那么这种算法就是O( N )的。

举例： 对分查找（binary search）

int BinarySearch(const int A[ ], int X, int N) { int Low, Mid, High; Low = 0; High = N - 1; while (Low <= High ) { Mid = ( Low + High ) / 2; if( A[Mid] < X ) Low = Mid + 1; else if( A[Mid] > X) High = Mid - 1; else return Mid; //Found } return -1; //Not Found } int main() { int A[10 + 5] = {0, 3, 5, 12, 23, 29, 47, 50, 72, 99}; int X = 29; //Target int N = 10; //Number of numbers int index; index = BinarySearch(A, X, N); cout << index; //Display 2 return 0; }

只需要讲mid与target去比较一次，就可以讲问题缩短一半。因此，运行时间是O ( logN )。

欧几里得算法 计算两个整数的最大公因数（Gcd）

int Gcd(int M, int N) { int Rem; while( N > 0 ) { Rem = M % N; M = N; N = Rem; } return M; } int main() { int M, N; int ans; M = 1989; N = 1590; ans = Gcd(M, N); cout << ans << endl; return 0; }

由定理，如果M > N, 则 M mod N < M / 2，可知，一次M mod N的操作，使问题大小缩减一半，故运行时间是O( log N )