В Части I мы представили Big O, поговорили о том, почему нам следует заботиться, и проанализировали Big O алгоритма. Сегодня мы поговорим немного подробнее о технических моментах, рассмотрим некоторые общие временные сложности и немного коснемся пространственной сложности. Пойдем!

Итак, мы обсудили, что Big O - это способ измерения производительности алгоритма. Хорошая новость заключается в том, что есть некоторые основные правила, которым вы можете следовать, чтобы получить большой О алгоритма, и существует лишь ограниченное количество общих шаблонов временной сложности. Все эти шаблоны основаны на форме кривой роста, которая получается при построении графика зависимости размера входных данных от времени выполнения, то есть алгоритм, работающий в линейном времени (такой, как тот, который мы обсуждали в Части I), может быть представлен следующим образом: кривая линейного роста. Правила следующие:

Правило 1: Проверьте количество операций, которые алгоритм выполнит относительно его входного размера (n), учитывая его худшее сценарий случая. Мы потратили некоторое время на обсуждение того, что это означает, и на примере из Части I, поэтому я не буду вдаваться в подробности, однако это важное правило, о котором стоит упомянуть, поскольку это чистая суть Big O. Например, если у нас есть алгоритм, который будет перебирать массив, который изменяет размер в зависимости от его ввода, это O (n).

Правило 2. Отбросьте константы. При определении Big O вы можете обнаружить, что вам нужно дважды перебрать один и тот же массив или выполнить какую-либо операцию постоянное количество раз. Вместо того, чтобы указывать эти константы как O (2n) или O (5n²), мы просто отбрасываем эти константы, чтобы получить O (n) или O (n²). По большому счету, эти константы не влияют на наш Большой О, потому что Большой О заботится только о кривой долгосрочного роста. В то время как добавление константы изменит время выполнения на постоянную величину, форма ее кривой роста останется прежней, делая константу несущественной. Например, линейная функция по-прежнему будет иметь кривую линейного роста, а экспоненциальная функция по-прежнему будет иметь кривую экспоненциального роста, несмотря на любые константы.

Правило 3. Включите только узкое место (термин высшего порядка). Допустим, у нас есть функция, подобная приведенной ниже, которая выполняет множество различных операций. Он включает в себя несколько циклов, некоторые из которых являются вложенными, а некоторые - нет, и, возможно, выполняет некоторые операции вне циклов.

function example(array){
    for (let i = 0; i < array.length; i++){
        for (let j = 0; j < array.length; j++){
            console.log(array[i] + array[j])
        }
    } 
    for (let i = 0; i < array.length; i++){
        console.log(array[i])
    }
    console.log(array[0])
}

Этот тип многооперационной функции гораздо более характерен для алгоритма, который разработчик может написать при решении проблемы - в конце концов, для решения большинства проблем требуется несколько шагов. Важно отметить, что каждая операция в функции может иметь разную временную сложность. В нашем случае вложенный цикл for - это O (n²), невложенный цикл for - это O (n), а последний console.log - это O (1). Так как же указать временную сложность такого алгоритма? Все, что нам нужно сделать, это указать член высшего порядка - O (n²) - это то, что будет определять нашу кривую роста и больше всего замедлять нашу программу. Это наше узкое место!

Общие временные сложности (от лучшего к худшему)

Итак, я использовал несколько нотаций Big O, таких как O (n²), O (n) и O (1). Давайте на самом деле обсудим эти и некоторые другие общие временные сложности, с которыми мы можем столкнуться в дикой природе. Взгляните на график ниже, чтобы получить представление об этом.

O(1)

Известная как постоянное время, это самая лучшая временная сложность, которую мы можем достичь. По сути, это означает, что ввод не влияет на количество операций, выполняемых этим алгоритмом. Например, если бы мы написали алгоритм, возвращающий первый элемент массива, размер массива не имеет значения. Некоторые другие примеры включают: доступ к n-му элементу в массиве; доступ к ключу в данном объекте (также известный как хэш или словарь); или выполнение математической операции (например, суммирование двух чисел).

