復雜度

復雜度分析是資料結構與演算法的核心精髓，指在不依賴硬體、宿主環境、資料集的情況下，粗略推導，考究出演算法的效率和資源消耗情況, 包括時間復雜度和空間復雜度

時間復雜度

首先從CPU的角度看待程式，每行代碼執行的操作都包括：讀程式，寫程式，運算，這里粗略估計，忽略每行代碼讀程式和寫程式的時間
假設每行代碼執行（運算）的時間都是一樣的，為單位時間（即假設程式執行一次均消耗單位時間）

大\(O\)記號

其中：

• \(T(n)\): 程式執行總時間
• \(n\): 資料規模大小
• \(f(n)\): 程式執行的總次數
• \(O\)：程式執行總時間\(T(n)\)與\(f(n)\)成正比

大\(O\)記號按最壞的情況來估計程式執行時間；大\(\Omega\)記號按最好情況估計程式執行時間；大\(\Theta\)記號按平均情況來估計程式執行時間，后文只分析大\(O\)記號，

大\(O\)記號的性質：

• 對任意常數\(c>0\), \(O(f(n))=O(cf(n))\)
• 對任意常數\(a>b>0\), \(O(n^a+n^b)=O(n^a)\)

常見時間復雜度

1. 常數階\(O(1)\)

public void sum(int n) {
    int sum = 0; // 執行一次
    sum = n*2; // 執行一次
    System.out.println(sum); // 執行一次
}

程式執行常數次，與問題規模\(n\)無關，復雜度記為\(O(1)\)

2. 對數階\(O(logn)\)

public void logarithm(int n) {
    int count = 1; // 執行一次
    while (count <= n) { // 執行logn次
        count = count*2; // 執行logn次
    }
}

該段代碼什么時候會停止執行呢？是當count大于n時，也就是說多少個2相乘后其結果值會大于\(n\)，即\(2^x=n\)，由\(2^x=n\)可以得到\(x=logn\)，所以這段代碼時間復雜度是\(O(logn)\)，

3. 線性階\(O(n)\)

public void circle(int n) {
    for(int i = 0; i < n; i++) { // 執行n次
        System.out.println(i); // 執行n次
    }
}

4. 線性對數階 \(O(nlogn)\)
   線性對數階\(O(nlogn)\)就是將一段時間復雜度為\(O(logn)\)的代碼執行\(n\)次

public void logarithm(int n) {
    int count = 1;
    for(int i = 0; i < n; i++) { // 執行n次
        while (count <= n) { // 執行logn次
            count = count*2; // 執行nlogn次
        }
    }
}

5. 平方階 \(O(n^2)\)
   雙重for回圈

public void square(int n) {
    for(int i = 0; i < n; i++){ // 執行n次
        for(int j = 0; j <n; j++) { // 執行n次
            System.out.println(i+j); // 執行n方次
        }
    }
}

復雜度分析

示例如下(限定條件: \(0<n\) 且 \(0<x\) 且\(n\)和\(x\)為整數)：

 public int Function(int n, int x)
 {
    int sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (i == x)
            break;
            sum += i;
    }
    return sum;
  }

• 當\(x>n\)時，此代碼的時間復雜度是\(O(n)\)
• 當\(1<=x<=n\)時，時間復雜度是一個我們不確定的值，取決于x的值
• 當\(x=1\)時，時間復雜度是\(O(1)\)

這段代碼在不同情況下，其時間復雜度是不一樣的，所以為了描述代碼在不同情況下的不同時間復雜度，我們引入了最好、最壞、平均時間復雜度，

1. 最好情況時間復雜度(best case)

最好情況時間復雜度，表示在最理想的情況下，執行這段代碼的時間復雜度，
上述示例就是當x=1的時候，回圈的第一個判斷就跳出，這個時候對應的時間復雜度就是最好情況時間復雜度，

2. 最壞情況時間復雜度(worst case)

