1 
for(int i=N; i>0; i=i/2)  
    irrelevant statement;

複雑度クラスを見つけるように求められましたが、Big-Omega 表記と Big-O 表記のどちらを使用すればよいかわかりません。しかし、定数を削除すると、それは O(N/2) であり、次に O(N) であると想定しています。

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

これについては、Nをドロップした後、O（N）* O（N + 1）-> O（N ^ 2 + N）、次にO（N ^ 2）だと思いますか？

4

3 に答える 3

3

最初の例では、N を 2 倍にすると、あと何回の操作が実行されるでしょうか?

于 2010-10-17T13:08:17.723 に答える
2

最初のものは、複雑度クラス O(log2(n)) を持ちます。これは、n を 2 倍にすると、もう 1 つの演算が追加されるだけだからです。

2 つ目は O((n^2)/2)、または単に O(n^2) です。これを理解する最も簡単な方法は、それを形として想像することです。2 つの for ループがあるため、最終的な複雑さは n^2 であることがわかりますが、最初のループが続くと、2 番目のループはゼロに減少します。これにより、効果的に三角形が作成されます。

于 2010-10-17T13:15:33.333 に答える
1

あなたは2番目のものについて正しいです。1 つ目は O(logN)、2 つ目は O(N^2) です。しかし、1つしかありません。あなたが言及しているものirrelevant statementは非常に関連性があるかもしれません。そのステートメントが、たとえば O(N) で機能する関数呼び出しである場合、複雑さはそれぞれ O(N*logN) と O(N^3) になります。irrelevant statementしたがって、が O(1)の場合は正しいです。

于 2010-10-17T13:14:59.720 に答える