這篇文章主要介紹“怎么理解web的時(shí)間與空間復(fù)雜度”，在日常操作中，相信很多人在怎么理解web的時(shí)間與空間復(fù)雜度問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”怎么理解web的時(shí)間與空間復(fù)雜度”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

創(chuàng)新互聯(lián)公司是少有的成都網(wǎng)站建設(shè)、網(wǎng)站制作、營(yíng)銷(xiāo)型企業(yè)網(wǎng)站、小程序設(shè)計(jì)、手機(jī)APP,開(kāi)發(fā)、制作、設(shè)計(jì)、買(mǎi)鏈接、推廣優(yōu)化一站式服務(wù)網(wǎng)絡(luò)公司,從2013年創(chuàng)立,堅(jiān)持透明化,價(jià)格低,無(wú)套路經(jīng)營(yíng)理念。讓網(wǎng)頁(yè)驚喜每一位訪客多年來(lái)深受用戶(hù)好評(píng)

算法（Algorithm）是指用來(lái)操作數(shù)據(jù)、解決程序問(wèn)題的一組方法。對(duì)于同一個(gè)問(wèn)題，使用不同的算法，也許最終得到的結(jié)果是一樣的，比如排序就有前面的十大經(jīng)典排序和幾種奇葩排序，雖然結(jié)果相同，但在過(guò)程中消耗的資源和時(shí)間卻會(huì)有很大的區(qū)別，比如快速排序與猴子排序：）。

那么我們應(yīng)該如何去衡量不同算法之間的優(yōu)劣呢？

主要還是從算法所占用的「時(shí)間」和「空間」兩個(gè)維度去考量。

• 時(shí)間維度：是指執(zhí)行當(dāng)前算法所消耗的時(shí)間，我們通常用「時(shí)間復(fù)雜度」來(lái)描述。

• 空間維度：是指執(zhí)行當(dāng)前算法需要占用多少內(nèi)存空間，我們通常用「空間復(fù)雜度」來(lái)描述。

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

大O符號(hào)表示法

大O表示法：算法的時(shí)間復(fù)雜度通常用大O符號(hào)表述，定義為 T[n] = O(f(n))。稱(chēng)函數(shù)T(n)以f(n)為界或者稱(chēng)T(n)受限于f(n)。

如果一個(gè)問(wèn)題的規(guī)模是n，解這一問(wèn)題的某一算法所需要的時(shí)間為T(mén)(n)。T(n)稱(chēng)為這一算法的“時(shí)間復(fù)雜度”。

上面公式中用到的 Landau符號(hào)是由德國(guó)數(shù)論學(xué)家保羅·巴赫曼（Paul Bachmann）在其1892年的著作《解析數(shù)論》首先引入，由另一位德國(guó)數(shù)論學(xué)家艾德蒙·朗道（Edmund Landau）推廣。Landau符號(hào)的作用在于用簡(jiǎn)單的函數(shù)來(lái)描述復(fù)雜函數(shù)行為，給出一個(gè)上或下（確）界。在計(jì)算算法復(fù)雜度時(shí)一般只用到大O符號(hào)，Landau符號(hào)體系中的小o符號(hào)、Θ符號(hào)等等比較不常用。這里的O，最初是用大寫(xiě)希臘字母，但現(xiàn)在都用大寫(xiě)英語(yǔ)字母O；小o符號(hào)也是用小寫(xiě)英語(yǔ)字母o，Θ符號(hào)則維持大寫(xiě)希臘字母Θ。

大O符號(hào)是一種算法「復(fù)雜度」的「相對(duì)」「表示」方式。

這個(gè)句子里有一些重要而嚴(yán)謹(jǐn)?shù)挠迷~：

• 相對(duì)(relative)：你只能比較相同的事物。你不能把一個(gè)做算數(shù)乘法的算法和排序整數(shù)列表的算法進(jìn)行比較。但是，比較2個(gè)算法所做的算術(shù)操作（一個(gè)做乘法，一個(gè)做加法）將會(huì)告訴你一些有意義的東西；

