算法

说到算法，我自己都没自信能说我了解算法。没参加过ACM，连一些最经典的算法问题都没一一搞定，排几个序，做个八皇后也算了解算法的话，说出来会笑掉大牙的。所以，这一章严格（不严格也一样）的来说，不是算法，而是几道C语言趣味题罢了。

什么是算法？

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点，也就是解决一个具体问题的步骤以及逻辑。

特征

高德纳在《计算机程序设计艺术》对算法的特征做了一下归纳：

输入：一个算法必须有零个或以上输入量。
输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地符合要求或期望。
有限性：一些定义规定算法必须在有限个步骤内完成任务。
有效性：又称可行性。算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

复杂度

关于算法，不得不说复杂度。在程序实现过程中，无非拿时间换空间，那空间换时间。

时间复杂度

算法需要消耗掉的时间资源。

时间复杂度一般用大写字母O表示，时间复杂度越大，程序效率越低。

O(1)：一条指令，如：访问数组某个元素、判断一个数的奇偶；
O(n)：需要执行n次，如：遍历一个数组；
O(log n)：每次呈对数形式接近目标，如：二分查找；
O(n^n)：执行次数呈幂函数是增长，如：多重循环、冒泡排序；

空间复杂度

算法需要消耗掉的空间资源。表示方式与时间复杂度相同。

空间复杂度计算的是程序在运行过程中，局部变量所占用的存储空间。它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。

常见算法举例

迭代算法：

在现有基础上，不断更新，每一次更接近最终目标。

如：N个数求最大值

int numbers[10] = {1, 5, 3, 10, 34, 0, 56, 9};
int max = numbers[0];

for (int i = 1; i < 10; i ++) {

   if (max < numbers[i]) {

       max = numbers[i];
   }
}
printf("max = %d", max);

递推算法

变化有一定规律，能写出递推公式，通过这个公式延伸至所有。

如：输出以下图形

*
**
***
****

for (int i = 0; i < 4; i ++) {

   for (int j = 0; j < i + 1; j ++) {

       printf("*");
   }
   printf("\n");
}

穷举算法

列出所有的可能性，根据条件一一排除。

如：求2000~2500年之间的闰年

for (int i = 2000; i <= 2500; i ++) {

   if (i % 400 == 0 || (i % 4 == 0 && i % 100 != 0)) {

       printf("%d ", i);
   }
}

递归算法

函数自己调用自己。

如：求n!，或数据结构中树的几种遍历方式

int test(int number) {

    int sum = 1;

    if (number > 0) {

        sum = number * test(number - 1);
        number --;
    }

    return sum;
}

其他算法

对于简单的程序逻辑，以上几种算法基本够用。感兴趣的同学，可以尝试着了解下以下几种算法：

分治算法：把一个复杂问题分割成几个小问题。例：快速排序、归并排序。
贪心算法：每次都选择最优条件。例：霍夫曼编码（最优二叉树）。