Сейчас я вам расскажу о сложности алгоритмов и как её можно описать, так же расскажу о самых распространённых зависимостях между входными данными и временем выполнения алгоритма.
Давайте сперва разберёмся что такое алгоритм, если просто, то это инструкция, которая чётко определена и которую можно использовать для решения определённой задачи.
Например, нам нужно найти факториал некого числа и мы напишем функцию, которую можно вызвать для любого числа, чтобы она нашла его факториал.
Эта функция и является алгоритмом, ведь она решает определённую задачу.
Теперь давайте разберёмся, что такое Big "O"?
Конкретного определения для этого нет, но Big "O" используется для описания сложности алгоритмов, где сложностью является некое время выполнения алгоритма, которое зависит от входных данных, а так же это может быть память, которая выделяется для хранения алгоритма, которая тоже зависит от входных данных.
а теперь давайте рассмотрим пару видов этих самых зависимостей, для лучшего понимания материала.
О(1)
O(1) описывает алгоритм, который всегда будет выполняться за одно и то же время (или занимать одно и тоже пространство) независимо от набора входных данных.
Давайте приведу пример кода:
Тут какой-бы не был большой список, код будет выполняться одинаково быстро, ведь мы обращаемся к определённому элементу массива. А вот, например, если мы хотим вывести все элементы массива, то ту уже будет решать и размер списка, но это уже другая закономерность, которую мы сейчас и рассмотрим.
О(N)
Это прямая зависимость сложности от входных данных, если рассматривать это математически, то это y = kx + b, где b != 0.
Примером, как я уже говорил, может служить алгоритм: вывести все элементы массива:
В данном случае сложность уже зависит от входящих данных, и Big"O" можно представить, как O(7).
Кстати первый пример с факториалом, тоже относится к O(N). Да и сюда относятся все алгоритмы с повторяющимися итерациями, например, циклы и рекурсии. А вот вложенные циклы относят к другому виду.
O(N²)
O(N²) представляет собой алгоритм, производительность которого прямо пропорциональна квадрату размера входного набора данных. Это характерно для алгоритмов, включающих вложенные итерации по набору данных. Более глубокие вложенные итерации приведут к O(N³), O(N⁴) и т.д.
Вот простой пример:
Вывод:
1 2 3
2 4 6
3 6 9
🔥На самом деле видов таких закономерностей намного больше, да и по этой теме много ещё, что есть мне рассказать, так что задавайте вопросы и ставьте плюсики, тогда я буду знать, что вам интересно и выпущу продолжение!
Так же заходите на мой ТГ-канал, там вы найдете ещë больше полезных статей и информации об ИТ и технологиях