Können Sie ein Beispiel für die Bewertung der Zeitkomplexität eines Sortieralgorithmus geben?

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

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