Searchは強力でソート済みでない配列に対して適用することも可能である。それどころか、対象が離散的な値である必要すら無い。分割統治(Divide-and-conquer)はそれに良く似た手法で、対象を再帰的に半分にしてく手法である。今回はランダムに数値が並んだ配列の中で、それらの数値の取りうる範囲が指定されており、その範囲の中で一つだけ数値が欠けていて、その欠けている数値を探し出す問題を考える。範囲が1〜10で配列の長さは9であり、配列の中の数値に重複は無い場合である。直感的に考えると配列をソートして一つずつ順に数値を見ていけば良い。数値が欠けていればインデックスとの対応が合わないはずだ。これは最速でもO(Nlog(N))かかることになる。詳しく言えば、ソートしてから一つずつ配列を見ていくので、最悪の場合はO(Nlog(N)+N)になるだろう。このような問題は分割統治を使ってもっと速くできる。Searchのようにインデックスをlow,highとして扱うような使い方では解けないため、ここは配列のサイズを1/2ずつに分割していく方法を組み合わせる。mid=5として初期設定し、midより大きい配列、小さい配列、に分ける。欠けている場合は、配列が期待するサイズよりも小さいはずなので、lowかhighにmidを設定し、そちらの配列を再帰的に検査していく。ここまで考えることができればO(Nlog(N))よりも速くできることが分かるだろう。ここに辿り着く前にこれがO(Nlog(N))よりも速くなる、ということに気付くのが難しい。実際には、midを元にサイズNの配列を作成するための走査が必要になるためO(N)になる。Searchを用いていることを実感したいならばもう少し詳しく考えて、N+N/2+N/4+...となるので初項=N、公比=1/2、の等比数列の和を求めると、N*(1-(1/2)^N)/1-(1/2)、となり、Nが十分大きければ(1/2)^N≒0となるためO(N)が導ける。O(Nlog(N))と比較するとすれば、log(N)の部分が定数になる(具体的には2になる)というところがパフォーマンスに影響する。この問題の解法は、例えば、k個の欠けている数値のうちの一つを探し出す、とか、k個の重複している数値のうちの一つを探し出すなどにも適用できる。配列をスクランブルした後、最後の要素を削除(配列のサイズをマイナス1)することによって、欠けている配列を作り出している。GitHubMBPでの実行結果。sec.$二つ目の問題は、配列の中で合計値が最大となる部分配列を発見する。配列の要素は整数なので、負の値も存在する。なる解法が存在するが、分割統治を利用した解法はO(NlogN)となる。1/2に分割しながら中央の値から左と右の部分配列の合計を計算し、最大となる部分配列を見つける。O(N)の解法の基礎となるアイデアは、配列の最初の要素から合計していくが、合計が負の値になったときはその次の要素を部分配列の最初の要素とする。やって部分配列を細切れにしながら合計の最大値を更新していくと、O(N)で、つまり一つのループで計算できる。GitHub出力としては、部分配列の最初のインデックス-[合計値]-部分配列の最後のインデックスとしている。Unicodeは文字集合である。仮想マシンのスタックとネットワークI/Oについて月別アーカイブ参加グループインターネットテクノロジープログラミングはてなブログをはじめよう!nishidyさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。