算法之帶你了解時(shí)間&空間復(fù)雜度

什么是算法？
算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰命令，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。如果一個(gè)算法有缺陷，或不適合于某個(gè)問題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問題。不同的算法可能用不同的時(shí)間、空間或效率來完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可用空間復(fù)雜度與時(shí)間復(fù)雜度來衡量。

這兩段代碼都可以稱之為算法，因?yàn)榉謩e可以解決兩個(gè)數(shù)相加和從1加到n的問題。算法并不一定要非常復(fù)雜，小到一行代碼，多到上萬行代碼，只要能解決特定問題，就是算法。

如何評(píng)估算法優(yōu)劣

使用不同算法，解決同一個(gè)問題，效率可能相差非常大

現(xiàn)有兩個(gè)求斐波那契數(shù) (fibonacci number) 的算法

（斐波那契數(shù)列：1 1 2 3 5 8 ……）
這里

public static int fib1(int n) {
    if (n <= 1) return n;
    return fib1(n - 1) + fib1(n - 2);
}

public static int fib2(int n) {
    if (n <= 1) return n;

    int first = 0;
    int second = 1;
    for (int i = 0; i < n - 1; i++) {
        int sum = first + second;
        first = second;
        second = sum;
    }
    return second;
}

這兩個(gè)算法哪個(gè)更優(yōu)呢？

如果單從執(zhí)行效率上進(jìn)行評(píng)估，可能會(huì)想到這么一種方案

比較不同算法對(duì)同一組輸入的執(zhí)行處理時(shí)間

這種方案也叫做：事后統(tǒng)計(jì)法

我們的做法是：

public static void main(String[] args) {
    int n = 45;//求第45個(gè)斐波那契數(shù)

    TimeTool.check("fib1", new Task() {
        public void execute() {
            System.out.println(fib1(n));
        }
    });//5.815秒

    TimeTool.check("fib2", new Task() {
        public void execute() {
            System.out.println(fib2(n));
        }
    });//0.0秒
}

上述方案有比較明顯的缺點(diǎn)

執(zhí)行時(shí)間嚴(yán)重依賴硬件以及運(yùn)行時(shí)各種不確定的環(huán)境因素

必須編寫相應(yīng)的測算代碼

測試數(shù)據(jù)的選擇比較難保證公正性 （n=100時(shí)可能第一種算法時(shí)間更短，n=200時(shí)可能第二種算法時(shí)間更短）

一般從以下維度來評(píng)估算法的優(yōu)劣

正確性、可讀性、健壯性（對(duì)不合理輸入的反應(yīng)能力和處理能力）

時(shí)間復(fù)雜度（time complexity）：估算程序指令的執(zhí)行次數(shù)（執(zhí)行時(shí)間）

空間復(fù)雜度（space complexity）：估算所需占用的存儲(chǔ)空間

我們用這種方案評(píng)估一下計(jì)算1+2+...+n的算法

顯然第二種算法更好。難道是因?yàn)榈诙N方法代碼更短嗎？斐波那契數(shù)列的例子已經(jīng)告訴我們并不是代碼越短越好。這個(gè)例子中第二個(gè)算法只需要三步運(yùn)算就可以解決問題，而第一種需要循環(huán)n次。首先都滿足正確性、可讀性、健壯性的條件，然后從時(shí)間復(fù)雜度來講，假定一步運(yùn)算的執(zhí)行時(shí)間的一定的，我們考察一下大致需要執(zhí)行多少次指令，就可以比較出兩種算法的時(shí)間長短；再從空間復(fù)雜度考慮，需要的變量越少、開辟的存儲(chǔ)空間越小，算法更好。

大O表示法

一般用大O表示法來描述復(fù)雜度，它表示的是數(shù)據(jù)規(guī)模 n 對(duì)應(yīng)的復(fù)雜度

方法步驟：

（1）估算時(shí)間復(fù)雜度/空間復(fù)雜度(主要是時(shí)間復(fù)雜度)

（2.1）忽略常數(shù)、系數(shù)、低階

? $9$>> O(1)

? $2n+6$ >> O(n)

