【久遠(yuǎn)講算法①】什么是時(shí)間復(fù)雜度

“閱讀本文大概需要6分鐘”

你好，我是久遠(yuǎn)，今天開始，由我來給大家分享算法以及數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識。

什么是算法

今天我們先來討論一個(gè)問題：什么是算法？

算法是指計(jì)算方法么？并不準(zhǔn)確。

算法這個(gè)名稱雖然聽著硬核，但是我們換個(gè)場景你就會非常熟悉。

小學(xué)數(shù)學(xué)課上，你是不是可以用 3+3+3 或者 3*3 來解決三個(gè)三相加這個(gè)問題，雖然算的結(jié)果都是9，但是中間我們用的方法是不一樣的。

假如你今天要做一道菜，你是不是需要菜譜，菜譜上肯定會告訴你，你做這個(gè)菜需要什么材料，分幾步完成，完成這道菜需要多久。

而我們今天要講的算法，就是計(jì)算機(jī)編程界的菜譜，它就是計(jì)算機(jī)解決問題的方法。用不同的辦法去解決同一個(gè)問題，結(jié)果雖然都一樣，但是過程可能千差萬別。

正因?yàn)橛?jì)算機(jī)解決問題的方法有很多個(gè)，我們便要拿標(biāo)準(zhǔn)去衡量，到底哪些算法更好，更適合我們?nèi)ナ褂谩?/span>

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

怎么衡量一個(gè)算法的好壞呢？

舉個(gè)現(xiàn)實(shí)的例子：

小明和小亮去企業(yè)面試，hr要求他們用代碼實(shí)現(xiàn)一個(gè)需求，一天之后，兩個(gè)人交付了各自的代碼，都能實(shí)現(xiàn)hr的需求。而只有小明被錄用了。這是因?yàn)椋?/span>

小明的代碼運(yùn)行一次花了50ms,內(nèi)存占用5MB。

而小亮的代碼運(yùn)行一次要花10s，占用內(nèi)存50MB。

小亮的代碼雖然能夠?qū)崿F(xiàn)功能，但是運(yùn)行時(shí)間和內(nèi)存占用都沒有小明的少，自然沒有被錄用。

所以我們衡量代碼的好壞要從時(shí)間和空間兩個(gè)角度去考慮。即：

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

• 空間復(fù)雜度

在本文中，我們先講解空間復(fù)雜度。

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

我們可以將時(shí)間復(fù)雜度劃分為兩個(gè)小概念：

• 基本操作次數(shù)
• 漸進(jìn)時(shí)間復(fù)雜度

基本操作次數(shù)

我們假設(shè)計(jì)算機(jī)運(yùn)行一行基礎(chǔ)代碼執(zhí)行一次運(yùn)算。

void T0101(){
System.out.print("hello world!"); //執(zhí)行一次
}

 print("helo world")#執(zhí)行一次

這個(gè)方法需要執(zhí)行1次運(yùn)算。

void T0102(int n){
for(int i = 0; i < n; i++){// 再計(jì)算for循環(huán)外層執(zhí)行次數(shù) n+1 次
System.out.print("hello world!")//先計(jì)算for循環(huán)里層執(zhí)行的次數(shù) n次
}
}

for i in range(n): #再計(jì)算for循環(huán)外層執(zhí)行次數(shù) n+1 次
    print("hello world!")#先計(jì)算for循環(huán)里層執(zhí)行的次數(shù)為 n次

上面這個(gè)方法需要執(zhí)行（n+1+n）= 2n+1 次運(yùn)算。

我們把算法需要執(zhí)行的運(yùn)算次數(shù)用 輸入大小n 的函數(shù)表示，即 T(n).

為了估算算法需要的運(yùn)行時(shí)間和簡化算法分析，我們引入時(shí)間復(fù)雜度的概念。

我們再來看幾個(gè)例子：

1. ,執(zhí)行次數(shù)是線性的。

void T0103(int n){
for(int i = 0; i < n; i++){ // 外層循環(huán)n次 
System.out.print("一"); //執(zhí)行一次
System.out.print("二"); //執(zhí)行一次
System.out.print("三"); //執(zhí)行一次
}
}

for i in range(n):# 外層循環(huán)n次 
    print("-")#執(zhí)行一次
    print("二")#執(zhí)行一次
    print("三")#執(zhí)行一次
    

2. ,執(zhí)行次數(shù)是用對數(shù)計(jì)算的。