• 表示(representation)：大O(用它最簡(jiǎn)單的形式)把算法間的比較簡(jiǎn)化為了一個(gè)單一變量。這個(gè)變量的選擇基于觀察或假設(shè)。例如，排序算法之間的對(duì)比通常是基于比較操作(比較2個(gè)結(jié)點(diǎn)來(lái)決定這2個(gè)結(jié)點(diǎn)的相對(duì)順序)。這里面就假設(shè)了比較操作的計(jì)算開(kāi)銷(xiāo)很大。但是，如果比較操作的計(jì)算開(kāi)銷(xiāo)不大，而交換操作的計(jì)算開(kāi)銷(xiāo)很大，又會(huì)怎么樣呢？這就改變了先前的比較方式；

• 復(fù)雜度(complexity)：如果排序10,000個(gè)元素花費(fèi)了我1秒，那么排序1百萬(wàn)個(gè)元素會(huì)花多少時(shí)間？在這個(gè)例子里，復(fù)雜度就是相對(duì)其他東西的度量結(jié)果。

常見(jiàn)的時(shí)間復(fù)雜度量級(jí)

我們先從常見(jiàn)的時(shí)間復(fù)雜度量級(jí)進(jìn)行大O的理解：

• 常數(shù)階O(1)

• 線性階O(n)

• 平方階O(n2)

• 對(duì)數(shù)階O(logn)

• 線性對(duì)數(shù)階O(nlogn)

O(1)

無(wú)論代碼執(zhí)行了多少行，其他區(qū)域不會(huì)影響到操作，這個(gè)代碼的時(shí)間復(fù)雜度都是O(1)

void swapTwoInts(int &a, int &b){
  int temp = a;
  a = b;
  b = temp;
}

O(n)

在下面這段代碼，for循環(huán)里面的代碼會(huì)執(zhí)行 n 遍，因此它消耗的時(shí)間是隨著 n 的變化而變化的，因此可以用O(n)來(lái)表示它的時(shí)間復(fù)雜度。

int sum ( int n ){
   int ret = 0;
   for ( int i = 0 ; i <= n ; i ++){
      ret += i;
   }
   return ret;
}

特別一提的是 c * O(n) 中的 c 可能小于 1 ，比如下面這段代碼：

void reverse ( string &s ) {
    int n = s.size();
    for (int i = 0 ; i < n/2 ; i++){
      swap ( s[i] , s[n-1-i]);
    }
}

O(n2)

當(dāng)存在雙重循環(huán)的時(shí)候，即把 O(n) 的代碼再嵌套循環(huán)一遍，它的時(shí)間復(fù)雜度就是 O(n2) 了。

void selectionSort(int arr[],int n){
   for(int i = 0; i < n ; i++){
     int minIndex = i;
     for (int j = i + 1; j < n ; j++ )
       if (arr[j] < arr[minIndex])
           minIndex = j;

     swap ( arr[i], arr[minIndex]);
   }
}

這里簡(jiǎn)單的推導(dǎo)一下

• 當(dāng) i = 0 時(shí)，第二重循環(huán)需要運(yùn)行 (n - 1)  次

• 當(dāng) i = 1 時(shí)，第二重循環(huán)需要運(yùn)行 (n - 2)  次

• 。。。。。。

不難得到公式：

(n - 1) + (n - 2) + (n - 3) + ... + 0
= (0 + n - 1) * n / 2
= O (n ^2)

當(dāng)然并不是所有的雙重循環(huán)都是 O(n2)，比如下面這段輸出 30n 次Hello,五分鐘學(xué)算法：）的代碼。

void printInformation (int n ){
   for (int i = 1 ; i <= n ; i++)
        for (int j = 1 ; j <= 30 ; j ++)
           cout<< "Hello,五分鐘學(xué)算法：）"<< endl;
}

