在确定一个算法正确的同时，也要保证算法的有效性。算法分析的最重要的标准时运行时间T(N)，运行时间与输入元素个数N有关。
数学基础
T(N) = O(f(N)) 表示T(N)以不快于f(N)的速度增长，也就是说，f(N)是T(N)的上界。f(N) = Ω(T(N)) 表示T(N)是f(N)的下届。
例：N3增长快于N2，因此N2 = O(N3) 或 N3 =Ω(N2)
法则：
- 若T1(N) = O(f(N))且T2(N) = O(g(N)),则有(a) T1(N)+ T2(N) = max{ O(f(N)) , O(g(N)) };(b) T1(N)* T2(N) =O( f(N * g(N) ).
- 如T(N)是k次多项式，则T(N) = theta（ Nk ）
- logkN = O(N)
大O中不包含常数项和低阶项。
算法运行时间
算法估计的运行时间一般是最坏运行时间。运行时间计算的一般法则：
- for循环：至多是for循环的语句(包括测试)的运行时间乘以迭代次数。
- 嵌套for循环：嵌套内的一条语句的运行时间是该语句运行时间乘以所有外层for循环大小的乘积。
- 顺序语句：所有语句中运行时间的最大值。
- if S1 else S2：至多为判断加上max（S1，S2）。
算法举例 (1)最大序列和问题
最大序列和问题的求解给出了四种解法，其中前两种解法是最常规的遍历所有的子序列和，这样的方法运行时间比较大，分别为O(N3)和O(N2)，对于这两种方法这里不详细叙述，重点叙述采用所谓“分治策略”的算法以及一个十分巧妙的算法。
解一：
将整个序列划分成三个部分，左半部分、右半部分以及跨越中部包含左右的中间部分。那么子序列和的最大值就只能出现在这三个位置。这样就可以以递归的方式求得左右部分的最大子序列和，然后将二者结合求出中间部分(包含左半部分的最后一个元素和右半部分的第一个元素)的最大子序列和。这个算法的时间复杂度为O(N logN)算法代码如下。
static int
MaxSubSum(const int A[], int left, int right)
{
int MaxLeftSum, MaxRightSum;
int MaxLeftBorderSum, MaxRightBorderSum;
int LeftBorderSum, RightBorderSum;
int center, i; if(left == right)
{
if(A[left] > 0)
return A[left];
else
return 0; } center = (left + right) / 2;
MaxLeftSum = MaxSubSum(A, left, center);
MaxRightSum = MaxSubSum(A, center + 1, right); MaxLeftBorderSum = 0; LeftBorderSum = 0;
for(i = center; i >= left; i --)
{
LeftBorderSum += A[i];
if(LeftBorderSum > MaxLeftBorderSum)
MaxLeftBorderSum = LeftBorderSum;
} MaxRightBorderSum = 0; RightBorderSum = 0;
for(i = center + 1; i <= right; i ++)
{
RightBorderSum += A[i];
if(RightBorderSum > MaxRightBorderSum)
MaxRightBorderSum = RightBorderSum;
} return Max( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum); }
int
MaxSubsequenceSum(const int A[], int N)
{
return MaxSubSum(A, 0, N-1);
}
解二:
这种解法可以被叫做扫描法，因为它只需要对数据进行一次扫描，一旦A[i]被读入处理，A[i]就不需要被记忆了，算法能对它已经读入的数据给出正确答案，这样的算法也叫做联机算法(online algorithm)。现在来解释这一个算法的运行过程，对于一个数列中的元素，依次读入数组的元素并求和，每次求和之后与之前获得的最大和比较，若比之大则更新最大和，若比之小则不更新，若小于0，则令为0(题设：若数据全为负，则输出为0)。如果前k个数的和为负，那么这个和与之后的元素的和不会大于这个元素本身，因此将有负数的和令为0是可行的。
下面先给出这种算法的代码表示。
int
MaxSubsequenceSum(const in A[], int N)
{
int ThisSum, MaxSum, j; ThisSum = MaxSum = 0;
for(j = 0; j < N; j++)
{
ThisSum += A[j]; if(ThisSum > MaxSum)
MaxSum = ThisSum;
else if(ThisSum < 0)
ThisSum = 0;
}
return MaxSum;
}
算法举例 (2)对分查找
对分查找：给定一个整数X和整数A0,A1…….An-1，后者已排序，求X在A中的下标，若不在数据中返回-1。
对分查找的基本思想是，用X与中间元素对比，如相等则可返回，若X比中间元素大，则继续在后半部分（假设升序）递归查找，反之在前半部分递归查找。算法如下：
int
BinarySearch(const ElementType A[], ElementType X, int N)
{
int left, right, mid; left = 0; right = N - 1;
mid = (left + right) / 2; while(left <= right) //查找是否结束
{
if(X == A[mid])
return mid; else if(X > A[mid])
left = mid + 1;
else
right = mid - 1;
} return -1;
}
算法举例 (3)欧几里得算法
欧几里得算法是用来计算最大公因数的。从下面的算法描述中可以看出，这个算法非常精妙，而且复杂度为O(logN)。欧几里得算法依赖一个定理
gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0)
实际上，在算法中如果N>M时，循环的第一次迭代将使他们互换。
unsigned int Gcd(unsigned int M, unsigned int N)
{
unsigned int Rem; while(N > 0)
{
Rem = M % N;
M = N;
N = Rem;
}
return M;
}
算法举例 (4)高效率求幂运算
常规的XN求幂运算方法是对X进行N-1此自乘，其复杂度为O(N)，可以想象，在N很大的时候其消耗还是很惊人的。因为XN=XN/2*XN/2,于是有下面递归实现的高效率求幂运算。由于把一个求幂运算分成两个最多只需要两次乘法(N为奇数时)，所以乘法总次数最多为2logN.
long int //long int防止过大的数溢出
Pow(long int X, unsigned int N)
{
if(N == 0)
return 1;
if(N == 1)
return X;
if(N % 2 == 0)
return Pow(X*X, N/2);
else
return Pow(X*X, N/2) * X; }