4

次のコードがある場合：

IterateArray(object[] array)
{
    for(int i=0; i<array.length; i++)
    {
        Dosomething(array[i]);
    }
}

メソッドのDosomething(object)時間パフォーマンスはO（log n）ですが、IterateArrayO（n）またはO（n log n）の全体的なパフォーマンスはありますか？

4

5 に答える 5

14

短くてやや間違った答えは O(n log n) です。

長い答え: O(n log m )と書く方が正確です。

DoSomething が実際に配列全体に依存しない限り、単一の要素で動作しているように見えます。したがって、「m」を使用して、これを個別に区別します。

于 2009-07-09T19:55:41.277 に答える
12

O（n log n）になります

O（log n）パフォーマンス操作をn回実行しており、Big Oで乗算が保持されるため、O（n）* O（log n）= O（n log n）

2つの異なるサイズの配列を表示している場合は、mとnを区別する必要がないことに注意してください。その理由は、mとnは両方とも定数であり、それらの成長率をグラフ化すると、それらは漸近的に同等であるためです。

于 2009-07-09T19:51:25.233 に答える
10

O( n log n )

考えてみてください。ログ n 操作を n 回実行しています。

于 2009-07-09T19:51:45.387 に答える
4

m オブジェクトごとに、DoSomething() のパフォーマンスが O(log n) の場合、m オブジェクトすべての合計パフォーマンスは O(m log n) になります。

于 2009-07-09T19:54:00.220 に答える
1

「for」ループは n (配列の長さが n とします) 回反復し、各反復で「Dosomething」が実行されるため、全体的なパフォーマンスは O(n logn) になります。

乾杯

于 2009-07-09T19:53:33.123 に答える