Следует отметить, что O (1) не означает, что алгоритм выполняет только одну операцию - он может выполнить 1000 операций для всего, что мы знаем (что мы упрощаем до O (1), отбрасывая константы). Все это означает, что количество операций (будь то 1 или 1000) будет одинаковым независимо от ввода. См. Пример ниже:

function countToFive(){
    for (let i = 1; i <= 5; i++){
        console.log(i)
    }
}

Несмотря на цикл, эта функция выполняется с постоянным временем, потому что цикл всегда выполняет 5 итераций - ни меньше, ни больше.

O (журнал n)

Также известный как логарифмический, O (log n) - это следующая лучшая временная сложность, которую мы можем достичь, хотя это немного сложнее понять. Возвращаясь к математике в средней школе, логарифм - это величина, обратная экспоненте. Итак, если 2³ = 8, то log2 (8) = 3. Чтобы получить 3, нам нужно спросить себя: «2 к какому показателю дает 8?» Вот почему O (log n) так хорош: тогда как экспоненциальная временная сложность (например, O (n²)) удвоит время выполнения при увеличении размера ввода всего на единицу, O (log n) потребуется удвоить размер ввода, чтобы добавить всего одна операция до этой временной сложности! Чтобы представить это в перспективе, учитывая размер ввода 1 миллион, нам нужно будет выполнить только 20 операций в худшем сценарии с использованием O (log n).

Конечно, не каждый алгоритм может быть записан за время O (log n). Обычно в O (log n) могут быть записаны алгоритмы с отсортированными массивами в качестве входных данных. Очень распространенный пример - запись двоичного поиска по массиву отсортированных чисел. При бинарном поиске мы бы проверили середину массива на предмет нашего целевого числа - если наше число меньше среднего числа, мы можем удалить всю вторую половину массива, зная, что она не может там появиться; если наше число больше, мы можем удалить всю первую половину массива. Затем мы будем использовать оставшуюся половину массива в качестве нового ввода. Таким образом, мы удаляем половину входного размера при каждой выполняемой нами проверке, и это гораздо более эффективное решение, чем проверка каждого отдельного элемента в массиве (в противном случае это время было бы O (n)).

O(n)

Время O (n) (также известное как линейное время) означает, что при n входных данных алгоритму потребуется выполнить n операций. Время выполнения этого алгоритма прямо пропорционально входному размеру, а форма кривой роста будет линейной, как показано ниже:

Хорошим индикатором линейного времени является алгоритм, который просматривает каждый элемент в данной коллекции. В Части I мы использовали пример цикла по массиву, чтобы найти первый элемент над целевым числом.

O (п войти п)

O (n log n), также называемое линейным, логлинейным и иногда квазилинейным временем, - это временная сложность, обычно связанная с алгоритмами сортировки, и это лучшая временная сложность, которую может достичь алгоритм сортировки. Некоторые примеры алгоритмов сортировки, которые выполняются за O (n log n), включают сортировку слиянием и сортировку кучи. Оба этих алгоритма используют общую парадигму, основанную на рекурсии, известную как разделяй и властвуй. Например, алгоритм сортировки слиянием рекурсивно разбивает массив, который нужно отсортировать, пополам, пока он не достигнет входов 1 элемента. Затем он отсортирует и объединит вновь отсортированные массивы.

O(n²)

Теперь мы переходим на территорию временных сложностей, которых лучше избегать. O (n²) - довольно неэффективная временная сложность, иногда известная как квадратичная или полиномиальная в зависимости от формы кривой роста (см. Ниже).

Алгоритмы O (n²) известны тем, что время их выполнения пропорционально квадрату их входного размера. Обычно индикатор времени выполнения O (n²) - это алгоритм, который использует вложенный цикл над одним набором данных. Типичный пример - это массив, который перебирает сам себя и на каждой итерации снова перебирает сам себя. Важно отметить, что вложенный цикл должен находиться над той же коллекцией. Если бы мы перебирали один массив, а затем перебирали разные массивы на каждой итерации, это был бы другой Big O, потому что мы не можем предположить, что массивы имеют одинаковый размер. Также следует отметить, что более глубоко вложенные итерации (более двух уровней) приведут к временным сложностям O (n³), O (n⁴) и т. Д.

