今天正式開啟算法之旅！

作為一個(gè)合格的技術(shù)人員，算法是必備知識(shí)?？梢赃@么說，雖然不懂算法的人并不會(huì)失業(yè)，但如果你想快速晉升擺脫業(yè)務(wù)工程師CRUD的命運(yùn)就一定離不開算法。同時(shí)不管是對(duì)于工作還是面試都是非常有用的。

由于這是算法第一篇，所以我們先從簡(jiǎn)單的復(fù)雜度說起。

任何算法都離不開復(fù)雜度分析，衡量一個(gè)算法的強(qiáng)與弱，其中一個(gè)比較統(tǒng)一的標(biāo)準(zhǔn)就是看它們之間的復(fù)雜度。

你可能會(huì)有所疑問，為什么要看復(fù)雜度呢？我直接跑一下代碼看執(zhí)行時(shí)間不就完事了嗎？

是的這樣也能統(tǒng)計(jì)出時(shí)間，但這種方法存在非常大的局限性。

試想一下，你在這種情況下得到的結(jié)果是否非常依賴于所處的測(cè)試環(huán)境，例如同一段代碼在2G與8G的手機(jī)上運(yùn)行的時(shí)間能一樣嗎？

另外還有一個(gè)非常明顯的缺陷是樣本規(guī)模太小，同一算法可能對(duì)不同規(guī)模的數(shù)據(jù)會(huì)產(chǎn)生不同的效果。

例如對(duì)于小規(guī)模的排序，插入排序可能比快速排序更快。

所以我們需要一個(gè)更科學(xué)的方式來衡量算法的強(qiáng)與弱，而這個(gè)方法就是復(fù)雜度。

而算法的復(fù)雜度又分為時(shí)間復(fù)雜度與空間復(fù)雜度兩大類。其實(shí)難點(diǎn)就是時(shí)間復(fù)雜度的計(jì)算，空間復(fù)雜度相對(duì)簡(jiǎn)單許多。

大O表示法

在說復(fù)雜度之前，我們?cè)賮砹私庖幌滤谋硎痉椒ā?/p>

我們先從一個(gè)簡(jiǎn)單的例子進(jìn)行分析

fun test(n: Int) {
    var i = 0 //1
    while (i < n) { //2
        var j = 0 //3
        while (j < n) { //4
            j++ //5
        }
        i++ //6
    }
}

假設(shè)執(zhí)行每一行代碼的時(shí)間為k，那么上面的代碼從上往下依次執(zhí)行的時(shí)間總和為

T(n) = k + n * k + n * k + n^2 * k + n^2 * k + n * k 
    = (1 + 3 * n + 2 * n^2) * k

這個(gè)公式我們分解一下看，左邊T(n)代表代碼的執(zhí)行時(shí)間，右邊(1 + 3 * n + 2 * n^2)部分可以代表代碼的執(zhí)行次數(shù)總和，而k是每行代碼的執(zhí)行時(shí)間。

試想一下是否不管是什么代碼都可以由這三部分組成呢？

答案自然是可以的。

那么上面的表示法就產(chǎn)生了一個(gè)重要的概念了：代碼執(zhí)行時(shí)間T(n)與代碼的執(zhí)行次數(shù)總和成正比。

有了這個(gè)規(guī)律，我們就可以將上面的表達(dá)式轉(zhuǎn)換成大O來表示

T(n) = O(f(n))

其中n代表數(shù)據(jù)規(guī)模，T(n)代表代碼的執(zhí)行時(shí)間，f(n)代表代碼的執(zhí)行次數(shù)總和，大O代表代碼執(zhí)行時(shí)間T(n)與代碼的執(zhí)行次數(shù)總和成正比。

將表達(dá)式套入到f(n)中，最終表示為

T(n) = O(1 + 3 * n + 2 * n^2)

這就是大O表示法，它代表的并不是代碼執(zhí)行的真正時(shí)間，而是一種趨勢(shì)，即代表執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模變化的趨勢(shì)，業(yè)界稱之為漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。

如果n的規(guī)模很大，那么我們就可以將常數(shù)、系數(shù)與低價(jià)進(jìn)行忽略，因?yàn)樗鼈円呀?jīng)不能左右趨勢(shì)的變化。所以就得到我們?nèi)粘Ｋ吹降慕Y(jié)果

