Вот что я узнал о нотации 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, чтобы узнать больше!
Приятного вам дня!