Примечание. Прежде чем читать эту статью, вы должны иметь общее представление о временной сложности.
Допустим, вы собираетесь попрактиковаться в кодировании. Вы переходите на codechallenge9000.com и выбираете случайный вызов кода. Вот что там написано:
Given an array of single numbers, return how many matching pairs exist. You will never be given more than two characters that are the same (this means one pair maximum of each character). Example: Input: [ 1, 2, 6, 7, 6 ] Expected result: 1
Вы думаете, что это довольно просто ... Вы думаете, как решить эту проблему ... Похоже, нам нужно будет сравнить каждый элемент в массиве друг с другом, и если мы когда-нибудь найдем совпадение, мы сможем увеличить значение некоторого счетчика. После всех сравнений мы можем вернуть это число. Но вы никогда раньше не кодировали что-то подобное ... Это кажется устрашающим. Через некоторое время вы придумали следующее решение:
function compare(array) {
let arrayLength = array.length;
let counter = 0;
//iterate over first char
for (let i = 0; i< arrayLength; i++) {
let charA = array[i];
let match = false;
//over second char
for (let e = i+1; e < arrayLength; e++) {
let charB = array[e];
if (charB === charA) {
match = true;
break;
}
}
//increment counter
if (match === true) {
counter += 1;
}
}
return counter;
}
Если вы запутались, вот версия с комментариями, объясняющими, как работает алгоритм. Обратите внимание, что мы могли бы реализовать что-то для запоминания парных значений, таким образом, когда мы перебираем уже парное значение, мы могли бы его пропустить, но мы откажемся от этого для целей этого примера.
function compare(array) {
let arrayLength = array.length;
//create something to keep track of the number of pairs
let counter = 0;
//iterate over first character
for (let i = 0; i< arrayLength; i++) {
//this for loop will loop through all items but the last
//lets use charA to keep track of the first character
let charA = array[i];
//we'll compare charA to all the characters to the right
//of it in the array, if there's a match we'll set
//match to true
let match = false;
//iterate over second character
for (let e = i+1; e < arrayLength; e++) {
let charB = array[e];
if (charB === charA) {
match = true;
//we'll end this loop because we found the only
//possible match
break;
}
}
//increment counter if a match is found between the first
//character and all the ones to the right of it in the array
if (match === true) {
counter += 1;
}
}
return counter;
}
Отличная работа! Итак, прямо сейчас у нас есть достойный алгоритм для решения этой проблемы. Он возвращает пары чисел в заданном массиве!
Теперь вы нажимаете "Отправить", но что-то не так! В обратной связи говорится, что решение должно иметь временную сложность O (n), а не O (n²). Какие!? Воскликните вы! Это почти невозможно.
Вы не можете придумать, как заставить его работать O (n)! Потому что нам нужен цикл внутри цикла!… Верно?….
Неправильный! Но как это сделать?
Решение проблемы - использовать объект. Почему объект?
Откровенно говоря, способ хранения объектов в памяти позволяет практически мгновенно получить любую из его пар "ключ-значение", если мы знаем ключ.
Example:
Let object = {
…1000 key-value pairs…
Name: ‘bob’
}
Здесь мы могли бы мгновенно получить доступ к значению «name» с помощью объекта [Name].
Зная это, мы можем заменить внутренний цикл внутри нашего алгоритма. Вместо того, чтобы сравнивать наше значение с каждым значением справа, мы можем просто проверить, соответствует ли object [character] = true для нашего объекта. Это мгновенная проверка, и если ее нет, мы можем ее создать. Теперь, если мы перейдем к другому значению, которое совпадает с тем, что мы добавили к этому объекту: мы можем проверить объект и найти совпадение!
В итоге:
1. Turn the array into an object 2. Start to loop through each item in the array 3. In the loop, check to see if the key-value exists on the object, and if not, add it to the object (If it does exist, we can iterate our counter and “continue our loop”)
Вот как выглядит код на практике:
(обратите внимание на то, как мы проверяем, существует ли элемент на объекте, может показаться странным,
if (cws [array [i]]! == undefined), но это действительно отличный способ проверить, не пара ключ-значение существует для объекта или нет. Если она не существует, она будет иметь значение undefined)
function compareUsingObject(array) {
//characters we’ve seen
let cws = {};
let arrayLength = array.length;
let counter = 0;
//first character
for (let i = 0; i < arrayLength; i++) {
//this will iterate over every character in array
let characterA = array[i];
let match = false;
//if we have seen it before, it should exist on the array
// a.k.a. it should NOT equal undefined
if (cws[array[i]] !== undefined) {
//this reads: if this character exists on the object
match = true;
} else {
//since it does not exists, let's add it to the object
cws[array[i]] = true;
}
//iterate counter
if (match === true) {
counter += 1;
}
}
//return number of pairs
return counter;
};
Поздравляем, Невероятная сложность выполнения! Это не обязательно означает, что он будет быстрее, из-за времени, необходимого для создания объекта, но как только размер ввода (размер массива) станет достаточно большим, он будет значительно быстрее, чем версия O (n²) алгоритм.
