線性階

線性階的迴圈結構會複雜很多，需要確定某個演算法的階次，我們常常需要確定某個特定敘述或某個敘述集的執行次數。

因此我們需要分析演算法的複雜度，關鍵就是要分析迴圈結構的執行情況。
下面這段程式，它的迴圈時間複雜度為 O(n)，因為迴圈本體中的程式需要執行 n 次。

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

對數階

下面這段程式，時間複雜度又是多少呢?

int count = 1;
while (count < n)
{
    count = count * 2;
    /* 時間複雜度為 O(1) 的程式步驟序列 */
}

由於每次 count 乘以 2 之後，就距離 n 更近了一分。也就是說，有多少個 2 相乘後大於 n，則會退出迴圈。由2ˣ = n 獲得 x = log₂n。所以這個迴圈的時間複雜度為 O(logn)。

換句話說，迴圈跑幾次時間就跟著變幾次的稱為線性階 O(n)，而每次以倍數快速逼近、次數呈現指數變化的則是對數階 O(log n)。

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