バブルソートはせいぜい O(n) 、最悪 O(n^2) で、メモリ使用量は O(1) です。マージソートは常に O(n log n) ですが、メモリ使用量は O(n) です。配列の長さが 1000 未満であると仮定して、整数の配列を取り、コレクション内の最大整数を返す関数を実装するために使用するアルゴリズムを説明してください。配列の長さが 1000 より大きい場合はどうなりますか?
2555 次
3 に答える
3
最も簡単な方法は、配列をトラバースし、移動しながら最大のものを追跡することです。これにはO(N)時間がかかります。したがって、ソートアルゴリズムも使用する必要はありません。
于 2013-10-04T19:08:01.817 に答える
2
ない。
アイテムをループして、見つけた最大値を追跡するだけです。これは O(n) ソリューションです。
于 2013-10-04T19:08:31.023 に答える
0
バブル ソートは平均的です。つまり、使用することをお勧めする場合はほとんどありません。O(n2)
マージソートは常にO(n log n).
したがって、これら 2 つの選択肢の中では、マージソートが望ましいです。
並べ替えには他にもたくさんの選択肢があります。数値データ専用のものもあります。
ただし、最大要素を見つけるためだけにソートする必要はありません。単純に整数を反復処理して最大値を追跡することができます。
于 2013-10-04T19:08:31.447 に答える