最壞情況時間復雜度，表示在最糟糕的情況下，執行這段代碼的時間復雜度，
上述示例就是\(n<x\)的時候，我們要把整個回圈執行一遍，這個時候對應的時間復雜度就是最壞情況時間復雜度，

3. 平均情況時間復雜度(average case)

好和最好情況是極端情況，發生的概率并不大，為了更有效的表示平均情況下的時間復雜度，引入另一個概念：平均情況時間復雜度，
分析上面的示例代碼，判斷x在回圈中出現的位置，有\(n+1\)種情況：\(1<=x<=n\) 和\(n<x\)，將所有情況下代碼執行的次數累加起來，然后再除以所有情況數量，就可以得到平均情況時間復雜度，即

大\(O\)表示法會省略系數、低階、常量，所以平均情況時間復雜度是\(O(n)\)，

考慮概率的平均情況復雜度：

\(x\)要么在\(1\sim n\)中，要么不在\(1\sim n\)中，所以它們的概率都是\(1/2\)，同時資料在\(1\sim n\)中各個位置的概率都是一樣的為1/n，根據概率乘法法則，\(x\)在\(1\sim n\)中任意位置的概率是\(1/(2n)\)，因此在前面推導程序的基礎上，我們把每種情況發生的概率考慮進去，得到考慮概率的平均情況復雜度：

引入概率之后，平均復雜度變為\(O(\frac{3n+1}{4})\)，忽略系數及常量后，最終得到加權平均時間復雜度\(O(n)\)，

多數情況下，我們不需要區分最好、最壞、平均情況時間復雜度，只有同一塊代碼在不同情況下時間復雜度有量級差距，我們才會區分3種情況，為的是更有效的描述代碼的時間復雜度，

4. 均攤情況時間復雜度

均攤復雜度是一個更加高級的概念，它是一種特殊的情況，應用的場景也更加特殊和有限，對應的分析方式稱為：攤還分析或平攤分析，
示例如下（限定條件：\(0\leq x\leq n\)且\(0\leq n\)且\(n\), \(x\)為整數）：

int n;
public int Function2(int x)
{
    int count = 0;
    if (n == x)
    {
        for (int i = 0; i < n; i++)
            count += i;
    }
    else
        count = x;
    return count;
 }

共有\(n+1\)種情況，每種情況的概率均為\(\dfrac{1}{n+1}\)當\(0\leq x<n\)時，時間復雜度為\(O(1)\); 當\(x=n\)時，時間復雜度為\(O(n)\)，
平均時間復雜度為：

當省略系數及常量后，平均時間復雜度為\(O(1)\)，
通過分析可以看出，上述示例代碼復雜度遵循一定的規律，對應1個\(O(n)\)，和n個\(O(1)\)，針對這樣一種特殊場景使用更簡單的分析方法：攤還分析法, 即把耗時多的復雜度均攤到耗時低的復雜度，得到對應的均攤時間復雜度為O(1)，

• 均攤時間復雜度是將高高復雜度均攤到其余低復雜度，故一般均攤時間復雜度就等于最好情況時間復雜度，
• 均攤時間復雜度是一種特殊的平均復雜度（特殊應用場景下使用）

空間復雜度

空間復雜度定性地描述該演算法或程式運行所需要的存盤空間大小，演算法空間復雜度的計算公式記作：\(S(n)=O(f(n))\)，其中\(n\)為問題的規模，\(f(n)\)為陳述句關于\(n\)所占存盤空間的函式，

參考：

• https://www.cnblogs.com/jonins/p/9956752.html
• 鄧俊輝資料結構（C++語言版）
• https://zhuanlan.zhihu.com/p/361636579
• https://zh.m.wikipedia.org/zh-hans/空間復雜度

標籤：其他

上一篇：【案例】基于LoRa技術的智能森林防火系統，保護大自然免受侵害！

下一篇：樹狀陣列