Clever Geek Handbook

最悪の堎合、O1の远加メモリを䜿甚しお、Onlogn時間で単方向リンクリストで゜ヌトしたす。

すべおは、gamedev.ru Webサむトのこのトピックから始たりたした。 Topikstarterは、次のプロパティを持぀゜ヌトを芋぀けるこずを提案したした。

  1. ランタむム-保蚌Onlogn。
  2. O1远加メモリを䜿甚したす。
  3. 単䞀リンクリストのデヌタの䞊べ替えの適甚可胜性ただし、これに限定されたせん。


3぀の制限すべおの予玄

  1. 保蚌されたOnlognは、たずえば、クむック゜ヌトの平均時間が適切でないこずを意味したす。Onlognは、最悪の入力であっおも取埗する必芁がありたす。
  2. 再垰は、再垰呌び出しのスタックを栌玍するためのOlognメモリを意味するため、䜿甚できたせん。
  3. ゜ヌトされた配列の芁玠ぞの任意のアクセスはありたせん。むテレヌタを任意の芁玠から隣接する芁玠O1を超えるにのみ移動し、䞀方向リストの前方にのみ移動できたす。 リスト自䜓を倉曎するこずはできたせん次の芁玠ぞのポむンタを䞊回るため。


配列の芁玠に぀いお知っおいるすべおの情報は、それらがすべお線圢に順序付けられたセットを圢成するずいうこずです。 できるこずは、配列の2぀の芁玠を比范しO1の堎合、それらを亀換するこずですO1の堎合も。



カットの䞋で、私たちに䜕が起こったのかを知るこずができたす。



挑戊する 猫の䞋を芋る前に、たずアルゎリズムに぀いお自分で考えるこずをお勧めしたす。 あなたが私たちのオプションよりもクヌルな䜕かを思い぀いたら-コメントを曞いおください。





ご予玄



蚘事を培底的に怜玢しなかったこずを予玄したす-すでに既知のアルゎリズムを再床開いたか、この問題を解決するアルゎリズムが長い間知られおいたすおそらく私たちよりもはるかに効果的です。



私たちのアルゎリズムの実甚的な応甚はほずんど䞍可胜であり、タスクは孊術的な関心のより倚くのものです。



情報収集



すぐに頭に浮かぶ既知の皮類は、3぀のポむントすべおを同時に満たすわけではありたせん。次に䟋を瀺したす。





䞭倮倀たたはBFPRTアルゎリズムの䞭倮倀



最初のコメントでは、FordPerfectの友人がMedian of Mediansアルゎリズムを提案したしたが、これは広く知られおいたせんでした。 圌の別の名前は、それを発明した科孊者の名前に由来するBFPRTです。マヌ゚ルBラム、ロバヌトW.フロむド、りォンプラット、ロナルドL.リベスト、ロバヌトE. Tアリアン。 アルゎリズムはWikipedia ru 、 en 、およびKormenで説明されおいたすが、Wikipediaではロシア語ず英語版を比范しお初めおその本質を理解できるほど䞍噚甚であるため、少し説明したす 元の蚘事も調べなければなりたせんでした  そしお、Habréでの圌の説明はただありたせんでした。 コヌメンでは、どちらかずいえば説明は正垞ですが、埌でこのアルゎリズムが存圚するこずがわかりたした。 このアルゎリズムを既に知っおいる堎合は、この蚘事の䞀郚をスキップできたす。



Median of Mediansアルゎリズムにより、最悪の堎合、線圢時間で任意の配列のk番目の順序統蚈を芋぀けるこずができたす。 C ++ STLラむブラリには、同様のアルゎリズムstd :: nth_elementがありたす。これは、Quickselectアルゎリズムに基づいおいるため、線圢時間のk番目の順序統蚈も怜出したす。 埌者は基本的にクむック゜ヌトで、各ステップで再垰の分岐を1぀だけ䞋っおいきたすQuickselectの詳现に぀いおは、 こちらずこちらをご芧ください 。 Median of Mediansは、Quickselectアルゎリズムの修正であり、「分岐」の悪い芁玠を遞択するこずはできたせん。最悪の堎合、二乗時間になりたす。



なぜ䞭倮倀の䞭倮倀が必芁なのですか はい、すべおが非垞に単玔です-その助けを借りお、線圢時間で配列の䞭倮倀n / 2次統蚈を芋぀け、この芁玠で高速゜ヌトアルゎリズムを分岐するこずが可胜です。 これにより、Onlognに察しお平均ではなく、最悪の堎合にクむック゜ヌトが機胜したす。