T(n) = O(n^2)

時(shí)間復(fù)雜度

說完大O表示法，現(xiàn)在正式分析時(shí)間復(fù)雜度。

我們考察一個(gè)算法，往往都要分析它的時(shí)間復(fù)雜度，那么時(shí)間復(fù)雜度又該如何又快又準(zhǔn)的分析出來呢？

其實(shí)很簡(jiǎn)單，我教大家?guī)讉€(gè)個(gè)方法，讓你更加迅速與準(zhǔn)確的得到時(shí)間復(fù)雜度。

貪心法則

何為貪心法則？簡(jiǎn)單來說就是找到你認(rèn)為最復(fù)雜的那段代碼，或者說循環(huán)次數(shù)最多的那段代碼。

在大O表示法中已經(jīng)說了，計(jì)算時(shí)間復(fù)雜度都會(huì)忽略常數(shù)、系數(shù)與低價(jià)，所以我們只需關(guān)注次數(shù)最多的那行代碼。例如:

fun search(n: Int): Int {
    var i = 0
    var result = 0

    while (i <= n) {
        result+=i
        i++
    }
    return result
}

這里一看就知道執(zhí)行最多的代碼在while循序中，所以用大O表示為

T(n) = O(3 * n)
     = O(n)

注意這里不管有多少個(gè)平級(jí)的while循序，最終通過加法合并在一起，然后去掉常數(shù)，時(shí)間復(fù)雜度還是O(n)。例如：

fun search(n: Int): Int {
    var i = 0
    var result = 0

    while (i <= n) {
        result+=i
        i++
    }
    
    var j = 0
    while (j <= n) {
        result+=j
        j++
    }
    
    return result
}

求同存異

這種累計(jì)的只適用于單個(gè)規(guī)模的變量，如果處在多個(gè)規(guī)模的變量，就直接按照正常的加法運(yùn)算進(jìn)行保留即可。例如：

fun search(n: Int, m: Int): Int {
    var i = 0
    var result = 0

    while (i <= n) {
        result+=i
        i++
    }
    
    var j = 0
    while (j <= m) {
        result+=j
        j++
    }
    
    return result
}

此時(shí)時(shí)間復(fù)雜度為O(n+m),因?yàn)榇嬖?code>n、m兩個(gè)不同規(guī)模的數(shù)據(jù)，所以不能直接合并，只能共存。

舉一反三，對(duì)于n、m嵌套的情況，就可以按照乘法法則進(jìn)行運(yùn)行。例如：

fun search(n: Int, m: Int): Int {
    var i = 0
    var result = 0

    while (i <= n) {
        result+=i
        i++
        var j = 0
        while (j <= m) {
             result+=j
             j++
          }
    }
    
    return result
}

時(shí)間復(fù)雜度為O(n*m)

相對(duì)來說我們遇到的時(shí)間復(fù)雜度的樣式并不多，主要為以下幾種

1. O(1)：常數(shù)階
2. O(n)：線性階
3. O(n^2)：平方階
4. O(logn)：對(duì)數(shù)階
5. O(nlogn)：線性對(duì)數(shù)階
6. O(2^n)：指數(shù)階
7. O(n!)：階乘階

而用的最多的就是O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)。

我們已經(jīng)對(duì)O(n)與O(n^2)進(jìn)行了舉例，至于常數(shù)階O(1)就不多說了，只要它沒有循環(huán)體或者遞歸存在，那它的時(shí)間復(fù)雜度就是O(1)

下面再來分析下O(logn)與O(nlogn)

對(duì)數(shù)階與線性對(duì)數(shù)階

var i = 1
while(i < n)
{
    i = i * 2
}

每次循環(huán)都將當(dāng)前值乘以2，所以不難得出它的終止表達(dá)式為

 2^0 , 2^1 , 2^2 , 2^3 , ... , 2^x = n

所以求得x等于log2^n，所以時(shí)間復(fù)雜度為O(log2^n)

如果我再將i = i * 2改成i = i * 3，其它都不變，此時(shí)時(shí)間復(fù)雜度為O(log3^n)

