如何从最坏、平均、最好的情况分析复杂度？

喜欢ヅ旅行 2023-03-01 03:23 30阅读 0赞

![file][]

> 本篇文章收录于专辑：[http://dwz.win/HjK][http_dwz.win_HjK]

# 前言 #

你好，我是彤哥，一个每天爬二十六层楼还不忘读源码的硬核男人。

上一节，我们从事后统计法过渡到渐近分析法，详细讲解了如何进行算法的复杂度分析。

但是，如果遵循严格的渐近分析法，需要掌握大量数学知识，这无疑给我们评估算法的优劣带来了很大的挑战。

那么，有没有更好地评估算法的方法呢？

答案是必然的，本节，我们就从最坏、平均、最好三种情况来分析分析复杂度。

# 案例 #

为了便于讲解，我写了一个小例子：

public class LinearSearch { 
        public static void main(String[] args) { 
            int[] array = new int[]{ 1, 8, 9, 3, 5, 6, 10, 13};
            int index = search(array, 10);
            System.out.println("index=" + index);
        }
    
        private static int search(int[] array, int value) { 
            for (int i = 0; i < array.length; i++) { 
                if (array[i] == value) { 
                    return i;
                }
            }
            return -1;
        }
    }

这个例子使用线性搜索从一个数组中查找一个元素，这个元素有可能存在，也有可能不存在于数组中。

# 最坏情况 #

在最坏情况下，要查找的元素不存在于数组中，此时，它的时间复杂度是多少呢？

很简单，必然需要遍历完所有元素才会发现要查找的元素不存在于数组中。

所以，最坏情况下，使用线性查找的时间复杂度为O(n)。

# 平均情况 #

在平均情况下，我们要照顾到每一个元素，此时，它的时间复杂度如何计算呢？

在上一节，我们已经讲过计算方式了，不过，这里考虑到有元素不存在于数组中，所以，是(n+1)种可能：

1*1/(n+1) + 2*/(n+1) + ... + n*1/(n+1) + (n+1)/(n+1) = 1/(n+1) * (n+1)(n+2)/2 = (n+2)/2

所以，在平均情况下，忽略掉常数项，使用线性查找的时间复杂度也是O(n)。

> 为什么要忽略掉常数项？
> 
> 当n趋向于无穷大的时候，常数项的意义不是很大，所以，可以忽略，比如(n+2)/2=n/2 + 1，n本身已经趋向于无穷大，加不加1有什么意义呢，n的倍数是2还是1/2并不会有明显的差别。
> 
> 同样地，低阶项一般也会抹掉，比如2n^2 + 3n + 1，当n趋向于无穷大的时候，n^2的值是远远大于3n的，所以，不需要保留3n。
> 
> 所以，计算复杂度时通常都会把常数项和低阶项抹掉，只保留高阶项。

# 最好情况 #

最好情况是什么呢？

如果我们要查找的元素正好是数组的第一个元素，查找一次就找到了，这无疑是最好的情况。

所以，在最好情况下，使用线性查找的时间复杂度是O(1)。

# 小结 #

通过上面的分析，可以看到，最坏情况和最好情况是比较好评估的，而平均情况则比较难以计算。

但是，最好情况又不能代表大多数样本，且平均情况与最坏情况在省略常数项的情况下往往是比较接近的。

所以，通常，我们使用最坏情况来评估算法的时间复杂度，这也是比较简单的一种评估方法，且往往也是比较准确的。

# 后记 #

本节，我们从最坏、平均、最好三种情况分析了线性查找的时间复杂度，经过详细地分析，我们得出结论，通常使用最坏情况来评估算法的时间复杂度。

请注意，我们这里使用了“通常”，说明有些情况是不能使用最坏情况来评估算法的时间复杂度的。

那么，你知道什么情况下不能使用最坏情况来评估算法的时间复杂度吗？