Мы рассмотрели варианты нотации Big O. Теперь давайте посмотрим на некоторый код JavaScript и проанализируем временную и пространственную сложность данного решения проблемы с кодом.

Как рассчитать временную и пространственную сложность данного решения?

Что мы добавляем, а что следует игнорировать?

Во-первых, временная сложность и пространственная сложность не одинаковы. Иногда они очень разные.

Данное кодовое решение может занимать лишь небольшое место в оперативной памяти компьютера во время работы. Но один и тот же фрагмент кода может быть выполнен x раз. Различные соображения для одного и того же фрагмента кода: требуемое пространство и требуемое время.

Мы поговорим об алгоритмах. Не волнуйтесь, я включу примеры для людей, озабоченных математикой. (В основном только для меня.)

Определение из Британики:

Алгоритм: Конкретная процедура решения четко определенной вычислительной задачи.

Использование алгоритмов требует понимания вариантов, доступных для решения проблемы.

Эти варианты для понимания включают, но не ограничиваются:

  • Аппаратное обеспечение
  • Сеть
  • Язык программирования
  • Ограничения производительности конкретного решения кода.

Итак, сколько места мы можем использовать в памяти компьютера? Сколько времени уместно потратить, пока код творит свое волшебство?

Алгоритм должен быть правильным, так как он полностью решает поставленную задачу и делает это наиболее эффективным способом.

Если вы хотите посмотреть, какие есть варианты для Big O, то ознакомьтесь с предыдущей статьей, которую я написал, «Обозначение Big O: о чем они говорят?».

Небольшое напоминание: константы и их удаление.

Из моего предыдущего поста вы, возможно, помните основной совет по константам. Наша цель — идентифицировать результаты как «n». Это может быть сколь угодно большим. Таким образом, по мере того, как «n» становится больше, меньшие соображения становятся незначительными для общего рассмотрения. Ниже вы увидите примеры, которые соответствуют: O(1) + O(n) + O(3) = означает O(n) в общей картине.

Хорошая вещь! Давайте посмотрим на решения постоянной, линейной, логарифмической и логарифмической временной сложности. Решение нотации Big O — большое решение!

Константа О(1)

Подсказка: проверьте, является ли число четным или нечетным.

Пример кода:

Временная сложность:O(1) Постоянное время

Пространственная сложность: O(1) Постоянное пространство

Почему?

Поскольку операции для каждого примера (если else и троичные версии выше) выполняются только один раз, системе потребуется одинаковое количество времени и места для запуска независимо от ввода. Поэтому, если я введу 10 000, а не 11, у меня все равно будет O(1). Мы не добавляем никаких новых переменных для хранения ответа, поэтому нет необходимости в дополнительном пространстве.

Другие примеры постоянного времени:

  • Найти значение на карте
  • Распечатать первый элемент из списка

Линейный O (n)

Подсказка. Найдите наибольшее число в несортированном массиве.

Пример кода:

Временная сложность:O(n) линейное время

Пространственная сложность:O(n) линейное время

Почему?

Время.У нас есть и другие операции, происходящие с этим, но они несущественны по сравнению с циклом. Цикл зависит от ввода. Выше в массиве семь элементов, но если бы их было 700, то все равно пришлось бы перебирать массив 700 раз. Временная сложность является линейной, потому что чем больше входные данные, тем больше времени потребуется.

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

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

Другие примеры линейного времени:

  • Распечатать все значения в списке
  • Суммируйте все числа в массиве

Логарифмический O (log n)

Подсказка: Найдите слово в словаре или число в отсортированном массиве.

Пример кода:

Временная сложность:O(log n) логарифмическое время

Пространственная сложность:O(1) постоянное пространство

Почему?

Время.Поскольку предоставленный массив уже отсортирован, мы можем разделить его пополам и проверить, больше или меньше искомый элемент, чем текущий средний. Как только мы узнаем, куда идти, мы можем продолжать разбивать массив пополам. Мы отбрасываем половину, которую исключили, пока не получим целевой элемент. Это экономит много времени, потому что мы не рассматриваем каждый элемент в отдельности. Мы сокращаем операции вдвое на каждом этапе.

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

Другие примеры логарифмического времени:

  • Двоичный поиск с рекурсией (в этом случае космическая сложность будет O (log n)).

Квадратичный O (n²)

Подсказка. Проверьте наличие дубликатов в массиве с помощью вложенного цикла for.

Пример кода:

Временная сложность:O(n²) квадратичное время

Пространственная сложность:O(1) постоянное пространство

Почему?

Время.Входной массив будет повторяться дважды для каждого элемента. Таким образом, [ i ] будет O (n), но тогда [ j ] также будет выполняться O (n) раз во внешнем цикле. Поскольку мы просматриваем каждый элемент (n) дважды, мы можем считать входной обход квадратным, что означает O(n²). Если в массиве 3 элемента, он просмотрит его 9 раз, с 4 элементами — 16 раз и так далее.

Строка 6: Массив имен будет выполняться пять раз, но затем строка 7 также будет выполняться еще 5 раз. Таким образом, будет 25 проверок. Массив может содержать 500 элементов, что означает 250 000 проверок. Вот почему это считается «наивным подходом», ваш ввод (n) будет проверен (n) x (n) раз. Это означает, что большой ввод займет много времени и может быть не самым эффективным.

Пробел:мы создаем только 2 дополнительные переменные вне входных массивов: [ i ] и [ j ]. Итак, еще раз: О(1) + О(1) = О(2). В качестве константы это будет просто закорочено до O (1).

Другие примеры квадратичного времени:

  • Поиск всех упорядоченных пар в массиве
  • Сортировка с помощью пузырьковой сортировки или сортировки вставками

Лог-линейный: O (n log (n))

Подсказка. Объедините два отдельных массива в один, отсортировав их от низшего к высшему (сортировка слиянием).

Пример кода:

Временная сложность:O(n log n) логлинейное время

Пространственная сложность:O(n) линейное пространство

Почему?

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

Но в функции mergeSorter() мы делаем что-то похожее на бинарный поиск, который мы делали выше в логарифмическом времени O(log n).

O (n) и O (log n) не похожи на подобные! Мы выполняем две разные операции одновременно, и, поскольку они разные, мы не можем просто объединить их, как делаем, когда видим, что O(3) округляется до O(1).

Пространство.Теперь занимаемое этим пространство зависит от двух массивов, которые мы объединяем. Нам нужно будет взять два массива и объединить их в результирующий массив. Это может занять десять или тысячу пробелов, это зависит от общей длины двух входных массивов, которые нам даны.

Другие примеры лог-линейного времени:

  • Быстрая сортировка
  • Сортировка кучей
  • Сортировка по дереву

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

Если вы используете любой из них в своих решениях для кодирования, вам, вероятно, нужно переосмыслить свои решения, по-крупному. Часто они настолько неэффективны, что, я бы сказал, их единственная цель — показать вам, что нельзя делать с временными и пространственными способностями вашего бедного компьютера.

Я надеюсь, что это было полезно для просмотра кода, чтобы увидеть, как на самом деле вычислить сложность Big O. Удачного кодирования!