Medians of Mediansアルゎリズムの説明。 入力デヌタ配列たずえば、リストの最初ず最埌の芁玠で指定されるず数倀k-どのアカりント芁玠を芋぀ける必芁があるか。

  1. 配列が十分に小さい堎合5芁玠未満-おでこで泡で゜ヌトし、k番目の芁玠を返したす。
  2. 配列のすべおの芁玠を5぀の芁玠のブロックに分割したす。 䞍完党な最終ブロックの可胜性に泚意を払っおいたせん。
  3. 各ブロックでは、芁玠をバブルで䞊べ替えたす。
  4. 各ブロックの䞭倮3番目の芁玠からサブアレむを遞択したす。 単玔に配列の先頭に移動できたす。
  5. これらの[n / 5]芁玠の䞭倮倀の䞭倮倀を再垰的に起動し、それらの䞭倮倀n / 10番目の芁玠を芋぀けたす。 この芁玠はピボット芁玠ず呌ばれたす。
  6. おそらく、クむック゜ヌトずクむックセレクトアルゎリズムでよく知られおいる分離手順を実行しおいたす。参照芁玠よりも小さい芁玠をすべお配列の先頭に移動し、すべおの芁玠を末尟に移動したす。 配列の最埌にある可胜性のある䞍完党なブロックの芁玠も考慮されたす。 合蚈で、3぀のブロックが埗られたす。芁玠は、基本よりも小さく、それず同等であり、それ以䞊です。
  7. どのブロックでk番目の芁玠を探す必芁があるかを決定したす。 2番目のブロックにある堎合、そこから任意の芁玠を返したすすべお同じです。 そうでない堎合、芁玠番号を修正できるこのブロックの䞭倮倀の䞭倮倀を再垰的に起動したす。3番目のブロックでは、番号kから前のブロックの長さを枛算する必芁がありたす。




ここで䜕が起こっおいるかの䟋を芋おみたしょう。 配列があり、その䞭倮倀を芋぀けたいずしたしょう







1から27たでの27の異なる番号がありたす。連続しお14番目の芁玠を探しおいたす。 芁玠を長さ5のブロックに分割し、各ブロック内の数字を䞊べ替えたす。







各ブロックの䞭倮倀は黄色で匷調衚瀺されたす。 それらを配列の先頭に移動し、アルゎリズムを再垰的に実行しお、その䞭の䞭倮倀を怜玢したす。







再垰の内郚で䜕が起こるかを曞き留めたせん。1぀はっきりしおいるこずは、12が望たしい䞭倮倀になるこずです。







この数倀12-䞭倮倀の支持芁玠たたは䞭倮倀-は、次の顕著な特性を持っおいたす。 数枚の写真に戻っお、次のようにブロックを粟神的に動かしおみたしょう。







すべおの列は䞭倮の芁玠で゜ヌトされ、さらに各列の芁玠も゜ヌトされたす。 支持芁玠の巊䞊にある芁玠の玄30正確には3 / 10n + O1は、それより倧きくないこずがわかりたす。 同様に、サポヌト芁玠の右䞋にある芁玠の玄30に぀いおは、それ以䞊です。 ぀たり、分離手順を実行するず、すべおの芁玠の玄30が必然的に支持芁玠の巊偎に、玄30が右偎になりたす。







実際、わずかな䞍正確さがありたす。幞運なこずに、参照芁玠に等しい芁玠が1぀だけ存圚するずいう事実がありたした。 そのような芁玠が倚数ある堎合、それらはすべおブロック党䜓を圢成し、サポヌト芁玠が正確にどこに収たるかは明確ではありたせん。 しかし、それは本圓に重芁ではありたせん。 支持芁玠以䞊の芁玠は少なくずも30であるこずがわかっおいたす。぀たり、支持芁玠より厳密に小さい芁玠は70以䞋です。 同様に、サポヌト芁玠よりも厳密に倧きい芁玠も70以䞋です。 したがっお、䞊蚘のアルゎリズムの説明からの最初ず3番目のブロックのサむズは、垞に7 / 10n + O1以䞋の長さを持ちたす







䟋の分析を続けたす。 分離手順の埌、14番目の芁玠が3番目のブロックにあるこずが明らかになるため、そのアルゎリズム党䜓を再垰的に実行したすが、珟圚は2番目の芁玠を探しおいたす。



アルゎリズムの耇雑さは䜕ですか



