Pode dar um exemplo de avaliação da complexidade temporal de um dos algoritmos de ordenação?

Рассмотрим пример оценки временной сложности алгоритма сортировки пузырьком (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]

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