数据结构——算法效率的度量

算法效率的度量

在这之前，首先介绍算法的五大特性与算法设计的要求。

五大特性

1. 有穷性：在有穷操作内完成
2. 确定性：算法只有唯一的执行路径，每一种输入对应唯一的输出
3. 可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
4. 输入：零个或多个输入
5. 输出：一个或多个输出

算法设计的要求

1. 正确性
2. 可读性
3. 健壮性
4. 效率与低存储量需求

算法效率的度量主要是通过时间维度和空间维度来考量的。

• 时间维度：是指执行当前算法所消耗的时间，我们通常用时间复杂度来描述。

• 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用空间复杂度来描述。

通常情况下，算法的时间消耗和空间消耗是二者不可兼得的关系，因此要求我们在编写算法时根据实际情况仔细斟酌。

一、时间复杂度

算法执行时间通过使用该算法编制程序在计算机上所消耗的时间来度量，而度量一个程序的执行时间通常有两种方法。

（1）事后统计的方法

目前计算机操作系统所提供的统计方法已经将时间精确到毫秒级，通过比较程序统计的执行时间长短即可比较出算法的时间复杂度。但这种方法有两个缺陷，一是统计时间依赖运行程序来测量，无法通过算法直接得出结果；二是所得时间的统计量依赖于计算机硬件、软件等环境因素，在不同的条件下执行结果并不一致。因此人们更长使用另一种事前估计的方法。

（2）事前分析估算的方法

同一种算法用不用的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机运行，再或者问题的规模不同，这些因素都会导致算法的执行时间不尽相同，这表明使用绝对的时间量度来衡量算法的效率是不合适的。因此我们需要一种相对的衡量方法，只取决于问题的规模n来决定，或者是，他是问题规模的函数。为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数$f(n)$，算法的时间量度记为

$$T(n)=O(f(n))$$

它表示随问题规模n增大，算法执行时间的增长率和$f(n)$的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。式中，$O$的含义是$T(n)$的数量级。

算法的时间复杂度不仅仅依赖于问题的规模，还取决于待输入的数据。例如在数组A[0:n-1]中，查找定值K的算法如下：

int findK(int A[], int n, int k)
{
	for (int i=0;i<n;i++){
        if (A[i]==k){
            return i;
        }
    }
    return -1; // 找不到返回-1
}

语句的频度是指语句重复执行的次数。

对于这个程序来说，若A中没有与K相等的数据，则i++语句频度为n，循环执行n次；若第0个数据为k，则i++频度为0，循环仅执行1次。

最坏时间复杂度是指在最坏情况下，算法的时间复杂度，对应上述算法中最后一次循环找到k或数组中没有K的情况；最好时间复杂度是指在最好的情况下，算法的时间复杂度，对应上述算法第一次循环便找到了K；平均时间复杂度是指在所有可能输入实例在等概率出现的情况下，算法的期望运行时间。一般总是考虑在最坏的情况下的时间复杂度，以保证算法的运行时间不会比它更长。

对于上面的算法，它的时间复杂度为$O(n)$，即最坏情况下需要遍历整个数组才能找到目标元素，或者确认目标元素不存在。对于一个无序数组来说，这已经是最优的线性搜索算法了，因为在最坏情况下你必须检查每个元素才能确定k是否在数组中。但如果这个数组是有序数组，则二分查找的算法有着更高的效率。

以下是一个基于二分查找的优化算法（假设数组是有序的）：

int findK(int A[], int n, int k)
{
    int left = 0;
    int right = n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (A[mid] == k) {
            return mid;
        } else if (A[mid] < k) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

二分查找每次迭代将搜索区间减半，每次迭代缩小到原先二分之一的范围，经过$\log_2(n)$次迭代后搜索区间缩小到1，因此时间复杂度是$O(\log n)$。

规则

在分析一个程序的时间复杂性时，有两条规则：

1. 加法规则：$T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))$
2. 乘法规则：$T(n)=T_1(n) \times T_2(n)=O(f(n)) \times O(g(n))=O(f(n) \times g(n))$

例如：

for (int i=0;i<n;i++){
	程序段1;
}
for (int j=0;j<n;j++){
	程序段2;
}

因此上述程序时间复杂度$O(n)+O(n)=O(n)$。

for (int i=0;i<n;i++){
	程序段1;
	for (int j=0;j<n;j++){
	程序段2;
	}
}

因此上述程序时间复杂度$O(n) /times O(n)=O(n)$。

for (int i=0;i<n;i++){
	程序段1;
	for (int j=0;j<n;j++){
	程序段2;
	}
}
for (int j=0;j<n;j++){
	程序段2;
}

因此上述程序时间复杂度$O(n^2) + O(n)=O(n^2)$。

在进行加法运算时，若将高时间复杂度的算法与低时间复杂度的相加，则取较高的项。$f(n)=n^3+n^2+n$的时间复杂度取$O(n^3)$。

常见的渐进时间复杂度

$$O(1)<O(log n)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$$

（3）为什么时间复杂度是$\log(n)$而不是$\log_2(n)$呢？

在大 O 表示法中，常数因子和常数项通常被省略。这是因为大 O 表示法旨在描述算法复杂度的增长速率，而不是具体的计算步骤或常数倍数。因此， $O(\log_2(n))$ 和 $O(\log(n))$ 被认为是等价的。

对数的底数转换

对数的底数转换公式为：

$$\log_a(x) = \frac{\log_b(x)}{\log_b(a)}$$

如果我们将对数的底数从 2 换成 10 或任何其他常数 $c$，可以看到：

$$\log_2(n) = \frac{\log(n)}{\log(2)}$$

由于 $\log(2)$ 是一个常数，所以 $\log_2(n)$ 和 $\log(n)$ 之间仅仅相差一个常数倍。大 O 表示法忽略这些常数因子，因此：

$$O(\log_2(n)) = O(\log(n))$$

大 O 表示法的性质

大 O 表示法关心的是当 $n$ 变得非常大时，算法的增长趋势。因此，常数因子和低阶项都可以忽略。例如，以下所有时间复杂度都是等价的：

• $O(2\log(n))$
• $O(3\log(n) + 5)$
• $O(\log_2(n))$

它们都简化为 $O(\log(n))$。

二、空间复杂度

类似于时间复杂度，我们用空间复杂度作为算法所需存储空间的量度，记作

$$S(n)=O(f(n))$$

其中n为问题的规模（或大小）。一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输人数据所占空间只取决于问题本身，和算法无关，则只需要分析除输人和程序之外的额外空间，否则应同时考虑输人本身所需空间（和输入数据的表示形式有关）。若额外空间相对于输人数据量来说是常数，则称此算法为原地工作，后面讨论的有些排序算法就属于这类。又如果所占空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。