¿Puede dar un ejemplo de la evaluación de la complejidad temporal de uno de los algoritmos de ordenamiento?

Рассмотрим пример оценки временной сложности алгоритма сортировки пузырьком (Bubble Sort).

Алгоритм проходит по списку несколько раз, сравнивая соседние элементы и меняя их местами, если они идут в неправильном порядке.

• В худшем и среднем случае алгоритм выполняет примерно n*(n-1)/2 сравнений, где n — количество элементов.
• Поэтому временная сложность — O(n²).

Пример кода на Python:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

Этот алгоритм неэффективен для больших массивов из-за квадратичной сложности.