Tnを、長さnの配列に察するMedian of Mediansアルゎリズムの最悪の堎合の数挔算ずしたす。 各ステップで、アルゎリズムは自身を2回再垰的に2回呌び出したす。 最初は、長さがn / 5 + O1個の芁玠の配列で䞭倮倀の䞭倮倀を芋぀けるこずです。 2回目-探玢空間を瞮小したすが、最悪の堎合、配列のサむズは7 / 10n + O1に枛少したす。 他のすべおの操䜜には線圢時間が必芁です。 合蚈は比率を取埗したす



Tn= T2 / 10n+ T7 / 10n+ Cn、ここでCは定数です。



この関係を拡匵したしょう。



Tn= Cn + 2/10 + 7/10 Cn + 2/10 + 7/10  2/10 + 7/10 Cn + ... = Cn * ∑ i =0..∞  9/10 i = 10Cn = On



いいね アルゎリズムには線圢の耇雑さがありたす



Median of Mediansは、再垰を䜿甚しおリストに簡単に実装できたす。これにより、Olognメモリを䜿甚した単䞀リンクリストでのOnlognの䞊べ替えが保蚌されたす。



コヌド



ここで再垰を取り陀きたしょう。



フラットクむック゜ヌト



始めるために、実際にはクむック゜ヌトから再垰を削陀したしょう。 これを行う方法は完党に明らかではないため、このセクションではその方法を説明したす。



このセクションでは、Comdade FordPerfectがgamedev.ruフォヌラムで提案したアむデアに぀いお説明したす実際、この蚘事のすべおのアむデアは私のものではありたせん-ちょうど投皿したした。 アむデアの出所は䞍明で、Googleはほずんどの郚分で沈黙し、スタックがかなり頻繁に゚ミュレヌトされるいわゆる反埩クむック゜ヌトぞの倚くのリンクを提䟛したすただし、同様のアむデアの議論がありたした。 「O1メモリを備えたクむック゜ヌト」タスクに぀いお考える時間。 「Flat quick sort」ずいう名前も自䜜です。おそらく、このアルゎリズムは別の名前で知られおいたす。



通垞の再垰クむック゜ヌトがどのように機胜するかを思い出したしょう。 入力デヌタたずえば、単玔に接続されたリストの開始芁玠ず終了芁玠の2぀の反埩子によっお指定される配列。

  1. 1぀のパスをチェックむンしたす。配列が既に゜ヌトされおいる堎合、実行するこずはありたせん-終了したす。
  2. 分離手順の芁玠ピボットを遞択したす-通垞はランダムですが、この堎合は、Median of Mediansアルゎリズムを䜿甚しお䞭倮倀を遞択したす。
  3. 分離手順を䜜成したす-3぀のブロックを取埗したす。ピボットよりも小さい芁玠。 圌に等しい芁玠; 芁玠が倧きくなりたす。
  4. 最初ず3番目のブロックに察しお再垰的にクむック゜ヌトを実行したす。




再垰䞭に芚えおおく必芁がある情報は、3番目のブロックの始たりず終わりです。



次のこずに泚意しおください。最初のブロックの芁玠は2番目のブロックの芁玠よりも小さく、2番目のブロックの芁玠は3番目のブロックの芁玠よりも小さくなりたす。



考え方は次のずおりです。各ブロックの最倧芁玠をブロックの先頭に移動したしょう。 その埌、次のブロックがどこから始たるかを明確に決定できたす これを行うには、ブロックの先頭から厳密に倧きい芁玠に出䌚うたで移動したす。次のブロックの先頭を通知したす



これで、クむック゜ヌトアルゎリズムを次のように曞き換えるこずができたす。

  1. ポむンタヌXずYを䜜成したす。ポむンタヌXが配列の先頭を指し、ポむンタヌYがその末尟を指すようにしたす。 たた、珟圚のブロックの終わりを指すポむンタヌZを䜜成したす。 最初は、Z = Yです。
  2. 次のアクションを際限なく実行したす。
    1. 珟圚のXZブロックが既に゜ヌトされおいる堎合、次のブロックを探したす。 XをZに続く芁玠に移動したす。Xを移動できない堎合、Z = Yであるため、ルヌプを終了したす。 ここで、Xが指す芁玠よりも倧きい、Xの埌の最も近い芁玠aを探したす。ない堎合は、Z = Yを実行したす。
    2. クむック゜ヌトの通垞のアクションを実行したす。分離する芁玠の遞択ず分離自䜓です。 3぀のブロックを取埗したす。
    3. 3番目のブロックのブロック化を行いたす。その䞭の最倧芁玠を探しお、先頭に移動したす。
    4. Zを最初のブロックの最埌に移動したす。




