2

挿入ソートを使用してソートしたい3つの異なるキー（、、および）TRUEのみFALSEを含む30個の要素のランダムな順序の配列があります。NULL時間計算量はどうなりますか？キーが3つしかないため、最悪の場合を想定した場合はO（n 2 ）になりますか、それとも最良の場合を想定した場合はO（n）になりますか？

4

1 に答える 1

2

nは配列のサイズを指し、配列の可能な要素ではありません。したがって、複雑さは同じです。

  • 最悪の場合：O（n 2）
  • ベストケース：O（n）
  • 平均的な場合：O（n 2）

3つの異なる要素があると、「挿入」フェーズ中にチェックする必要のある要素の量が減りますが、一定の係数だけです。これにより、漸近ランタイムは変更されません。

たとえば、平均的なケースでは、n個の要素を挿入チェックする代わりに、n /3個の要素をチェックします。これは優れていますが、漸近的ではありません。

于 2012-04-17T00:00:14.630 に答える