第二章 程序设计基础知识

“程序 = 算法 + 数据结构”，其中算法可以理解为解决实际问题的方法，数据结构则是计算机存储、组织数据的方式。

算法是程序设计的核心和灵魂，有了算法就可以结合数据结构转变成程序。

第1节 程序基本常识

一、算法的定义及特征

算法就是解决问题的操作步骤。一个算法必须满足以下五个重要的特征:

1. 有穷性：执行有穷步，在有穷的时间内完成。
2. 确切性：每一条指令必须有确切的含义，不会产生歧义。在任何条件下算法只有唯一的一条执行路径。
3. 可行性：算法中的操作可以通过执行有限次来实现。
4. 输入：一个算法有零个或者多个输入。
5. 输出：一个算法有一个或者多个输出。

二、算法的复杂度

同一个问题可用不同的算法来解决，而一个算法质量的优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适的算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

（一）空间复杂度

空间复杂度指执行算法所需占用的内存空间。算法执行时所需的存储空间包括程序本身占用的空间、输入数据占用的空间以及算法执行时所需空间。

算法在时间的高效性和空间的高效性之间通常是矛盾的，所以一般会取一个平衡点。通常假设程序运行在足够大的内存空间中，所以研究更多的是算法的时间复杂度。

（二）时间复杂度

1. 定义及表示：指算法执行时所需消耗时间，通常用算法执行次数来衡量，记作 $T(n)=O(f(n))$ ，其中 $f(n)$ 是算法执行次数的函数。用大写 $O()$ 来体现算法时间复杂度的记法，称之为大 $O$ 记法。
2. 计算步骤
   • 找出基本操作确定规模 $n$ 。通常取最深层循环内的语句所描述的操作作为基本操作。
   • 计算执行次数的函数 $f(n)$ 并求出 $T(n)=O(f(n))$ 。 $O(f(n))$ 是取 $f(n)$ 中 $n$ 增长最快的那项系数为1的形式。
3. 计算规则：加法规则、乘法规则、比较规则。