3

指定されたコード (以前の質問から 1 つだけを使用しています) の場合、O 表記を使用した実行時間は O(n^2) です。シータ表記を使用して実行時間を表現したい場合、それは同じでしょうか? 意味シータ(n^2)?

for(int i=0; i<N; i++){
   for(int j=1; j<N; j++){

    System.out.println("Yayyyy");
    if(i<=j){
        System.out.println("Yayyy not");
    }
}
}
4

2 に答える 2

0

本質的に：大きなO表記は、実行時間の上限を表します。これは、ほとんどのアルゴリズムにいくつかの大きなO境界があることを意味します（たとえば、アルゴリズムはアルゴリズムO(n^23)よりもはるかに効果的であるため、theta(n^23)アルゴリズム
はタイトな境界用です）。すべてのアルゴリズムに明確に定義されたタイトバウンドがあるわけではありません。これは、他の関数に比例して大きくなることを意味するためです。あなたの例では、「Yayyy not」（n ^ 2-n）/ 2回を出力せずにアルゴリズムを終了する方法はなく、この回数を超えて実行されることはないため、常にnに比例して増加します。 ^ 2、したがってtheta(n^2)限界があります！

于 2012-09-04T18:37:35.193 に答える
0

これを短くておいしくするために、BigO(n^2) は、アルゴリズムが ~n^2 時間より長くかからないことを意味します。BigTheta(n^2) は、アルゴリズムが ~n^2 時間より長くかからず、~n^2 時間より短くならないことを意味します。

于 2012-09-04T18:44:14.300 に答える