? $n^2+2n+6$ >> O($n^2$)

? $4n^3+3n^2+22n+100$ >> O($n^3$)

(2.2) 對(duì)數(shù)階一般省略底數(shù)

? $log_2n=log_29+log_9n$ (任意底數(shù)的對(duì)數(shù)可通過乘以一個(gè)常數(shù)相互轉(zhuǎn)化)

? 所以 $log_2n$、$log_9n$ 統(tǒng)稱為 $logn$

注意：大O表示法僅僅是一種粗略的分析模型，是一種估算，能幫助我們短時(shí)間內(nèi)了解一個(gè)算法的執(zhí)行效率

計(jì)算下面幾段代碼的時(shí)間復(fù)雜度

public static void test1(int n) {
    //1（進(jìn)行一次判斷操作）
    if (n > 10) { 
        System.out.println("n > 10");
    } else if (n > 5) { // 2
        System.out.println("n > 5");
    } else {
        System.out.println("n <= 5"); 
    }
    // 1（定義一次i) + 4(i累加四次) + 4（判斷i<4四次) + 4（循環(huán)體一條語句執(zhí)行四次）=9
    for (int i = 0; i < 4; i++) {
        System.out.println("test");
    }
    // 大O表示法時(shí)間復(fù)雜度O(1)
}

public static void test2(int n) {
    // 1(定義一次i）+ 3n（i累加n次+判斷i<n n次+循環(huán)體一條語句執(zhí)行n次)=1+3n
    for (int i = 0; i < n; i++) {
        System.out.println("test");
    }
    // 大O表示法時(shí)間復(fù)雜度O(n)
}

public static void test3(int n) {
    // 1(定義一次i） + 2n（i累加n次+判斷i<n n次) + n(外層循環(huán)體語句執(zhí)行n次) * (1(定義一次j） + 3n（j累加n次+判斷j<n n次+內(nèi)層循環(huán)體一條語句執(zhí)行n次))=3n^2 + 3n + 1
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println("test");
        }
    }
    // 大O表示法時(shí)間復(fù)雜度O(n^2)
}

public static void test4(int n) {
    // 8 = 2^3
    // 16 = 2^4

    // 3 = log2(8)
    // 4 = log2(16)

    // 執(zhí)行次數(shù) = log2(n)
    while ((n = n / 2) > 0) {
        System.out.println("test");
    }
    // 大O表示法時(shí)間復(fù)雜度O(logn)
}

public static void test5(int n) {
    // log5(n)
    while ((n = n / 5) > 0) {
        System.out.println("test");
    }
    // 大O表示法時(shí)間復(fù)雜度O(logn)
}

public static void test7(int n) {
    // 1(定義一次i） + 2*log2(n)(i*2運(yùn)算次數(shù)) + log2(n)（外層循環(huán)執(zhí)行次數(shù)） * (1 + 3n)（內(nèi)層循環(huán)執(zhí)行次數(shù)）
    for (int i = 1; i < n; i = i * 2) {
        // 1 + 3n
        for (int j = 0; j < n; j++) {
            System.out.println("test");
        }
    }
    // 1 + 3*log2(n) + 2 * nlog2(n)
    // 大O表示法時(shí)間復(fù)雜度O(nlogn)
}

$O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2n)<O(n!)<O(n^n)$

可以借助函數(shù)生成工具對(duì)比復(fù)雜度的大小

https://zh.numberempire.com/graphingcalculator.php

篇幅有限，在此不再過多講解。總而言之，算法的目的你可以簡單的理解為在有效的時(shí)間內(nèi)用最快的方法來解答問題，這也是算法的魅力所在，吸引著無數(shù)coder為之努力。

如果您想提升自己，學(xué)習(xí)更多算法、高級(jí)編程語言技巧，這里有免費(fèi)的相關(guān)學(xué)習(xí)資料，歡迎加微信：19950277730獲取更多技術(shù)提升秘籍。這里不僅有志同道合的小伙伴，更有無數(shù)免費(fèi)編程技巧、學(xué)習(xí)視頻和資料，加上微信來一起探討學(xué)習(xí)技術(shù)吧！！