O(logn)

int binarySearch( int arr[], int n , int target){
  int l = 0, r = n - 1;
  while ( l <= r) {
    int mid = l + (r - l) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] > target ) r = mid - 1;
    else l = mid + 1;
  }
  return -1;
}

在二分查找法的代碼中，通過(guò)while循環(huán)，成 2 倍數(shù)的縮減搜索范圍，也就是說(shuō)需要經(jīng)過(guò) log2^n 次即可跳出循環(huán)。

同樣的還有下面兩段代碼也是 O(logn) 級(jí)別的時(shí)間復(fù)雜度。

// 整形轉(zhuǎn)成字符串
string intToString ( int num ){
 string s = "";
 // n 經(jīng)過(guò)幾次“除以10”的操作后，等于0
 while (num ){
  s += '0' + num%10;
  num /= 10;
 }
 reverse(s)
 return s;
}

void hello (int n ) {
   // n 除以幾次 2 到 1
   for ( int sz = 1; sz < n ; sz += sz) 
     for (int i = 1; i < n; i++)
        cout<< "Hello,五分鐘學(xué)算法：）"<< endl;
}

O(nlogn)

將時(shí)間復(fù)雜度為O(logn)的代碼循環(huán)N遍的話，那么它的時(shí)間復(fù)雜度就是 n * O(logn)，也就是了O(nlogn)。

void hello (){
  for( m = 1 ; m < n ; m++){
    i = 1;
    while( i < n ){
        i = i * 2;
    }
   }
}

不常見(jiàn)的時(shí)間復(fù)雜度

下面來(lái)分析一波另外幾種復(fù)雜度： 遞歸算法的時(shí)間復(fù)雜度（recursive algorithm time complexity），最好情況時(shí)間復(fù)雜度（best case time complexity）、最壞情況時(shí)間復(fù)雜度（worst case time complexity）、平均時(shí)間復(fù)雜度（average case time complexity）和均攤時(shí)間復(fù)雜度（amortized time complexity）。

遞歸算法的時(shí)間復(fù)雜度

如果遞歸函數(shù)中，只進(jìn)行一次遞歸調(diào)用，遞歸深度為depth；

在每個(gè)遞歸的函數(shù)中，時(shí)間復(fù)雜度為T(mén)；

則總體的時(shí)間復(fù)雜度為O(T * depth)。

在前面的學(xué)習(xí)中，歸并排序 與 快速排序 都帶有遞歸的思想，并且時(shí)間復(fù)雜度都是O(nlogn) ，但并不是有遞歸的函數(shù)就一定是 O(nlogn) 級(jí)別的。從以下兩種情況進(jìn)行分析。

① 遞歸中進(jìn)行一次遞歸調(diào)用的復(fù)雜度分析

二分查找法

int binarySearch(int arr[], int l, int r, int target){
    if( l > r ) return -1;

    int mid = l + (r-l)/2; 
    if( arr[mid] == target ) return mid;  
    else if( arr[mid] > target ) 
    return binarySearch(arr, l, mid-1, target);    // 左邊 
    else
    return binarySearch(arr, mid+1, r, target);   // 右邊
}

比如在這段二分查找法的代碼中，每次在 [ l ,  r  ] 范圍中去查找目標(biāo)的位置，如果中間的元素arr[mid]不是target，那么判斷arr[mid]是比target大 還是 小 ，進(jìn)而再次調(diào)用binarySearch這個(gè)函數(shù)。

在這個(gè)遞歸函數(shù)中，每一次沒(méi)有找到target時(shí)，要么調(diào)用 左邊 的binarySearch函數(shù)，要么調(diào)用 右邊 的binarySearch函數(shù)。也就是說(shuō)在此次遞歸中，最多調(diào)用了一次遞歸調(diào)用而已。根據(jù)數(shù)學(xué)知識(shí)，需要log2n次才能遞歸到底。因此，二分查找法的時(shí)間復(fù)雜度為 O(logn)。

