时间复杂度的定义
一般情况下，算法中基本操作重复执行的次数是问题规模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 + 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]){ // 基本操作次数1(外层循环n*n次)
// 然后用 splice 函数将相同的元素替换成SAME_ELE。
arrayA.splice(i,1,SAME_ELE) // 基本操作次数1(外层循环n*n次)
arrayB.splice(j,1,SAME_ELE) // 基本操作次数1(外层循环n*n次)
//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+6 .
令 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容器中，基本操作次数是3n次(最糟糕的情况)。
for(const key in objectA){ // 取出n个元素n次(最糟糕的情况)。
res[res.length] = key // 读取n次length n次，存入n个元素n次，一共2n(最糟糕的情况)。
}
// 将第二个对象剩下来的key push到res容器中，基本操作次数也是3n次(最糟糕的情况)。
for(const key in objectB){ // 取出n个元素n次(最糟糕的情况)。
res[res.length] = key // 读取n次length n次，存入n个元素n次，一共2n(最糟糕的情况)。
}
// 返回结果，基本操作次数1。
return res
}
时间复杂度分析
改进后的函数基本操作次数算起来非常简单，注释写的很清楚了，所以
T(n) = 14n+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)
当n=100时的耗时结果
相差15倍
当n=1000时的耗时结果
相差128倍
当n=10000时的耗时结果
相差1148倍
