Определение временной сложности
В общем случае количество повторений основных операций в алгоритме есть функция размера задачи 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 раз в худшем случае, что является It Говорят, что базовые операции, обернутые этими двумя циклами for, будут повторяться n*n раз, обернутый код содержит в общей сложности 3 оператора, а сам цикл for имеет 4n операций, так что всего 3*n*n +4n основные операции. Следующий оператор return является составным оператором.Основная операция concat записывается как n, а основная операция фильтра записывается как n, затем базовая операционная функция всей функции
T(n) = 4n^2+8n+6 .
Пусть f(n) = порядок величины T(n).
lim(T(n)/f(n)) = k {k|k≠0, k∈constant}
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
}
анализ временной сложности
Количество основных операций улучшенной функции очень просто посчитать, а комментарии написаны очень понятно, поэтому
Т(n) = 14n+7.
Пусть f(n) = порядок величины T(n).
lim(T(n)/f(n)) = k {k|k≠0, k∈constant}
f (n) = n (удалите постоянные члены и члены с низкой степенью и удалите коэффициенты членов с наивысшей степенью)
T(n) = O(n)
Прогнозировать конкретные пробелы
Когда n стремится к бесконечности
Алгоритм 1 должен работать в O(n^2)/O(n) раз медленнее, чем алгоритм 2.
=> 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)