算法时间复杂度-对数复杂度

衡量一个算法性能好坏的指标：时间复杂度、空间复杂度
在上位机中，更关注时间复杂度。

时间复杂度的衡量方法：大O计法
常见的几种时间复杂度：O(n3) O(n2) O(nlogn) O(n) O(log n) O(1)
在分析时间复杂度时，对数负责度最为复杂。

对数最常出现的规律为：如果一个算法用常数时间将问题的大小削减为其一部分（通常为1/2）,那么该算法的时间复杂度为O(log N)
exam1:对分查找

给定一个整数X和整数A0、A1、A2、、、An-1,后者已经预先排序并在内存中，求使得Ai=X的下表i，如果不存在，则返回i=-1
 

int findIndex(cont int* array, int X, int n)
{
	int low, mid, high;
	low = 0; high = n-1;
	while( low <= high)
	{
		mid = (high + low) / 2;
		if(array[mid] > X)
		{
			high = mid + 1;
		}
		else if(array[mid] < X)
		{
			low = mid - 1;
		}
		else
		{
			return mid;
		}
	}
}

exam2:欧几里得算法
计算最大公因数的欧几里得算法。两个整数的最大公因数Gcd是同时整除二者的最大整数。于是，Gcd(50,15) = 5。

unsigned int Gcd(unsigned intm ,unsigned int n)
{
    unsigned int Rem;
    while (n > 0) {
        Rem = m % n;
        m = n;
        n = Rem;
    }
    return m;
}

exam3:幂运算

计算X的N次方常见的算法是使用N-1次乘法自乘。但是用递归算法更好。

bool isEven(unsigned int n)
{
    if (n % 2 == 0) {
        return 1;
    } else {
        return 0;
    }
}

 long Pow(long x ,unsigned int n)
{
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return x;
    }
    
    if (isEven(n)) {
        return Pow(x*x, n/2);
    } else {
        return Pow(x * x ,n / 2) * x;
    }
}