算法分析

发表于   |   分类于   |     |   次阅读

#分析算法

通常从正确性、可读性、健壮性、效率等几个方面来评价算法的性能：

  1. 正确性：算法的执行结果应当满足预先规定的功能和性能要求。
  2. 可读性：算法应当思路清晰、层次分明、简单明了、易读易懂。
  3. 健壮性：当输入不合法数据时，应能做适当处理，不至于引起严重后果。

  4. 效率：时间效率和空间效率。

时间复杂度

两种分析方法：

  1. 理论分析方法
  2. 实验分析方法
    处理一下几种情况： 非常复杂的算法，理论分析不可行；指数时间复杂度属于N-P问题范畴的；海量数据。

非递归算法时间复杂度分析步骤

  1. 确定度量问题的规模 n。
  2. 确定基本操作。
  3. 明确输入数据的分布对算法时间复杂性是否有影响。分别分析最坏情况下、最好情况、平均情况下时间复杂性。
  4. 针对算法实现方式，统计基本操作的执行次数，利用求和关系式求出时间复杂度的函数关系。对于非递归算法，时间复杂度函数关系 T(n) 一般是一个关于 n 的多项式函数。
  5. 进行时间复杂的渐进分析，明确时间复杂性渐进阶的类型。

递归算法时间复杂度分析步骤

  1. 确定问题规模 n。
  2. 确定基本操作。
  3. 明确输入数据的分布对算法时间复杂性是否有影响。分别分析最坏情况下、最好情况、平均情况下时间复杂性。
  4. 针对实现方式，写出时间复杂度 T(n) 的递归关系式。
  5. 进行时间复杂的渐进分析，明确时间复杂性渐进阶的类型。

例如：汉诺塔问题

有A、B、C三根柱子，A柱上有 n 个大小不一的盘子，盘子有大到小从下到上放置，要求将 A 上的盘子移动到 C 上，要求一次移动一个盘子，任何时候不允许大盘子在小盘子上面。

算法设计：

public void hanoi(int n, Char A, Char B, Char C){
    if(n == 1){
        move(A, C);//只有一个盘子，直接移动
    }
    hanoi(n-1, A, C, B);//将上面的 n-1 个盘子移动到 B
    move(A, C);//直接移动 A 最下面的盘子到 C
    hanoi(n-1, B, A, C);//将 B 上的 n-1 个盘子移动到 C
}

时间复杂度分析：

  1. 问题规模 n。
  2. 基本操作： 移动圆盘, 即 move(A, C)。
  3. 递归关系式： T(1) = 1; T(n) = 2T(n-1) + 1;
  4. 求解递归，得到 T(n) 函数式。

求解递归关系式可以用替代法或者特征方程法，这里用替代法求解：

T(n) = 2T(n-1) + 1
     = 2^2T(n-2) + 2 + 1
     = ...
     = 2^iT(n-i) + 2^(i-1) + ... + 2^1 + 1

2
带入 i = n - 1得 T(n) = 2^(n -1) + 2^(n-1) + … + 1 得 T(n) = 2^n - 1;即T(n) = O(2^n)。