次に、䟋を䜿甚しおこのアルゎリズムを怜蚎したす。







私はすでにこの配列を芋たした...ポむンタヌX、Y、Zを入れたしょう







XZブロックは゜ヌトされたせん。 次に、䞭倮倀を芋぀けたす。







䞭倮倀怜玢手順は、最も奇劙な方法で芁玠をシャッフルし、䞭倮倀自䜓を最初に残すず仮定したす䟋ずしお、実装は、䞭倮倀である芁玠に反埩子を返す堎合がありたす。 では、分離手順を実行したしょう。







それは3ブロックになりたした。 最埌のブロックをブロックし、Zを最初のブロックの最埌に移動したす。







今、私たちは最初から始めたす。 珟圚のXZブロックは゜ヌトされおいないため、その䞭の䞭倮倀を探しおいたす。







分離手順を実行したす。







3番目のブロックをブロックし、Zを最初のブロックの最埌に移動したす。







もう䞀床、XZを芋おください。







ラッキヌです ブロックは゜ヌトされおいるため、そのたたにしお次のブロックを探すこずができたす。 ポむンタヌXずZは次のように移動したす。







これは前のステップの2番目のブロックであるため、突然、このブロックも゜ヌトされたす。 次のブロックを探しおいたす







泚文を確認したす-残念ながら、今回は幞運ではなかったので、手配する必芁がありたす。 䞭倮倀を芋぀けおから、分離手順を実行したす。











次に、ブロック[8,9]に移動し、゜ヌトされたす。そのため、XずZはブロック[10]に移動し、これも゜ヌトされたす。その埌、アルゎリズムはブロック[13、11、12]を考慮したす。 。 アレむの埌半の゜ヌト分析は、読者が個別に実行するこずを提案したす。



コヌド



O1の远加メモリを備えた䞭倮倀のおおよその䞭倮倀



残念ながら、Median of Mediansでは、最倧芁玠を䜿甚しおフラットクむック゜ヌトでブロックを識別するなどのトリックは機胜したせん。これは、毎回配列の芁玠が䞍明確に混圚しおいるためです。 ここでは、別のフォヌカスを䜿甚したす。



実際、保蚌されたOnlognに察しお迅速な゜ヌトを実行するために、分離段階の正確な䞭倮倀を芋぀ける必芁はありたせん。 近䌌倀を芋぀けるだけで十分です。 特定のC <1に぀いお、分離段階埌の最初ず3番目のブロックがCnを超えないこずを保蚌する堎合、Onlognのクむック゜ヌトが機胜したす。 C = 0.99でも。 激しい狂気の隠された定数であるが、Onlogn



したがっお、メディアンの䞭倮倀を倉曎しお、゚ラヌK = Olog 2 nの䞭倮倀を芋぀けたす。 ぀たり、シリアル番号がn / 2-K / 2〜n / 2 + K / 2の範囲にある芁玠が芋぀かりたす。 Kは察数の次数であるため、セグメント[n / 2-K / 2、n / 2 + K / 2]が存圚する具䜓的にはnを芋぀けるのは簡単です。たずえば、1 / 4nず3 / 4nの間です。 すべおの小さいnに぀いお、バブルだけで゜ヌトできたす。



なぜK = Olog 2 nですか はい、K配列芁玠を䜿甚しお、スタックに必芁なすべおの情報を栌玍したすこれもFordPerfectの仲間です。 再垰レベルはOlognであり、それぞれに぀いお、OlognビットごずにO1の数倀を栌玍する必芁がありたす。 そしお、残りのNK芁玠の䞭でクむック゜ヌトの䞭倮倀を芋぀けたす。



各ビットは、配列の2぀の連続する異なる芁玠によっお衚されたす。 それらの最初の倀が2番目の倀より小さい堎合、ビットは状態0を栌玍し、そうでない堎合は-1たたはその逆を栌玍したす。 解決する必芁がある最初のタスクは、配列の異なる芁玠のK / 2ペアを芋぀け、あたり倚くのペアが芋぀からない堎合の察凊方法を理解するこずです。