См. Ниже пример O (n²) - алгоритма, который перебирает массив и возвращает все пары, равные целевой сумме. В этом алгоритме используется метод грубой силы, при котором заданный массив проходит n² раз во вложенном цикле for. * Имейте в виду, что для этой проблемы можно добиться лучшего результата.

function twoSum(arr, target){
    const sums = [];
    for (let i = 0; i < arr.length; i++){
        for (let j = i + 1; j < arr.length; j++){
            if (arr[i] + arr[j] === target){
                sums.push([arr[i], arr[j]])
            }
        }
    }
    return sums;
}
twoSum([3, 5, 2, -4, 8, 11], 7) => [[5,2],[-4,11]]

O(2^n)

Также известное как экспоненциальное время, O (2 ^ n) - одна из наихудших временных сложностей, и ее следует избегать как можно чаще. Наиболее распространенные алгоритмы, которые выполняются за время O (2 ^ n), обычно принимают входные данные размера n и используют рекурсию для решения двух меньших задач входных данных n-1. Классический пример - Фибоначчи, использующий рекурсивное решение:

function fibonacci(n){
    if (n <= 1) return n;
    else {
        return fibonacci(n-2) + fibonacci(n-1);
    }
}

Причина, по которой это решение настолько неэффективно, состоит в том, что каждый рекурсивный вызов этой функции производит еще два рекурсивных вызова, которые производят еще два рекурсивных вызова, которые производят два… вы понимаете.

O(n!)

O (n!), Также известный как факториал n, также известный как Oh no! - шучу по поводу последнего - это наихудшая временная сложность, которая может быть достигнута. В математике факториал числа (n) - это все положительные целые числа, умноженные друг на друга, начиная с n и убывающие на единицу. Например, 5! будет 120, что является результатом умножения 5 x 4 x 3 x 2 x 1. Примеры алгоритмов, которые выполняются за O (n!), генерируют все перестановки строки и знаменитую задачу коммивояжера. Эта известная задача предоставляет список городов и расстояния между ними, и для нее требуется, чтобы коммивояжер нашел кратчайший маршрут для посещения всех городов.

Перспектива

Теперь, когда мы проанализировали общие временные сложности, давайте рассмотрим их в перспективе, чтобы сравнить их время выполнения. На приведенной ниже диаграмме, взятой из Руководства по разработке алгоритмов Стивена С. Скиены, сравниваются временные сложности, которые мы проанализировали сегодня, за исключением O (1) (постоянное время), поскольку входные данные не будут влиять на время выполнения. В крайнем левом углу мы видим различные размеры входных данных от 10 до 1 миллиарда. В остальных столбцах мы можем увидеть, сколько времени потребуется для выполнения каждого алгоритма для каждой временной сложности. Это хорошее напоминание о необходимости всегда оптимизировать код при решении проблем, поскольку ни у кого нет 31 года, чтобы ждать, пока сработает алгоритм O (n²).

Секреты и уловки

Во-первых, я хотел бы упомянуть, что, хотя мы проанализировали наиболее распространенные нотации Big O, не стоит просто запоминать каждую из них. Важно знать, как анализировать Big O, так как есть несколько других обозначений, которые вы можете найти, обратив внимание. Особенно важно обращать внимание на входные данные, особенно когда задействовано несколько коллекций. Давайте рассмотрим приведенный ниже пример:

function exampleOne(array1, array2){
    for (let i = 0; i < array1.length; i++){
        for (let j = 0; j < array2.length; j++){
            console.log(array[i] + array[j])
        }
    } 
}

На первый взгляд, у нас может возникнуть соблазн сделать вывод, что Big O этого алгоритма равен O (n²) из-за вложенного цикла for. Однако мы не можем предполагать, что два входных массива имеют одинаковую длину, поэтому их следует рассматривать как отдельные объекты. Следовательно, во вложенном цикле, где не гарантируется, что коллекции имеют одинаковый размер, правильная временная сложность фактически равна O (n * m).

А как насчет приведенного ниже примера?

function exampleTwo(array1, array2){
    for (let i = 0; i < array1.length; i++){
        console.log(array1[i])
    }
    for (let i = 0; i < array2.length; i++){
        console.log(array2[i])
    }
}

