平方階

下面實例是一個迴圈巢狀結構，它的內迴圈時間複雜度為 O(n)。

int i j;
for (i = 0; i < n; i++)
{
    for (j = 0; j < n; j++)
    {
        /* 時間複雜度為O(1)的程式步驟序列 */
    }
}

而對於外層的迴圈，不過是內部這個時間複雜度為 O(n) 的敘述，再循環 n 次。
所以這段程式的時間複雜度為 O(n²)。

如果外迴圈的循環次數改為了 m，時間複雜度就變為 O(mxn)。

int i,j;
for (i = 0; i < m; i++)
{
    for (j = 0; j < n; j++)
    {
        /* 時間複雜度為O(1)的程式步驟序列 */
    }
}

所以可以歸納得出，迴圈的時間複雜度等於迴圈本體的複雜度乘以該迴圈執行的次數。

那麼下面的這個迴圈巢狀結構，它的時間複雜度是多少呢?

int i,j;
for (i = 0; i < n; i++)
{
    for (j = i; j < n; j++) /* 注意 j = i 而不是 0 */
    {
        /* 時間複雜度為O(1)的程式步驟序列 */
    }
}

換句話說，巢狀迴圈的時間複雜度就是把內外層的次數相乘，雙層都跑 n 次就會變成平方階 O(n²)，而當內層迴圈的起點隨著外層改變時，就會形成像等差級數般遞減的執行次數。

今日的分享就到這囉，我們明天見，掰掰！