12

質問があります。アルゴリズムが必要とするメモリの大きな順序を見つけるとはどういう意味ですか?

それとビッグオー作戦の違いは何ですか？

例えば

次の疑似コードを考えると、初期化された 2 次元配列 A があり、両方の次元のサイズが n です。

for  i <- 1  to  n  do
       for  j <- 1  to  n-i  do
                        A[i][j]=  i + j

メモリの大きな o 表記は単に n^2 であり、計算も n^2 ではないでしょうか?

4

5 に答える 5

17

Big-Oh は、何かが他の何かに従ってどのように成長するかについてです(技術的には、何かがどのように成長するかの制限)。最も一般的な導入用の使用法は、入力のサイズに応じてアルゴリズムが実行される 速度を示すことです。

入力のサイズに応じて、どれだけのメモリが使用されているか を知ることができないということはありません。

iあなたの例では、とのすべての配列にバケットがあるため、スペース要件は のようにj大きくなります。O(i*j)O(n^2)

しかし、アルゴリズムが代わりに各配列のすべての数値の合計ではなく最大の合計を追跡していた場合、アルゴリズムO(n^2)は現在の i のみを追跡する必要があるため、実行時の複雑さは依然として一定ですが、スペースの複雑さは一定です。 、現在の j、現在の最大値、およびテストされる最大値。

于 2012-11-12T21:11:03.920 に答える
3

メモリの Big-O オーダーとは、処理される要素の数が増えるにつれて、アルゴリズムの実行に必要なバイト数がどのように変化するかを意味します。あなたの例では、データはサイズ nxn の正方配列に格納されているため、Big-O オーダーは n 二乗だと思います。

操作の大きな順序は、処理される要素の数が増えるにつれて、アルゴリズムを実行するために必要な計算の数がどのように変化するかを意味します。

于 2012-11-12T21:10:16.423 に答える
2

はい、上記の疑似コードの空間と時間の複雑さは n^2 です。

ただし、以下のコードでは、スペースまたはメモリの複雑さは 1 ですが、時間の複雑さは n^2 です。私は通常、メモリの複雑さを与えるコード内で行われる割り当てなどを使用します。

for i <- 1 to n do

   for  j <- 1  to  n-i  do

                    A[0][0]=  i + j
于 2012-11-12T21:11:33.900 に答える
1

正直なところ、「メモリの大きなO」については聞いたことがありませんが、計算時間に大まかに関連しているだけであると簡単に推測できます-おそらく下限を設定するだけです。

例として、n^2 メモリと n^3 計算を使用するアルゴリズムを設計するのは簡単ですが、その逆は不可能だと思います - n 複雑さの n^2 データを計算的に処理することはできません。

アルゴリズムの複雑さは 1/2 * n^ 2 なので、O(n^2)

于 2012-11-12T21:11:00.877 に答える