数据结构与算法及其效率评估

一、算法的基本概念
算法（Algorithm） : 是对特定问题求解过程的系统化描述。其本质为一组有限的指令序列；该概念具备以下五个关键属性：
1.1、有穷性：步骤数量有限，执行所需时间亦为有限；
1.2、确定性：每条指令必须具有明确的定义。换句话说，对于相同的输入条件，必然产生一致的输出结果。
1.3、可行性：算法应具备可实现性，其中所描述的操作均能通过已有的基础运算经过有限次数完成。
1.4、输入
1.5、输出

评估一个优质算法的标准包括以下几个方面：
1.正确性
2.可读性
3.健壮性
4.效率及对存储资源的需求

二、算法效率的度量
2.1时间复杂度：语句频度指的是该语句在算法运行过程中被重复执行的次数。将整个算法中所有语句频度相加后得到T（n），它表示的是该算法问题规模n对应的函数形式，而时间复杂度主要关注T（n）的数量级；通常情况下，循环结构中最深层循环体内的操作频度与T（n）处于同一数量级。因此，在分析时间复杂度时，往往采用基本运算频度f（n）作为依据。由此得出时间复杂度表达式如下：
T(n) = O(f(n))
上述O符号表示的是T（n）的数量级关系。从数学角度严格定义来看，若T（n）和f(n)是两个定义在正整数集合上的函数，则存在正整数C和 n0，使得当n >= n0时，始终满足0 <= T(n