求和

int sum (int n) {
  if (n == 0) return 0;
  return n + sum( n - 1 )
}

在這段代碼中比較容易理解遞歸深度隨輸入 n 的增加而線性遞增，因此時(shí)間復(fù)雜度為 O (n)。

求冪

//遞歸深度：logn
//時(shí)間復(fù)雜度：O(logn)
double pow( double x, int n){
  if (n == 0) return 1.0;

  double t = pow(x,n/2);
  if (n %2) return x*t*t;
  return t * t;
}

遞歸深度為logn，因?yàn)槭乔笮枰?2 多少次才能到底。

② 遞歸中進(jìn)行多次遞歸調(diào)用的復(fù)雜度分析

遞歸算法中比較難計(jì)算的是多次遞歸調(diào)用。

先看下面這段代碼，有兩次遞歸調(diào)用。

// O(2^n) 指數(shù)級(jí)別的數(shù)量級(jí)，后續(xù)動(dòng)態(tài)規(guī)劃的優(yōu)化點(diǎn)
int f(int n){
 if (n == 0) return 1;
 return f(n-1) + f(n - 1);
}

與之有所類(lèi)似的是 歸并排序 的遞歸樹(shù)，區(qū)別點(diǎn)在于

• 1. 上述例子中樹(shù)的深度為n，而 歸并排序 的遞歸樹(shù)深度為logn。

• 2. 上述例子中每次處理的數(shù)據(jù)規(guī)模是一樣的，而在 歸并排序 中每個(gè)節(jié)點(diǎn)處理的數(shù)據(jù)規(guī)模是逐漸縮小的

因此，在如 歸并排序 等排序算法中，每一層處理的數(shù)據(jù)量為 O(n) 級(jí)別，同時(shí)有logn層，時(shí)間復(fù)雜度便是 O(nlogn)。

最好、最壞情況時(shí)間復(fù)雜度

最好、最壞情況時(shí)間復(fù)雜度指的是特殊情況下的時(shí)間復(fù)雜度。

動(dòng)圖表明的是在數(shù)組 array 中尋找變量 x 第一次出現(xiàn)的位置，若沒(méi)有找到，則返回 -1；否則返回位置下標(biāo)。

int find(int[] array, int n, int x) {
  for (  int i = 0 ; i < n; i++) {
    if (array[i] == x) {
        return i;
        break;
    }
  }
  return -1;
}

在這里當(dāng)數(shù)組中第一個(gè)元素就是要找的 x 時(shí)，時(shí)間復(fù)雜度是 O(1)；而當(dāng)最后一個(gè)元素才是 x 時(shí)，時(shí)間復(fù)雜度則是 O(n)。

最好情況時(shí)間復(fù)雜度就是在最理想情況下執(zhí)行代碼的時(shí)間復(fù)雜度，它的時(shí)間是最短的；最壞情況時(shí)間復(fù)雜度就是在最糟糕情況下執(zhí)行代碼的時(shí)間復(fù)雜度，它的時(shí)間是最長(zhǎng)的。

平均情況時(shí)間復(fù)雜度

最好、最壞時(shí)間復(fù)雜度反應(yīng)的是極端條件下的復(fù)雜度，發(fā)生的概率不大，不能代表平均水平。那么為了更好的表示平均情況下的算法復(fù)雜度，就需要引入平均時(shí)間復(fù)雜度。

平均情況時(shí)間復(fù)雜度可用代碼在所有可能情況下執(zhí)行次數(shù)的加權(quán)平均值表示。

還是以find函數(shù)為例，從概率的角度看， x 在數(shù)組中每一個(gè)位置的可能性是相同的，為 1 / n。那么，那么平均情況時(shí)間復(fù)雜度就可以用下面的方式計(jì)算：

