0

今週受けたクラスワークに行き詰まっており、本当に学びたい科目なので、一度追加の読書をしようと思いました!!!!

メソッドは私たちに提供されており、私はいくつかのテストケースを書いています。これは、私の知識が少しぼやけているところです。時間が増えると、私が信じている複雑さを過小評価していますか? この場合、n^3 では十分ではなく、n^4 では多すぎるため、徐々に 0 に減らします。

これは、2 の間にある複雑さがあることを意味します。これは、log n が n より小さい値であるため、log n が入る場所です。しかし、これは私の知る限りです

誰かが講義のスライドよりも良い説明でこの混乱を解消してくれることを本当に望んでいました。彼らは私にはまったく意味がないので、ありがとう

/**
 * Number 5
 */
public int Five(int n)
{
    int sum=0; 
    for(int i=0; i<n; i++){
        for(int j=0; j<i*i; j++){
            sum++;
        }
    }

    return sum;
}

   public void runFive()
    {
// Test n^2 complexity 
//         System.out.println("We are passing the value 5, This returns us an n value of " + Five(5) + " , With a time complexity of " + complexityN2(Five(5), 5) + " This is to test the value of 5 in a n^2 test" );
//         System.out.println("We are passing the value 10, This returns us an n value of " + Five(10) + " , With a time complexity of " + complexityN2(Five(10), 10) + "This is to test the value of 10 in a n^2 test" );
//         System.out.println("We are passing the value 100, This returns us an n value of " + Five(100) + " , With a time complexity of " + complexityN2(Five(100), 100) + "This is to test the value of 100 in a n^2 test" );
//         System.out.println("We are passing the value 1000, This returns us an n value of " + Five(1000) + " , With a time complexity of " + complexityN2(Five(1000), 1000) + "This is to test the value of 1000 in a n^2 test" );
//         System.out.println("We are passing the value 10000, This returns us an n value of " + Five(10000) + " , With a time complexity of " + complexityN2(Five(10000), 10000) + "This is to test the value of 10000 in a n^2 test" );

// Test n^3 complexity          
//         System.out.println("We are passing the value 5, This returns us an n value of " + Five(5) + " , With a time complexity of " + complexityN3(Five(5), 5) + " This is to test the value of 5 in a n^3 test" );
//         System.out.println("We are passing the value 10, This returns us an n value of " + Five(10) + " , With a time complexity of " + complexityN3(Five(10), 10) + "This is to test the value of 10 in a n^3 test" );
//         System.out.println("We are passing the value 100, This returns us an n value of " + Five(100) + " , With a time complexity of " + complexityN3(Five(100), 100) + "This is to test the value of 100 in a n^3 test" );
//         System.out.println("We are passing the value 1000, This returns us an n value of " + Five(1000) + " , With a time complexity of " + complexityN3(Five(1000), 1000) + "This is to test the value of 1000 in a n^3 test" );
//         System.out.println("We are passing the value 10000, This returns us an n value of " + Five(10000) + " , With a time complexity of " + complexityN3(Five(10000), 10000) + "This is to test the value of 10000 in a n^3 test" );
//         

//Test n^4 complexity
        System.out.println("We are passing the value 5, This returns us an n value of " + Five(5) + " , With a time complexity of " + complexityN4(Five(5), 5) + " This is to test the value of 5 in a n^3 test" );
        System.out.println("We are passing the value 10, This returns us an n value of " + Five(10) + " , With a time complexity of " + complexityN4(Five(10), 10) + "This is to test the value of 10 in a n^3 test" );
        System.out.println("We are passing the value 100, This returns us an n value of " + Five(100) + " , With a time complexity of " + complexityN4(Five(100), 100) + "This is to test the value of 100 in a n^3 test" );
        System.out.println("We are passing the value 1000, This returns us an n value of " + Five(1000) + " , With a time complexity of " + complexityN4(Five(1000), 1000) + "This is to test the value of 1000 in a n^3 test" );
        System.out.println("We are passing the value 10000, This returns us an n value of " + Five(10000) + " , With a time complexity of " + complexityN4(Five(10000), 10000) + "This is to test the value of 10000 in a n^3 test" );

    }

ここに複雑なメソッドがあります

public double complexityN2(double time, double n)
{
    return time / (n * n);
}

public double complexityN3(double time, double n)
{
    return time / (n * n * n);
}

 public double complexityN4(double time, double n)
{
    return time / (n * n * n * n);
}

public double complexityLog(double time, double n)
{
    return time / (Math.log(n) * (n*n));
}
4

5 に答える 5

5

big-O 表記は、アイテムの数が無限に近づくときの動作を表すことに注意してください。そのため、ほぼすべての実用的な量の計算を処理する場合に、正確な適合を期待するべきではありません。実際、どのような状況でも正確な適合が見られるとは限りません。漸近的に適合に近づく可能性がありますが、(実際的な観点から)関係する数が非常に大きい場合でも、非常に近い適合ではありません。テストの一部に使用しているような小さな数値 (たとえば、5、10、100) では、多くの場合、よくても当てはまりが非常に悪くなります。

