3

私は最近、友人が就職の面接で見た質問を解決するために私に挑戦してもらいました。

N個の要素がk個の配列に分割されます。（k log N）時間で要素のいずれかが同一であるかどうかを返すアルゴリズムを見つけます。

答えを出さないでください、私は本当にそれを自分で解決したいと思います。

私が持っている質問は次のとおりです。私のアルゴリズムの複雑さをテストするためのregexpalに似たWebサイトはありますか？そうでない場合、誰かが実際に複雑さを見つける方法について何か提案がありますか？

私は一般的な考えを持っていますが、私が最後にこのような問題を試みてからしばらく経ちました。

編集：これに追加する新しい質問。KLogNはNlogNとどのように比較されますか。明らかに、Kが1の場合、それはlog Nであり、O（n）よりも効率的ですが、K> = nの場合、N log Nよりもさらに悪いですよね？

4

2 に答える 2

2

通常、アルゴリズムの複雑さは、推論と数学的証明によってわかります。一部のデータでアルゴリズムを実行しても、真の複雑さ（BigOhまたはTheta）は得られません。提供されたデータの見積もりが得られるだけです。

たとえば、クイックソートは平均的 BigOh n log nですが最悪の場合BigOh n^2、悪いピボットを選択した場合に最悪のケースが発生します。

あなたは自分で最悪のケースを理解し、私が恐れている分析を行う必要があります。分析を行うためのヘルプ（またはリマインダー）が必要な場合は、米国の主要大学のコンピューターサイエンスカテゴリにあるYouTubeまたはiTunesU（たとえば、MITのアルゴリズム入門）を参照してください。

于 2012-11-13T18:18:59.587 に答える
1

編集：これに追加する新しい質問。KLogNはNlogNとどのように比較されますか。明らかに、Kが1の場合、それはlog Nであり、O（n）よりも効率的ですが、K> = nの場合、N log Nよりもさらに悪いですよね？

編集に答えるには、k <nの場合はklognアルゴリズムを使用し、n<kの場合はnlognアルゴリズムを使用できます。

于 2012-11-13T19:37:44.310 に答える