((1 + 2 + … + n) / n + n)  /  2 = (3n + 1) / 4

find函數(shù)的平均時(shí)間復(fù)雜度為 O(n)。

均攤復(fù)雜度分析

我們通過(guò)一個(gè)動(dòng)態(tài)數(shù)組的push_back操作來(lái)理解均攤復(fù)雜度。

template <typename T>
class MyVector{
private:
    T* data;
    int size;       // 存儲(chǔ)數(shù)組中的元素個(gè)數(shù)
    int capacity;   // 存儲(chǔ)數(shù)組中可以容納的最大的元素個(gè)數(shù)
    // 復(fù)雜度為 O(n)
    void resize(int newCapacity){
        T *newData = new T[newCapacity];
        for( int i = 0 ; i < size ; i ++ ){
              newData[i] = data[i];
            }
        data = newData;
        capacity = newCapacity;
    }
public:
    MyVector(){
        data = new T[100];
        size = 0;
        capacity = 100;
    }
    // 平均復(fù)雜度為 O(1)
    void push_back(T e){
        if(size == capacity)
            resize(2 * capacity);
        data[size++] = e;
    }
    // 平均復(fù)雜度為 O(1)
    T pop_back(){
        size --;
        return data[size];
    }

};

push_back實(shí)現(xiàn)的功能是往數(shù)組的末尾增加一個(gè)元素，如果數(shù)組沒(méi)有滿，直接往后面插入元素；如果數(shù)組滿了，即size == capacity，則將數(shù)組擴(kuò)容一倍，然后再插入元素。

例如，數(shù)組長(zhǎng)度為 n，則前 n 次調(diào)用push_back復(fù)雜度都為 O(1) 級(jí)別；在第 n + 1 次則需要先進(jìn)行 n 次元素轉(zhuǎn)移操作，然后再進(jìn)行 1 次插入操作，復(fù)雜度為 O(n)。

因此，平均來(lái)看：對(duì)于容量為 n 的動(dòng)態(tài)數(shù)組，前面添加元素需要消耗了 1 * n 的時(shí)間，擴(kuò)容操作消耗  n 時(shí)間 ，
總共就是 2 * n 的時(shí)間，因此均攤時(shí)間復(fù)雜度為 O(2n / n) = O(2)，也就是 O(1) 級(jí)別了。

可以得出一個(gè)比較有意思的結(jié)論：一個(gè)相對(duì)比較耗時(shí)的操作，如果能保證它不會(huì)每次都被觸發(fā)，那么這個(gè)相對(duì)比較耗時(shí)的操作，它所相應(yīng)的時(shí)間是可以分?jǐn)偟狡渌牟僮髦衼?lái)的。

空間復(fù)雜度

一個(gè)程序的空間復(fù)雜度是指運(yùn)行完一個(gè)程序所需內(nèi)存的大小。利用程序的空間復(fù)雜度，可以對(duì)程序的運(yùn)行所需要的內(nèi)存多少有個(gè)預(yù)先估計(jì)。一個(gè)程序執(zhí)行時(shí)除了需要存儲(chǔ)空間和存儲(chǔ)本身所使用的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還需要一些對(duì)數(shù)據(jù)進(jìn)行操作的工作單元和存儲(chǔ)一些為現(xiàn)實(shí)計(jì)算所需信息的輔助空間。程序執(zhí)行時(shí)所需存儲(chǔ)空間包括以下兩部分：

(1) 固定部分，這部分空間的大小與輸入/輸出的數(shù)據(jù)的個(gè)數(shù)多少、數(shù)值無(wú)關(guān)。主要包括指令空間（即代碼空間）、數(shù)據(jù)空間（常量、簡(jiǎn)單變量）等所占的空間。這部分屬于靜態(tài)空間。

(2) 可變空間，這部分空間的主要包括動(dòng)態(tài)分配的空間，以及遞歸棧所需的空間等。這部分的空間大小與算法有關(guān)。

