時間複雜度分析

概念

將算法中執行 基本操作 的次數作為這個算法的時間複雜度的考量，這裏所説的“時間”不是指執行一段程序的總時間，而是指基本操作（算法）的執行總次數

思路

明確算法中哪些操作是基本的核心操作與問題規模，計算出規模n的函數f(n)，求T(n)=O(f(n)中增長最快的項/此項的係數)；將能使基本操作執行次數最多的輸入作為計算時間複雜度的入參，即：將最壞的情況作為算法時間複雜度的度量

公式

T(n)=O(f(n)中增長最快的項/此項的係數)
例：f(n)=2n³+4n²+100，則T(n)=O(2n³/2)=O(n³)

常用的時間複雜度比較關係

O(1) ≤ O(log₂(n)) ≤ O(n) ≤ O(nlog₂(n)) ≤ O(n²) ≤ O(n³) ≤ ··· ≤ O(nᵏ) ≤ O(2ⁿ)

例題舉例

求以下算法的時間複雜度

void fun(int n)
{
    int i = 1, j = 100;
    while (i < n)
    {
        ++j;
        i+=2;
    }
}

一：找出基本操作，確定規模n

1、先找出基本操作。基本操作是以求時間複雜度為目的前提下，基本操作重複執行次數和算法執行時間成正比的操作，多數情況取最深層循環內的語句為算法的基本操作；
  ++j與i+=2，可以作為基本操作

2、確定規模。由while的條件：i<n，可以得知基本操作的執行次數，與入參的參數n有關，所以n就是規模n

二：計算n的函數f(n)

n確定後，while循環的結束與變量i有關

i的初始值為1，每循環一次就自增2，設循環的次數為“m”
則循環結束後，i的最終值的函數公式為：1+2m（初始值+每次循環自增的值*循環次數）

    因此，得到1+2m+K=n(n為算法規模，K為常數，因為i在循環結束後的值大於n，所以要加一個常數)
    解得m=(n-1-K)/2
    
    即f(n)=(n-1-K)/2
    f(n)中增長最快的項為n/2，n與f(n)的關係是線性關係，

    所以得出時間複雜度T(n)=O(n)