但是，根據(jù)對(duì)數(shù)之間的相互轉(zhuǎn)換規(guī)律，log3^n = log3^2 * log2^n，所以O(log3^n)可以轉(zhuǎn)成O(k * log2^n)。

其中k是常量可以進(jìn)行忽略，所以轉(zhuǎn)化之后它們都是O(log2^n)。

因此，在對(duì)數(shù)階時(shí)間復(fù)雜度的表示方法里，我們忽略對(duì)數(shù)的底，統(tǒng)一表示為O(logn)。

那么對(duì)應(yīng)的線性對(duì)數(shù)階O(nlogn)也就是一樣的，只是對(duì)對(duì)數(shù)階的代碼執(zhí)行了n遍，原理都是一樣的。

你可能還聽說過最好時(shí)間復(fù)雜度、最壞時(shí)間復(fù)雜度、平均時(shí)間復(fù)雜度與均攤時(shí)間復(fù)雜度。其實(shí)它們也很好理解，本質(zhì)就是字面上的意思，具體就不到這過多說明，后續(xù)遇到具體算法后再進(jìn)行具體說明。

最后再附上一張它們之間的曲線圖，來更加直觀的看它們之間的變化趨勢(shì)。

空間復(fù)雜度

分析完時(shí)間復(fù)雜度，再來看空間復(fù)雜度就簡(jiǎn)單許多了。

空間復(fù)雜度也是用大O來表示，空間復(fù)雜度也是漸進(jìn)空間復(fù)雜度，表示算法之間的存儲(chǔ)空間與數(shù)據(jù)規(guī)模之間的關(guān)系。

簡(jiǎn)單看一個(gè)例子

private fun test(n: Int) {
    var i = 0
    val temp = IntArray(n)
    while (i < n) {
        temp[i] = i + 1
    }
}

在這里申請(qǐng)了一個(gè)n大小的temp數(shù)組，只有這一塊有額外的空間申請(qǐng)，所以它的空間復(fù)雜度就是O(n)。

對(duì)于空間復(fù)雜度，我們常見的空間復(fù)雜度為：O(1)、O(n)與O(n^2)，而對(duì)于對(duì)數(shù)階、線性對(duì)數(shù)階、階乘階與指數(shù)階都基本用不到。所以相對(duì)于時(shí)間復(fù)雜度的分析，空間復(fù)雜度更加簡(jiǎn)單。

這個(gè)也會(huì)在之后的算法中進(jìn)行同步分析。

關(guān)于算法的復(fù)雜度今天就聊到這里，對(duì)于算法復(fù)雜度的分析，我們并不需要刻意的去找算法進(jìn)行練習(xí)，只需在每次遇到的算法的時(shí)候有復(fù)雜度的這個(gè)概念，然后在寫完算法之后進(jìn)行分析對(duì)比即可。

項(xiàng)目

android_startup: 提供一種在應(yīng)用啟動(dòng)時(shí)能夠更加簡(jiǎn)單、高效的方式來初始化組件，優(yōu)化啟動(dòng)速度。不僅支持Jetpack App Startup的全部功能，還提供額外的同步與異步等待、線程控制與多進(jìn)程支持等功能。

AwesomeGithub: 基于Github客戶端，純練習(xí)項(xiàng)目，支持組件化開發(fā)，支持賬戶密碼與認(rèn)證登陸。使用Kotlin語言進(jìn)行開發(fā)，項(xiàng)目架構(gòu)是基于Jetpack&DataBinding的MVVM；項(xiàng)目中使用了Arouter、Retrofit、Coroutine、Glide、Dagger與Hilt等流行開源技術(shù)。

flutter_github: 基于Flutter的跨平臺(tái)版本Github客戶端，與AwesomeGithub相對(duì)應(yīng)。

android-api-analysis: 結(jié)合詳細(xì)的Demo來全面解析Android相關(guān)的知識(shí)點(diǎn), 幫助讀者能夠更快的掌握與理解所闡述的要點(diǎn)。

daily_algorithm: 每日一算法，由淺入深，歡迎加入一起共勉。

歡迎關(guān)注Android補(bǔ)給站