Пространственная сложность алгоритма сортировки пузырьков
я пытаюсь сделать исследование по Пространственной сложности алгоритма пузырьковой сортировки, что я знаю, что Пространственная сложность алгоритма пузырьковой сортировки составляет O (1), учитывая приведенный ниже алгоритм пузырьковой сортировки, как я могу изменить код aalgorthim пузырьковой сортировки, чтобы сделать пространство или сложность памяти до O (n) или O (n квадрат) и т. д. Мне нужно понять, где сложность пространства играет роль … спасибо
public void bubbleSort(int[] arr) {
boolean swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < arr.length - j; i++) {
if (arr[i] > arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
Решение
Сложность пространства — это мера того, сколько дополнительной памяти требует ваш алгоритм.
Если бы вам пришлось выделить дополнительный массив размером n (когда n — это переменный размер входного массива), сложность пространства была бы O(n),
Другие решения
Если вы хотите увеличить сложность пространства, вам просто нужно тратить память, например добавить код, чтобы использовать больше памяти.
Это уменьшает сложность пространства, что сложно.
Я думаю, что он заслуживает ответа, потому что он имеет некоторый вклад в большую букву O:
Ваш алгоритм уже есть O(n) а также O(n^2) пространство
Это потому что O(1) это подмножество O(n) и оба являются подмножествами O(n^2)
Почему это так?
Обратите внимание, что O(f(n)) это набор функций с «асимптотической верхней границей функции f (n)» (интуитивное определение, не формальное).
Таким образом, для каждого g(n)<h(n)<f(n), если h(n) является асимптотической верхней границей g(n)тогда f (n) также является его асимптотической верхней границей.
Таким образом, если g(n) в O(h(n)) — это также в O(f(n))
И в вашем случае, если функция сложности T(n) в O(1)это также в O(n)
Ваш алгоритм уже занимает O (n) места, так как вам нужно как минимум n ячеек памяти
В общем случае алгоритмы сортировки имеют пространственную сложность O (1). Это хорошая вещь
Как тратить больше памяти, было бы, если бы вы скопировали свой вход в другой массив. Временная сложность та же, вы только добавляете O (N), но теперь вам нужно O (n) памяти, потому что вам нужно выделить место для каждой позиции.
Например, для heapsort требуется построить кучу. В этом случае вам нужно использовать больше памяти.