算法效率是評估算法性能的關(guān)鍵指標。時間復(fù)雜度，用大O表示法表示，是描述算法運行時間的函數(shù)。

簡單來說，時間復(fù)雜度就是一個函數(shù)，與其他函數(shù)所不同，它是用大寫的 O 來表示的，比如說 O(1)、O(n)、O(log n) 等等。時間復(fù)雜度用來定性描述該算法的運行時間，強調(diào)定性表示，即描述大致的運行時間趨勢。

讓我們看一張時間復(fù)雜度的圖，列舉了常見的幾種時間復(fù)雜度。需要關(guān)注的是 O(1)、O(log n)、O(n)、O(n^2) 這幾種。你要明白它們的大小關(guān)系，比如說 n^2 比 n 大，n 比 log n 大，log n 比 1 大。

讓我們通過幾段簡單的代碼來理解時間復(fù)雜度

1. 首先是一個 O(1) 的例子：常數(shù)時間

function exampleO1(arr) {
    return arr[0];
}

解釋：

這個例子是一個常數(shù)時間復(fù)雜度的算法。函數(shù) exampleO1 接收一個數(shù)組 arr 作為參數(shù)，然后立即返回數(shù)組的第一個元素 arr[0]。無論輸入數(shù)組的規(guī)模有多大，函數(shù)的執(zhí)行時間都是恒定的。這是因為函數(shù)只執(zhí)行一次數(shù)組訪問操作，與輸入規(guī)模無關(guān)，沒有循環(huán)或其他影響執(zhí)行時間的結(jié)構(gòu)。因此，這個算法的時間復(fù)雜度是 O(1)。

2. 再看一個 O(n) 的例子： 線性時間

function linearTime(arr) {
    for (let i = 0; i < arr.length; i++) {
        console.log(arr[i]);
    }
}

解釋：

這個例子展示了一個線性時間復(fù)雜度的算法。函數(shù) linearTime 接收一個數(shù)組 arr 作為參數(shù)，然后通過 for 循環(huán)遍歷整個數(shù)組，逐個打印數(shù)組元素。隨著輸入數(shù)組規(guī)模 n 的增加，循環(huán)執(zhí)行的次數(shù)也線性增加。因此，這個算法的時間復(fù)雜度是 O(n)。
如果你先執(zhí)行一個時間復(fù)雜度為 O(x) 的代碼，然后接著執(zhí)行一個線性時間復(fù)雜度的 for 循環(huán)（O(n)），整體的時間復(fù)雜度是 O(x + n)。在計算時間復(fù)雜度時，如果兩個時間復(fù)雜度先后排列，我們將它們相加，取增長趨勢更快的時間復(fù)雜度。

3. 再來看一個 O(log n) 的例子：對數(shù)時間

function binaryExponential(n) {
    let i = 1;
    while (i < n) {
        i *= 2;
    }
}

解釋：

這個例子展示了一個對數(shù)時間復(fù)雜度的算法。函數(shù) binaryExponential 接收一個參數(shù) n，然后通過 while 循環(huán)，不斷將變量 i 乘以 2，直到 i 大于等于 n。循環(huán)體內(nèi)執(zhí)行的次數(shù)是 log n，因為它在求 2 的多少次方等于 n。因此，這樣的代碼時間復(fù)雜度是 O(log n)。

對數(shù)時間復(fù)雜度通常在有序數(shù)據(jù)的查找中出現(xiàn)，比如二分查找算法。

4. 最后我們來看下O(N2) - 平方級增長

function quadraticTime(arr, n) {
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            console.log(arr[i], arr[j]);
        }
    }
}

解釋：

這個例子展示了一個平方級增長的算法，時間復(fù)雜度為 O(N2)。函數(shù) quadraticTime 接收一個數(shù)組 arr 和一個參數(shù) n，然后通過嵌套的兩個循環(huán)遍歷整個數(shù)組。由于兩個循環(huán)的迭代次數(shù)都是 n，總的執(zhí)行次數(shù)是 n 乘以 n，即 N2。這樣的算法在處理規(guī)模為 N 的輸入時，執(zhí)行時間隨輸入規(guī)模的平方級增長。

通過以上例子，我們更深入地理解了算法的時間復(fù)雜度。這種理解從常數(shù)到線性，再到對數(shù)，展現(xiàn)了代碼運行時的規(guī)律。

示例練習(xí)：

1. 多變量循環(huán)

function variableLoop(N, M) {
    let count = 0;
    for (let k = 0; k < M; k++) {
        count++;
    }
    for (let k = 0; k < N; k++) {
        count++;
    }
    console.log(count);
}

解釋

這個算法的時間復(fù)雜度為 O(N+M)，因為我們無法確定 N 和 M 哪一個更大。算法包含兩個循環(huán)，一個循環(huán)執(zhí)行 M 次，另一個執(zhí)行 N 次，因此整體時間復(fù)雜度是它們的和。

2. 字符串查找

function findCharacter(str, c) {
    while (str !== '') {
        if (str[0] === c) {
            return str;
        }
        str = str.slice(1);
    }
    return null;
}

解釋：

這個字符串查找算法的時間復(fù)雜度為 O(N)，其中 N 是字符串的長度。在最壞情況下，需要遍歷整個字符串，直到找到目標字符或遍歷結(jié)束。

3. 冒泡排序

function bubbleSort(arr, n) {
    for (let end = n; end > 0; end--) {
        let exchange = 0;
        for (let i = 1; i < end; i++) {
            if (arr[i - 1] > arr[i]) {
                swap(arr, i - 1, i);
                exchange = 1;
            }
        }
        if (exchange === 0)
            break;
    }
}

解釋：

冒泡排序的時間復(fù)雜度為 O(N2)，其中 N 是數(shù)組的長度。算法通過嵌套的循環(huán)，對數(shù)組進行多次比較和交換，使得整體的時間復(fù)雜度為 N 的平方級別。

3. 二分查找

function binarySearch(arr, n, x) {
    let begin = 0;
    let end = n - 1;
    while (begin < end) {
        let mid = begin + ((end - begin) >> 1);
        if (arr[mid] < x)
            begin = mid + 1;
        else if (arr[mid] > x)
            end = mid;
        else
            return mid;
    }
    return -1;
}

解釋：

二分查找的時間復(fù)雜度為 O(log?N)，其中 N 是數(shù)組的長度。該算法通過不斷縮小搜索范圍，將查找的時間復(fù)雜度降低到對數(shù)級別。

3. 遞歸

function fibonacci(N) {
    return N < 2 ? N : fibonacci(N - 1) + fibonacci(N - 2);
}

解釋：

遞歸算法的時間復(fù)雜度為 O(2^N)，其中 N 是輸入的參數(shù)。這是因為遞歸算法反復(fù)調(diào)用自身，導(dǎo)致指數(shù)級別的增長，效率相對較低。

總結(jié)

通過這些例子，能夠更深入地理解算法的時間復(fù)雜度，從而更好地評估和選擇合適的算法以提高程序的性能。