第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號(hào)安全,請(qǐng)及時(shí)綁定郵箱和手機(jī)立即綁定

如何從最壞、平均、最好的情況分析復(fù)雜度?

图片描述

前言

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

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

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

那么,有没有更好地评估算法的方法呢?

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

案例

为了便于讲解,我写了一个小例子:

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)。

小结

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

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

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

后记

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

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

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

下一节,我们接着聊。

點(diǎn)擊查看更多內(nèi)容
TA 點(diǎn)贊

若覺(jué)得本文不錯(cuò),就分享一下吧!

評(píng)論

作者其他優(yōu)質(zhì)文章

正在加載中
  • 推薦
  • 評(píng)論
  • 收藏
  • 共同學(xué)習(xí),寫(xiě)下你的評(píng)論
感謝您的支持,我會(huì)繼續(xù)努力的~
掃碼打賞,你說(shuō)多少就多少
贊賞金額會(huì)直接到老師賬戶
支付方式
打開(kāi)微信掃一掃,即可進(jìn)行掃碼打賞哦
今天注冊(cè)有機(jī)會(huì)得

100積分直接送

付費(fèi)專欄免費(fèi)學(xué)

大額優(yōu)惠券免費(fèi)領(lǐng)

立即參與 放棄機(jī)會(huì)
微信客服

購(gòu)課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

公眾號(hào)

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)

舉報(bào)

0/150
提交
取消