算法M是求解一个特定问题的有限个良好定义的相继步骤的列表。
通常可以有不止一种方法求f(X)。获得f(X)的算法M的选择依赖于算法的“效率”和“复杂性”。
算法的复杂性是算法效率的衡量标准。
假设 M 是一种算法，并设 n 为输入数据的规模。实施M所占用的时间和空间是衡量该算法之效率的两个主要指标。 时间由“键盘操作”次数衡量。
比如：
1. 对于排序和查找，对 比较次数 计数
2. 在计算中，对乘法计数而忽略加法
键盘操作的定义前提是其他操作时间大大小于或 最多与键盘操作时间成比例。 空间由实施该算法所需的最大内存来衡量。
算法 M 的复杂性是一个函数 f(n)，它对于输入数据的规模n给出运行该算法所需时间与所需存储空间。 执行一个算法所需存储空间通常就是数据规模的倍数。 因此，除非特殊情况，“复杂性”将指运行算法的时间。
求 复杂性函数f(n) 在复杂性理论中研究最多的两种情况是：
1. 最坏情况 对于任何可能的输入，f(n)的最大值
2. 平均情况 f(n)的期望值
给定一个包含n个元素的线性数组DATA，和一个特定的信息ITEM， 在数组DATA中求出ITEM的位置LOC，或者传送某个信息，比如LOC = 0 表示ITEM不出现DATA中。 线性查找算法解决这个问题的途径是将ITEM与DATA中的元素一个一个地进行比较，直到求出LOC为止。
线性查找算法的复杂性由ITEM与DATA[K]之间的比较数字C给出。 C(n)的最坏情况和平均情况如下：
1. **最坏情况** C(n) = n；
2. **平均情况** C(n) = (n + 1) / 2
假定M是一个算法，并设n为输入数据的大小，显示M的复杂性f(n)随着n的增长而增长。通常我们需要考察的是f(n)的增长率。 常常由f(n)与某标准函数相比较而得。假如： $$ \log_{2} n, n, n \log_{2} n, n^2, n^3, 2^n $$
等等，都可被用作为标准函数。 （对数函数 \log_2 n 增长最慢，而指数函数 2^n 增长最快）
定义 设f(x)与g(x)为定义于R或者R的子集上的任意两个函数，我们说“f(x)与g(x)同阶”，记作：
如果存在字数 k 和正常如C使得对于所有的x > k有：
同样地，当f(x) - h(x) = O(g(x))时，记：
计算机科学中一些著名的查找和排序算法的复杂性
- 线性查找：O(n)
- 二叉查找：O(\log n)
- 冒泡排序：O(n^2)
- 归并排序：O(n \log n)