一個(gè)算法所需的存儲(chǔ)空間用f(n)表示。S(n)=O(f(n))，其中n為問(wèn)題的規(guī)模，S(n)表示空間復(fù)雜度。

空間復(fù)雜度可以理解為除了原始序列大小的內(nèi)存，在算法過(guò)程中用到的額外的存儲(chǔ)空間。

以二叉查找樹(shù)為例，舉例說(shuō)明二叉排序樹(shù)的查找性能。

平衡二叉樹(shù)

如果二叉樹(shù)的是以紅黑樹(shù)等平衡二叉樹(shù)實(shí)現(xiàn)的，則 n 個(gè)節(jié)點(diǎn)的二叉排序樹(shù)的高度為 log2n+1 ，其查找效率為O(Log2n)，近似于折半查找。

列表二叉樹(shù)

如果二叉樹(shù)退變?yōu)榱斜砹?，則 n 個(gè)節(jié)點(diǎn)的高度或者說(shuō)是長(zhǎng)度變?yōu)榱薾，查找效率為O(n)，變成了順序查找。

一般二叉樹(shù)

介于「列表二叉樹(shù)」與「平衡二叉樹(shù)」之間，查找性能也在O(Log2n)到O(n)之間。

冰火交融

對(duì)于一個(gè)算法，其時(shí)間復(fù)雜度和空間復(fù)雜度往往是相互影響的。

比如說(shuō)，要判斷某某年是不是閏年：

• 1. 可以編寫(xiě)一個(gè)算法來(lái)計(jì)算，這也就意味著，每次給一個(gè)年份，都是要通過(guò)計(jì)算得到是否是閏年的結(jié)果。

• 2. 還有另一個(gè)辦法就是，事先建立一個(gè)有 5555 個(gè)元素的數(shù)組（年數(shù)比現(xiàn)實(shí)多就行），然后把所有的年份按下標(biāo)的數(shù)字對(duì)應(yīng)，如果是閏年，此數(shù)組項(xiàng)的值就是1，如果不是值為0。這樣，所謂的判斷某一年是否是閏年，就變成了查找這個(gè)數(shù)組的某一項(xiàng)的值是多少的問(wèn)題。此時(shí)，我們的運(yùn)算是最小化了，但是硬盤(pán)上或者內(nèi)存中需要存儲(chǔ)這 5555 個(gè) 0 和 1 。

這就是典型的使用空間換時(shí)間的概念。

當(dāng)追求一個(gè)較好的時(shí)間復(fù)雜度時(shí)，可能會(huì)使空間復(fù)雜度的性能變差，即可能導(dǎo)致占用較多的存儲(chǔ)空間；  
反之，求一個(gè)較好的空間復(fù)雜度時(shí)，可能會(huì)使時(shí)間復(fù)雜度的性能變差，即可能導(dǎo)致占用較長(zhǎng)的運(yùn)行時(shí)間。

另外，算法的所有性能之間都存在著或多或少的相互影響。因此，當(dāng)設(shè)計(jì)一個(gè)算法(特別是大型算法)時(shí)，要綜合考慮算法的各項(xiàng)性能，算法的使用頻率，算法處理的數(shù)據(jù)量的大小，算法描述語(yǔ)言的特性，算法運(yùn)行的機(jī)器系統(tǒng)環(huán)境等各方面因素，才能夠設(shè)計(jì)出比較好的算法。

到此，關(guān)于“怎么理解web的時(shí)間與空間復(fù)雜度”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！

文章名稱(chēng)：怎么理解web的時(shí)間與空間復(fù)雜度
網(wǎng)頁(yè)URL：http://aaarwkj.com/article14/igcsge.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、服務(wù)器托管、外貿(mào)網(wǎng)站建設(shè)、商城網(wǎng)站、定制網(wǎng)站、虛擬主機(jī)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)