冒泡排序算法的空间复杂度

Question

我正在尝试对冒泡排序算法的空间复杂度进行研究，我知道冒泡排序算法的空间复杂度是O(1)给定下面的冒泡排序算法，我如何才能改变冒泡排序算法的代码，使空间或内存复杂度达到O(n)或O(n平方)，等等我需要了解空间复杂度在哪里起作用...thanks

 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

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

它降低了空间复杂度，这是很难的。

Answer 3

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