logo标签列表

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

c#javac++algorithmcomplexity-theory
6

我正在研究冒泡排序算法的空间复杂度。据我所知，冒泡排序算法的空间复杂度为O(1)。在下面的冒泡排序算法中，如何修改代码以使空间或内存复杂度为O(n)或O(n square)等。我需要了解空间复杂度的作用...谢谢。

 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;
            }
        }
    }
1
你的算法已经是 O(n) 空间复杂度。请注意，O(1) 是 O(n) 的子集。 - amit
7个回答
11

空间复杂度是衡量算法需要额外内存的度量。

如果您要分配一个大小为n的额外数组（其中n是输入数组的变量大小），则空间复杂度将为O(n)。

6

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

降低空间复杂度才是困难的。

代码意味着算法中的指令，还是应该增加数据？谢谢。 - user1862650
除非它能提高性能并且您需要这种改进，否则不应增加内存使用量，或者在这种情况下，出于兴趣。如果要将内存使用量增加为O(N)，请在开头添加arr.clone()。对于O(N^2)，可以在第一个循环内添加。对于O(N^3)，请在嵌套循环内添加。 - Peter Lawrey
1
准确地说，要增加空间复杂度（用大O符号表示），你不需要做任何事情。 O(1)是O(n)的子集。对于大Theta符号，答案当然是完全正确的。 - amit
6

我认为这值得回答，因为它对大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)中。

5

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

1
不，她的算法不需要任何“额外”的内存，并且排序是在同一个未排序的数组中进行的！因此根据我的理解，它在空间复杂度方面是O(1)。 - Marco167
1

您的算法的空间复杂度为O(n)，辅助空间复杂度为O(1)。

通常我们比较辅助复杂度。为什么？

归并排序需要O(n)的辅助空间，插入排序只需要O(1)的辅助空间。这两个排序算法的空间复杂度都是O(n)。

1
Bubble sort(A,n)
  for(i=n;i>=1;i--)
     for(j=1;j<=i-1;j++)
       if(a[j]>a[j+1])
       {
         t <- a[j]
         a[j] <- a[j+1]
         a[j+1] <- t
       }

在这里，我们展示了空间复杂度的输入变量和临时变量，其中i和j是输入变量，其空间复杂度始终为常数，临时变量t始终显示1，因此冒泡排序的空间复杂度为O（1）。

0
通常排序算法的空间复杂度为O(1)，这是一件好事。
如果您将输入复制到另一个数组中，那么如何浪费更多的内存呢？时间复杂度是相同的，只增加了O(N)，但现在您需要O(n)的内存，因为您需要为每个位置分配空间。
例如，对于堆排序，您需要构建一个堆。在这种情况下，您需要使用更多的内存。
你不能原地构建堆吗？ - Cruncher
@Cruncher 你可以这么做，但是对于堆排序，你需要将其弹出并添加到数组的前面。最简单的方法是使用一些额外的内存来完成这个过程。 - bcurcio
一般来说，排序算法的空间复杂度为O(1)。为什么呢？因为快速排序不是O(1)，它对于栈的空间复杂度为O(logn)。归并排序的空间复杂度为O(n)。 - amit
@amit，快速排序和归并排序都有O(1)的实现方式，但你说得对，标准实现是需要超过O(1)的内存的好例子。 - bcurcio
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接