2

私は以下の擬似コードを持っています。これは、長さの特定のソートされていない配列を取り、配列size内の最大値と最小値を見つけることによって範囲を見つけます。私はさまざまな時間効率の方法について学んでいますがΘ(n)、より長い配列は固定数のアクションを追加するため、以下のコードは .

たとえば、 and への実際の代入を無視するmaxとmin(ソートされていない配列は任意であり、これらの代入は事前に不明であるため)、長さ 2 の配列では合計 5 つのアクションしか必要ありません (最終的な範囲の計算を含む)。長さ 4 の配列は合計 9 つのアクションのみを使用し、最終的な範囲計算を追加します。長さ 12 の配列は 25 個のアクションを使用します。

Θ(n)線形関係であるため、これはすべて私を指しています。これは正しいです？

擬似コード:

// Traverse each element of the array, storing the max and min values
// Assuming int size exists that is size of array a[]
// Assuming array is a[]

min = a[0];
max = a[0];

for(i = 0; i < size; i++) {
    if(min > a[i]) {         // If current min is greater than val,
        min = a[i];        // replace min with val
    }

    if(max < a[i]) {         // If current max is smaller than val,
        max = a[i];        // replace max with val
    }
}

range = max – min;             // range is largest value minus smallest
4

4 に答える 4

3

あなたが正しい。O(n)です。

簡単なコード (上記のようなコード) で簡単に見分ける方法は、for() ループがネストされている場合、その数を確認することです。「通常の」ループ (i = 0 -> n から) ごとに、係数 n を追加します。[Edit2]: つまり、次のようなコードがある場合:

array a[n]; //Array with n elements.
for(int i = 0; i < n; ++i){ //Happens n times.
    for(int j = 0; j < n; ++j){ //Happens n*n times.
        //something //Happens n*n times.
    }
}
//Overall complexity is O(n^2)

一方

array a[n]; //Array with n elements.
for(int i = 0; i < n; ++i){ //Happens n times.
    //something //Happens n times.
}
for(int j = 0; j < n; ++j){ //Happens n times.
    //something //Happens n times.
}
//Overall complexity is O(2n) = O(n)

これはかなり初歩的なことですが、誰かがアルゴリズムのコースを受講していない場合に役立ちます。

for() ループ内の手順は、複雑さの問題には関係ありません。

[編集]: これは、サイズが実際には配列 a のサイズを意味すると想定しています。

于 2013-09-19T23:31:52.650 に答える
3

はい、これは Θ(n) です。ただし、あなたの推論は少し歪んでいます。

ループ内のすべての項目を調べる必要があるため、線形関数によって上に制限されます。逆に、すべての要素を見ることを避けることができないため、線形関数 (実際には同じ関数) によって下に制限されます。

O(n) は上にバウンドすることのみを要求し、Omega(n) は下にバウンドすることを要求します。Θ(n) は、両側で制限されていると言います。

于 2013-09-19T23:36:16.437 に答える
2

サイズを とすると、常に比較が行われ、最後に単一の代入がnあることが明らかです。2nしたがって2n + 1、このアルゴリズムには常に操作があります。

最悪のシナリオでは、2n割り当てがあるため、 2n + 1 + 2n= 4n + 1= O(n).

最良のシナリオでは、0割り当てがあるため、2n + 1 + 0= 2n + 1= Ω(n).

したがって、最良のケースと最悪のケースの両方が線形時間で実行されます。したがって、Ɵ(n).

于 2013-09-19T23:33:53.017 に答える
1

ええ、これは確かにO(n)アルゴリズムです。アルゴリズムの複雑さに関する結論に到達するために、比較の数を確認するためにドリルダウンする必要はないと思います。入力のサイズが大きくなるにつれて、比較の数がどのように変化するかを確認してみてください。比較ではO(n)、入力の増加に伴って直線的に増加する必要があります。それO(n^2)は n の倍数などで増加するからです。

于 2013-09-19T23:34:04.283 に答える