算法的分析

评价一个算法优劣的要素便是算法的性能（包括时间复杂度和空间复杂度）。当我们去比较两个算法时，最传统的方法就是实践，可以采用控制变量法，让两个算法在同一台机器上以相同的数据跑，比较所花费的时间。这样做不但有些麻烦，而且可能发生奇怪的事，比如：对于第一组数据，算法A优于算法B，而对于第二组数据，算法B优于算法A。这就无法比较两个算法的优劣了。

为了解决上面可能出现的问题，渐进分析应运而生。我们通过使用数据的size来评价一个算法的性能。对于一个有n个数的array，线性查找的时间可用n表示，而折半查找可用Logn表示。

当然，渐进分析也并不能比较任何两个算法的优劣，比如：nLogn与100nLogn的两个算法，根据渐进分析，它们的性能并无优劣之分。

 

 

当我们分析一个算法时，可以有三种情况

1.Best case

2.Average case

3.Worst case

比如线性查找：

int search(int arr[], int n, int x)

{

    int i;

    for (i=0; i<n; i++)

    {

       if (arr[i] == x)

         return i;

    }

    return -1;

}

 

1.Best case:

X=arr[0],即要找的值位于数组的首位，此时时间复杂度为O(1),这种情况存在偶然性且不具代表性，因此通常不使用。

2.Average case:

我们假定所有的n+1（x为arr中n个值中的一个或者不在arr中）种情况出现的概率相同，那么

T（n）= [1+2+……+n+(n+1)]/(n+1) = O(n).

这种情况代表了一个算法的平均水平，极具代表性，但是，它很难被算出来，所以，有些算法无法用它表示。

3.Worst case:

X不在arr中，时间复杂度O(n),相对来说，这种情况的可能性更大，最重要的一点是，它代表了一个算法最差的情况，最高的时间按复杂度。当我们知道一个算法的最差情况，那么一个算法必将小于等于最差情况，因此这种情况通常被使用。

 

 

渐进分析算法有以下三种标记：

1.ϴ：同时确定上下限时使用

 

 

2.O：只能确定上限时使用

 

3.Ω：只能确定下限时使用

 

 

循环语句的分析:

 

1.O(1)

 

 // c为常量      for (int i = 1; i <= c; i++) {          // O(1)的语句   }

2.O(n)

 

// c为常量      for (int i = 1; i <= n; i += c) {          // O(1)的语句   }    for (int i = n; i > 0; i -= c) {        // O(1)的语句

}

 

3.O(n2)

// c为常量 

for (int i = 1; i <=n; i += c) {       for (int j = 1; j <=n; j += c) {          // O(1)的语句       }   }    for (int i = n; i > 0; i += c) {       for (int j = i+1; j <=n; j += c) {          // O(1)的语句

}

 

4.O(Logn)

 

for (int i = 1; i <=n; i *= c) {       // O(1)的语句   }   for (int i = n; i > 0; i /= c) {       // O(1)的语句   }

 

5.O(LogLogn)

 

// pow为平方函数

for (int i = 2; i <=n; i = pow(i, c)) {        // O(1)的语句   }   // fun 为开平方函数   for (int i = n; i > 0; i = fun(i)) {        // O(1)的语句   }

 

 

递归函数的分析:

 

1.替换法

步骤：

1) 猜测给定算法的时间复杂度

2) 证明猜测的时间复杂度正确

例：T(n)=2T(n/2)+n

1) 猜测T(n)=O(nLogn)

2) 证明：T(n)<=cnLogn成立

T(n) = 2T(n/2)+n

 <=2c*(n/2)*Log(n/2)+n

 =cnLogn-cnLog2+n

 <=cnLogn (当cLog2>1时)

 

2.递归树法

步骤：

1) 根据递归关系画出递归树

2) 合计总的时间代价

 

For example consider the recurrence relation T(n) = T(n/4) + T(n/2) + cn2            cn2         /      \     T(n/4)     T(n/2) If we further break down the expression T(n/4) and T(n/2), we get following recursion tree.                 cn2           /           \             c(n2)/16      c(n2)/4      /      \          /     \  T(n/16)     T(n/8)  T(n/8)    T(n/4) Breaking down further gives us following                 cn2            /            \             c(n2)/16          c(n2)/4       /      \            /      \c(n2)/256   c(n2)/64  c(n2)/64    c(n2)/16 /    \      /    \    /    \       /    \   To know the value of T(n), we need to calculate sum of tree nodes level by level. If we sum the above tree level by level, we get the following seriesT(n)  = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ....The above series is geometrical progression with ratio 5/16. To get an upper bound, we can sum the infinite series. We get the sum as (n2)/(1 - 5/16) which is O(n2)

 

 

3.主定理法

 

 

 

 

<!--EndFragment-->