タイミングの観点からは、Java のほとんどの実装では、作業も大幅に困難になります。問題は、ほとんどの JVM が、より最適化されたマシン コードにコンパイルする価値があるほど頻繁に実行されていると判断する前に、一部のコードの最初の数回 (「少数」はかなり大まかに定義されている) の反復を解釈することです。使用している数値はほぼ確実に小さいため、場合によっては解釈されたコードとコンパイルされたコードのタイミングを計っています (そして、その中のどこかで、コードのコンパイルにかかった時間も含めた実行を取得しています)。これは Big-O 表記の正確性には実際には影響しませんが、(特に小さい数の場合) big-O が予測するものにタイミングがどれだけ近づくかに実質的な影響を与える可能性があり、また影響を与えるでしょう。

于 2009-10-18T14:31:50.317 に答える
4

この場合、n^3では不十分です

それは真実ではない。の外側のループはFive正確にn回実行されます。iの値ごとに、内側のループは正確にi²回実行されるため、外側のループが実行するステップ数は、iが0からn-1まで実行されるときのi²の合計、つまりn/6--n²/2+n³/です。 3（誘導で証明するのは簡単）。これは3次の多項式であるため、O（n³）です。

于 2009-10-18T14:51:01.543 に答える
4

質問の唯一の疑問符は、この文の最後に表示されます。

これは、2 の間にある複雑さがあることを意味します。これは、log n が n より小さい値であるため、log n が入る場所です。

その文は質問ではなく、ステートメントです。ここで何を尋ねていますか?

あなたが何でlog(n)あるかを尋ねているなら、それはp10 (log 10と表示) または(自然e対数について話すとき) をその累乗 (すなわち 10 p , e p ) に累乗したときに が得られる数です。したがって、n が増加するにつれて非常にゆっくりと上昇します (実際には、指数関数的な増加とは正反対です)。n

log 10 (10) は 1 (10 1 == 10)
log 10 (100) は 2 (10 2 == 100)
log 10 (1000) は 3 (10 3 == 1000)

すでにこれらすべてを知っていたら、申し訳ありません。

于 2009-10-18T14:03:47.373 に答える
3

残念ながら、あなたは問題に正しく取り組んでいません。関数に対してやみくもにテストしても、これまでのところしか得られません。

O() 表記法は、実際には、x の値が非常に大きい場合、関数は時間 (aO(x)) で完了すると言っているようなものです。ここで、a は任意の定数です (0.00001 と 6305789932 のいずれかになります)。

コードを見てみましょう: 内側のループは i 2回実行されますが、(外側のループ) は n 回実行され、i は 0 から n までです。

ここで、内部操作 (sum++) Sum i=1,n i 2が実行され、ウィキペディアの知恵によって (*) になります。

次に、O() 表記を適用します。大きな n (たとえば 10 100 ) の場合、n 3は n 2とさらに多くの n 1を圧倒するので、それらを破棄するだけです: O(*) = O(n 3 )、これが練習問題の解です。

HTH

于 2009-10-18T14:55:05.420 に答える
0

このように理解してみてください。時間の複雑さを見つけるには、ループが実行される回数を見つける必要があります。ここでの合計も同じ数を表しているため、複雑度関数で時間の代わりに使用できます。この仮定は、ステートメントの各処理に一定の時間がかかるという仮定に基づいています。ループの実行回数を数えると、i = 0 の場合、内側のループは i = 1 の場合 0 回実行されます。内側のループは i = 2 の場合 1 回実行されます。内側のループは i = 3 の場合 4 回実行されます。内側のループは 9 回実行されます。回 i = m の場合、内側のループは m*m 回実行されます

したがって、処理されたステートメントの総数は次のようになります -- sum = 0 + 1 + 4 + 9 + .... + m m + ... +(n-1) (n-1) sum = 1 + 4 + 9 + .... + m m + ... +(n-1) (n-1) これらは自然数の 2 乗です 最初の N 個の自然数の合計は - N(N+1)(2N +1) / 6 この場合は N=n-1 なので、合計 = (n-1)(n)(2n-1) / 6 合計 = (nn -n) (2n -1) /6 合計 = (2n. nn - 2n.n - nn -n) /6 合計 = (2n^3 -3n^2 -n) / 6 合計 = 1/3n^3 - 1/2n^2 -1/6n

ここで、Big O は n の最高次数のみを考慮します。したがって、複雑さは n^3 のオーダーです。

n^3 の時間計算量関数は、正確にこの数値を取り、それを n^3 で割るので、合計は 1/3 - 1/2n^-1 -1/6n^-2 のようになります。

および n^4 の場合、さらに小さい数値であり、n が増加するにつれてさらに小さくなり、0 まで徐々に減少します。

于 2009-10-18T15:01:49.340 に答える