これは非垞に簡単です。 反埩子XずYが配列の最初の芁玠を指すようにしたす。 Xず等しくない芁玠が芋぀かるたでYを前方に移動したす。それが芋぀かったら、Xを前方に移動し、XずYが指す芁玠を亀換し、Xを前方に再床移動したす+小さい堎合を匕き続き凊理する必芁がある堎合-Yを前方に移動したすXに盎面した。 そしお、K / 2ペアが芋぀かるたで。 Yがすでに配列の終わりに達し、K / 2ペアがただ芋぀からない堎合はどうなりたすか これは、XからYたでのすべおの芁玠が同じであるこずを意味したす この䞍倉匏がアルゎリズム党䜓の実行䞭に保存されるこずを確認するのは非垞に簡単です。 次に、サポヌト芁玠ずしお、これらの芁玠の1぀をすぐに遞択できたす。 K <n / 2を遞択した堎合、このサポヌト芁玠は正確な䞭倮倀になりたす。



さお、質問は次のずおりです。スタックを操䜜するず、アルゎリズムの挞近的な動䜜が壊れたすか これは非垞に良い質問です。䞀芋するず、再垰ツリヌの頂点の順序はOnであり、各頂点に察しおスタックでOlog 2 n操䜜が必芁だず思われるためです。 Median of Mediansの挞近的挙動はOnlog 2 nおよびアルゎリズム党䜓のOnlog 3 nに悪化しおいたすか ここではすべおが少し耇雑です。



ツリヌ内の頂点の正確な数を蚈算するには、次の繰り返しを解決する必芁がありたす。



Nn= Nn / 5+ N7N / 10+ 1

n <Cの堎合、Nn= 1



䞊蚘ず䌌たようなものが芋られたすが、Cnを1に眮き換えるず、再垰の蚈算がやや​​難しくなりたす。 Acra-Bazzi方匏が助けになりたす。 再垰はすべおの条件に適合し、察応するすべおの順列の埌、頂点の数NnがOn 0.84 より正確にはΘn 0.839780 ... ずしお増加するこずがわかりたす 。 アルゎリズムの総時間耇雑床はOn + n 0.84 log 2 n= Onです。



アルゎリズムのこれ以䞊のスペルは䞍芁であるず考えおいたす。この蚘事の前の章のいずれかで説明されたものを実装するだけです。 コヌドをすぐに確認するこずをお勧めしたす。 画像もありたせん。アルゎリズムがたったく機胜しないためには、配列内にかなり倚くの芁玠が必芁です。 どっち 詳现に぀いおは、以䞋をご芧ください。



提案されたアルゎリズムはどの皋床非実甚的ですか 蚈算は次のずおりです。



実際の䞭倮倀から1 / 4n以䞋の偏差を取埗するずしたす぀たり、K <n / 2。 次に、3 [logn]再垰レベルでスタックをハンマヌで打぀必芁がありたすここで、logは2進数で、3/4 3 <0.5であり、[x]は数倀xを最も近い敎数に切り䞊げたす。 再垰レベルごずに2 [logn]ビットが必芁です。珟圚の配列の長さ、珟圚探しおいる芁玠この数は垞に[logn] -1ビットに収たりたすおよびトラバヌサルツリヌのトラバヌサル順序を維持するためのもう1ビットを栌玍する必芁がありたす必芁ですどの再垰分岐から戻ったかを思い出しおください。 各ビットには2぀の芁玠があり、スタックごずに合蚈12 [logn] 2぀の芁玠がありたす。



ここで方皋匏を解きたす12 [logn] 2 <n / 2たたは24 [logn] 2 <n。 nを芋぀ける必芁がありたすn> = nの堎合24 [logn] 2 <n。 このn 'は3500のオヌダヌです。぀たり、n <3500の堎合、バブルで゜ヌトする必芁がありたす。



Kが垞にn-1500を超えないnの制限、぀たり、n <1500の堎合、゜ヌトは機胜したせんスタックを゚ミュレヌトするのに十分な芁玠がありたせん。ここではためらうこずなくバブルを䜿甚する必芁がありたす。 ただし、定数をいじるず、おそらくこの掚定倀は改善される可胜性がありたす。



コヌド



コヌド



蚘事党䜓のコヌドぞのすべおのリンクを1か所で





読む



  1. gamedev.ru のアルゎリズムの説明。
  2. りィキペディアのメディアンの䞭倮倀 en 、 ru 。
  3. Quickselectに぀いおは、 こちらずこちらをご芧ください 。
  4. りィキペディアのAcra-Bazziメ゜ッド 。
  5. Manual Blum、Robert W. Floyd、Vaughan Pratt、Ronald L. Rivest、およびRobert E. Tarjan。 遞択の時間範囲 。 pdf、eng
  6. S.バッティアト、D。カントン、D。カタラノ、G。シンコッティ。 近䌌䞭倮倀遞択問題の効率的アルゎリズム 。 pdf、eng-高速の近䌌確率的䞭倮倀䞭倮倀


More articles:


All Articles