0

今夜締め切りのプロジェクトの一部として Big O のアイデアを把握しようとしていますが、これが正しいかどうかはわかりません...

このプロジェクトには、数学演算に対する反復および再帰ソリューションの作成が含まれていました。

ここにいくつかの方法があります。

public int inc(int n)
{
    n = n + 1;
    return n;
}
public int dec(int n)
{
    n = n - 1;
    return n;
}

public int add(int lhs, int rhs)
{
   int sum = lhs;    
   while (rhs > 0) {
        sum = inc(sum);
        rhs = dec(rhs);
    } // while
    return sum;
}


public int fac(int num)
{
    int ans = num;
    while(num > 1)
        {
            ans = mul(ans, dec(num));
        }
    return ans;
}



public int div(int lhs, int rhs) throws ArithmeticException
{
    int quot = 0;
    while (lhs > 0)
        {
            lhs = sub(lhs,rhs);
    if(lhs < rhs)
                {
        quot = 0;
                }   
            else
                {
                    quot = inc(quot);
              }
        }
    return quot;
}


public int lshift(int lhs, int rhs)
{
    return mul(lhs,pow(2,rhs));       
}

これらはすべて O(n) でしょうか? それとも単に inc,dec, and add?

他のメソッドが呼び出される行 (mul -multiply - in fac および lshift など) の場合、これは定数時間ですか、それとも n であり、O(n^2) になりますか? 誰か説明してくれませんか？

また、再帰的なメソッドをどのように処理すればよいでしょうか?

public int  mul(int lhs, int rhs)
{
    if (rhs == 0 || lhs == 0) return 0;
    else if(rhs == 1) return lhs;
    return add(lhs, mul(lhs, dec(rhs)));
}

誰かが他のことを求めない限り、再帰的な例を 1 つ残します。if と else if はそれぞれ一定時間と見なされますよね？次に、return は (明らかに) それ自体だけでなく、あらゆる種類の他の再帰メソッドを呼び出しており、どこから始めればよいかまったくわかりません。

誰かがこれを本当に簡単に説明しようとすることができますか?

編集：パウを追加

public int pow(int lhs, int rhs)
{
    int ans = lhs;
    for(int i = rhs; i > 1; i--)
    {
    ans = mul(ans,lhs);
    }
    return ans;
}
4

2 に答える 2

1

Big-Oh の背後にある考え方は、それが特定のアルゴリズムの平均実行時間だということです。ランタイムを分析するときは、次のような重要なことを探します。

  • 使用されているパラメーターと、それを使用して実行されている操作との関係
  • 渡されるパラメータに対するコードの「重要な部分」の関係

最善の場合と最悪の場合の動作など、他にもいくつか確認する必要があります。

さて、あなたの方法に進みましょう。

  • incとはどちらもdec一定時間です。渡されたパラメーターのサイズに応じて、実行に時間がかかりません。

  • addrhsの値ごとに 1 ステップずつインクリメントするため、 は のサイズにバインドされrhsます。したがって、そのランタイムは O(n) になります。*

  • mul、再帰的な例ごとに、2つの基本ケースと反復ケースの3つのケースがあります。基本ケースは一定時間で実行されると想定されますが、反復ケースがあるため、基本ケースの実行時間よりも優先されます。

    その場合、rhs渡されたのサイズに拘束されるため、O(n) 時間で実行されます。

  • fac渡されたのサイズにバインドされnumます。O(n) ランタイムになります。

  • divにバインドされてlhsおり、O(n) ランタイムになります。

*: 2 つの数を加算する奇妙な方法について話します...

于 2013-04-15T00:19:40.540 に答える
0

incdecこれらは常に一定数の操作で実行でき、引数として渡す値に依存しないため、O(1) です。

addたとえば、引数として渡す数値に依存するため、この数値を「順序」と見なすと、addO(n) になります。

簡単に言えば、引数として渡す値が大きいほど、より多くの操作を行う必要があります。この増加は直線的であるため (大まかに言えば、100 ずつ増加すると、同じ桁数の操作が増加します)。

これは、より「高価mulな」操作のコストであるため、実装も O(n) 時間で実行されますadd。

理解する必要があるのは、Big-O 表記の意味です。つまり、アルゴリズムの実行時間と入力のサイズの変動との関係です。

これを念頭に置いておけば、メソッドのコストを把握するのがずっと簡単になります。

于 2013-04-15T00:20:29.980 に答える