首页 科技正文

若何从最坏、平均、最好的情形剖析复杂度?

admin 科技 2020-07-22 56 0

本篇文章收录于专辑: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)。

小结

通过上面的剖析,可以看到,最坏情形和最好情形是对照好评估的,而平均情形则对照难以盘算。

然则,最好情形又不能代表大多数样本,且平均情形与最坏情形在省略常数项的情形下往往是对照靠近的。

以是,通常,我们使用最坏情形来评估算法的时间复杂度,这也是对照简单的一种评估方式,且往往也是对照准确的。

后记

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

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

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

下一节,我们接着聊。

关注民众号“彤哥读源码”,解锁更多源码、基础、架构知识!

,

欧博亚洲APP下载

欢迎进入欧博亚洲APP下载(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

版权声明

本文仅代表作者观点,
不代表本站Allbet的立场。
本文系作者授权发表,未经许可,不得转载。

评论