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 )