冒泡算法的空间复杂度

Question

我正在尝试研究泡沫排序算法的空间复杂度我知道泡泡排序算法的空间复杂度是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;
            }
        }
    }

Answer 1

空间复杂度衡量算法需要多少额外内存.

如果你要分配一个大小为n的额外数组(当n是输入数组的可变大小时),空间复杂度就是O(n).

Answer 2

我认为它值得一个答案，因为它对大 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)

Answer 3

如果你想增加空间复杂性,你只需要浪费内存,例如添加一些代码来使用更多内存.

它减少了空间复杂性,这很难.

Answer 4

您的算法已经是 O(n) 空间，因为您至少需要 n 个内存单元