Оценка сложности алгоритма позволяет измерить, как изменение размера входных данных влияет на время работы или используемую память. В Python для оценки сложности используется нотация Big-O, которая описывает, как быстро растет время работы алгоритма или его потребности в памяти.

Вот основные типы сложности:

• O(1) — Константное время. Время выполнения не зависит от размера входных данных. 

Пример:

def constant_time_example(arr):
   	 return arr[0]  # O(1)

• O(n) — Линейное время. Время выполнения пропорционально количеству элементов в данных. 

Пример:

def linear_time_example(arr):
    	for item in arr:
        	print(item)  # O(n)

• O(n^2) — Квадратичное время. Например, вложенные циклы, где количество операций пропорционально квадрату размера входных данных. 

Пример:

def quadratic_time_example(arr):
    	for i in arr:
        	for j in arr:
            		print(i, j)  # O(n^2)

Пример из реальной жизни

При сортировке массива алгоритм быстрой сортировки имеет среднюю сложность O(n log n), что значительно быстрее, чем сортировка методом пузырька, который имеет сложность O(n^2).