算法的基础知识

算法的五大特性

确定性
有穷性
可行性
输入和输出（可以没有输入，但是得要有输出）

辨析

程序是不是算法？
答案是 False，因为程序可以没有输入。

算法的要求

正确性（correctness）
可读性（readability）
健壮性（robustness）
效率与低储存量需求

算法的书写

我们要把它写成一个函数。

声明行由返回值类型（int、char、double、float、void、long int）、函数名称和形式参数声明区构成

returnValueType functionName(type1 value1;type2 value2) {
    command 1;
    command 2;
    ……
    command n;
}

如果没有声明行，那一定要原型声明，如果不进行原型声明，就有可能造成 C 语言去猜测变量。

如果输入参数与定义的不匹配，那么会发生变量类型转换。

当然如果你把要声明的函数放到 main 函数的前面或者是放到头文件当中就不会需要声明行了。
总之，要知道，我们要用到函数来表示一个算法。譬如，我们要从顺序表（从零号位开始存数据，里面的数值都大于等于 0）中返回指定位置的值：

/*
#define maxSize 100 
typedef struct {
    elementType data[maxSize];
    int length;
};
*/
elementType initAlist(seqList *L, int i) {
    if(i > L->length) return -1;
    return L->data[i-1];
}

至于顺序表是什么，为什么要特别声明是从 0 号位开始，我们以后再说。
不过，在这里形式参数声明区代表的是要输入的值的区域，函数名称得表达出算法的用途，实在不行可以随意。

算法的衡量标准

即时间复杂度（time complexity）和空间复杂度（space complexity）。

时间复杂度（time complexity）

又分为事前估计和事后估计

事前估计

语句频度

顺序结构、分支结构、循环结构 —— 运行次数会有变化，取最大的运行次数。

渐进时间复杂度（asymptotic time complexity）

T (n) = O (f (n))，渐进时间复杂度。
主要是要找到关键操作（递归和循环），就是嵌套最深的语句，可以是判断、也可以是普通语句。
当存在最好和最坏情况后，用平均复杂度。

例题 ¹

多重循环
一重循环

事后统计

利用计算机的计时工具，用一组或多组数据去测。缺点是要运行程序，还会依赖于硬件、软件等因素。

空间复杂度（space complexity）

算法本身会占用：输入、输出、指令、常数、变量等。
看看弄出了多少空间被占用。
注意：如果是递归的算法，那就是看层数，不是看节点数，因为递归算法是单线程的弄完一个以后，就会删除掉。