>> スピーカー：すべての権利、これはCS50である。
これを週に3回の終わりであり、もし すでに活用していないが、
ランチがあることを知っている ここで、いつものように今週の金曜日
あなたは良い会話を楽しむことができます 火と氷でと食品
CS50ののいくつかに スタッフとクラスメート。
ここにこのURLへのヘッド。
>> これでリコールすることや すぐに精通することができ、
ここではこれらの事、その 終了時に与えられている
多くのクラスのための学期。
におけるいわゆる受験青本、 あなたが試験にあなたの答えを書いてください。
今私はここにある26など それらのそれぞれの青色の書籍、
Zまで名前はAを書き込まれ、 確かに名前が単純な、Aということである
Zまでそして、もう一つの 手近な目標、今日
何を続けることになるだろう 私たちではありません月曜日、上で開始
とても多くのコードを見て、本当に アイデアや問題解決を見て。
目標の一つと このコースの約束
もっと考えすることを教えることです 慎重に、より念入りに、
より効率的な問題を解決する。
そして実際、私たちは本当にそれを行うことができます でも、コードの行を触れることなく。
だから私は、ゾウのカップルを持っている ここに今日、オレンジ、青、
私たちは1ボランティアを得ることができれば、 多分少し奥にいつもよりから。
どのようにすぐそこについては、下に来る。
の目標は、になるだろう ここで、この試験に役立つプラス管理する。
あなたの名前は？
>> 聴衆：メアリーベス。
スピーカー：メアリー·ベス、アップ時に来る。
私はあなたのためにここにマイクを取得しましょう​​。
よろしくね。
>> 聴衆：はじめまして。
スピーカー：すべての権利、私は持っている ここにブルーブックのAからZ、
そして私はそれをふりをするつもりだ 私は学生のいずれかを持って、
それらは幾分ランダムに入って来ている 3時間の試験ブロックの終わりに、
ので、いくつかで終わるいる このようなセミランダムな順序。
今だけの瞬間のあなたの仕事は、起こっている これは彼らが取得する方法実際にbe--する
の最後に中になって クラス、最も可能性が高い。
あなたの仕事は今非常に、あることを行っている 単純に、私たちのためにこれらの青い本をソートする
AからZまで
>> 聴衆：ああ、これは 永遠に連れて行く。
>> スピーカー：そして、私たちは見てます これを行うように、全くプレッシャーはありません。
聴衆：いや、いや、圧力か何か。
>> スピーカー：そして楽しみのために、 のタイマーを設置しましょう​​。
>> 聴衆：とても楽しい、とても楽しい。
>> スピーカー：私はあなたのためにマイクを保持することができます。
すべての権利、私たちは私たちの速度を倍増しました。
だからその間に、私は何のポーズましょう メアリーベスのための質問になるだろう
彼女がどのように、何をやっているされている 彼女はこれを解決するについて行く？
そして、実際に、あなたが持っていない可能性があり 今まで何かについて考えた
あなたが選ぶときと非常にシンプル このように26冊まで、
自然がありますかどの 彼らに注文する。
プロセスとは何ですか あなたが実際に使用するのか？
それだけでかなりランダムである あなたが見る最初のものを選ぶ
その場所にそれを置く？
あなたが最初に周りのあなたの手を動かしてください その後、Bを探して先をお探しですか？
あなたが見てみてください 並んでそれら一対のサイド
ちょうど、ちょっと待って、これを言う 右ではなく、その後の順序を入れ替える？
私たちは月曜日にすでに見ました いくつかの方法がありますことを
私たちはこれを行うことができる、と 確かに私たちはここで終わり近くなど、
私はおそらくノートを取る メアリーベスが何をしているかの。
私たちは、それはそう少数の山、持っている 3小さいもの、1より大きい。
>> 聴衆：私はそれらを注文してい 私は2つの文字を見つけたとき
私が知っている順序で一緒にしていること、 私はそうでないので、私はそれらを一緒に入れて
維持を心配する必要はあり 本の全体の行を追跡。
それは、Aが最初で、ああ、ちょうどだ 私はここで、このスタックを持っている。
スピーカー：だから、ほとんどのような パズルのピースこと
右の形状にしてい お互いに一致。
聴衆：かなり多く、うん。
スピーカー：OK、優れた。
そして今、これらの各 杭は、おそらくソートされて？
>> 聴衆：うん。
>> スピーカー：すべての権利、Z.すべてのAから 右、おめでとう、あなたはそれをやった。
あなたの選択肢があります。
ブルー？
すべての権利、それをありがとうございました。
だから、メアリーベスは提案しなかった 彼女のアプローチは何だった、
しかし、別のアプローチは、どのように何 これらのことを並べ替えて行くのでしょうか？
あなただったらどうしましたか？
ビートにレコードがあったであろう 1分50秒かそこら、
プラスのものは私が数えるのを忘れていました。
あなただったらどうしましたか？
うん？
聴衆：スタックを取る。
初めから開始します。
あなたの論文をチェックしてください。
そして一番上が高い場合 以上は、多分、それらは、ある
底ものである 高く、それらを切り替えてください。
>> スピーカー：そう、始まる 上部と下部に、
そして、あなたの方法を作業 内側に、それらを交換すること、そのような？
類似の[OK]を、これほど少ない バブルソートとその精神においては、
しかし両極端を選ぶ しない隣接する対。
しかし、それの短いがありますということです 確かに、さまざまな方法の束
私たちはこれを行うことができ、そして 率直に言って、私はちょっとあなたを思う
右、カップルのアプローチを採用した？
次の4つのソートされた杭のようなものを作り、 その後効果的にそれらを一緒にマージされた。
そして、それは、あえて言う、別の 完全な技術。
あなたは、一つの大きな山として扱っていなかった あなたは、4クワッドに問題を分割
あなたが説明し、その後何とか場合 最終的にはそれらを統合しました。
>> それでは、最終的には、考えてみましょう、 どのように他の私たちは、これを行うことがあります。
私たちは、概念を形式化 バブルソート前回、
とバブルソートのリコールだった 私たちは可視化されたアルゴリズム
ここまでクラスメートの8と、 一見ランダムに最初に選別した。
そして、私たちは、その後も、ペアごとに決定した 2つの要素は、順不同である
単にそれらを交換。
だから、4と2アール 明らかに故障して、
ので、これらの2クラスメート ポジションを入れ替え。
そして、私たちは4と6を用いて繰り返し、 その後6および8、それぞれの繰り返しで、
右に移動する。
>> だから、どのように多くのペアごとの8人に与えられた から歩きながら、私は比較をしましたか
そのような反復で左から右へ？
どのように多くの比較は？
セブン、右か？
そのため8があるかどう 人が、あなたはペアを持っている
彼らとあなたが動かし続ける 一方、右にホップ
あなたが8を持っているつもりはない 比較あなたは比較することはできませんので、
自身に対する要素、またはそれはだろ あなたは7を持っているので、単に、無意味であること。
またはより一般的には、もし 私たちは、n人を持って、私たち
nはマイナス1比較を行う バブルソートで。
>> それでは、今どのように良いか考えてみましょう 悪いバブルソート、実際にあった、とみてください
と自分自身の語彙を精製して、 これは、このようなアルゴリズムを批判するために、
そしてすぐに私たち自身。
を最初に通過だから バブルソート、初めて
私が渡って、左から右に歩い 舞台は、私のn - 1の比​​較を行った。
そして、それは私のことになるだろう 測定単位、右か？
私はこの種の話を散歩し、 やややや遅い、速い、
そう秒の私の数を数える 特に語っていないが、
しかしの数を数える 私は月曜日に行った操作を、
2人を比較し、それは感じている メジャーの素敵な単位を挙げることができる。
>> だから、nはマイナス1は、第1の時間ステップ、 が、その後何がその後起こったのですか？
ワンパスの1利点は何ですか それ以外の場合はソートされていないリストを？
あなたは何の要素について教えてくださいすることができます あそこのすべての方法は誰でしたか？
うん？
そう、最大の要素でしたか？
ナンバー8、でも彼女も 私は、ここに毎回開始
彼女に対して比較 隣人、彼女が保た
右まで泡立てる リストの右側。
そして実際、それはどこだ このアルゴリズムは、その名前を取得します。
>> 今、そのロジックによる、どのように多くの比較 私は2番目の時間に行う必要があります
私は、左から右に通過させる？
nはマイナス2、右か？
私はあればそれはちょうど私の時間を無駄にすることになる 誰かに対して8を比較しておく
他に、私たちはすでに知っているので、 彼女は正しい場所にいた。
だから少しです 最適化のため、次のパス
プラスnはマイナス2段階になるだろう、 ここで、nは、人の数である。
今、あなたはちょっとさえ、外挿することができます あなたはコンピュータ科学者いないのであれば、
これはどのように終了します。
このアルゴリズムの終了時に、おそらくは あなただけの1の比較左持っている。
あなたはちょっと修正する必要があり ケース2に、リストの先頭
一つは、順不同である と、1と2でなければなりません
これはで底に プラス1の最終比較。
>> さて、ドット、ドット、それはだ波のドット種類 ジューシーな詳細のいくつかを手に、
しかしちょうど先に行くと単純化しましょう​​。
あなたが高いから思い出して 学校、率直に言って、あなた方の多く
持っていた数学の本を持っていた 少しチートシート
前面カバーまたはオン お見せした背面カバー
どのシリーズのような和 これは、最終的に合算。
一般的なケースでは、あなたが持っている場合 nのような変数、そして実際にこれ、
あなたはあなたを見ている場合 古い学校の数学の本、
これが実際にあることを見るでしょう 、ここではこの合計につながります
n回nはマイナス1すべて2で割った。
だから、今の私にはちょうど明記しましょう これは、そのように信仰の飛躍に、真である
それが、これは合計何 まで、私たちは可能性
より一般的な場合にそれを証明する。
しかし、今のはこれを拡張してみましょう。
それはですのでそれでは、これを掛けてみましょう nの二乗、マイナスnは、すべてが2で割った。
それは、本当にだのn乗 マイナスnは2の上に、2で割った、
その結果は、すべて素晴らしく、興味深いです。
しかし、私たちとどうなる 今プラグイン値はありますか？
私は8を持​​っていなかったとします 人が、万人に言う。
そして、万人という理由だけで それはかなり大きな数だが、
のは、その中にプラグインして、何が起こるか見てみましょう。
だから私は、その数式に万人を接続した場合 私は、万人が乗取得するつもりだ
2で割った、マイナスA 百万ドルは、2で割った。
今等しくしようとしていることは何ですか？
だから5000億、マイナス50万。
そして、私は実際に行うかどう その数学アウト、その手段
その仕分け人 バブルソートを持つ人
私に4999.995億がかかる場合があります 最後のステップや比較、
私たちは外挿している。
>> これはかなり遅いと感じますが、率直に言って 1特定の入力を測定する
このように、すべてのことを語っていない。
しかし、確かに、それはnはそれを示唆していない ますます大きく、このアルゴリズムを取得します
ちょっと悪く感じ、 悪いことに、またはあなたが本当に
それの痛みを感じ始める べき乗、すなわちnは、乗
これはかなり急速に追加されます。
そして、このディテールではありません 実際には、人を失った
数年前、ある上院議員だった人 選挙運動、面接のために座っ
Googleのエリックと シュミット、当時の最高経営責任者（CEO）、
質問でチャレンジした 多くのように今日は模索しています。
それでは見てみましょう。
>> [ビデオ再生]
>> -Senator、あなたはここにいる グーグルで、私は好き
大統領を考えるために 就職の面接など。
今、それを得るのは難しい 社長としての仕事、
そしてあなたは今厳しさを通じてつもりだ。
それは、Googleの仕事を得ることも難しい。
私たちは、質問がある、と私たち 私たちの候補者の質問を、
この1つは、ラリー·シュワイマーからのものである。
あなたたちは、私は思うWhat-- 冗談、それはここです。
への最も効率的な方法は何ですか 万人の32ビット整数を並べ替える？
>> -Well--
>> 申し訳ありません-I'm、maybe--
>> いや、いや、 - いいえ。
私は、バブルソートを考える どこへ行くか、間違った方法だろう。
>> -COMe上、誰が彼にこれを言った？
私はコンピュータを見ていない あなたの背景の科学。
>> -We'veはそこに私たちのスパイを得た。
>> -OK、の異なる尋ねるみましょう 面接の質問。
>> [END VIDEO再生]
>> スピーカー：だからの話 しかし具体的な数値、
すべてのことに有用であることを行っていません。
それは、人生の教訓そのバブルではない ソート、万人の入力を与え、
できるだけ多く5000億などのステップがかかる場合があります。
あなたは本当に一般化することはできません あまりにも効果的とは
そして良いデザインの意思決定を行う プログラムを書くとき。
それでは、どのようにも注目しましょう 私たちは、この結果を単純化することがあります。
>> だから私はここに黄色で強調表示した n個の結果は、2で割った値の二乗
乗ので万人 2で除算し、次いで
私は何を強調してきた 究極の答えはあった
私たちはオフを差し引いた後、nは2で割った。
そして、私が今するつもりだ主張は、ある あなたがオフに引くかどうheckが気に誰が
2時第1オーバー少し古いのn この数式の一部はそんなに大きい？
これは、他を支配 この用語は、nは2で割った二乗
ように、明確に、そんなに大きい nは、万人のように大きくなる
それは本当にでは大きな差がある 5000億間の一日の終わりに
と4999.995億？
いまいち。
だから私たちがしようとしているもの コンピュータ科学者であるように行います
これらの低次の項を無視して、 このような何かを取り、実際に
単にそれを簡素化する 問題にはなるだろう言葉。
当社のデータセットが取得大きく、大きく 私達のデータベースは、複数のウェブページを取得する
私たちは、検索するより多くを持っている あなたがFacebook上で持っている友人。
>> nが大きくなると、私たちは本当にしている 最大の気にするつもりは
任意のそのような分析での用語 私たちのアルゴリズムの性能。
そして、私はあなたが何を知っている、と言うつもりです、 バブルソートは大きなOのオーダーである、
n個のオーダーで二乗。
それは、ちょうどnではありません 私たちが見てきたように乗、
誰が本当に気に これらのより小さな用語について、
と率直に言って、誰が本当に 私たちは2で割る場合に気に？
それはちょうど一定の係数です。
そして、250対5000億です 億契約の本当に大きい？
私はちょうど一年待つことができる、 文字通り私のラップトップを聞かせて
ハードウェアでの倍の速取得、 その差のその種
ちょうど時間をかけて自然に消えます。
>> 私たちが気にすることはあり 表現、一部
変化させるために起こっている表現の 私たちの入力がどんどん大きくなるにつれて。
そして実際、現実の世界では、 それはますます何が起こっているのかだ
私たちの問題への入力で、 アルゴリズムが大きくなっている。
だから、大きなO記法であることを行っている、 漸近記法、私たちだけでは
記述するためにコンピュータ科学者として使用 性能、走行時間、
アルゴリズムの。
私たちはアルゴリズムを比較できるように、 書かれた別のコンピュータ上で
さまざまな人による、使用することにより いくつかの基本的に同じようなメトリック
比較の数のようにあなたがしている 多分スワップの数を作ったり、
あなたが作っている。
>> 私たちはするつもりはない カウントは時間である
それは時計を渡し 通常、壁に。
私たちが心配するつもりはない 約どのくらいのメモリである。
あなたが本日使用している 少なくとも、それはだけれども
私たちが計測した場合、別のリソース。
私達は私達の分析をベースにしようとするつもりだ ただ、基本的な操作について、もの、
率直に言って、あなたが最も視覚的に見ることができる。
n個のビッグOのようなものとそう 乗、私は、nのOは二乗と主張している
いわゆる上限です バブルソートの実行時間。
言い換えれば、あなたの場合 があることを主張したかった
何でこの上限 アルゴリズムがかかることがあり、手順、
それは、nの大きなOになるだろう 上限は、この場合、二乗。
>> 私が代わりに変更された場合 バブルソートではないようにする話、
しかし、この上限に関する。
あなたは、アルゴリズムを考えることができます 私たちはすでに見てきたこと
その上限は、最大 時間や動作を測定し、
有界されると言われる nは、線形関数によって
湾曲したのではない二次1？
そのアルゴリズムは何ですか 常にこれ以上取らない
nステップ等より 2nのステップ、または3nのステップ？
うん？
>> 聴衆：検索 リストの中の最大の数は？
>> スピーカー：パーフェクト、発見 リストの中の最大の数。
私はのリストを与えられている場合は 例えば人、
人のそれぞれは、番号を保持している 最大数は何ですか
ステップでそれは私を取る必要があり、 合理的にスマートな人、
そのリストで最大の人を見つけるには？
nは、右か？
最悪の場合には、どこにあるため 最大値はでしょうか？
右、最後にすべての方法。
最悪の場合にはそう 私は、上限かもしれません
すべての道を行かなければならない こっち等であっても、
ああ、ここ数8ですが、 またはその値が何であれ。
今ではただ愚かなことだろう 私が続けられた場合には、右か？
より多くの要素を探して そのうちの最後のは、あそこであれば？
だからきっと、nが上限である。
私は実行する必要はありません それ以上のステップ。
>> だから何かの代わりに私がすることを提案 この世界ではアルゴリズムが存在すること
の稼働時間がある ログnのビッグOで囲まれた、ログn？
どこに前にこれを見たことがありますか？
うん？
>> 聴衆：電話帳の問題では？
スピーカー：電話帳の問題のように。
どのようにの尺度は何だった 多くの時間、またはどのように多くの涙、それ
のような人を見つけるために連れて行ってくれました 電話帳内のマイク·スミス？
私たちは、ログnを主張した、と でも、不慣れな場合、またはそれです
何A少しかすん 対数または指数だった、
ちょうどそのログnを覚えている 一般的プロセスを指し、
この場合は、分割する 再び、そして再び半分に何か、
そして再び、そして再び、そのようなこと、その あなたはそれを行うように、ますます小さな取得します。
>> nは必ず、参照するのだからログインし、 電話帳を例に、
理論的には二分探索に、とき、私たち ボード上の仮想のドアを持っていた、
またはショーンだったとき 何かを探し。
彼はバイナリ検索を使用していた場合は、ログn どのくらいの上限になります
かかる時間。
しかし、中に走ったそれらのアルゴリズム nは何キー詳細を引き受けログ？
リストは、右のソートされていること？
あなたのアルゴリズムでは、もし間違っている あなたの入力がソートされていない、
まだあなたが使用している バイナリサーチのようなもの
あなたがジャンプする可能性がありますので、 右の要素の上に
実現することなく、それは確かにありま​​す。
>> さて、これは一つ、大きなOで何を意味するのでしょうか？
これは、アルゴリズムという意味ではありません 唯一の一歩を踏み出し、
それはちょうどそれがかかることを意味 ステップの定数。
多分それは多分それはだ、1だ 10、多分それは千ですが、
それはとは無関係だ 問題の大きさ。
どんなに大きなnは、 定数時間アルゴリズム
常に同じステップ数をとります。
それでは、アルゴリズムかもしれない 私たちは話をしたか、単に
直感的にそれがあることをあなたに来る いつも、いわゆる一定の時間で実行されます？
うん？
>> 聴衆：二つの数字を追加します。
スピーカー：二つの数字を追加し、 2プラス2は行われ、4に等しい。
だから、うまくいくかもしれない、他に何？
どのように、より現実の世界についての、ええ？
>> 聴衆：検索 リストの最初のもの。
スピーカー：最初の検索 リストの要素、確認してください。
私たちは、実際に話をしてきた すでにアレイに関する、
どのように入手できますか 配列の最初の要素、
どんなに長い 配列はCコードである？
あなただけのブラケットのように使用します ゼロ表記は、バム、あなたはそこにいる。
余談としてそして実際の配列、 一般的に知られている何かをサポート
ランダムアクセス、ランダムアクセスなど メモリ、あなたは文字通りことができるので、
いずれかの場所にジャンプします。
私たちも、より簡単にこれを行うことができます 私たちは週にゼロに巻き戻すことができます
私たちはスクラッチをしたとき。
それがためにどのくらいの時間がかかりました スクラッチでのブロックは実行に言う？
ただ、一定の時間、右か？
、何かを言うと言う 何か、それは問題ではない
大きな傷の世界がどのように、それは常にです 同じ時間を取るつもり
単に何かを言って。
>> だから、一定の時間だ、 しかしフリップサイドは何ですか？
それは、上側であった場合 境界、私たちが何をしたい場合
下限を記述するために 私たちのアルゴリズムの時間を実行している？
ほぼベストケース 潜在的に、可能ならば、
これらの用語は最高に適用される可能性がありますが ケース、最悪の場合、平均的なケースより
一般的に、しかしちょうど注目しましょう より一般的には下限について。
持つアルゴリズムは何ですか 低い、nステップの下限
または2nのステップ、または3nのステップ？
nステップのいくつかの要因、 それは、その下限です。
うん？
>> 聴衆：バブルソート？
>> スピーカー：バブルソート取る あなた最小限nステップ、なぜですか？
これはなぜですか？
なぜそれはあなたに来て開始する必要があります 直感的に、それがない場合でも、だけではなく、
まだ？
うん？
>> 聴衆：[聞こえない]。
スピーカー：その通り。
の可能な限り最高のシナリオでは バブルソート、およびアルゴリズムの多くは、
私はあなたに8人が手にした場合 誰がすでにソートされている、
それは愚かなことだ あなたのために、アルゴリズム、
前後に行くために 何度も、右か？
とすぐにあなたとあるので 一度リストの中を歩く、
あなたは、実現すべきああ、私が作ったノー スワップは、このリストは、出口にソートされます。
しかし、それは、あなたのnのステップを取ることになるだろう。
>> 逆に、別のものだ それについての考え方？
バブルソートは、オメガである、 これのN、話す、
あなたが見れば理由 どのようなn個の要素、より少ない
根本的な問題はありますか？
それは、右のソートだ場合は、知りません。
私たちは8時マイトの視線を人間 人とは、、のようなああ、それはソートだこと
それは私のnステップを取らなかったが、それはなかった。
あなたの目、にもかかわらず、あなたの種類の のビジョンの大きな視野を持って、
あなたは8つの要素を見て、 あなたは八人を見て、
それが効果的に8つのステップです。
そして、私は、全体の中を歩く場合にのみ、 リストには、私は、はい、ソートされ、実現しません。
私は途中ですべて、思考停止した場合 右、それはかなり、これまでのソートだ
それはソートされていないだオッズは何ですか？
それは正しいことを行っていないアルゴリズム。
速いが、正しくない可能性があります。
>> だから今、私たちはの方法を持っている 下限を記述し、
そして、時定数約何？
下を持つアルゴリズムは何ですか 1、その実行時間の下限？
1ステップ、2ステップ、10ステップが、 、定数nは独立して、
入力のサイズは？
ええ、後ろに。
>> 聴衆：のprintf？
スピーカー：それは何ですか？
聴衆：のprintf？
スピーカー：のprintf。
[OK]を、確認してください。
だから、ステップの固定数を取ります。
そして、私は今ではnow--必要があります 私たちはCコードの話をしている
そして、何かをスクラッチしない 、と言うようなのprintfと、
私たちは慎重に取得するために開始する必要があります。
printfのは時間がかかりますかので 入力は、文字列ですが、
や文字列は、技術的に長さを持っています。
だから私たちは現在、ピックアップする場合は、 あなたに、あなたは気にしない場合には、
技術的に、私たちはそのprintfのを主張する可能性が 可変長の入力を取得し、
そして確かにそれはより多くかかることがあります この長い文字列を表示するための時間、
この長いより。
>> だから私たちは何を検討している場合 仕分けと例をお探しですか？
電話でのマイク·スミスについての何 ブック、またはより一般的には二分探索？
最良のケースでは、何が起こるのでしょうか？
私は、バム、電話帳を開いて、 マイク·スミスの数があります。
私はすぐに彼を呼び出すことができます。
>> 一歩、多分2つのステップを取った、 しかしステップの一定数の
私は幸運であれば。
そして、率直に言って、私たちは上を見た 月曜日あなたの同級生
2回続けて非常に幸運。
そして、それは確かに一定であった 下限の時間
問題のアルゴリズムに見つけるための 閉じそれらの背後にある数50
ドア。
>> さて、余談ですが、あなたは発見するかのように ビッグO、上限、両方その
オメガ、下限、 その同じの1である
同式は、 括弧、あなたもできます
ちょうど空想であると言う その何かがシータにあり
nまたは他の値のシータの。
それはちょうどその時、大きな意味 Oとオメガは同じです。
今どのような選択ソートはどうですか？
それではこの新しい語彙を使用してみましょう。
選択ソートでは、何だった もう一度やって、そして再び、そして再び？
私が通って行き来した リストには、誰をお探しですか？
最小数。
>> それでは、どのよう多くの手順、方法 多くの比較は私でした
誰を把握するために行う必要があります リスト中の最小要素でしたか？
nはマイナス1、右か？
私はちょうど私は1で始まる場合は、そのため 与えられたと私は彼または彼女を比較開始、
その後、彼または彼女は彼 または彼女は彼または彼女は、私
要素のみをペアリングすることができます 一緒のn - 1回。
だから選択はソートも同様に取り nはマイナス1は、第1回繰り返します。
>> それはに私を取るんどのように多くの手順 二番目に小さい要素を見つける？
nはマイナス2、私はだから、ダムであること 私は、同じ人を見続ければ
再び私はすでに彼を選択した場合は、 または彼女とその場所にそれらを置く。
そして第三段階はn マイナス3、そしてnはマイナス4。
私たちは、このパターンを見てきました の前に、実際
選択ソート同様 上限があります
私たちは、その総和を行う場合は、nの二乗。
その下限、選択ソートとは何ですか？
最低限、どのくらいの時間の必須の選択 私たちは月曜日にそれを定義されている並べ替え、取る？
つのオプションを提案する。
多分それは以前と同様に、Nさん。
多分それはそれとして、二乗Nさん 上限として、今です。
>> 聴衆：nの二乗。
スピーカー：nの二乗。
なぜ？
>> 聴衆：あなたが持っているので [聞き取れない]を定義します。
>> スピーカー：その通り。
私は、選択ソートを定義した少なくとも同 それはかなりナイーブだった、続ける、
最小の要素を探します。
最小の要素を見つけ、再度行く。
のないソートはありません そこに、その中で最適化
私は後に中止させていただく場合がございます ちょうどn個かそこらのステップ。
だから実際には、選択 ソート、n個のオメガ二乗。
>> 私が撮った挿入ソート、約どのような 私は与えられたし、私は彼をそのまま流し方
または彼女の右の場所で？
それから私は、二人目に進ん 正しい場所に彼または彼女をそのまま流し。
そして、次の人は、そのまま流し 彼または彼女の右の場所で。
これは非常にあることに注意してください いわばリニア、。
私は私は、直線よ 行ったり来たりしない、
私は本当に戻って見ていないが、初めてだ 私は彼を挿入したときに何が起こっている
または彼女の先頭へ 私たちは月曜日に行ったように、リスト？
何が起きているのでしょうか？
うん？
聴衆：[聞こえない]。
スピーカー：ええ、その 右、キャッチでしたか？
あなたが思い出すかもしれませんから クラスメート、彼らの場合
との任意の動きを作っていた 自分の足、それが動作した。
だからここに3人があった場合には 新しい人は、そこに道の上に属し
このような長いステージ上で、確かに、彼 または彼女はちょうど最後の最後まで行くことができます。
しかし、私たちは考えている場合は、 コンピュータとメモリの配列、
これらの人々が行っている オーバーシャ​​ッフルに持っている
その人のための部屋を作る。
そして、その結果、nはマイナス1 shufflings、 nはマイナス2 shufflings、n個
マイナス3 shufflingsはただ一種のです 私の後ろではなく、私の目の前で起こって
以前のように、ある意味で。
今はさておき、などなど あなたがオンラインで見ているかもしれません
何についてチャンスをうかがっ起動した場合 ソート、非常に多くの異なるものがあります
そのうちそこに、いくつかの 他よりも優れています。
実際、bogosortは1である それがルックアップする楽しみのようなものだ。
Bogosortはセットを取る 番号やカードのデッキを言う、
ランダムにシャッフルし、 彼らはソートしている場合はチェックします。
ない場合には、再びない。
そうでない場合は、再びない。
信じられないほど愚かな。
>> そして実際、あなたが読んでいる場合 Wikipediaの記事のように、
そのニックネームは愚かなものです。
それは最終的に動作しますが、 うまくいけば、十分な時間を与え、
しかしその時間 かなりの時間がかかることがあります。
私ができるのであれば、のは物事をスピードアップしましょう 以前のメアリーベスの例からアップ、
さらにいくつかの要素を有することによって、 2つ以上のプロセッサ。
二人、よろしければ 私を参加気にしないだろう。
どのように約1こっち、と それではあそこ誰もgo--ないしましょう​​？
あそこ誰か？
[OK]をクリックします。
黒であなた シャツは、はい、ダウン来る。
すべての権利、あなたの名前は何ですか？
>> 聴衆：ピーター。
>> スピーカー：それは何ですか？
>> 聴衆：ピーター。
スピーカー：ピーター、デビッド、はじめまして。
すべての権利、私たちは、ここでピーターを持っているあなたの場合 こっちのテーブルの上に来てほしい。
そして、あなたの名前は何ですか？
>> 聴衆：エレナ。
スピーカー：エレナ。
OK、はじめまして。
エレナはピーターを満たしています。
ピーター、エレナ。
そして、私たちはアンドリューが必要です ここでもアップでお願いします。
そして、あなたの課題は、起こっている カードのデッキをソートすることができます。
そして不慣れな場合は、デッキ カードべき究極的に
のような少し何かをソートする 私たちはその後、クラブをやるときは、この
その後スペード、ハートと 一つとしてエースからダイヤモンド、、
王までのすべての方法。
>> 私はあなたを与えるつもりだカード 量が52であることを行っている。
私たちは、同じようにするつもりだ ちょっと時間ができ、。
私たちはアンドリューをスローするつもりだ ここで画面上に、
これを行うように見るようにする。
だからこれのすべてのこと 、すべてがより見えている
これらは、私がアマゾンに乗ったカードです。
そこで、彼らはランダムにすでに ソートされ、私たちはあなたのタイミングをするつもりだ。
そして、私たちはするつもりだ 本当のこの時間は、それを維持し、
私たちはあなたに圧力をしようとしている そうでなければ、これは退屈でしょう理由
すぐに。
あなたが52を並べ替えるに進みことができれば 今一緒にいくつかの手段を介して要素。
>> そして再び、私たちはこれらを見ながら 人は最終的に、何をすべきか
明白なことを生成するために起こっている 結果は、本当に考える
どのように彼らはお互いにそれをやっている、 どのようにそれを記述することがあります。
再び、これらは理由 すべてのプロセス、アルゴリズム、
人間として当たり前の私たちは取ること。
しかし、あなたは、おそらく長い間持っていた 直感、限り、あなたの前にあっても
服用を考えた コンピュータサイエンスのクラスます
との直感を持っていたかもしれない これは、このような問題点を解決する。
しかし、あなたが認識したら、 パターンと開始
での手順を形式化するために あなたはこれらの問題を解決している、
あなたは多くを解決できることを見つけることができます より興味深く、はるかに複雑
迅速に問題。
だから、聴衆から誰かが、何か アルゴリズムの少なくとも1つの要素
彼らはここ使用していること？
>> 聴衆：[聞き取れない]
スピーカー：それは何ですか？
聴衆：スーツバイ。
スピーカー：スーツバイ。
したがって、最初の彼らはクラスタリングされている ダイヤモンドのすべて一緒に
それは、全て思わ 一緒にそれはそう心、
など、尊敬せずに カードの番号などです。
そして今、彼らは、例えば、表示され、 数によってそれらをソートする。
非常に良い。
>> すべての権利、これに何が起こっているか ここで、最終的な段階である？
私たちは、4つのソートされたスーツを持っていたら、どのような 私たちは4山に何をする必要があります
1を達成するために、 非常に単純に、デッキをソート？
だから私たちは再びそれらをマージする必要があります。
>> だから面白いアイデアがあります 再び、あえて言う、でも非常に直感的です
あなたが平手打ちことはなかった可能性がある場合 その上の標識のようなもの。
分割するこの基本的な概念 この半分の時間で問題ではない、
しかし、少なくとも4個に。
ほとんどの解決 基本的には同一の問題
互いの単離において、 し、結果をマージする。
そして、優れた、やった。
すべての権利は​​、大きな丸い 拍手の、私たちができれば。
>> [拍手]
>> スピーカー：私は何をよ見当がつかない これらとは、しかしここに行く。
どうもありがとうございました。
それでは、2分見てみましょう そして8秒、
あなたの友人に挑戦したいと思います。
その後何になるだろう このことから奪うこと
私たちは、より一般的に活用できる​​のか？
さて、戻って考える この数値の配列、
とのいくつかにすぐに戻って考える 私たちは、過去に書いた擬似コード、
これはのための擬似コードだった 電話帳の問題を解決する。
これにより擬似コードでは、私は より系統的な方法を列挙し
私は非常に直感的にやった方法を説明するの 電話を分割する人間アルゴリズム
半分に本、繰り返し、繰り返し、繰り返し、 私はマイク·スミスのような人を見つけるまで、
彼は電話帳に実際にある場合。
>> しかし、私は一種の私が電話するよ何に使用 ここで非常に反復アプローチ、
特に通知の中8行目と11行目。
これらは、反復の証拠である アプローチ、ルーピングの手法、
それはまさにだから 彼らが誘発する行動。
これらの行の両方がに行くと言う ライン3、そしてあなたができるような
あなたにそのことを考える ループものとして心の目。
これは、バックステップに上がるためにあなたを伝えるだ 3を繰り返し、再び、そして再び、
そして再び。
>> しかし、私たちは主要なアイデアをどのように活用した場合 ここで私たちは前回しなかったことを、
そして、ライン8を簡素化し、 11行目とその隣人
ちょうどこの、黄色のように。
それは基本的に短くしないです 擬似コード非常に多く、
それは根本的に変えることだ 私のアルゴリズムの性質に依存する。
私が今言っている 手順7で、ステップ10において、
マイクを検索することです まったく同じ方法で、
ちょうど左側にある 半分または右半分。
>> そのように、換言すれば、もし 私は、ステップ1からスタート
中央に開いた、電話帳をピックアップ 電話帳の名前を見て、
スミスは間にある場合には 名前の、マイク、他の呼び出し
スミスは、以前の本の中であれば、7ステップ 本の左半分にマイクを検索してください。
しかし、そのようなもののように感じている それは正しい、ぶら下がっ私を残している？
黄色で表示されます 命令が、私をどのように行う
左にマイクを検索 電話帳の半分？
私はどこにありますか 私とアルゴリズム
マイク·スミスのような人を検索することができますか？
まあ、それは顔で私たちを見つめています。
私は、文字通り、まったく同じを使用することができます プログラムは、効果的にトップに上がっていく
何度も再実行 同じコード行。
>> だから、これは感じるはずにもかかわらず、 循環的な定義のビットのような
あなたが誰かのに答えるどこ ちょうど一種の尋ねることで問題
再び同じ質問、 のような、なぜ、なぜ、なぜ？
私たちは、ハードコーディングされたので現実はある 特別な数行、手順4、
、あれば、ステップ12であるその 効果的に別のブランチであり、
私たちはそれらのその場しのぎの対策を持っているので、 私たちは、このアルゴリズムは終了します
マイクを見つけるか、私たちはしないと。
しかし、今のステップ7と10年には持っている 私たちは再帰アルゴリズムと呼ぶことにします。
そして、再帰は確かに強力なアイデアです それは、最初は少し曲げ心だ
次のように私たちが今、適用する。
>> 最後のソートになるソートマージすること 私たちは正式には少なくともクラスで、見てください。
そして、それは根本的に違う これらの最後の3つから、確か
最後の4つは、私たちはbogosortが含ま​​れている場合。
ここではマージソートのための擬似コードです。
n個の要素の入力にするため、ある場合には 大きさnの配列、nが2未満である場合には、
リターン。
では、なぜ私はそれを持っています 正気最初のチェック？
私はあなたを渡した場合に意味の周辺情報 その長さnの配列が2未満である？
それはすでに、右、明らかに、ソートされたのですか？
リストには、どちらか持っているので 自明である一つの要素、
それはだからソート そこに唯一のもの。
それとも、それは意味の大きさゼロのためです 本質的になるようにソートするものは何も、ありません
それがソートされます。
そこに間違っただけでは何もありません。
だから、私たちの、いわゆるベースケースです。
>> つまり、基本的に変わるところである 私たちはマイクで何をしたかと。
マイクの電話帳にある場合は、彼に電話。
彼がそこにいないなら、あきらめる。
それは確認する、いわゆるベースケースだ 一日の終わりに、このアルゴリズム
特定の状況で停止します。
>> しかし、ここで信仰の飛躍は、他に、今だ 要素の左半分を並べ替える
右を並べ替える 要素の半分、
してからソートされた半分をマージ。
それは感じているところそして、ここだ 私たちは盗むしているような。
私は、並べ替えることができます求めてきました n個の要素、と私は今
[OK]を、ソートしてそれを行う、と言って 左と右のソート。
しかし、私は1つを言っている 他の事、そしてこの
それはそう重要なテーマであり、 これまで勘と、
マージのこの第三段階があります。
どちらも、それも 精神でそのようにダムだが、
のような物事をマージ 一緒に、それが思われる
に向けた重要なステップであると その二つの問題の再組み立て
半分に最終的に分割した。
>> あなただろう場合それでは、これをやらせる、ソートマージ もう一つのデモンストレーションとユーモア私、、
ちょうどそのように私たちはいくつかを持っている で動作する数字。
私は8ストレスを交換することができます 8人のためのボール？
どのように約3すべての権利、あなた4 このセクション、5つ、6つ、そしてみましょう中
7、図8に示すように、投入時に来るのか。
[OK]うん、OK。
マイナス8は、そこに私達は行く、プラス1。
優秀。
すべての右、上に来てみましょう すぐにあなたの番号を与える。
ナンバー2、ナンバー3、4番、 数5つ、6つ、7つ、8。
私は正しくこの時間を8でした。
>> そう、あなたができれば先に行くと、 それでは元の順序で並べ替えてみましょう
昨日持っていたことを見ている このように、あなたは気にしないならば。
そしてのは、テーブルの前でそれを行うことができます。
すべての権利なので、ソートマージ。
それが起こっている場所です 興味深いの種類を取得するには、
私は自分自身を与えているように見えるので、 そんなに少ない情報今日。
>> したがって、最初のすべてのマージソート n個の要素の入力で、
それがだ、明らかではない2未満である 8ので、私は行うにいくつかのより多くの仕事を持っている。
だから今精神的に私たちのクラスとして 他の枝に今ある、
その3つのステップを意味します。
第一に、私はソートする必要が 要素の左半分。
それでは、どのよう私はこれをやって行くのですか？
まあ、私は一種のつもりだ 精神的にここにリストを分割し、
あなたがする必要はありません 物理的に移動し、私は今
のみに焦点を当てるつもり ここで要素の左半分。
だから私は、ソートについてどのように行くのですか 今のサイズ4のリストは？
私のアルゴリズムは何ですか？
最初に私は確認していない、nは2未満である、 私は再び他のブロックに進みます。
並べ替え要素の半分を残しました。
>> だから今、もう一度、精神的に、 これはどこにある
あなたはたくさんの計上しなければならない 精神的な歴史、可能ならば。
今、私は左の並べ替えています 左半分の半分。
すべての権利、今私は私の同じマージを呼び出す ソートアルゴリズムを、2 nよりも小さい？
いいえ、それは2であるので、私はソートする必要が 左半分、右半分。
だからここに私達は行く、左半分を並べ替える。
なぜあなたは単にない 前進1歩を踏み出す。
あなたの名前は？
>> 聴衆：ダレン。
>> スピーカー：ダン。
ダンは踏み出しています。
>> 聴衆：ダレン。
スピーカー：ダレン行わ。
あなたはダレンやダンを言ったの？
>> 聴衆：ダレン。
>> スピーカー：ダレン。
[OK]を、ダレンは強化しています フォワードと彼は今ソートされます。
そして、これはほとんどあり 無意味なクレーム、右か？
私は実際に達成されていないようだ 何が、のを続行しましょう​​。
今私は、右を並べてみましょう 要素の半分。
あなたの名前は？
>> 聴衆：ルーク。
>> スピーカー：ルーク。
さあ、一歩前進。
完了、私はルークをソートしています。
左半分が現在ソートされており、 右半分は現在、ソートされ
これもまた、ここで重要なステップがあります。
私は次に何をする何が必要ですか？
ソートされた半分をマージします。
今、私たちはただ必要があるとしている 前後にこのように誰もが、
私は一種の必要があるため いくつかのスクラッチ領域。
それはほとんどこれらのようなものだ 人はテーブルの上にある、
と私はいくつかの部屋を必要とする 上でそれらを周りに移動します。
だから私は、マージするつもりです 見ることによってあなたたち
左半分と右半分で。
そして、明らかに最初に来る人は、 左半分または右半分？
だから、右半分は、それでは、以上のルークを移動してみましょう ここダレンの元の位置に。
そして今では自分の左半分をマージするには ダレンは、すぐそこに移動するようになるだろう。
>> だから、ほとんどのように感じている バブルソート効果、
しかし、私の基本的なアルゴリズム、 今回は非常に異なる。
物事が取得する場所しかし、今だ 少し迷惑なあなたのため
精神的に巻き戻ししなければならない 私はどこにオフにしておいた。
私はソートされた半分を合併しましたが、 これは私が私のアルゴリズムでどこてる意味？
私は右の、右半分を並べ替える必要がありますか？
>> あなたは文字通り、巻き戻した場合 ビデオでは、よ
私たちはこれになっていることがわかり ルークとダレンのポイント
左をソートすることにより 左半分の半分。
それから、それらをマージ 、半分をソートしている
次のステップは、ソートであることを意味し 左半分の右半分。
すべての権利、そうしてみましょう より迅速にこれを行う。
すべての権利、6、私は主張するつもりだ あなたは今、前方に来て、並べ替えられています。
あなたの名前は？
>> 聴衆：アドリアーノ。
>> スピーカー：アドリアーノ。
アドリアーノは現在ソートされます。
そして、あなたの名前は何ですか？
>> 聴衆：アレックス。
>> スピーカー：アレックスは今ソートされます。
左半分、右半分、 最後のステップは何ですか？
マージ。
プリティ些細なので、私は今 6マージしようとして、
バックステップを取る、 8は、ステップを取り戻す。
そして今、これは注意してください 便利持ち帰り、何
今の左半分程度真実である リストに関係なく、私たちはどのように始まったのかの？
それは、ソートされます。
>> 今ではで並べ替えないです 物事の大きなスキーム、
それは独立してソートされ 残りの半分の。
私が続ければ今何段階私が上だ 物語がどのように始まったのか、巻き戻し？
今、私は右半分をソートする必要があります。
だから今、私たちは道奥にしている 物語の冒頭、
とのより迅速、これをやらせる。
だから私は、ソートするつもりです リスト全体の右半分。
次のステップは何ですか？
右半分の左半分をソートします。
の左半分をソート 右半分の左半分。
そして、あなたの名前は何ですか？
>> 聴衆：オマール。
>> スピーカー：オマールは、行われ、前進。
左半分がソートされます。
そして、あなたの名前は何ですか？
>> 聴衆：クリス。
>> スピーカー：クリスは、一歩を踏み出す 前進、あなたは今ソートされる。
今重要なステップは何ですか？
マージ。
したがって、1つの場所に合流しようとしている ここに、あなたが戻って一歩を踏み出すことができれば、
そして3人はしようとしている マージ、ステップを取り戻す。
だからの左半分 右半分は、ソートされるようになりました。
率直に言って、このアルゴリズムは、私たちのように感じている 以前より道より多くの時間を無駄にしている、
私たちはリアルタイムでこれをしなかったなら、私たちはよ 持ち帰りがあることを行ってものを見る。
今ここに私は右の、午前 右半分の半分、
私が先に行くと左半分を並べてみましょう。
一歩前進、あなたの名前は何ですか？
聴衆：ラムジー。
スピーカー：ラムジーは今ソートされます。
あなたの名前は？
>> 聴衆：マリーナ。
>> スピーカー：マリーナは今のようにソートされる さて、あなたは一歩を取る場合。
ここで重要なステップは、今私は、マージされている 私の二つのリストから摘み取るつもり、
左と右。
ファイブは、最初に来ることを行っている そして7は、次の来ることを行っている。
そして再び、これは意図的なもの。
彼らが取っているという事実 前後のステップ
私たちができないことを示すためのものです 同様に容易な場所にこのアルゴリズムを行う
バブルソート、選択ソートなど、 どこでちょうど私達と挿入ソート
人を入れ替える続けた。
私は文字通りの並べ替えを必要とする メモ用紙のもので
これらの人々を置くために 私はマージを行いながら、
そして私は場所に戻ってそれらを置くことができます。
私が使用しているので、それがキーだ 新しいリソース、スペースだけではなく、時間。
>> [OK]を、これは素晴らしいです。
左半分、右半分は、ソートされ ソートされた、今ではキーのマージステップ。
どのように私はこれをマージするつもり？
だから、あなたが私に従うだろうかどう 左手と右手、
私は私の左手を指すつもりだ 左半分では、私の右手
右半分では、今私が持っている にマージする段階的に決定する。
誰が、明らかに最初に来る？
ナンバーワン。
だから、こっちに来て、 ここに私たちのスクラッチパッドです。
だから今ナンバーワン、と予告 私は自分の右手で何をやる、
私は私の右手1を移動するつもりです ポイント番号3にステップオーバー、
そして今、私は確認する必要があり 同じ決定。
そして、実際に右に立つ ここでルークの前もしできれば、
これは私たちのスクラッチパッドであるためです。
だから、誰が次に来る？
私たちは、数2でルークを持っている または番号3とクリス。
もちろんルーク、数 2、あなたがここに来るようにします。
>> しかし、私の左手は今まで起こっている ダレンを指すようにインクリメントされ、
とここで奪うキーです マージ、私はこれをやり続けるつもりだ、
明らかに、あなたの種類の場合 の論理に従ってください。
しかし、私の手は決してありません 後方に行くつもり、
その私は今までに移動してることを意味 私のマージ処理が残され、
それがカギになるだろう 一瞬で私たちの分析。
>> だから今のが急速にこれを終了させ。
だから3人は、次に来る その後4人が次に来る、
そして今5は、6その後、次に来る そして最後に、その後7、および8。
最も遅いアルゴリズムのように感じている まだではなく、実際に私たちの場合
同じ種類でそれを実行する クロック速度の、に非常に
同じで、話す 以前のように時計を刻む。
なぜ？
さて、見てみましょう 最終結果を見てください。
>> とさせて頂いて、のはこちらに戻りましょう 視覚的にデモを引き上げ
私達はちょうど何をしたかの。
この上で、ここにズーム こちらのページは、Firefoxを伝える
私たちはキューしたいこと このボックスに、最大みましょう
これで、バブルソートを言う 私たちは、現在十分に精通している
別のある選択ソート、 かなり簡単な1、
これ、今、今日のマージソート、 私たちのクライマックス結末になります。
それはそんなに時間がかかった理由 ここに人間と私と一緒に口頭で、
明らかに、私はすべての工程を説明するよ。
しかし、あなたは、単に多く、これを実行した場合 私たちは、バブルソートや選択を行ったように
並べ替えだけでなく、視覚的に、時計 どれだけ、より効率的に
このレバレッジ 分裂と征服
のデータセットに適用することができる場合 なくてもサイズが8、それでもずっと、
はるかに大きい。
私は、あなたがすることによって、ソート側マージ与える これらの他のアルゴリズムを有する側。
これは痛みを伴う取得する予定です 迅速、エンディング
特にクライマックスではありません 彼らはただソートすることになります。
しかし、キーが奪うということです より高速なマージソートどのくらい見て
あなたは私は考えていない限り、だった だけの種類のあなたといじり。
私たちは、この最後に1回行うと、 それではこれをリロードしてみましょう、の戻りましょう
そして、バブルソートを選択 ちょうど蹴りのために、
の挿入]を選択してみましょう ソート、ちょうど良い測定のために。
そして再び、この時間は、みましょう マージソートを選択してみましょう
実際に並んでこれらの副作用を実行します。
>> そしてそれは、実際には、まぐれではありません。
私は効果的にやったのは、私だである もう一度、半分に私の入力を分け、
そして再び、そして再び。
そして、あなたができるだけなので何度もあります 半分に入力を分割し、左
と右。
私たちが見ておくの式は何ですか つまり、半分に分割を記述する
再び、そして再び、そして再び、そして再び？
>> 聴衆：nはログインしてください。
>> スピーカー：ログのn。
しかし、その後、一つの他の重要なステップがあります、 このアルゴリズムは、n個のステップをログに記録されていません。
それがあった場合はログのみのnステップ、 私たちは同じ問題になるだろう
私たちがすることはできませんここで前と 必ずすべてのソートされた。
あなたは最小限にn個の要素を見ている n個の要素がソートされていることを確認することが、
それ以外の場合は、信仰の飛躍だ。
>> だから、最小限にログインするn個のステップですが、 このキー併合ステップについてどのような
私がマージされ、私の左半分と右 ステージ全体に歩い半分？
マージすることは、どのように多くの手順とは？
それはnのだが、私はちょうどしませんでした 最終的な時間をマージ。
これらのネストされた呼び出しのそれぞれには、それぞれに これらのネストされたマージ、私はまだソート。
私は、これら2つのこれらの2人を、マージ みんな、これら2つの人など。
>> だから私は再び、そして再びマージしなかった。
何回？
だから、毎回、私は分割 リストは半分に、私はマージを行いました。
マージを行うには、半分にリストを分割します。
だから、リストを分割する場合は、 ログをn回行うことができ、
とマージは、最終的にn個をとり 今アッパーかもしれないどのような手順、
ランニングの下限 このアルゴリズムの時間？
nはn個を記録します。
>> そして実際、それは何ですか 私たちはここで達成した。
ですから、視覚的にしたときに表示感触 これらの3つのものが並んで実行
N Nに対して二乗さ n個のログのn乗に対して。
どの基本的に私たちが表示されます、 今日が、将来的にだけでなく、
はるかに、はるかに高速です。
これらの人のための拍手、 私はストレスボールとそれらを報いるであろう。
今日はここに休会しましょう​​、と 私たちは月曜日にお会いします。