算法定义与特性

算法是指解决问题的步骤描述，在计算机中表现为有限的指令序列。

算法具有五个基本特性：

  1. 输入：一个算法必须有零个或以上的输入。
  2. 输出：一个算法必须有一个或以上的输出，输出量是算法计算的结果。
  3. 明确性：算法的每个步骤都具有确定的含义，不会出现二义性。
  4. 有穷性：算法在执行有限的步骤之后会自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。。
  5. 可行性：算法的每一步都是可行的，也就是说，每一步都能够通过执行有限次数完成。

设计一个好的算法需要符合以下几点：

  • 正确性：算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。
  • 可读性：算法设计的另一目的是为了全球阅读、理解和交流。可读性高有助于人们理解算法，晦涩难懂的算法往往隐含错误，不易被发现且难于调试和修改。
  • 健壮性：当输入数据不合法时，算法也能做出相关的处理，不是产生异常或是莫名其妙的结果。
  • 时间效率高和存储量低：设计算法应尽量满足时间效率高和存储量低的需求。

算法复杂度

算法的效率主要由以下两个复杂度来评估。

  • 时间复杂度（Time Complexity）：评估执行程序所需的时间。可以估算出程序对计算器处理器的使用程度。
  • 空间复杂度（Space Complexity）：评估执行程序所需的存储空间。可以估算出程序对计算器内存的使用程度。

好的算法应该是空间复杂度和时间复杂度都尽可能小，但现实情况往往是鱼和熊掌不可兼得，所以在有时候，我们可以牺牲空间换时间，或是牺牲时间换空间。

由于现代计算机扩展内存相对容易但提升处理器主频较为困难，所以时间复杂度往往比空间复杂度更容易出问题，因此我们在分析算法的复杂度时，一般是指算法的时间复杂度，即算法运行所需要的时间。

算法运行的时间跟很多因素有关，比如CPU的工作频率，问题的输入规模，算法计算过程等。要统计一个算法的运行时间，可以分前事后统计法和事前分析法。事后统计需要通过运行程序才能得出算法的运行时间，可行性比较低，比较依赖计算机硬件和软件因素，所以一般不予采用，而是采用事前分析估算的方法。

事前分析一个算法的运行时间包括以下几个方面的内容：

  1. 算法采用的策略、方法；
  2. 编译产生代码的质量；
  3. 问题的输入规模；
  4. 机器指令的执行速度；

抛开与计算机硬件、软件相关的因素，算法的运行时间只依赖于算法的好坏和问题的输入规模，这是我们分析一个算法的关键。下面通过一个求和的例子来计算算法的时间复杂度：

int i, sum = 0, n = 100;       // 执行1次
for(i = 1; i <= n ; i++) {     // 执行n次
    sum = sum + i;
}
printf("%d\n", sum);           // 执行1次

这个程序一共运行了1 + n + 1 = n+2 次，而如果将程序改成下面这样：

int sum = 0, n = 100;         // 执行1次
sum = (1 + n) * n / 2;        // 执行1次
printf("%d\n", sum);          // 执行1次

则同样是求和，这个程序只执行了 1 + 1 + 1 = 3 次，好坏显而易见。如果我们忽略开头和结尾，只关注代码的中间计算部分，则这两个算法的差别就是n次与1次的差距。

如果将上面的程序改成这样：

int i, j, sum = 0, n = 100;        // 执行1次
for(i = 1; i <= 100; i++){         // 执行n^2次
    for(j = 1; j <= 100; j++){
    sum = sum + j;
    }
}
printf("%d\n", sum);               // 执行1次

这个例子一共要执行n^2+2 次，显然这个算法相对于输入规模 n=100 来说，执行次数要比前两个算法很多，而且可以预测，随着n的增大，执行次数的增加也将远远多于前面两个算法。

到这里已经可以发现，测试算法运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数，把这个执行次数写成与输入规模相关的函数来表示算法的复杂度，比如上面的三个复杂度函数分别为：

f1(n) = n + 3;

f2(n) = 3;

f3(n) = n^2 + 2;

函数的渐近增长与大O计法

在近似比较算法的时间效率时，不需要通过详细的公式去推导算法之间的差别，只需要比较算法的渐近增长就可以了，假设有以下几个算法：Alt text

在n较小时，比较几个算法的执行次数并不能判断谁好谁坏，但随着n的增大，可以明显地看到，A最好，D最差，中间的B, B', C各有差别，但是差别也不大，这就是函数渐增长性。如果输入规模n没有限制，浙进增长最慢的算法是最优的。

算法的渐进增长可以表示成大O记法，大O记法基于以下一点计算：

判断一个算法的效率，函数中的常数和其他次要项常常可以忽略，而更应该关注最高项的阶数。

推导算法的大O阶的方法是：

  1. 用常数1取代运行时间中所有的加法常数
  2. 只保留函数的最高阶项
  3. 如果最高阶项存在，去除与这个项相乘的常数

通过以上方法，就可以得到算法的大O阶表示的时间复杂度。

Alt text

常用的时间复杂度

常数阶O(1)

int sum = 0, n = 100;        // 执行1次
sum = (1 + n) * n / 2;       // 执行1次
printf("%d\n", sum);         // 执行1次

线性阶O(n)

int i, sum = 0, n = 100;     // 执行1次
for(i = 1; i <= n ; i++){    // 执行n + 1次
    sum = sum + i;
}
printf("%d\n", sum)    ;     // 执行1次

对数阶O(logn)

int i = 1, n = 100;        // 执行1次
while(i < n) {             // 执行log2(n)次
    i = i * 2;
}

平方阶O(n^2)

int i, j, sum = 0, n = 100;       // 执行1次
for(i = 1; i <= 100; i++){        // 执行n^2次
    for(j = 1; j <= 100; j++){
        sum = sum + j;
    }
}
printf("%d\n", sum);            // 执行1次

各种时间复杂度的比较

常用的时间复杂度所耗费的时间从小到大依次是：

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < 0(n^n)

最坏情况与平均情况

分析一个算法时，往往还需要考虑算法在最坏情况和平均情况下的运行时间。以顺序查找为例，从n个元素的数组中查找某个数字时，如果数组的第一个元素就是查找的目标，则此时算法的时间复杂度为O(1)，但如果这个数字在数组的最后一个位置，则查找算法的时间复杂度将是O(n)，这是最坏的情况。

最坏情况运行时间是一种保证，在应用中是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况下的运行时间。

而平均运行时间也就是从概率的角度看，这个数字在每个位置出现的可能性都是相同的，所以平均的查找时间为n/2次后发现目标元素。

对算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度称为平均时间复杂度，一种情况是统计最坏情况下的时间复杂度，称为最坏时间复杂度。一般在没有特殊说明时，都是指最坏时间复杂度。

  • 无标签