Здесь у нас может возникнуть соблазн предположить, что временная сложность составляет O (2n), упрощенная до O (n) из-за двух не вложенных циклов. В этом случае мы фактически перебираем две разные коллекции и снова не можем предполагать, что они будут одного размера. Следовательно, вместо O (2n), упрощенного до O (n), правильная временная сложность этого алгоритма составляет O (n + m). На этот раз мы используем знак плюса, потому что операции выполняются одна за другой, что увеличивает время. В предыдущем примере нам пришлось умножать, потому что циклы были вложенными, что увеличивает временную сложность.

Еще одно важное замечание, которое следует упомянуть при анализе временной сложности: остерегайтесь собственных методов! Собственные методы большинства языков программирования, особенно методы массивов, вероятно, увеличат временную сложность, и их абсолютно необходимо учитывать. Хорошее практическое правило - подумать о том, как реализовать собственный метод с нуля, такой как метод JavaScript .find. Если при реализации метода с нуля вам нужно будет перебрать каждый элемент в массиве, то этот собственный метод добавит временную сложность O (n). Давайте рассмотрим приведенный ниже пример.

function findMatchingElement(arr1, arr2){
    for (let i = 0; i < arr1.length; i++){
        if (arr2.includes(arr1[i]){
            return arr[i];
        }
    }
}

В приведенном выше примере мы написали функцию, которая выглядит достаточно невинной. Мы перекрестно проверяем два массива, чтобы определить, можем ли мы найти элемент, появляющийся в обоих массивах. Мы делаем это, просматривая один массив и проверяя, включает ли этот элемент второй массив. Один цикл for заставляет многих поверить в то, что этот метод работает за O (n). Однако важно отметить, что собственный метод .includes в JavaScript выполняется за O (n) под капотом. Следовательно, истинная временная сложность этого алгоритма на самом деле составляет O (n * m).

Замечание о космической сложности

Если вы зашли так далеко и поняли, как работает временная сложность, то у вас не должно возникнуть проблем с пространственной сложностью. Обозначения Big O для пространства записываются так же, как и для времени. Единственное отличие состоит в том, что вместо измерения количества операций, выполняемых алгоритмом, мы проверяем, сколько дополнительного места выделяет алгоритм при выполнении. Чтобы определить сложность пространства, мы обычно проверяем любые новые переменные, которые объявляются при запуске алгоритма. Это поможет нам определить, что мы храним в ОЗУ во время работы алгоритма и сколько места занимают эти переменные.

Возьмем простой пример:

function countUpToNum(num){
    let i = 1
    while (num <= num){
        console.log(i)
        i++
    }
}

В приведенной выше функции мы вводим новую переменную во второй строке, в которой хранится целое число. Теперь целые числа и строки являются примитивными типами данных в JavaScript, которые не могут быть изменены, поэтому эта переменная (несмотря на то, что она меняется каждый раз в цикле while) занимает константу или пространство O (1).

А как насчет других видов космической сложности? Что ж, если бы мы сохранили переменную пустого массива или объекта, который продолжает заполняться пропорционально нашему входному размеру, наша сложность пространства была бы линейной O (n). Если бы мы должны были хранить двумерный массив или вложенный объект, например, при заполнении матрицы, то наша пространственная сложность может быть O (n²) или O (n * m) в зависимости от того, являются ли внутренние и внешние коллекции одинаковыми. размер. Однако обычно имеет смысл повернуть или отсортировать массив или матрицу на месте, чтобы не усложнять пространство. В паттерне, аналогичном временной сложности, чем глубже мы вкладываемся, тем хуже становится наша пространственная сложность.

Сегодня мы обсудили, как более подробно анализировать «О» алгоритма. Мы коснулись некоторых правил, которым нужно следовать при анализе Big O, мы рассмотрели наиболее распространенные временные сложности и коснулись сложности пространства. До скорого!

Любой умный дурак может сделать вещи больше и сложнее ... Чтобы двигаться в противоположном направлении, требуется немного гения и много мужества.

- Альберт Эйнштейн