アカウント名:
パスワード:
いろいろなアルゴリズムや技術の名前は知っているのだけれど、それをブラックボックスとしてしか理解していない人が驚くほどいるんですよね。
最悪計算量が O(n^2) とかいう話？
アルゴリズムの話なのだから、当然これですね。 Quick Sort の最良値が O( N * log N ) になるのは、理解できると思う。で、最悪値が O( N^2 ) になるのも(書き込んでいるぐらいだから)理解できると思う。と言う事は、このアルゴリズムはこの2つの間のどこかの計算量になり、どうなるかは「与えられたデータに強く依存する」と言う事だ。 Quick Sort は決して O( N * log N ) のアルゴリズムではない。単に「係数」部が非常に軽いので、O( N * log N )である事が保証されている他のアルゴリズムを、平均値では追い抜いているのに過ぎない。最悪値比較をすれば、O( N * log N )が保
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
アレゲはアレゲを呼ぶ -- ある傍観者
車輪の再発明をさせろ (スコア:4, すばらしい洞察)
ライブラリが無い環境でどうしていいか分からなくなる。
コードは書けるけど、アルゴリズムが無いと何もできない子になる。
一度Cとかのなにもない環境でやらせないとダメ。
無いものは作るというハングリー精神が無くなる。
#最近はPythonでしか書いてないなぁ…
#10行でWebサーバが書けるのには感動。
Re: (スコア:3, 興味深い)
学生の雇用面接（@US）をすると、いろいろなアルゴリズムや技術の名前は知っているのだけれど、それをブラックボックスとしてしか理解していない人が驚くほどいるんですよね。ちょっと話すと色々知っているし、レジュメを見てもいろんなものを作っているように見える。でもちょっと掘り下げるとすぐに馬脚を表して、がっかり。そういう人は確かに典型的に Java, そして perl や Python 止まりで C はできるけれどそれほど得意じゃない。そういう感じ。最近立て続けに、The Perils of JavaSchools [joelonsoftware.com] とNYUの先生の記事を読んで、なるほどそういう背景があったのか、ポンっと膝を叩く気分でした。
こっちの期待しているのは車の運転の仕方を知っている人ではなくて、車を作れる人なんだけどな。
Re: (スコア:2, 興味深い)
私が面接をした範囲では、quick sort を O( N * log N ) のアルゴリズムだと思い込んでいる、と言うあたりが馬脚の基本ですね。
# 逆にそこをつついてくる面接を受けた事もあります。
# 多分、あそこの面接官は本当に技術力があったんだろうな。
fjの教祖様
Re: (スコア:1)
最悪計算量が O(n^2) とかいう話？
それとも，ピボット選択がどうとか，分割後の要素数が閾値以下になったらとか実装に関わる話？
はたまた，並列計算で O(log n) に近づけられるとかそういうこと？
Re: (スコア:3, 参考になる)
アルゴリズムの話なのだから、当然これですね。
Quick Sort の最良値が O( N * log N ) になるのは、理解できると思う。
で、最悪値が O( N^2 ) になるのも(書き込んでいるぐらいだから)理解できると思う。
と言う事は、このアルゴリズムはこの2つの間のどこかの計算量になり、どうなるかは「与えられたデータに強く依存する」と言う事だ。
Quick Sort は決して O( N * log N ) のアルゴリズムではない。単に「係数」部が非常に軽いので、O( N * log N )である事が保証されている他のアルゴリズムを、平均値では追い抜いているのに過ぎない。最悪値比較をすれば、O( N * log N )が保
fjの教祖様
Re: (スコア:1)
ああ，なるほど．単純に (n * log n) を n で割ってしまいました．
よく考えたら，仮に「データを分配する」処理を無視できたとしても，
(※ 計算開始時に既にデータが無限個の計算ノードに分散しているなど)
計算量 O(log n) にはならないですね．
再帰回数 O(log n) は並列化しても減りそうにないので，
再帰 1 回当たりの計算量を O(1) にしなければ全体の計算量 O(log n) にならないが，
全ノードへのブロードキャスト O(log n) などの操作が含まれているだけでアウトですからね…．
> # と言うわけで、O(N)を切るソート方式はありえないのだよ。
最初から昇順に並んだデータに対し，
隣接要素を 1 個ずつ比較して結果がソートされているか確かめる，
というだけでも O(n) 必要ですね．
Re:車輪の再発明をさせろ (スコア:0)
>というだけでも O(n) 必要ですね．
比較するという手段が必須であれば、の話。
比較しないソート方法に対しては、その前提は崩れる。
#まあそれが汎用的かと言われればなかなか‥。
Re:車輪の再発明をさせろ (スコア:1)
(与えられたデータの各要素が大小関係の二分木のどこに属するかを決める必要があるから)
比較に基づかないビンソートや基数ソートなどでも O(n) は切らないですよね？
O(n) の前提が崩れるっていうのは近似アルゴリズムの話ですか？
Re:車輪の再発明をさせろ (スコア:1)
> 比較するという手段が必須であれば、の話。
比較しなくてもデータを読むだけでO(n)必要なので...。
O(n)より速くするには最初からソートされたデータ構造(二分検索ツリ、AVLツリー、RBツリー)を使えば良い訳です。時間のかかることは出来るだけしないようにする。部分を速くするよりも、それを使わなくする、という大局的な視点で見るのも重要。そのためにはプロファイリングが重要。
Best regards, でぃーすけ