算法的复杂度

（1）算法的概念

一般认为：“程序 = 算法 + 数据结构”。算法是能解决问题的逻辑、方法和步骤，数据结构是数据在计算机中的存储和访问方式。算法和数据结构是紧密结合的，而且有些数据结构有特定的处理办法，此时很难把数据结构和算法区分开来。

算法（algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列。算法有以下5个特征

        （1）输入：一个算法可以有零个输入或多个输入。算法可以没有输入，如一个定时闹钟程序，它不需要输入，但是每隔一段时间就输出一个报警。

        （2）输出：一个算法有一个或多个输出。程序可以没有输入，但一定要有输出。

        （3）有穷性：一个算法必须在执行有穷步之后结束，且每一步都在有穷的时间内完成。

        （4）确定性：算法中的每条指令必须有确切的含义，对于相同的输入只能得到相同的输出。

（2）复杂度和大O记号

衡量算法性能的主要对象是时间复杂度，一般不考虑空间复杂度。因为一个算法的空间复杂度是容易分析的，而时间复杂度往往关系到算法的根本逻辑，不容易分析，更能说明一个程序的优劣。

1. O(1)

计算时间是一个参数，与问题的规模 n 无关。例如，用公式计算时，一次计算的复杂度就是O(1)；哈希算法用哈希函数在常数时间内计算出存储位置；在矩阵 A[ M ][ N ] 中查找 i 行 j 列的元素，只需要对 A[ i ][ j ] 做一次访问就够了；贪心法的时间复杂度也常常是O(1)。

2. O()

计算时间是对数，通常是以 2 为底的对数，每步计算后，问题规模缩小一半。二分法、倍增法、分治法的复杂度为（）。例如二分法，在一个长度为 n 的有序数列中查找某个数，用折半查找的方法，只需要  次就可以找到。

3. O(n)

计算时间随规模 n 线性增长。在很多情况下，这是算法可能达到的最优复杂度，因为对输入的 n 个数，程序一般需要处理所有数，即计算 n 次。例如，查找一个无序数列中的某个数，可能需要检查所有的数。再如图问题，一个图中有 V 个点和 E 条边，大多数图问题都需要搜索到所有的点和边，复杂度至少为O(V + E)

4. O()

O()常常是算法能达到的最优复杂度，n 个问题规模，为操作步骤。例如分治法，一共有 O() 个步骤，每个步骤对 n 个数操作一次，所以总复杂度为 O() 。用分治法思想实现的快速排序算法和归并排序算法，复杂度就是 O()。

5. O()

一个二重循环的算法时间复杂度为这么多，如冒泡排序是典型的二重循环。类似的复杂度有 O()、O()等，如矩阵乘法、Floyd算法，都是 3 个 for 循环。

6. O()

一般对应集合问题，如一个集合中有 n 个数，要求输出它的所有子集，共有  个子集

7. O( n !)

在排列问题中，如果要求输出 n 个数的全排列，共有 n！个，复杂度为 O(n!)。

在C/C++的算法竞赛中，时间限制一般是 1 秒，以下是不同算法复杂度与 n 的关系：