今天我们把时间复杂度进一步细化，分为：
1.最好情况时间复杂度(best case time complexity)
2.最坏情况时间复杂度(worst case time complexity)
3.平均情况时间复杂度(average case time complexity)
复杂度分析
public int findGirl(int[] girlArray, int number) {
int i = 0;
int pos = -1;
int n = girlArray.lentgh();
for (; i < n; ++i) {
if (girlArray[i] == number) {
pos = i;
break;
}
}
return pos;
}
上面这段代码实现的功能是：寻找 int 类型变量 number 在 int 类型数组 girlArray 中的位置。这段代码在不同情况下，时间复杂度是不一样的，所以，为了 描述代码在不同情况下的时间复杂度，我们引入了 最好、最坏、平均时间复杂度
- 变量 number 在数组的第一个位置时，那么代码的时间复杂度是 O(1)
- 变量 number 在数组的最后一个位置时，那么代码的时间复杂度是 O(n)
- 当变量 number 不在数组中的时候，则需要将 int 类型的数组一个一个检查完毕才知道，这个时候时间复杂度就是 O(n)
最好情况时间复杂度
在最理想的情况下，假如 int 类型数组 girlArray 的第一个元素就是我们想要查找的变量 number，那么，时间复杂度就是 O(1)
最坏情况时间复杂度
最坏的情况，就是变量 number 在 int 类型数组的最后一位或者不在该数组中，此时我们需要一个一个检查，那么时间复杂度就是 O(n)
平均情况时间复杂度
其实最好与最坏都是极端情况，发生的概率并不大。为了能更好的的表示平均情况下的时间复杂度，在这里引入了一个新的词汇 平均情况时间复杂度
还是上面的那段代码，判断变量 number 在 int 类型数组中 girlArray 出现的位置情况，根据上面的介绍，我们知道变量 number 在 girlArray 数组中出现的情况有 n + 1 种，在数组中 n 种，不在数组中 1 种。每种情况我们要遍历的次数都不一样，我们把每种情况需要遍历的次数累加，然后再除以所有情况数 n + 1,就能得到需要遍历次数的平均值。公式就是 平均情况时间复杂度 = 每种情况遍历次数累加和 / 所有情况数量
平均情况时间复杂度为：
((1+2+3+......+n) + n) / (n + 1) = n(n+3) / 2(n+1)
根据前面我们介绍的 大 O 时间复杂度表示法，常量、低阶、系数可以省略，所以，平均情况时间复杂度是 O(n)
期望时间复杂度
上面的平均情况时间复杂度推导没有考虑 每种情况发生的概率，根据前面的介绍我们知道，变量 number 在和不在 girlArray 数组中的情况总计有 n + 1 种，每一种情况发生的概率是不一样的，所以，在分析平均情况时间复杂度的时候我们还需要将每种情况发生的概率考虑进去
在 n + 1 种情况中我们分为两种大类，一种是变量 number 在 girlArray 数组中，另一种是变量 n 不在 girlArray 数组中，所以它们的概率是 1 / 2
当变量 number 在 girlArray 数组中，变量 number 在 girlArray 数组中的每一个位置概率都为 1 / n。根据 概率乘法法则 可以知道变量 number 在 0~n-1 各个位置出现的概率为 1 / 2n
注意：这里不了解概率乘法法则的同学可以补一下相关知识，条件概率的乘法法则是求几个事情同时发生的概率
所以，在上面推导的基础上我们把每种情况发生的概率考虑进去，那么平均情况时间复杂度的计算过程就是：
考虑概率的平均情况时间复杂度：
((1(1/2n) + 2(1/2n) + 3(1/2n) + ...... + n(1/2n)) + n*(1/2)) / (n + 1) = ((3n + 1) / 4) / (n + 1) = 3n + 1 / 4n + 4
这就是概率论中的 加权平均值 也叫做 期望值，所以，平均情况时间复杂度全称叫: 加权平均情况时间复杂度 或者 期望时间复杂度。在引入每种情况发生的概率后，平均情况时间复杂度变成了 O(3n + 1 / 4n + 4)，忽略系数以及常量最终得到的加权平均情况时间复杂度为 O(n)
注意：多数情况下，并不区分 最好、最坏、平均情况时间复杂度。只有同一段代码在不同情况下的时间复杂度差别在量级的时候，我们才会区分这 3 种情况，为的是能够更加有效的描述代码的时间复杂度
网友评论