void T0104(int n){
    for(int i = n; i>1; i/=2){//觀察n與i的運(yùn)算關(guān)系 成對數(shù)關(guān)系
        System.out.println("一");//執(zhí)行一次
        System.out.println("二");//執(zhí)行一次
        System.out.println("三");//執(zhí)行一次
        System.out.println("四");//執(zhí)行一次
        System.out.println("五");//執(zhí)行一次
    }
}

i = n #在這里n代表的是某個(gè)特定的數(shù)字，如果要進(jìn)行代碼復(fù)制，請將n改為指定的數(shù)字去運(yùn)行
while i > 1 :
    print("一")#執(zhí)行一次
    print("二")#執(zhí)行一次
    print("三")#執(zhí)行一次
    print("四")#執(zhí)行一次
    print("五")#執(zhí)行一次
    i = i//2

3. , 執(zhí)行次數(shù)是常量。

void T0105(int n){
    System.out.println("一");//沒有循環(huán)次數(shù)
    System.out.println("二");//只需要輸出兩次內(nèi)容執(zhí)行次數(shù)為2
}

print("一")#無循環(huán)次數(shù)
print("二")#只需要輸出兩次內(nèi)容執(zhí)行的次數(shù)為2

4. ,執(zhí)行次數(shù)為冪函數(shù)。

void T0106(int n) {
    for(int i = 0; i < n; i++) { // 循環(huán)次數(shù)為 n
        for(int j = 0; j < n; j++) {// 循環(huán)次數(shù)為 n
            System.out.println("Hello, World!"); //循環(huán)體時(shí)間復(fù)雜度為 O(1)
        }
    }
}

for i in range(n):#循環(huán)次數(shù)n
    for j in range(n):#循環(huán)次數(shù)n
        print("hello world")#循環(huán)體時(shí)間復(fù)雜度為O(1)

漸進(jìn)時(shí)間復(fù)雜度

現(xiàn)在我們已經(jīng)有了 T(n) ,是否就可以分析和比較代碼的運(yùn)行時(shí)間了呢？不不不，n你還沒確定呢。

假設(shè)A的執(zhí)行次數(shù)是，算法B執(zhí)行的次數(shù)是? ,這倆誰大就要取決于n了。

因此為了解決這類難題，我們有了漸進(jìn)時(shí)間復(fù)雜度的概念。

維基百科的定義如下：

在計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定性描述該算法的運(yùn)行時(shí)間。時(shí)間復(fù)雜度常用大O符號表述，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)。使用這種方式時(shí)，時(shí)間復(fù)雜度可被稱為是漸近的，亦即考察輸入值大小趨近無窮時(shí)的情況。

維基百科

直白的講就是，漸進(jìn)復(fù)雜度就是將我們計(jì)算的程序的執(zhí)行次數(shù)函數(shù)?簡化為數(shù)量級，例如?、?、?等。

那我們要如何推算出時(shí)間復(fù)雜度呢？有以下幾個(gè)原則：

• 如果運(yùn)行時(shí)間是常數(shù)級的（例如：1,2,3,4,6等），則直接用常數(shù)1代替表示。
• 只保留時(shí)間函數(shù)中的最高階項(xiàng)。
• 如果最高階項(xiàng)存在，則省去最高階項(xiàng)前面的系數(shù)。

例如，如果一個(gè)算法對于任何大小為 n （必須比 n0 大）的輸入，它至多需要? 的時(shí)間運(yùn)行完畢，那么它的漸近時(shí)間復(fù)雜度是?。

這個(gè)推算過程即為：

• 保留函數(shù)中的最高階項(xiàng)。

即:???

• 最高階項(xiàng)存在，則省去最高階項(xiàng)前面的系數(shù)。

即:???

我們再來復(fù)習(xí)一下我們剛才看的那幾個(gè)計(jì)算時(shí)間函數(shù)的例子。

最高階項(xiàng)為 ,省去3，則轉(zhuǎn)化為的時(shí)間復(fù)雜度為：

2. , 最高階項(xiàng)為?，省去系數(shù) 5，則轉(zhuǎn)化的時(shí)間復(fù)雜度為：

2. ，只有常數(shù)量級，則拿1替換常數(shù)，轉(zhuǎn)換后的時(shí)間復(fù)雜度為：

   
   

這四種時(shí)間復(fù)雜度究竟誰更快，誰更更慢呢？

當(dāng) n 足夠大時(shí)，我們可以得到這樣的結(jié)論：

<<<