Puoi fare un esempio di valutazione della complessità temporale di uno degli algoritmi di ordinamento?

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

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