漸進時間復(fù)雜度O(n)

在說漸進時間復(fù)雜度O(n)前要說一下基本操作執(zhí)行次數(shù)函數(shù)T(n)

基本操作執(zhí)行次數(shù)函數(shù)T(n)

T(n) = n

echo 1;
echo 2;

以上php代碼為三行，假設(shè)每行執(zhí)行時間為1秒，代碼無論什么時候執(zhí)行都為2，執(zhí)行次數(shù)只與行數(shù)有關(guān)，假設(shè)行數(shù)為n，這個時候執(zhí)行的次數(shù)就是n所以就可以說 T(n) = n

T(n) = 2n

for($i=0; $i<n; $i++) {
    echo 1;
    echo 2;
}

以上代碼真實執(zhí)行行數(shù)為2，是固定的，但是外層套了個循環(huán)，這個時候總執(zhí)行行數(shù) = 固定代碼行數(shù) * 循環(huán)次數(shù) 所以就是 T(n) = 2n,T(n) 就是 固定行數(shù) 的 倍數(shù) 下面再舉一個栗子

T(n) = 4n

for($i=0; $i<n; $i++) {
    echo 1;
    echo 2;
    echo 3;
    echo 4;
}

T(n) = 2logn

for($i=1;$i<n;$i=$i*2) {
    echo 1;
    echo 2;
}

以上這個稍微有點復(fù)雜我們采用代入數(shù)據(jù)來理解

假設(shè)n = 4,代碼就變成

for($i=1;$i<4;$i=$i*2) {
    echo 1;
    echo 2;
}

第一次循環(huán)：

$i=1;

echo 1;

echo 2;

i * 2 = 2;

$i = 2 小于 10 循環(huán)繼續(xù)

第二次循環(huán)：

$i=2;

echo 1;

echo 2;

i * 2 = 4;

$i = 4 不小于 4 循環(huán)結(jié)束

我們發(fā)現(xiàn)以上代碼每次執(zhí)行次數(shù)固定為2，總執(zhí)行次數(shù)等于2*logn

如何使用操作復(fù)雜度推算時間復(fù)雜度？

我們使用以下原則即可

1. 如果運行時間是常數(shù)量級，用常數(shù)1表示
2. 只保留時間函數(shù)中的最高階項；
3. 如果最高階項存在，則省去最高階項前面的系數(shù)。

T(n) = n

T(n) = n 可以記做 T(n) = O(1) ,因為表示隨著時間增長，他的復(fù)雜度是恒定的

T(n) = 2n

T(n) = 2n，根據(jù)原則3 ，省去最高階的系數(shù)，所以得到 O(n),表示復(fù)雜度隨著時間增長而增長，可以說復(fù)雜度就是時間

T(n) = 2logn

T(n) = 2logn 根據(jù)原則3，省去系數(shù)2 得到O(logn)