Q

文字列をソートするのはなぜですか（n log n）？

2010-12-13 2 views 7 likes

7

可能性の重複：それは、文字列をソートすると、プログラミングのパズルへの答えで
Plain English explanation of Big O 文字列をソートするのはなぜですか（n log n）？

はO（n個のnを記録）時間がかかります。これはどのようにして得られますか？

誰もがBig Oリソースの参照リンクを持っていますか？

おかげ

2010-12-13 Percy Flarge

+0

「文字列の並べ替え」はどういう意味ですか？あなたは文字列のリストをソートすることを意味しますか？ – jjnguy

+0

文字列内の文字を並べ替えることもできます。 –

+1

文字列内のソート文字。私はbig Oが何であるかを知っています。なぜ文字列内の文字を並べ替えるのがなぜn log nなのか分かりません。 –

A

答えて

1

定義とビッグOのいくつかの例は、例えば、検索エンジンを使用して求めることができますここでは一緒に必要な比較の数に下限の説明と

http://en.wikipedia.org/wiki/Big_O_notation

要素を比較することに基づいてソートアルゴリズムの説明は、ここで見つけることができる：

http://en.wikipedia.org/wiki/Comparison_sort

2010-12-13 22:06:38

10

文字列をソートするのはなぜですか（n log n）？

文字列内の文字のソートは、必ずしもO（n log n）である必要はありません。

Oは（N Nログ）comparison sortため最適値です。また、多くの言語のデフォルトソート実装の複雑さです。しかし、これより確実に悪いことは可能です。文字列内の文字の並べ替えの複雑さは、このタスクを解決するために選択した特定のアルゴリズムによって異なります。
場合によっては、比較ソートではないソートアルゴリズムを使用することによって、O（n log n）より優れた処理を行うこともできます。たとえば、最大127文字のASCII文字列があることがわかっている場合は、O（n）のcounting sortを使用できます。カウントソートは、すべての文字がBasic Multilingual PlaneにあるUnicode文字列に対しても実行可能です。

2010-12-13 22:13:12

関連する問題