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)

なんでそうなの？ これは、「f（n）の漸近的な上限」（直観的な定義であり、形式的ではない）を持つ関数のセットであることに
注意してください。O(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

少なくとも n セルのメモリが必要なため、アルゴリズムはすでに O(n) スペースです

于 2012-12-06T23:55:32.827 に答える
0

一般に、並べ替えアルゴリズムのスペースの複雑さは O(1) です。これは良いことです

入力を別の配列にコピーする場合、より多くのメモリを浪費する方法があります。時間の複雑さは同じで、O(N) を追加するだけですが、各位置にスペースを割り当てる必要があるため、O(n) メモリが必要になります。

たとえば、ヒープソートの場合、ヒープを構築する必要があります。この場合、より多くのメモリを使用する必要があります。

于 2012-12-05T11:14:26.483 に答える