之前讲了一下时间复杂度、空间复杂度以及大O表示法，举得例子也相对比较简单，今天在之前的基础上，再讲几个时间复杂度相关的知识。分别是最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度(worst case time complexity)、平均情况时间复杂度(average case time complexity) 和均摊时间复杂度（amortized time complexity）。这几个时间复杂度的分析可能会比上一节讲的时间复杂度分析复杂一点，但不会太复杂。
最好情况时间复杂度和最坏情况时间复杂度
还是先看一段代码。
int Find (int data[],int len,int element) {
int i;
int result = -1;
for ( i=0; i < len; i++) {
if (element == data[i]) {
result = i;
}
}
return result;
}
这段代码的意思是，向 Find 函数里传入一个数组 data 和一个整型 element ，若 element在数组 data 中，返回 element 在 数组 data 中的索引值，若不在数组 data 中，则返回 -1 。
要计算这段代码的时间复杂度，用上一节讲的方法很容易就得出 T(n) = O(n)，仔细看一下这段代码，会发现代码有点低效，因为在这段代码中，不管你有没有找到 element 在数组 data 中的位置，也不管你什么时候找到了 element 在数组 data 中的位置，都必须遍历一遍数组，所以，我们优化一下代码。
int Find (int data[],int len,int element) {
int i;
int result = -1;
for ( i=0; i < len; i++) {
if (element == data[i]) {
result = i;
break;
}
}
return result;
}
加了一个 break 后，当在数组 data 中找到 element 时，终止遍历操作，直接返回索引值，若遍历完成后没有找到 element ，则返回 -1。
这样，element 的查找过程有最好和最坏两个极端情况，最好的情况就是，当查找到数组 data 的第一个元素即为 element ，这样时间复杂度为 O(1)，最坏的情况就是遍历完整个数组 data 后，没有找到 element ，返回 -1，这样时间复杂度为 O(n)。这就是最好情况时间复杂度（best case time complexity）和最坏情况时间复杂度(worst case time complexity)。
平均情况时间复杂度
这两种复杂度是对应的都是极端情况下的复杂度，发生的概率不大，为了表示平均情况下的复杂度，现在引入一个概念：平均情况时间复杂度，简称 “平均时间复杂度”。平均时间复杂度怎么计算呢？对于上面这段代码，要查找元素 element 在数组中的位置，一共有 n+1 种情况，即在 0~n-1 位置和不在数组中。我们把每种情况下要遍历的元素个数累加起来，再除以 n+1，即 (1+2+...+n+n) / (n+1)，整理一下结果为 n(n+3) / 2(n+1)。利用上一节中的知识，将式子中的低阶项、常数项和系数都去掉，只保留最高阶项，所以计算出时间复杂度为 O(n),即为平均时间复杂度。
我们这种计算时间复杂度的方法好像有点缺点，就是忽略了每种情况发生的概率，从大处讲，有元素 element 在或者不在数组 data 中两种情况，我们先假设这两种情况发生的概率分别为 1/2，对于在数组中的情况，又分为 n 中不同的情况，即元素 element 可能在数组 data 的 1 or 2 or...or n 的位置，并且每个位置发生的概率都为 1/n ，这样，我们再计算一下平均时间复杂度，为 1*(1/2n) + 2*(1/2n) + ... + n*(1/2n) + n * (1/2)，整理一下为 (3n+1)/4，这个值是概率论中的加权平均值，也叫做期望值，所以平均时间复杂度的全称应该是加权平均时间复杂度或者期望时间复杂度， 很容易计算出平均时间复杂度为 O(n)。
均摊时间复杂度
还有一种与平均时间复杂度类似的复杂度，称为均摊时间复杂度。先看一下这段代码。
int[ ] array = new int[n];
int count = 0;
void Insert (int val) {
if (count == array.length) {
int sum = 0;
for ( int i = 0, i < array.length; i++) {
sum += array[i];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
这段代码只是为了说明这个均摊时间复杂度而写的，可能在语法上有些问题，但是逻辑上还是能很好的解释均摊时间复杂度的。这段代码什么意思呢，就是将一个数 val 插入一个数组 array ，每插入一次，计数器 count 就加1，直到 count == array.length 时，遍历所有数组 array ，将数组内所有元素累加，将累加值赋给 array[0] 。
这样每个空数组可以插入 n 次，到 n+1 次时，数组已经满了，就需要遍历数组求和，这种插入方式是有规律的，即遍历数组中 n 个元素求和后，后面直接插入 n-1 个数组，即求和时的时间复杂度为 O(n)，后面插入元素的时间复杂度为 O(1)。
我们再深入分析一下，这里向数组插入元素一共有 n+1 种情况，即 n 种数组未满时插入和 1 种数组满时插入，所以可以计算出平均时间复杂度：1/(n+1) + 2/(n+1) +... + n/(n+1)，整理一下，保留高阶项，平均时间复杂度为 O(1)，这就是我们说的均摊时间复杂度，其实就是一种特殊的平均时间复杂度。
小结
这一节，我们学习了一下 最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度和均摊情况时间复杂度，至此，复杂度相关的知识就学习得差不多了，但是还需要多看代码，多加练。，知识大都是不会太难的，学好知识、学懂知识也不难，那些知识学的很好的人，唯手熟尔罢了。
网友评论