2 
function DoStuff(someNumber) {
    for(var i = 1; i <= someNumber; i++) {
        // some arbitrary logic
        for(var a = 0; a <= 3; a++) { // This loop gets run 4 times regardless of i
            // Do something 
        }
    }
}

このメソッドの BigO 表記は O(n) + 4 なので、O(n) だけですか?

4

3 に答える 3

1

はい、O(4*n)それは です。これは と同じO(n)です。次のように考えることができます: ループは一定回数繰り返されるため、次のように「展開」できます。

for(var i = 1; i <= someNumber; i++) {
    // some arbitrary logic
    // Do something
    // Do something
    // Do something
    // Do something
}

これは間違いないO(n)。

于 2013-04-25T01:05:55.623 に答える
1

アルゴリズムは時間 O(n) で実行されますが、分析は間違っています。これらのネストされたループを使用すると、次のことがわかります。

  • 内側のループは常に一定の回数実行されるため、内側のループを実行するたびに O(1) の作業が行われます。

  • 外側のループは O(n) 回実行されます。各反復では、一定量の作業に加えて、内側のループを実行するために必要な作業が行われます。したがって、各反復は O(1) の作業を行います。したがって、ループの入れ子を実行するために必要な合計作業は O(n) です。

2 つを一緒に追加しないことに注意してください。内側のループが 4 回実行され、外側のループが O(n) 回実行されるため、作業が O(n) + 4 = O(n) であると言うのは正しくありません。 . むしろ、それらを増やす必要があります。答えは同じですが、それはアプローチが正しいという意味ではありません。たとえば、内側のループも n 回実行された場合、実行時間は O(n) + O(n) = O(n) と誤って示されますが、実際には実行時間は O(n) × O になります。 (n) = O(n 2 )。

お役に立てれば！

于 2013-04-25T01:06:24.527 に答える