Какие существуют алгоритмы с разной временной сложностью?

Некоторые алгоритмы с разной временной сложностью:

• O(1) — константная сложность. gitverse.ru proglib.io Время выполнения не зависит от объёма входных данных: алгоритм всегда выполняется за одинаковое количество операций. gitverse.ru Пример — функция сложения двух чисел. gitverse.ru
• O(n) — линейная сложность. gitverse.ru habr.com Время выполнения увеличивается пропорционально объёму входных данных: если объём увеличивается в 5 раз, то время выполнения тоже пятикратно увеличивается. gitverse.ru Классический пример — поиск минимального значения. gitverse.ru
• O(log n) — логарифмическая сложность. gitverse.ru habr.com Такие алгоритмы уменьшают объём данных для обработки на каждой итерации. gitverse.ru Время работы логарифмических алгоритмов растёт медленно относительно увеличения объёма входных данных, поэтому их относят к эффективным. gitverse.ru Пример — бинарный поиск в отсортированном массиве. gitverse.ru
• O(n log n) — линейно-логарифмическая сложность. gitverse.ru habr.com Возникает, когда в алгоритме комбинируется перебор всех элементов и уменьшение их количества на каждой итерации. gitverse.ru По эффективности такие программы располагаются между линейной и квадратичной сложностью. gitverse.ru
• O(n²) — квадратичная сложность. gitverse.ru habr.com Время работы зависит от квадрата объёма входных данных, квадратичная сложность свойственна некоторым алгоритмам сортировки, например, сортировке пузырьком. gitverse.ru
• O(n!) — факториальная сложность. gitverse.ru habr.com Это наименее эффективные алгоритмы: их скорость быстро падает с увеличением объёма входных данных. gitverse.ru
• O(n³) — кубическая сложность. habr.com Время выполнения зависит от размера входных данных в кубе. habr.com Например, алгоритмы, которые имеют три вложенных цикла, такие как некоторые методы многомерной обработки данных. habr.com
• O(2ⁿ) — экспоненциальная сложность. vc.ru Время на выполнение таких алгоритмов растёт в степени n к размеру входных данных. vc.ru Одним из примеров может служить рекурсивный алгоритм Фибоначчи. vc.ru