Вот что я узнал о нотации Big-O и сложности времени!

Первоначально опубликовано на Hashnode.

Содержание:

  • Введение
  • Что такое нотация Big-O и временная сложность?
  • Почему я должен переживать?
  • Как это рассчитать?
  • Классы общей сложности

Введение

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

В каких именно условиях?

По времени выполнения, необходимому пространству, читабельности кода…

Все зависит от конкретной ситуации, вы поняли.

А для этого требуется знакомство с Time Complexity.

Что такое нотация Big-O и временная сложность?

Сложность времени:

Это оценка эффективности алгоритма для заданного входа.

Обозначение Big-O:

Это обозначение для сложности времени, обозначаемое как O (что-то).

Также известен как нотация Бахмана-Ландау или асимптотическая нотация для читателей, интересующихся математикой.

Произносится: O чего-то, Порядок чего-то или Big-O чего-то.

Тогда как «что-то» - это математическая функция от n.

n - размер ввода. Например, если ввод является строкой, n будет ее длиной (количеством символов). А если это массив, это количество элементов в нем.

Для подробного определения рекомендую Википедию.

Почему я должен переживать?

Большинство собеседований (если не все) для специалистов по разработке программного обеспечения проверяют ваши навыки решения проблем И оптимизации алгоритмов; как найти эффективное решение и как его улучшить.

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

У вас также будет представление о том, какой подход использовать с учетом размера входных данных.

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

Итак, как его рассчитать?

А теперь самое интересное!

Петли

Что делает алгоритм таким медленным большую часть времени, так это наличие множества вложенных циклов; чем больше вложенных циклов, тем медленнее:

Если есть k вложенных циклов, сложность времени равна O (n ^ k).

Следующий код имеет сложность O (n):

Порядок величины

Как мы упоминали ранее, временная сложность - это оценка алгоритма, что означает, что он не предоставляет нам точное количество раз, когда код внутри нашего цикла выполняется. .

Итак, что это дает нам?

Он дает нам величину.

Например:

  • O(2n + 1) is O(n)
  • O(1000n +300) is O(n)
  • O(5n²) is O(n²)

И так далее…

Фазы

Фаза - это отдельный цикл в коде.

Например:

Так как же рассчитать временную сложность такого кода с несколькими фазами?

Мы берем самую большую временную сложность одной фазы.

Почему?

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

В продолжение предыдущего фрагмента кода, его временная сложность - это временная сложность 2-го этапа, которая равна O (n * m).

Иногда временная сложность зависит от дополнительных факторов к размеру ввода n, как, например, m в предыдущем примере. .

Классы общей сложности

Вы, скорее всего, будете часто сталкиваться с такими сложностями:

  • Постоянный алгоритм O (1): функция (f (n) = 1) не зависит от n; размер ввода не влияет на время выполнения. Мы обычно видим это с помощью математических формул.
  • Линейный алгоритм O (n): время выполнения растет пропорционально увеличению размера входных данных; f (n) = n. Когда требуется определенная манипуляция с данными, это часто является лучшим решением, поскольку входные данные проходят только один раз!
  • Квадратичный алгоритм O (n²): содержит два вложенных цикла. Обычно проходит вход дважды. То же самое касается кубического алгоритма O (n³), который имеет по очереди три вложенных цикла; проходим вход три раза.
  • Логарифмический алгоритм O (log (n)): он логарифмический, потому что на каждом шаге размер ввода уменьшается вдвое, log (n), таким образом, это количество раз n нужно разделить, чтобы получить 1.
  • O (n!): это часто означает, что алгоритм проходит через все возможные перестановки входных данных.

Спасибо за чтение!

Вот и все, дамы и господа, надеюсь, вам понравилась статья!

Любые отзывы или конструктивная критика приветствуются и приветствуются, поэтому, пожалуйста, поделитесь своим мнением в комментариях, чтобы я мог улучшить качество. Спасибо за чтение ❤️!

Следите за моим блогом и моим Twitter, чтобы узнать больше!

Приятного вам дня!