0
У нас есть серия чисел. Мы можем видеть, что эта серия почти отсортировано. Поскольку эта серия почти отсортировано означает ли это, что сложность O (n)?Сложность сортировки пузырьков O (n)
A
ответ
1
Нет. Есть так много причин, это трудно понять, с чего начать. Во-первых, нотация O() не определена для конкретных примеров ввода. Сложность алгоритма определена для любого возможного ввода.
Кроме того, даже почти Сортированный список может потребовать O (N^2) время сортировки. Просто возьмите отсортированный список, замените первый и последний элементы и передайте это в Bubble Sort. Похоже, что это будет соответствовать определению почти отсортированного, но Bubble Sort примет N^2 операций, чтобы поместить список в полный порядок.
+0
https://en.wikipedia.org/wiki/Bubble_sort, похоже, не согласен. Он рассматривает нотацию O() как не определяемую размером ввода, но случаи ввода являются штрафом - худшим случаем, в лучшем случае каждый может получить O() 'd –
+0
@DavidB wikipedia можно редактировать goofballs, но O() Обозначение для алгоритма не имеет ничего общего с конкретными случаями и всегда зависит от размера ввода. Я предлагаю вам проверить Cormen, Leiserson, Rivest, «Введение в алгоритмы» для авторитетного источника, а не википедии. –
+0
Если википедия ошибочна в этом вопросе, мы должны это исправить. –
0
Да. Этот пример можно рассматривать как O(n).,
Есть случаи, когда O(n) и даже меньше, чем это возможно.
ПРИМЕРЫ
Уже отсортированный массив (1 2 3 4 5 6)
Массив, в котором обмениваются (2 1 4 3 6 5)
т.д.
только альтернативные значения Сохраняя лучшие случаи или исключительные случаи в сторону, сложность сортировки Bubble для заданного случайного несортированного массива - O(N^2).
+0
Этот ответ создает впечатление, что вы не представляете, для чего предназначена O(). –
0
Это очень расплывчато, но Обозначение O() говорит о В худшем случае runtime. Таким образом, любой вход, который передается для сортировки пузырьков (например), может принимать не более n^2 количество операций для сортировки. Конкретные примеры могут занимать от наименьшего количества операций до максимально возможного количества операций (с пузырьковой сортировкой, которая равна O (n^2)).
Смежные вопросы
- 1. Почему сложность сортировки пузырьков равна O (n^2)?
- 2. Найдите временную сложность сортировки пузырьков?
- 3. Какова временная сложность этой функции сортировки пузырьков?
- 4. Is Big O временная сложность этого кода сортировки n^2?
- 5. сложность слияния O (nlogn) + O (n)?
- 6. O (N^2) сложность
- 7. алгоритмическая сложность O (N)
- 8. Как анализировать сложность данной оптимизированной сортировки пузырьков?
- 9. Анализ алгоритма сортировки пузырьков
- 10. временная сложность алгоритма сортировки имен с использованием сортировки пузырьков
- 11. O (N) Алгоритм сортировки
- 12. Алгоритм сортировки O (n)
- 13. Сложность Время O (n) или O (n (n + 1)/2)
- 14. Не должна ли пространственная сложность сортировки вставки быть O (N)?
- 15. Имеется ли алгоритм сортировки, который имеет временную сложность O (N)?
- 16. O (N + M) временная сложность
- 17. O (N log N) Сложность - аналогично линейному?
- 18. Является ли сложность O (log (n)) эквивалентной O (sqrt (n))?
- 19. Сложность времени O (N) или O (Log N)?
- 20. O (n) или O (n)^2 временная сложность алгоритма?
- 21. Временная сложность O (N журнал (журнал N)) + п O (L)
- 22. Сложность времени создания пузыря сортировки
- 23. Пространственная сложность большинства алгоритмов сортировки O (1) Вспомогательная?
- 24. Сложность сортировки
- 25. BIG O сложность n или n^2log (n)
- 26. Сложность сортировки и сортировки пузырьков для списка с заданным числом инверсий
- 27. Процедура сортировки пузырьков
- 28. Ошибка сортировки пузырьков
- 29. Измененная ошибка сортировки пузырьков
- 30. Параллельные характеристики сортировки пузырьков
Это будет зависеть от определения «почти отсортированного». – SamB
Что относительно (2 3 4 5 6 1)? Это также почти сортировано. –