時間復雜度的定義

一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n)，使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n))，稱O(f(n))為算法的漸進時間復雜度(O是數(shù)量級的符號)，簡稱時間復雜度。

求法

如果lim(T(n)/f(n))的值為不等于0的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n))。

實現(xiàn)方法

這篇文章討論兩種不同時間復雜度的實現(xiàn)方法

方法一

function findDifferentElements1(array1, array2) {
    // 先對兩個數(shù)組進行去重操作。基本操作次數(shù)2n(最糟糕的情況)。
    const arrayA = Array.from(new Set(array1))
    const arrayB = Array.from(new Set(array2))
    // 定義一個數(shù)組A，B內一定不存在的變量 SAME_ELE ?；静僮鞔螖?shù)1
    const SAME_ELE = Symbol('$$__SAME__ELE__TAG')
    // 提前取出數(shù)組長度常數(shù)?；静僮鞔螖?shù)2
    const lengthA = arrayA.length
    const lengthB = arrayB.length
    // 用兩層 for 循環(huán)嵌套檢查出每一個相同的元素?；静僮鞔螖?shù) 3n^2 + 4n + 2
    for(let i = 0; i < lengthA; i++ ){ // n次i比較 n次i++ 初始化i記一次 一共操作2n+1次
        for(let j = 0; j < lengthB; j++) { // n次j比較 n次j++ 初始化j記一次 一共操作2n+1次
            if(arrayA[i] === arrayB[j]){ // 基本操作次數(shù)1(外層循環(huán)n*n次)
                // 然后用 splice 函數(shù)將相同的元素替換成SAME_ELE。
                arrayA.splice(i,1,SAME_ELE) // 基本操作次數(shù)1(外層循環(huán)n*n次)
                arrayB.splice(j,1,SAME_ELE) // 基本操作次數(shù)1(外層循環(huán)n*n次)
                //break (實際上可以用break優(yōu)化，這里不討論break優(yōu)化的情況)
            }
        }
    }
    // 合并兩個數(shù)組然后將數(shù)組內所有的 SAME_ELE 去掉，留下的就是不同的元素了?；静僮鞔螖?shù)2n+1
    return Array.prototype.concat(arrayA,arrayB).filter(item=>item!==SAME_ELE)
}

時間復雜度分析

這個函數(shù)前面定義了5個變量基本操作數(shù)為2n+3。

接下來是兩個for循環(huán)嵌套，假設兩個數(shù)組的長度都是n，那么第一個for循環(huán)需要運行n次，第二個for循環(huán)在最壞的情況下也要運行n次，也就是說被這兩個for循環(huán)包裹起來的基本操作將會被重復運行n*n次，被包裹起來的代碼一共有3條語句，加上for循環(huán)本身有4n次操作所以一共有3*n*n+4n次基本操作。接下來的return語句是一個復合語句concat基本操作記為n，filter的基本操作記為n，那么整個函數(shù)的基本操作函數(shù)

T(n) = 4n^2+8n+6 .

令 f(n) = T(n) 的數(shù)量級。

lim(T(n)/f(n)) = k {k|k≠0,k∈常數(shù)}

f(n) = n^2 （口訣是去掉常數(shù)項和低次冪項以及去掉最好高次冪項的系數(shù)）

T(n) = O(n^2)

方法二

function findDifferentElements2(array1, array2) {
    // 定義一個空數(shù)res組作為返回值的容器，基本操作次數(shù)1。
    const res = []
    // 定義一個對象用于裝數(shù)組一的元素，基本操作次數(shù)1。
    const objectA = {}
    // 使用對象的 hash table 存儲元素，并且去重?；静僮鞔螖?shù)2n。
    for(const ele of array1) { // 取出n個元素n次
        objectA[ele] = undefined // 存入n個元素n次
    }
    // 定義一個對象用于裝數(shù)組二的元素，基本操作次數(shù)1。
    const objectB = {}
    // 使用對象的 hash table 存儲元素，并且去重。基本操作次數(shù)2n。
    for(const ele of array2){ // 取出n個元素n次
        objectB[ele] = undefined // 存入n個元素n次
    }
    // 使用對象的 hash table 刪除相同元素?；静僮鞔螖?shù)4n。
    for(const key in objectA){ //取出n個key (n次操作)
        if(key in objectB){ // 基本操作1次 (外層循環(huán)n次)
            delete objectB[key] // 基本操作1次 (外層循環(huán)n次)
            delete objectA[key] // 基本操作1次 (外層循環(huán)n次)（總共是3n 加上n次取key的操作 一共是4n）
        }
    }
    // 將第一個對象剩下來的key push到res容器中，基本操作次數(shù)是3n次(最糟糕的情況)。
    for(const key in objectA){ // 取出n個元素n次(最糟糕的情況)。
        res[res.length] = key // 讀取n次length n次，存入n個元素n次，一共2n(最糟糕的情況)。
    }
    // 將第二個對象剩下來的key push到res容器中，基本操作次數(shù)也是3n次(最糟糕的情況)。
    for(const key in objectB){ // 取出n個元素n次(最糟糕的情況)。
        res[res.length] = key // 讀取n次length n次，存入n個元素n次，一共2n(最糟糕的情況)。
    }
    // 返回結果，基本操作次數(shù)1。
    return res
}

時間復雜度分析

改進后的函數(shù)基本操作次數(shù)算起來非常簡單，注釋寫的很清楚了，所以

T(n) = 14n+7 。

令 f(n) = T(n) 的數(shù)量級。

lim(T(n)/f(n)) = k {k|k≠0,k∈常數(shù)}

f(n) = n (去掉常數(shù)項和低次冪項以及去掉最高次冪項的系數(shù))

T(n) = O(n)

預測具體差距

當n趨于無窮大的時候

算法1應該比算法2的性能慢 O(n^2)/O(n) 倍

=> O(n) 慢 n 倍

測試 當n=100時的耗時情況

//  定義兩個數(shù)組
const array1 = []
const array2 = []
// 數(shù)據(jù)量為100
const n = 100
// 初始化
for(let i = 0; i < n; i++){
    array1.push(i)
    array2.push(n - i) // 這兩個數(shù)組中相同的元素距離相距都比較遠，算是比較接近糟糕的情況的但也不是時最糟糕的情況。
}
// 開始測試第一個方法耗時
console.time()
const res1 = findDifferentElements1(array1,array2)
console.timeEnd()
console.log(res1)
// 開始測試第二個方法耗時
console.time()
const res2 = findDifferentElements2(array1,array2)
console.timeEnd()
console.log(res2)

當n=100時的耗時結果

n=100

相差15倍

當n=1000時的耗時結果

n=1000

相差128倍

當n=10000時的耗時結果

n=10000

相差1148倍