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

Что такое временная сложность?

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

Типы временной сложности

Есть много типов сложности времени выполнения. Как только вы их поймете, вам будет легко распознать среду выполнения как вторую натуру.

Самым простым из них является постоянный тип O (1), который является самым быстрым во время выполнения.

O (1) - самое быстрое время выполнения. Ваш алгоритм должен соответствовать этому типу.

Пример линейного времени выполнения

Давайте попробуем понять более сложный тип, который является линейной сложностью. Остальные типы построены на этом.

В следующем примере нам нужно написать функцию, которая проверяет, есть ли во входной строке гласный звук. Если во входной строке есть гласная, то верните, сколько гласных.

Нотация Big-o - это научный термин, обозначающий временную сложность. Ученые и исследователи использовали название Big-O Notation в своих исследованиях и академических публикациях.

Построение алгоритма

Итак, мы можем решить эту проблему, объявив переменную для счетчика и присвоив ей значение «0». Во-вторых, объявите постоянную переменную для гласных букв и установите ее равной массиву гласных букв. После этого выполняется итерация по каждому символу входной строки. Затем проверяется, включен ли этот символ в массив гласных, который мы определили ранее. Наконец, верните счетчик.

P.S: Я установил гласные в массив, потому что в случае, если вы захотите добавить больше букв в будущем.

Обсуждение решения с точки зрения сложности времени

После решения проблемы интервьюер спросит вас, какова временная сложность вашего решения. Или сколько процессорной мощности компьютер должен потратить для запуска вашего алгоритма? Если ваш ввод станет «Я очень счастлив сегодня», вам придется повторить цикл for 5 раз - количество букв в сегодня . Означает, что процессор должен увеличить вычислительную мощность в N раз, если у нас есть N символов. Это отношение линейного типа.

При увеличении размера ввода время увеличивается пропорционально - обратите внимание на зеленую линию.

То же самое, если вы перебираете половину коллекции, например, при проверке, является ли входная строка палиндромом. Время выполнения n / 2, что приводит к O (n).

Квадратичная временная сложность

Квадратичный означает удвоение в математике. Это уравнение называется квадратным уравнением x² + 4x + 4 = 0. Это уравнение можно абстрагировать до (x + 2) ² = 0. Итак, в нашем случае, если у вас есть два вложенных цикла, повторяющих одну и ту же коллекцию, это будет квадратичная сложность выполнения, потому что у вас есть цикл². Процессору необходимо удвоить работу, чтобы запустить алгоритм.

Так почему же сортировка требует времени?

Я всегда задавал себе этот вопрос, пока не понял логику этого алгоритма ¹. Алгоритм сортировки занимает O (n * log n) - квазилинейное время, что является наилучшим наихудшим случаем. время выполнения, которое мы можем получить для сортировки. Для сортировки массива обычно используется алгоритм сортировки слиянием. Сортировка слиянием - это разделение массива на две части, сортировка их, а затем повторное соединение двух частей в одну всю отсортированную коллекцию. Следующая иллюстрация демонстрирует, что именно происходит за сценой.

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

Обобщение типов сложности времени выполнения

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

Шпаргалка

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

  • Если вы перебираете одну коллекцию элементов, используя один цикл, время выполнения будет O (n) .
  • Если вы повторяете более половины коллекции, это будет O (n / 2) - ›O (n).
  • Если вы перебираете по двум отдельным коллекциям, используя два разных цикла, он станет O (n + m) - ›O (n).
  • Если вы повторяете одну коллекцию с использованием двух вложенных циклов, это будет O (n²).
  • Если вы перебираете две разные коллекции с использованием двух вложенных циклов, она станет O (n * m) - ›O (n²).
  • Если вы сортируете коллекцию, она становится O (n * log (n)).

Заключение

Сложность по времени - обширная тема, которую можно решить всего в одной статье. В этом посте я попытался дать вам лучшую отправную точку, с чего начать. Я надеюсь, что смогу описать вам теорию и дать ее понять. В справочном разделе вы можете найти лучшие ресурсы для более глубокого изучения этой темы. Если вам понравился мой пост, поставьте мне 👏 👏 👏 и подпишитесь на меня здесь в среде или оставьте комментарий. Вы можете подписаться на меня в твиттере @salmaneg. Спасибо за прочтение!!!

Использованная литература:

  1. Торт интервью - логарифм в сортировке ¹.
  2. Википедия Big-O-Notation.
  3. Устойчивость в алгоритме сортировки - geeksforgeeks.
  4. Визуализация алгоритма сортировки - топтал.
  5. Если вы любите глубоко нырять, то этот сборник научных публикаций будет приятно читать - Kalle Rutanen.