Ответ
Временная сложность (Time Complexity) — это мера, описывающая, как время выполнения алгоритма зависит от объёма входных данных. Она позволяет оценить эффективность и масштабируемость алгоритма.
Для измерения используется нотация «O-большое» (Big O), которая описывает асимптотическое поведение функции роста времени, отбрасывая константы и члены низшего порядка.
Основные классы сложности:
O(1)— Константная: Время выполнения не зависит от размера данных.- Пример: Доступ к элементу массива по индексу.
O(log n)— Логарифмическая: Время выполнения растёт очень медленно. Характерна для алгоритмов, которые на каждом шаге отбрасывают половину данных.- Пример: Бинарный поиск в отсортированном массиве.
O(n)— Линейная: Время выполнения растёт прямо пропорционально размеру данных.- Пример: Поиск максимального элемента в несортированном списке.
O(n²)— Квадратичная: Время выполнения растёт пропорционально квадрату размера данных.- Пример: Вложенные циклы для сравнения каждой пары элементов (например, в пузырьковой сортировке).
Пример на Python:
# Данный алгоритм имеет сложность O(n), так как в худшем случае
# он пройдет по всем 'n' элементам списка один раз.
def find_element(data_list, target):
for item in data_list:
if item == target:
return True
return FalseКлючевая идея — понять, как будет вести себя алгоритм при значительном увеличении объёма данных (n).