Время выполнения пузыря / простой сортировки

Question

В классе простая сортировка используется как одно из наших первых определений времени выполнения O (N) ...

Но, поскольку каждый раз, когда она запускается, она проходит на одну и ту же итерацию массива, не будетt это что-то более похожее на ...

время выполнения bubble = sum (i = 0, n, (ni))?

И не только самые большие процессы при запускеодин за другим считается в асимптотическом анализе, который был бы итерацией N, почему по определению этот вид не O (N)?

Answer 1

Сумма 1 + 2 + ... + N равна N*(N+1)/2 ... (математика средней школы) ... и приближается к (N^2)/2, когда N уходит в бесконечность.Классический O(N^2).

Answer 2

Я не уверен, откуда вы (или ваш профессор) поняли, что пузырьковая сортировка - O (n). Если бы у вашего профессора был гарантированный алгоритм сортировки O (n), было бы разумно попытаться запатентовать его: -)

По своей природе пузырьковая сортировка O (n ² ).

Это потому, что он должен сделать полный проход всего набора данных, чтобы правильно разместить первый элемент.

Затем второй проход N - 1 элементов для правильного размещения второго. И третий проход N - 2 элементов для правильного размещения третьего.

И так, эффективно заканчивая операциями, близкими к N * N / 2, которые, удаляя лишнюю константу 0.5, равны O (n ² ).

Answer 3

Сложность по времени сортировки пузырьков O (n ^ 2). При рассмотрении сложности учитывается только наибольшее выражение (но не фактор)