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;
            }
        }
    }
4

7 回答 7

11

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

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

于 2012-12-05T11:10:53.450 回答
6

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

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

于 2012-12-05T11:09:40.337 回答
5

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

于 2012-12-05T11:31:48.053 回答
4

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

于 2012-12-06T23:55:32.827 回答
1

这里算法的空间复杂度是 O(n)，辅助空间复杂度是 O(1)。

一般来说，我们会比较辅助复杂度。为什么 ？

合并排序需要 O(n) 辅助空间，而插入排序需要 O(1) 辅助空间这两种排序算法的空间复杂度是 O(n)。

于 2019-01-13T14:29:05.400 回答
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
       }

Here we show input variable and temporary variable for space complexity then i and j are input variable of which space complexity always be constant and temporary variable t always be show 1 so space complexity of bubble sort is o(1).

于 2020-11-26T08:50:21.977 回答
0

一般来说，排序算法的空间复杂度为 O(1)。这是一件好事

如果您将输入复制到另一个数组，如何浪费更多内存。时间复杂度是一样的，你只加 O(N)，但是现在，你需要 O(n) 内存，因为你需要为每个位置分配空间。

例如，对于堆排序，您需要构建一个堆。在这种情况下，您需要使用更多内存。

于 2012-12-05T11:14:26.483 回答