Если вы ярый любитель компьютерных наук, скорее всего, вы столкнулись с нотацией Big O. Это обозначение обычно записывается в форме O(n), что произносится как «o of n». Обозначение Big O используется для описания времени работы алгоритма и демонстрации того, насколько он (не)эффективен и необходим в интервью.
Хотя есть много других обозначений, таких как Большая Тета и Большая Омега. Причина, по которой мы заботимся о нотации Big O, заключается в том, что она показывает нам наихудший возможный случай, когда какой-то код потенциально может работать. Прежде чем мы перейдем к фактическому коду. Давайте рассмотрим пример того, как это может быть применено в реальной жизни.
Допустим, мы хотим через некоторое время отправить некоторые данные «веб» из Нью-Йорка в Лос-Анджелес. Если данные очень маленькие, например, простое сообщение, мы, вероятно, сможем отправить через Интернет за несколько миллисекунд. Но что, если бы мы отправили большой файл размером 10терабайт, это может занять часы или даже дни. . В этом конкретном случае время выполнения O(web) будет зависеть от размера файла, и если он будет экспоненциально большим, в худшем случае это может занять дни, месяцы, а может быть, и годы. На самом деле лучшим подходом для этого было бы попросить кого-нибудь записать его на жесткий диск и отправить этого человека в Лос-Анджелес на самолете. Время будет временем полета «самолет», которое является постоянным и всегда будет приблизительно одинаковым, независимо от размера данных. Это намного лучше, чем ждать дни, месяцы или даже годы. Можно сказать, что время работы O(самолет) быстрее, чем O(сеть).
Теперь давайте применим нотацию большого O к вопросу кодирования:
По заданному массиву целых чисел, уже отсортированному в порядке возрастания, найдите два числа, которые в сумме дают определенное целевое число.
Один из способов решения этой проблемы состоит в том, что мы можем начать с первого числа и сверить это первое число со всеми остальными числами в массиве. Если совпадений не найдено, начните со второго числа и сравните это число с остальными числами и так далее.
function findMatch(array, targetVal) {
for (let i = 0; i < array.length-1; i++) { // O(n)
for (let j = i+1; j< array.length; j++) { // O(n)
if (array[i] + array[j] === targetVal) // O(1)
return true;
}
}
return false; // O(1)
}
Если n — длина массива и пусть n = 10, то в худшем случае решение будет в конце. Это означает, что потенциально нам придется пройти цикл 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 раз. Мы можем вычислить сумму такой последовательности с помощью математического уравнения
(n² + n)/2. Что приводит к времени работы O (n²).
Что, если мы попробуем другой подход. Может быть, есть способ не пробовать каждую возможную комбинацию, чтобы добраться до финала. Допустим, targetVal = 9, а первое число в массиве равно 3. Это означает, что нас интересует только его дополнение 6, потому что 9–3 = 6. Давайте используем хэш-карту для хранения дополнений, а затем мы можем проверить, если targetVal минус текущее значение находится в нашем хеше.
function findMatch(array, targetVal) {
let complementMap = {}; // can also use a set
for (let i = 0; i < array.length; i++) { // O(n)
let complement = targetVal - array[i]; // O(1)
complementMap[complement] = array[i]; // O(1)
}
for (let i = 0; i < array.length; i++) { // O(n)
let complement = targetVal - array[i]; // O(1)
if (complement in complementMap) // O(1)
return true; // O(1)
}
return false; // O(1)
}
Если бы мы сложили все времена выполнения приведенного выше кода, то увидели бы, что время выполнения этой реализации равно O(2n), которое мы упрощаем до O(n). Это значительно быстрее, чем наш предыдущий алгоритм, который имел время работы O(n²). Обратите внимание, что хотя этот алгоритм намного быстрее и лучше, мы используем больше места, чем первая реализация, потому что мы использовали хэш-карту. Кроме того, здесь есть ошибка, посмотрите, сможете ли вы ее понять. Посмотрим, сможем ли мы сделать даже лучше, чем это.
Это может быть не так очевидно, как в предыдущих реализациях, но важно отметить, что массив отсортирован. Это означает, что мы можем фактически использовать два указателя, один из которых начинается в начале, а другой — в конце массива, и перемещать указатель слева направо только в том случае, если сумма значений двух указателей меньше targetVal, и мы только переместите указатель справа налево, если сумма значений двух указателей больше targetVal.
function findMatch(array, targetVal) {
let begin = 0; // O(1)
let end = array.length-1; // O(1)
while(begin != end) { // O(log n)
let sum = array[begin] + array[end]; // O(1)
if (sum === targetVal) {
return true; // O(1)
} else if (sum < targetVal) {
begin++; // O(1)
} else {
end++; // O(1)
}
}
return false; // O(1)
}
Время выполнения этой реализации составляет O(log n), потому что мы почти разделяем количество обращений к массиву. Это даже лучше предыдущей реализации O(n) и не может быть сделано быстрее.
Хотя существует множество реализаций решения проблемы, мы можем использовать нотацию большого O, чтобы увидеть, какой алгоритм более выгоден. Это можно применять не только в программах, но и в реальной жизни, и, надеюсь, вы сможете стать более эффективным человеком.
