前端面試題，寫出一個快速找出兩個陣列不同值的函式。
一般情況下，演算法中基本操作重複執行的次數是問題規模n的某個函式，用T(n)表示，若有某個輔助函式f(n)，使得當n趨近於無窮大時，T(n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函式。記作T(n)=O(f(n))，稱O(f(n))為演算法的漸進時間複雜度(O是數量級的符號 )，簡稱時間複雜度。
求法
如果lim(T(n)/f(n))的值為不等於0的常數，則稱f(n)是T(n)的同數量級函式。記作T(n)=O(f(n))。
實現方法
這篇文章討論兩種不同時間複雜度的實現方法
方法一
function findDifferentElements1(array1, array2) {
// 先對兩個陣列進行去重操作。基本操作次數2n(最糟糕的情況)。
const arrayA = Array.from(new Set(array1))
const arrayB = Array.from(new Set(array2))
// 定義一個數組A，B內一定不存在的變數 SAME_ELE 。基本操作次數1
const SAME_ELE = Symbol('$$__SAME__ELE__TAG')
// 提前取出陣列長度常數。基本操作次數2
const lengthA = arrayA.length
const lengthB = arrayB.length
// 用兩層 for 迴圈巢狀檢查出每一個相同的元素。基本操作次數 3n^2 + 4n
for(let i = 0; i < lengthA; i++ ){ // n次i比較 n次i++ 一共操作2n次
for(let j = 0; j < lengthB; j++) { // n次j比較 n次j++ 一共操作2n次
if(arrayA[i] === arrayB[j]){ // 基本操作次數1
// 然後用 splice 函式將相同的元素替換成SAME_ELE。
arrayA.splice(i,1,SAME_ELE) // 基本操作次數1
arrayB.splice(j,1,SAME_ELE) // 基本操作次數1
//break (實際上可以用break優化，這裡不討論break優化的情況)
}
}
}
// 合併兩個陣列然後將陣列內所有的 SAME_ELE 去掉，留下的就是不同的元素了。基本操作次數2n+1
return Array.prototype.concat(arrayA,arrayB).filter(item=>item!==SAME_ELE)
}
複製程式碼
時間複雜度分析
這個函式前面定義了5個變數基本運算元為2n+3。
接下來是兩個for迴圈巢狀，假設兩個陣列的長度都是n，那麼第一個for迴圈需要執行n次，第二個for迴圈在最壞的情況下也要執行n次，也就是說被這兩個for迴圈包裹起來的基本操作將會被重複執行n*n次，被包裹起來的程式碼一共有3條語句，加上for迴圈本身有4n次操作所以一共有3*n*n+4n次基本操作。接下來的return語句是一個複合語句concat基本操作記為n，filter的基本操作記為n，那麼整個函式的基本操作函式
T(n) = 4n^2+8n+4 .
令 f(n) = T(n) 的數量級。
lim(T(n)/f(n)) = k {k|k!=0,k∈常數}
f(n) = n^2 （口訣是去掉常數項和低次冪項以及去掉最好高次冪項的係數）
T(n) = O(n^2)
方法二
function findDifferentElements2(array1, array2) {
// 定義一個空數res組作為返回值的容器，基本操作次數1。
const res = []
// 定義一個物件用於裝陣列一的元素，基本操作次數1。
const objectA = {}
// 使用物件的 hash table 儲存元素，並且去重。基本操作次數2n。
for(const ele of array1) { // 取出n個元素n次
objectA[ele] = undefined // 存入n個元素n次
}
// 定義一個物件用於裝陣列二的元素，基本操作次數1。
const objectB = {}
// 使用物件的 hash table 儲存元素，並且去重。基本操作次數2n。
for(const ele of array2){ // 取出n個元素n次
objectB[ele] = undefined // 存入n個元素n次
}
// 使用物件的 hash table 刪除相同元素。基本操作次數4n。
for(const key in objectA){ //取出n個key (n次操作)
if(key in objectB){ // 基本操作1次 (外層迴圈n次)
delete objectB[key] // 基本操作1次 (外層迴圈n次)
delete objectA[key] // 基本操作1次 (外層迴圈n次)（總共是3n 加上n次取key的操作 一共是4n）
}
}
// 將第一個物件剩下來的key push到res容器中，基本操作次數是2n次(最糟糕的情況)。
for(const key in objectA){ // 取出n個元素n次(最糟糕的情況)
res[res.length] = key // 存入n個元素n次(最糟糕的情況)
}
// 將第二個物件剩下來的key push到res容器中，基本操作次數也是2n次(最糟糕的情況)。
for(const key in objectB){ // 取出n個元素n次(最糟糕的情況)
res[res.length] = key // 存入n個元素n次(最糟糕的情況)
}
// 返回結果，基本操作次數1。
return res
}
複製程式碼
時間複雜度分析
改進後的函式基本操作次數算起來非常簡單，註釋寫的很清楚了，所以
T(n) = 12n+7 。
令 f(n) = T(n) 的數量級。
lim(T(n)/f(n)) = k {k|k!=0,k∈常數}
f(n) = n (去掉常數項和低次冪項以及去掉最好高次冪項的係數)
T(n) = O(n)
預測具體差距
當n趨於無窮大的時候
演算法1應該比演算法2的效能慢 O(n^2)/O(n) 倍
=> O(n) 慢 n 倍
測試 當n=100時的耗時情況
//定義兩個陣列
const array1 = []
const array2 = []
// 資料量為100
const n = 100
// 初始化
for(let i = 0; i < n; i++){
array1.push(i)
array2.push(n - i) // 這兩個陣列中相同的元素距離相距都比較遠，算是比較接近糟糕的情況的但也不是時最糟糕的情況。
}
// 開始測試第一個方法耗時
console.time()
const res1 = findDifferentElements1(array1,array2)
console.timeEnd()
console.log(res1)
// 開始測試第二個方法耗時
console.time()
const res2 = findDifferentElements2(array1,array2)
console.timeEnd()
console.log(res2)
複製程式碼
相差15倍相差128倍相差1148倍