#big-o #bubble-sort
#big-o #сортировка пузырьками
Вопрос:
Мне было интересно, возможно ли вообще в качестве концепции иметь Big-O-нотацию O (0) (в очень специфическом сценарии).
Представьте, что у меня есть список со значениями, и я хочу отсортировать его с помощью Bubblesort . Предположим, однако, что список уже отсортирован. Если я не ошибаюсь, это будет иметь Big-O-нотацию O (n), где n — количество элементов.
Теперь я хочу выразить Big-O-нотацию обменов, которые мне пришлось сделать, чтобы отсортировать список. В этом очень специфическом сценарии не было произведено никаких замен. Итак, я бы пошел на это, сказав, что Big-O-нотация swaps равна O (0) или это минимум, который я могу иметь O (1), и почему?
Комментарии:
1. Обозначение Big O обозначает, как сложность зависит от размера входных данных. Количество обменов в отсортированном массиве (ноль) постоянно относительно длины массива, так что это
O(1).2. О, спасибо, это проясняет ситуацию: D
Ответ №1:
Простейшая сложность — это O(1) постоянное время (или пространство, или что-то еще, что вы можете измерять, включая количество обменов). Это постоянно, даже если значение равно нулю.
В любом случае функции сортировки не являются O (1), потому что, как минимум, вы должны проверить, что они отсортированы, даже если вы не производите никаких замен. Ваше конкретное измерение количества подкачки может дать вам O (1), но мне было бы интересно, почему это считается полезной метрикой 🙂