ハッシュテーブルは を実現する、夢のような方法です。 の数式の中には n がありません。つまり、どんなにデータ量が増えたとしても速度がほとんど変わらないということです。それを実現するために、力まかせ探索や二分探索のように「違ったら次を探す」では…

力まかせ探索は でした。二分探索（バイナリサーチ）は です。クイックソートは でしたが、「半分、また半分」のときにlog nが登場します。二分探索も「半分、また半分」です。 詳しい説明はwikipediaで。力まかせ探索と違い、二分探索はソート済みであるこ…

何かを検索するプログラムを書く場合に、一番簡単かつ分かりやすい方法が「力まかせ探索」とか呼ばれる方法です。「力まかせ探索」はどちらかといえば通称で、正確には名称は存在しないかもしれません。データベースではフルスキャンと呼ばれます。 $val) {…

エラトステネスのふるいとは、素数を見つけ出すための方法です。解説はwikipediaにおまかせです。wikipediaのgif動画はすごいですね。

最速とされているクイックソートの計算量は ですが、分布数え上げソートは です。その速さはクイックソートを上回ります。

計算量とは、アルゴリズムの速さの目安になるものです。入力データの個数をnとしたときの処理回数を大雑把に表します。 先のバブルソートだと 、クイックソートだと と書きます。第１回のデータは $input = array(5, 2, 4, 3, 4, 8, 7, 2, 1); だったので、n…

クイックソートはPHPに限らずいろんな言語でライブラリとして実装されており、例えばC言語ではqsort()として標準ライブラリとして用意されています。 その名の通り「速いソート」で、実装時の工夫等もあり汎用ソートアルゴリズムとしては最速とされています…

10番煎じぐらいな気がしなくもないですが、PHPでアルゴリズムのお勉強です。 初回はおなじみバブルソート。バブルソートそのものの解説はwikipediaでどうぞ。 0; $n--) { // $n はソート対象範囲の最大 for ($i = 0; $i < $n; $i++) { // $i はソートのポイ…