Введение в временную сложность с помощью Рататуя

Привет, повар Реми! С возвращением на кухню!

Сегодня мы собираемся завершить наше введение в Big O Notation с помощью O (log n), O (n log n), O (2 ^ n) и O (n!) С помощью безупречного фильма Pixar Рататуй. Когда мы в последний раз остановились, мы готовили наше знаменитое блюдо рататуй для печально известного ресторанного критика Антона Эго, который терпеливо ждал своей еды.

В качестве напоминания ознакомьтесь с таблицей сравнения временной сложности ниже:

O (log n) Время записи

Допустим, наш официант получил заказ от загадочно замаскированного человека (замаскированный шеф-повар Скиннер! 🕵🏻‍♂️), который сказал: «Я возьму то, что у него есть», имея в виду Антона Эго.

Мы знаем, что Антон Эго сидит за столом 29, поэтому нам нужно будет найти его заказ на еду по его номеру стола. К счастью для нас, номера таблиц всегда хранятся отсортированными в нашем массиве orders. Это очень полезно, потому что в ресторане очень много посетителей, и мы не можем заставить клиентов ждать! Нам нужен быстрый способ выяснить, что заказал Антон Эго, чтобы мы могли удвоить его для таинственного покупателя-джентльмена (coughSkinnercough):

Поскольку заказы отсортированы по table номеру, мы можем использовать двоичный поиск, чтобы сократить время поиска. В этом методе мы берем средний порядок в массиве orders и проверяем три вещи:

  • Это table соответствует тому tableNum, которое мы ищем? Если да, то отлично! 🎉Возвратите этот объект заказа. Если не:
  • Это table меньше того tableNum, которое мы ищем? Если да, удалите первую половину массива. Если не:
  • Это table больше, чем tableNum, которое мы ищем? Если да, удалите вторую половину массива.

Мы повторяем этот процесс, пока не найдем искомый объект заказа. Поскольку мы постоянно удаляем половину массива на каждом рекурсивном шаге, мы говорим, что временная сложность равна O (log n) или log time.

Это относится к очень математическому термину, логарифм, который в нотации Big O рассматривает вопрос: Сколько 2 мы умножаем вместе, чтобы получить n? Если бы n было равно 8, потребовалось бы 3 операции, потому что 2 * 2 * 2 = 8. Если бы n было 100, потребовалось бы 7 операций, а если бы n было 4 000 000 000, то потребовалось бы только 32! (Алгоритмы Grokking)

Эта временная сложность супероптимальна и чуть выше постоянной времени O (1)! Если ваше решение находится за время O (log n), вы должны быть очень довольны! 🙌

O (n log n) Линейное время

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

Если бы мы хотели сократить это время (потому что Антон Эго ждет, и его отзыв сделает или испортит этот ресторан !! ⏳ ), мы вместо этого можно использовать алгоритм mergesort. Представим, что каждый ломтик овощей имеет рейтинг от 1 до n, где 1 - лучший ломтик, а n - худший:

Сортировка слиянием использует подход разделяй и властвуй (аналогичный бинарному поиску), непрерывно выбирая массив и разбивая его, пока каждый элемент не станет его собственным индивидуальным подмассивом. Затем он рекурсивно сортирует эти подмассивы попарно, пока весь массив не будет отсортирован и снова не объединен. Эта статья отлично объясняет алгоритм более подробно.

При таком подходе временная сложность составляет O (n log n) из-за двух основных этапов. Разрушение исходного массива zucchiniSlices происходит за время O (log n). Чтобы собрать их вместе с помощью сортировки, требуется время O (n), поскольку необходимо учитывать каждый элемент (ломтик цуккини), а также время O (log n), чтобы объединить каждый подмассив. Это похоже на выражение n * log n и также известно как линейное время.

Поскольку этот метод сортировки и временная сложность более оптимальны, чем O (n²), мы можем поместить эти овощи в духовку и на тарелку Антона Эго намного быстрее! 👍

O (2 ^ n) экспоненциальное время

Рататуй почти готов к подаче, но кажется, что ему не хватает… чего-то. Как шеф-повар Реми, вы смотрите вокруг и думаете о трех травах, которые можно было бы добавить сверху: тимьян, розмарин и / или майоран 🌱.

Обдумывание различных комбинаций трав даст O (2 ^ n) возможностей:

// with just 1 herb there are 2 options:
[""] or ["thyme"]
// with 2 herbs there are 4 options:
[""] or ["thyme"] or ["rosemary"] or ["thyme", "rosemary"]
// with 3 herbs there are 8 options:
[""] or ["thyme"] or ["rosemary"] or ["marjoram"] or
["thyme", "rosemary"] or ["thyme", "marjoram"] or ["rosemary", "marjoram"] or ["thyme", "rosemary", "marjoram"]

Как видим, количество вариантов растет пропорционально 2 ^ n:

  • Когда n = 1, у нас есть 2 ^ 1 возможностей.
  • Когда n = 2, у нас есть 2 ^ 2 возможности.
  • Когда n = 3, у нас есть 2 ^ 3 возможности и так далее.

Это называется набором мощности, цель которого состоит в том, чтобы найти все возможные подмножества данных вариантов, а временная сложность может быть дорогостоящей. К счастью для Антона Эго, вы инстинктивно точно знаете, что нужно добавить (веточку розмарина, конечно! 👌), и вам не нужно думать о каждой комбинации. Блюдо наконец готово!

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

O (n!) Факториальное время

Сегодняшний вечер - это торжественное открытие нашего ресторана, столики забиты, а серверы очень заняты, чтобы обслужить каждого из них!

Поскольку время имеет значение, а люди голодны, наш официант Лингвини хотел бы рассчитать лучший маршрут между столиками, чтобы он прошел (или покатался на коньках) минимальное расстояние между каждым столиком. Оказывается, существует МНОГО возможных маршрутов между таблицами, даже если их всего несколько!

Если Linguini назначен на 5 таблиц, чтобы изучить каждый возможный маршрут, вам нужно будет выполнить (5 * 4 * 3 * 2 * 1) перестановок, что в сумме составит 120. (Алгоритмы Grokking) Если бы вы добавили еще одну таблицу, чтобы получилось 6, это увеличилось бы до 720 операций (6 * 120). Если вы добавите еще одну, чтобы получить 7 таблиц, это число вырастет до 5 040, а если у вас каким-то образом было 15 таблиц ... это выльется в 1 307 674 368 000 операций! Ой! 😱

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

Вот и все! Кульминация нашего руководства из двух частей для начинающих по нотации Big O. (Не стесняйтесь проверить часть 1 здесь, охватывающую O (1), O (n) и O (n²)!)

Так как же все прошло с рататуем? Кажется, им понравилось. 😊