[音楽再生] DAVIDマラン：すべての権利。すべての権利は、戻って歓迎します。だから、これは第4週、始まりですその、すでに。そして、あなたはその先週思い出して、我々は置くほんの少しのために取ってコーディングするそして我々はもう少し話し始めのようなことについて、ハイレベルいるものの、検索とソートややシンプルなアイデアは、されている問題のクラスの代表あなたは、特に解決するために開始されますあなたは、最終的なことを考え始めるとプロジェクトや興味深いソリューションあなた現実世界の問題を持っているかもしれません。今、バブルソートは、最も単純なの一つであったそのようなアルゴリズム、およびそれこれらの小数値を有することによって働いリストまたは配列の種類の中でまでトップにバブル自分の道を、と大きな数字は、への道を下に移動そのリストの最後。そして、我々は視覚化できることを思い出すバブルソート少しこのような何か。だから私は先に行くと、[開始]をクリックしてみましょう。私はバブルソートを事前に選択しました。そして、あなたはその背青を思い出す場合ラインは小さな、大きな数字を表す青い線は次のように、小さな数値を表す我々は何度も何度もこれを通過し、再び、それぞれの次の二つのバーを比較する赤の他の、我々は交換するつもりだ最大と最小の場合彼らは、順不同である。だから、これは上に行くと上に行くと行くで、あなたはそれが大きく表示されます要素は、への道を作っている右に、そしてより小さい要素は左への道を作ること。しかし、我々は定量化し始めた効率、このアルゴリズムの品質。そして、私たちによると、最悪で場合、このアルゴリズムはかかった大体どのように多くの手順は？だからnの二乗。そしてnは何でしたか？読者：要素の数。 DAVIDマラン：だからnがあった要素の数。そして私たちはしばしばこれをやる。我々は大きさについて話をしたい任意の時間問題やサイズの入力、またはそれにかかる時間出力を生成するために、私達はちょうどよ一般的などんな入力は、nのようになります。だから戻って週0で、その数はページ電話帳にnがあった。学生数部屋にnがあった。だからここに、あまりにも、私たちは、フォローしているそのパターン。さてN乗特にない速いので、私たちはより良い実行しようとしました。そして、我々はいくつ見他のアルゴリズムのうち、選択ソートであった。だから選択ソートだった少し異なる。それはほとんど単純でしたが、私はあえて言う、それによって、私は開始時に開始私たちのボランティアのリストと、私はちょうど再びと何度も何度も経てリスト、最小を摘採当時の要素と、彼を入れたり、彼女のリストの先頭に。しかし、これは、あまりにも、かつて我々は考え始め数学を通して、より大きな絵は、何回考えた私が行ったり来たりと戻っていた行ったり来たり、我々は最悪の場合で述べている、選択ソートは、あまりにも、何でしたか？ nの2乗。今、現実の世界では、それは可能性がある実際にはわずかに速くなる。再びので、私は維持する必要がありませんでした私が並べ替えられていた後にバックトラック最小要素。しかし、我々は非常に大きなnを考えてみれば、とあなたは、ソートの数学などを行う場合私はnの二乗で、ボード上でやったマイナス何か、他のすべて nの二乗、一度N以外本当に大きくなる、しません本当に同じくらい重要では。だから、コンピュータ科学者として、私たちは、一種の小さい方に目をつぶる要因や唯一の要因に焦点を当てに作るために起こっている表現最大の違い。さて、最後に、私たちは見て挿入ソートで。そして、これは、精神で同様であったが、反復して通過するのではなくとで最小の要素のいずれかを選択する時間は、私の代わりに手を取っている私すべては、配られ、私が決定しました右側には、ここに属し。それから私は、次の要素に移っと決めた彼または彼女はここに属していた。そして、私は延々と移動しました。そして、私は、道に沿って、にかもしれないするためにこれらの人をシフト彼らのために場所を空ける。だから精神的な逆転のようなものだった選択ソートのものたち挿入ソートと呼ばれる。これらのトピックが発生するので、現実の世界である。ほんの数年前、時一定の上院議員は大統領のために実行されていた、エリック·シュミット、当時の最高経営責任者（CEO） Googleは、実際に機会がありました彼にインタビューする。そして、我々は、このYouTubeのを共有しようと思いました我々がターンアップができれば、ここであなたをクリップボリューム。 [ビデオの再生] - 現在、上院議員、あなたがGoogleでここにいる、と私は大統領を考えるのが好き就職の面接のように。 [笑い] - 今、それを得るのは難しい社長としての仕事。そして、あなたが通過している今厳しさ。それはGoogleの仕事を得ることも難しい。我々が質問を持っていると我々は尋ねる我々の候補者の質問。、この1つはラリーシュワイマーからのものである。 [笑い] - 君たちは、私は冗談だと思う？それはここです。への最も効率的な方法は何ですか二百万ビットの整数を並べ替える？ [笑い] まあ、ええと - は - 私は申し訳ありません。多分、我々はすべき - - いや、いや、いや、いや、いや。 - それはない - OK。 -Iは、バブルソートと思う移動するための間違った方法である。 [笑い] [応援と拍手] 彼にこれを言った人、オン観賞したい？ OK。 [ENDビデオ再生] DAVIDマラン：だからそこにあなたがそれを持っている。だから私たちは、これらの実行を定量化するために始めました何か回、いわば、ある漸近記法と呼ばれるただ回す当社ソートを参照それらの小さい要因に見て見ぬふりとのみ実行時間を見て、これらのアルゴリズムの性能は、 nは時間をかけて本当に大きくなるとして。そして我々は大きなO.そしてビッグOを導入しました我々は思っていた何かを表現上限としての。そして実際に、バリー、我々は下げることができますマイク少しも？私たちは、これが上限であると考える。 nの二乗の手段だからビッグOでその最悪の場合、のような何か選択ソートはかかるだろう nの二乗のステップ。挿入ソートのような、または何か nの二乗のステップでしょう。今すぐ挿入のような何かのためソート、最悪の場合何でしたか？配列を指定して、何が最悪だあなたが見つけるかもしれないという可能性シナリオ自分に直面？それは右、完全に後方のですか？それは完全に後ろ向きだ場合なので、あなたは、仕事の全体の多くを行う必要があります。なぜなら、あなたは完全に後方なら、あなたを見つけるつもりだここでの最大の要素は、たとえそれはそこに属しています。だからでは、と言って、すべての権利をつもりだ時間のこの瞬間、あなたがここに属している、ので、あなたは一人でそれを残す。その後は、ああ、実現いまいましい、私がしなければならないこのわずかに小さい要素に移動あなたの左。その後、私は再びそれをしなければならないと何度も何度も。そして、私は前後に歩いている場合、あなたパフォーマンスの感じのようなものであろう常に私がいるので、そのアルゴリズム、でダウンして皆をシャッフルそれのための部屋を作るために配列。だから最悪のケースだ。対照的に - これは前回接戦だった - 我々は言っている挿入ソート何のオメガでしたか？最高のケースは何を実行している挿入ソートの時間？だから、実際にnのだ。それは我々が残した空白になっていましたボード上の最後の時間。そしてそれは、nのオメガ理由からだ？まあ、非常に最良の場合には、何挿入ソートは手渡しするつもり？完全に並べ替えられているまあ、リスト行うためにすでに、最低限の仕事。しかし、挿入ソートについてきちんとしたものだそれはここから始まるとためです決定し、ああ、あなたは数である 1、あなたはここに属しています。ああ、何が幸運。あなたはナンバー2だ。また、ここに属しています。さらに良い3番、あなたがここに属しています。できるだけ早くそれが年末になるにつれてリスト当たりの挿入ソートの擬似コード私たちは、口頭を歩いている最後の時間は、それが行われている。しかし、選択ソート、対照的に、何をして保管？リストを通過保持もう一度、もう一度、もう一度。キー洞察力だけがあったので一度にすべての方法を見てきましたリストの最後には、特定することができます選択した要素があったことを確かに現在は最小要素。最後は、これらの異なったメンタルモデルはそういくつかの非常に現実世界をもたらすまで私たちにとっての違いだけでなく、これらの理論上の漸近的な違い。だから、nのビッグO、その後、おさらいする乗、我々はいくつかのように見てきましたこれまでのアルゴリズム。 n個のビッグO？可能性アルゴリズムは何ですか nは大きなOであると言うこと？最悪の場合には、かかるステップの線形数。 OK、線形探索。最悪の場合には、どこにあるのあなたは時を探している要素線形探索を適用する？ OK、最悪の場合には、それもありません。又は第最悪の場合には、周辺です最後にすべての方法、プラスまたはマイナスワンステップ差。だから一日の終わりに、我々はそれが線形だと言うことができます。 n個のビッグOは、線形探索だろう最悪のケースであるため、要素があってもそこにはありませんか、それはだ最後にすべての方法。さて、n個のログの大O。我々は、約非常に詳細に話をしなかったこれが、我々は前にこれを見てきました。何がいわゆる対数で実行時間、最悪の場合には？うん、そうバイナリ検索。最悪の場合には、バイナリ検索どこかの要素があるかもしれない途中、どこか配列の内部。しかし、あなただけに一度それを見つけるで、半分にリストを分割半分に半分、半分に、。そして出来上がり、それはそこだ。または再び、最悪の場合、それもありません。しかし、あなたはそれがないということを知らないあなたは、ソートのその最後に到達するまで半減によってボトムほとんどの要素と半減と半減。 1のビッグO。だから私たちは3の2、ビッグOのビッグO可能性。あなただけの一定数をいつでも、私達はちょうどだけ簡素化する一種のその1の大Oとして。でも、現実的に、それがかかる場合でもそれはしても2または100ステップ、ステップ一定数、私達はちょうど1のビッグO言う。のアルゴリズムは何ですか 1のビッグOで？読者：長さを見つける変数の。 DAVIDマラン：検索変数の長さ？聴衆：いいえ、長さそれがすでにソートましょう。 DAVIDマラン：良い。 [OK]を、ので、何かの長さを見つけるその何かの長さがあれば、のようなアレイは、いくつかの変数に格納されている。あなただけの変数を読むことができますので、または変数を印刷したり、ただ、一般的にその変数にアクセスします。と出来上がり、それは一定の時間がかかります。これとは対照的に、スクラッチに戻って考える。 Cの最初の週に戻って考える、単にprintfの呼び出し、印刷画面上の何かが間違いなくある時定数は、それだけかかるため表示するCPUサイクルのいくつかの数画面上でそのテキスト。それとも待つ - それをしない？他にどのように我々は、モデルかもしれません printf関数のパフォーマンス？誰かが、反対したい多分それは本当に時定数ではないのですか？ printfを実行しているかもしれませんどのような意味で実際に上の文字列を印刷する時、画面には、何かで定数以外。読者：[聞こえない]。 DAVIDマラン：うん。だから、それは私たちの視点に依存します。私たちは実際に入力を考える場合文字列であるとしてprintf関数、および従って私達はそれの大きさを測定その長さによって入力 - それでは、と呼ぶことにしましょうそれだけでなく、長さn - 間違いなく、printf関数自体は、nのビッグOですそれはあなたnステップを取るために起こっているので、これらn個のそれぞれをプリントアウトする最も可能性の高い文字は、。少なくとも我々は想定している範囲で多分それはforループを使っていることをボンネットの下に。しかし、我々はそれを見なければならないでしょうそれをよりよく理解するためのコード。そして実際、一度皆さんが開始あなたは、あなた自身のアルゴリズムを解析します文字通りまさにそれ。眼球のソートコードと考えるについて - すべての権利、私はこのループを持っているここか私はここでネストされたループを持っている、 n個のものをn回、行うために起こっていることそして、あなたは理由のあなたの方法を並べ替えることができますコードを、たとえそれがだ擬似コードではなく、実際のコード。だから乗、nのオメガはどうですか？アルゴリズムとは何だった最高にケース、まだ取っN乗のステップ？うん？読者：[聞こえない]。 DAVIDマラン：だから選択ソート。その問題に実際に減少しているため再び、私は知らないという事実に私まで、現在の最小を見つけた私はすべてのくそ要素をチェックしました。 nは、言う、のオメガだから、我々一つ思い付いた。挿入ソート。リストがソートされるような場合すでに、最良のケースで我々だけで持っているそれを介して1パスを作るために、その時点で我々は確信している。次いで言えること確かに、線形である。 1のオメガはどうですか？最良の場合には、かかるかもしれないもの、ステップ一定数？だからリニアサーチは、あなただけの幸運を得る場合あなたが探している要素、リストの先頭にある右あなたを始めているところです場合そのリストの線形トラバーサル。そして、これは真であるものの数。例えば、偶数バイナリ検索は1のオメガです。あなたは本当にくそ何を得ればのでの途中で幸運とピシャリ-DAB あなたの配列は数値ですあなたが探している？だから、あなたにも、そこに幸運を得ることができます。このいずれか、最後に、n個のログのnのオメガ。だからnのログN、私たちは本当にしませんでしたまだの話、しかし - 読者：ソートマージ？ DAVIDマラン：マージソート。つまり、前回の接戦だったどこで我々が提案し、我々が示した視覚的に、アルゴリズムが存在することを。そして、ちょうどそのようなのようなものをマージ根本的に高速であるアルゴリズムこれらの他の人の一部より。実際には、だけでなく、短いマージ最悪で最高のケースnのログN、ケースnのログN。そして、あなたは、この偶然の一致を持っているときオメガとビッグOは同じものであること？私たちは、実際に何としてそれを記述することができますそれはでも、シータと呼ばれる少し一般的。しかし、それは単に、2境界を意味しますこの場合には、同じである。だからソートマージ、これは何を行います本当に私たちのために煮詰める？まあ、動機を思い出す。私は別のアニメーションのことをプルアップしてみましょう我々は、最後の時間を見ていませんでした。このいずれか、同じ考えですが、それは少し大きいです。そして、私は先に行くと指摘するつもりだ最初に - 私たちは上の挿入ソートを持って左上、その後、選択ソート、バブルソート、他の種類のカップル - シェルと迅速な - 私たちは話していないこと約、およびヒープとソートマージ。だから、少なくとも上であなたの目を集中しようとするその後、左と上のトップ3 私がクリックしたときにソートをマージこの緑の矢印。しかし、私はちょうどに、それらのすべては実行してみましょうあなたの多様性の感覚を与える世界に存在するアルゴリズム。私はこの実行してみましょうするつもりですほんの数秒間。そして、あなたはあなたの目の焦点を合わせる場合 - ピックただのためのアルゴリズムは、それに焦点を当てる秒 - あなたが見ることから始めましょうそれが実装しているというパターン。マージソート、通知は、行われます。ヒープソート、クイックソート、シェル - 我々は3つを導入したので、それはそう最悪のアルゴリズムが先週。しかし、それは私たちが今日ここにいることが良いことだの一つであるマージソート、見より簡単なものでも、見ることですそれはおそらくあなたの心を曲げるでしょうが少しだけ。ここでは見ることができますどれだけ選択ソートは吸う。しかし、フリップ側では、それはだ実装は本当に簡単。と多分の一つだPセット3、用を実装することを選んだアルゴリズム標準版のために。完全に正しい、完全に罰金。しかし、再び、nが大きくなるように、もしあなたより高速なアルゴリズムを実装するマージソートのように、オッズはで大きく、大きな入力が、あなたのコードは、ある高速に実行するつもり。あなたのウェブサイトは、より良い仕事になるだろう。ユーザーは幸せになるだろうしている。そして、これらの効果があります実際に与えることの私たちいくつかのより深い思考。それでは、マージ何を見てみましょうソートは、すべてについて実際にある。涼しい事はマージということですソートは、ちょうどこれです。これは、我々が呼ばれたものを、再び、です擬似コード、擬似コードの存在英語のような構文。とシンプルです魅惑的な一種の。だから、n個の要素の入力に - ようただ意味、ここでは、配列です。それは、その中にn個のものを持っている。それは我々がそこに言っているすべてです。 nが2未満であると、戻り。だから、それはただ些細ケースだ。 nが2未満の場合、明らかにそうではありケースの事で1または0、すでにソートまたは存在している、これだけを返す。行うには何もありません。だからオフに摘むための単純なケースだ。そうでなければ、我々は3つのステップがあります。要素の左半分、ソートをソート要素の右半分、その後並べ半分をマージ。何がここで興味深いのは、つまり私は右の、パントのようなものだ？円形の定義のようなものがありますこのアルゴリズムへ。どのような意味では、このアルゴリズムのです定義円形？読者：[聞こえない]。 DAVIDマラン：ええ、私のソートアルゴリズム、そのステップの二人は "ソートです頼むので何か。 "そして、質問、まあ、何私が使用するつもりです左半分をソートする右半分？そして、ここの美しさはであるにもかかわらず再び、これはハラハラドキドキです部分は、潜在的には、同じ使用することができます左半分をソートするアルゴリズム。しかし、ちょっと待って。あなたは、並べ替えるように言われているとき左半分、二人は何ですか手順は次のことを行って？我々の左半分を並べます左半分と右左半分の半分。くそー、どのように私はそれら二つを並べない半分、または四半期、今？しかし、それはOKです。我々はここでソートアルゴリズムを持っている。そして、あなたはで心配かもしれませんが最初、これは無限の一種であるループは、それはことはないサイクルだ終わろうとして - それはに起こっている何が起こるかを一度終了？いったんnが2未満である。どの最終的に起こるために起こっている、あなたが続ければ半減しているため確かに、これらの半分を半分に半減最終的には終了するつもりだアップするだけで、1または0の要素を持つ。その点、このアルゴリズムで設定が完了したら言う。だから、これで本当の魔法アルゴリズムは、内にあるように見えその最後のステップ、マージ。ちょうど2つをマージするというシンプルなアイデア物事は、それが最終的に何が起こっているのだ私たちはの配列をソートできるようにするには、 8要素、言うてみましょう。だから私は、最大8つのより多くのストレスボールを持ってここでは、8枚の紙、一グーグルガラス - その私が手にする。 [笑い] DAVIDマラン：私たちは、8を取ることができればボランティア、と我々はできるかどうかを確認してみましょうそう、これを果たしている。うわー、OK。コンピュータサイエンスは、楽しみを得ています。わかりました。それでは、どのように約3、そこに最大の手。後ろの4つ。そして、私たちはあなたをやる方法についてこの行の3？前にと4。だから、8までに来る。 [笑い] DAVIDマラン：私は実際によそれが何であるかわからない。それはストレスボールはありますか？デスクランプ？材料？インターネット？ OK。だから、最大で来る。誰がしたい - 来続ける。見てみましょう。そして、これは場所であなたを置く - あなたは、場所1にいる。おっと、ちょっと待って。 1、2、3、4、5、6、7 - 良い、ああ。すべての権利、私たちはいいです。すべての権利は、誰もが、席を持っているしかし、Googleではなくガラスに。私キューこれら最大ましょう。あなたの名前は？ MICHELLE：ミシェル。 DAVIDマラン：ミシェル？すべての権利は、ように見えるようになるオタク、OKだ場合。まあ、私もそう、私が思う、ちょっと。スタンバイ、大丈夫。私たちは、思い付くしようとしてきた Googleのガラスのケースを使用しており、我々それだけでやるのは楽しいだろうと思ったこの人々がステージにいるとき。我々は世界を記録します彼らの視点から。わかりました。ではない、おそらくGoogleが意図したもの。あなたが気にしない場合は、すべての権利は、身に着けている次厄介分間この、それは素晴らしいことでしょう。そうすべての権利、私たちはここでの配列を持っている要素、およびその配列、当たりとしてこれらの人々に紙の破片 ' 手が、現在並べ替えられています。 MICHELLE：ああ、それはとても奇妙なことだ。 DAVIDマラン：それはかなりランダムです。そして、ちょうどその瞬間に、私たちは試してみるつもりだ実装するために一緒にマージソートそのキー洞察力がどこにあると参照してください。とマージソートとここにトリックがある我々はまだ想定していないことを何か。私たちは、実際にいくつかを必要とする追加スペース。だから何が特になるだろうこれについて興味深いのは、これらです。みんな少し動き回るつもりですちょっと、私はあることを仮定するつもりですので、スペースの余分な配列が、そこ右それらの後ろ、言う。だから彼らは椅子の後ろなら、それは二次的な配列です。彼らはここに座っているなら、それはだ主要配列。しかし、これは我々が持っているリソースですバブルでこれまで活用しないソート、選択ソートと、挿入ソートと。ちょうど先週思い出して、誰もがの種類は場所にシャッフル。彼らは、任意の追加のメモリを使用しませんでした。我々はによって人々のための部屋を作った周りの人を動かす。だから、これは、あまりにも重要な洞察である。このトレードオフは、一般に、そこ資源のコンピュータサイエンス、。あなたが何かをスピードアップしたい場合は時間のように、あなたはするつもりだ代金を支払わなければならない。そして、それらの価格の一つは、非常に頻繁にあるスペース、メモリの容量やハードあなたが使用しているディスクスペース。または、率直に言って、量プログラマの時間。どのくらいそれが人間の、あなたにかかる時間、実際にいくつかの詳細を実装する複雑なアルゴリズム。しかし、今日のために、トレードオフ時間と空間です。だから、あなたたちは、ちょうどあなたを保持することができればので、我々はあなたがしていることを数字を見ることができます確かに4,2、6、1、3、図7、図8に一致する。優秀。だから私は画策しようとするつもりだ物事、君たちだけで可能であればここに私のリードに従ってください。だから私は、最初に、実装するつもりですある擬似コードの最初の一歩、 nがある場合n個の要素の入力に 2未満、その後復帰。明らかに、それはしません適用されるので、私たちは上を移動する。だから要素の左半分を並べ替える。だから私は私を集中するつもりだということを意味するこれらの上でちょっと注目ここに4人。すべての権利、私は次に何をしますか？読者：左半分をソートします。 DAVIDマラン：だから今、私はソートする必要がこれらの人の左半分。再びので、自分自身に仮定目標は、左半分をソートすることです。どのようにそれを行うのですか？たださえ、指示に従ってください我々は再びそれをやっているのに。だから左半分を並べ替える。今、私は、これらの2つの人を選別しています。次に何が来る？読者：左半分をソートします。 DAVIDマラン：並べ左半分。だから今は、これらの、ここでこの席、大きさ1のリストです。そして、あなたの名前は何です再び？ PRINCESS DAISY：プリンセスデイジー。 DAVIDマラン：プリンセスデイジーはここにある。そして彼女はすでにいるので、ソートされているリストはサイズ1である。私は次は何をしますか？そのリストがあるので、[OK]を、返す 2未満であるサイズ1。その後、次のステップは何ですか？そして今、あなたはどのようなする必要がありますあなたの心に後戻り。ある右半分を、ソート - お名前は何ですか？ LINDA：リンダ。 DAVIDマラン：リンダ。そして我々は今、その何をしますか我々は大きさ1のリストを持っている？ AUDIENCE：リターン。 DAVIDマラン：慎重。我々は最初に戻り、今では第三のステップ - と私は種類のことで、それを表現する場合私は今、現在、2つの座席を受け入れこれら2つの要素をマージする必要があります。だから今は残念なことに、要素順不同です。しかし、それはどこにマージ処理だ説得力の取得を開始します。君たちだけのために立ち上がることができるのであれば瞬間、私はで、あなたを必要とするつもりだ瞬間、あなたの椅子の後ろに移行する。そして、もしリンダ、2であるため、 4よりも小さく、なぜしないあなたは、最初に集まってくる？そこに滞在。リンダだから、あなたは最初に集まってくる。今、現実にはそれだけで、配列の場合私達はちょうどリアルタイムで彼女を動かすことができこの椅子からこの場所へ。だから、いくつかの定数を取ったことを想像ステップ1の数。そして今 - しかし、我々にあなたを配置する必要がありますここで最初の場所。そして今、あなたの周りに来ることがあれば、同様に、我々はするつもりだ位置2にある。そして、それはこのような感じにもかかわらずしばらく取って、今ある素敵なものだのその左半分左半分は現在、ソートされます。私たちは今、そうであれば次のステップは、何だった物語の中で、さらに巻き戻し？聴衆：右半分。 DAVIDマラン：並べ右半分。だから、みんなにも、これを行う必要があります。だから、立ち上がることができれば、ちょっと？そして、あなたの名前は何ですか？ JESS：ジェス。 DAVIDマラン：ジェス。 [OK]を、ので、ジェスは今左です右半分の半分。そして、彼女はサイズ1のリストだ。彼女は明らかに並べ替えられている。そして、あなたの名前を再び？ MICHELLE：ミシェル。 DAVIDマラン：ミシェルは明らかである大きさ1のリスト。彼女はすでにソートだ。だから今魔法が、起こるマージ処理。だから、誰が最初に来るようになるだろう？明らかミシェル。だから、あなたが戻って周りに来ることがあれば。我々は今、彼女のために用意してスペース右ここにこの椅子の後ろにあります。そして今、あなたにも戻ってくることができれば、我々は現在、2つ、明確にすること、持っている半分、サイズ2の各 - とだけ描写の為に、もしあなたスペースの少しを作ることができる - 1は、半分ここ残さここでは右半分。物語の中で、さらに巻き戻します。次は何ステップです？読者：マージ。 DAVIDマラン：だから今、私たちは、マージする必要があります。だからOK、今、ありがたいことに、私たちはわずか4椅子を解放。だから我々は、多くのメモリを二回使っていますが、我々は、間にフリップフロッピングを与えることができます二つの配列。どのように番号が最初に来ている？だから明らかに、ミシェル。だから周りに来て、取るここにあなたの席。そして2番は明らかである次ので、あなたはここに来る。 4番、6番。そして再び、そこにもかかわらず関与歩行を少し、実際に、これらは、瞬時に発生する可能性 - ひとつ移動させることにより [OK]を、よくやった。 [笑い] DAVIDマラン：そして今、我々はしているかなり良い形である。全体の左半分入力は、現在ソートされている。すべての権利なので、これらの人が持っていた私の利点 - それはどのように上のすべての女の子を終わらなかった左と右の上のすべての男の子？ [OK]を、ので、みんな 'は今にしてください。だから私は、順を追ってませんこれらの手順。我々は再適用することができれば我々は、表示されます同じ擬似コード。あなたが先に行くと、立ち上がるしたい場合そして君たちは、私はあなたにマイクを与えてみましょう。あなたは何を複製することはできませんかどうかを確認してください我々だけでここにしましたリストのもう一方の端。誰が、最初に話をする必要があるアルゴリズムに基づいて？だから、前にやっているかを説明あなたは、任意の足の動きを作る。 SPEAKER 1：すべての権利、そう以来私の左半分です左半分は、私が返すこと。右？ DAVIDマラン：良い。 SPEAKER 1：そして - DAVIDマラン：ないマイクは、次に行く？ SPEAKER 1：次の番号。 SPEAKER 2：だから私は右半分だの左半分の左半分、私は戻ります。 DAVIDマラン：良い。あなたが返す。だから今あなたのために横に二人は何ですか？ SPEAKER 2：私たちは小さいです誰が見て欲しい。 DAVIDマラン：その通り。私たちは、マージしたい。我々はマージするために使用するつもりだスペースあなたも、彼らはしているものの、中に明らかにすでにソート、我々は行っている同じアルゴリズムに従うこと。だから、誰が戻って最初に行く？ 3だから、その後7。そして今、マイクが行くこれらの人に、OK？ SPEAKER 3：だから私は右半分だ左半分、私のnがより小さい 1、ので、私はただ合格するつもりです - DAVIDマラン：良い。 SPEAKER 4：私の右半分だ右の右半分の半分、私はよまた一人、私はそう復帰するつもり。だから今我々はマージ。 SPEAKER 3：だから我々は戻って行く。 DAVIDマラン：だからあなたが戻って入る。だから、5、8、その後、最初に行く。であり、現在観客、我々は今、巻き戻ししなければならない段階戻って私達の心の中に？読者：マージ。 DAVIDマラン：左半分と右のマージオリジナルの左半分の半分。だから今 - とだけ、これは明確にするスペースを少し作るあなたとの間に二人の男。だから今、二つのリストだと、左右。それでは、どのように我々は今、みんなにあなたをマージしない再び席の最前列？図3は、最初に行く。次に5、明らかに。その後7、今8。 [OK]を、今、私たちは何ですか？読者：行っていない。 DAVIDマラン：行っていない、なぜなら明らかに、残りの1ステップがあります。しかし、再び、私はこれを使用している理由 "あなたの心の中で巻き戻し、"のような専門用語それが本当にだから、それはだ何が起こっている。我々は、これらの手順のすべてを行っているしかし、我々のために一時停止のようなものだ深く瞬間、ダイビングアルゴリズム、一瞬一時停止、アルゴリズムに深く、そしてダイビング今、我々は我々の巻き戻しのようなものする必要があります心とこれらの層のすべてを元に戻す私たちは、ソートの保留にしたこと。だから今我々はサイズ4の2つのリストを持っている。君たちは、最後にもう一度立ち上がることができればとここまでの空間を少し作るこれが左であることを明確にするオリジナルの半分オリジナルの右半分。誰が最初の数字だと、私たち背面にプルする必要がありますか？もちろんミシェル、。だから私たちはここでミシェルを置く。誰がナンバー2を持っている？番号2は、同様に背面に来る。数3？優秀。 4番、5番、6番、 7番、および8番。 [OK]を、ので、たくさんのように感じたステップの、確かに。しかし、今、我々は確認することができないかどうかを確認してみましょう直感的に、この種の根本的に、特にとしてアルゴリズム nは、私たちが見てきたように、本当に大きくなりアニメーションであり、根本的に速くなります。だから私は最悪で、このアルゴリズムを主張最良のケースでケースとさえ、 n回ログのnのビッグOです。つまり、本のいくつかの側面があり n個の手順がかかりますが、アルゴリズム別の態様は、どこかにありその繰り返し、そのループ、そのログnステップをとります。我々はどのようなものに我々の指を置くことができます 2つの数値はを参照している？さて、どこに - マイクはどこでしょう？ SPEAKER 1：ログnのだろう二つに私たちを壊す - 本質的には、2で割る。 DAVIDマラン：その通り。我々はこのように、任意のアルゴリズムを参照してくださいいつでもまでのところ、このパターンがあっただ分割、分割、分割。そしてそれは通常、削減だ何かへ対数、ログベース2。しかし、それは本当に、何もすることができるしかし、ベース2を記録。今、nはどうですか？私は、我々は一種のことを分けていることがわかりますみんな - あなたを分け、あなたに分け、あなたを分け、分けた。終わりはどこから来るのでしょうか？だから、マージです。なぜならそれについて考える。あなたは一緒に8人をマージすると、それによってそれらの半分4のセットですそして残りの半分は別です 4のセット、あなたはどのように行くのですかマージをしてはどうでしょうか？さて、皆さんはそれをやったかなり直感的。しかし、私はその代わりに、もう少しそれをしなかった場合念入りに、私が指さしたかもしれない私の左の最初の一番左の人一番左の方を指差し手、私の右手でその半分の、とただその後を歩い最小の要素を指すリスト、たびに、私の指を上を移動し、リストを通して、必要に応じてオーバー。しかし、これは合併に関する重要なものだプロセスは、私はこれらのペアを比較していますです要素。右半分から左から半分、私は一度バックトラックはないよ。マージ自体は取っているので、 Nステップ以上のものはありません。そして、どのように何回は、私が持っていたマージそれを行うには？さて、nより多くの、いや、私たちだけ最後のマージとのことを見た。そして、あなたは取る何かをする場合、nはn回のステップ、またはその逆を記録するそれは私たちn回ログnを与えるために起こっている。そして、なぜこれが良いですか？さて、私たちはすでにそのログを知っていれば右 - nはnより良いですか？我々は、二分探索で電話帳を見たたとえば、ログnは間違いだったリニアよりも良い。だから、nはn回ログを意味する n回別のものより間違いなく良い nは、AKA nの二乗。そして、それは我々が最終的に感じるものだ。拍手のそれほど大きく丸い、もし我々はこれらの人については、可能性。 [拍手] DAVIDマラン：そして、あなたの別れの贈り物 - あなたには、数値を保つかもしれないご希望の場合。そして、あなたの別れの贈り物、いつものように。ああ、と私たちはあなたを送信します映像、ミシェル。ありがとう。わかりました。ストレスボールをご自由にお召し上がりください。そして、私はその間に、プルアップしてみましょう提供する私たちの友人ロブボーデンこの上にやや異なる視点、あなたは、これらを考えることができるので幾分で起こっ手順別の方法。約ロブは何のために実際には、セットアップ私たちがしたことを前提としています表示する既に分割までの完了 8小さなリストに大きなリスト、サイズ1の各。だから我々は、擬似コード変更している少しだけで得るのソートするどのようにマージする作品の核となるアイデア。しかし、何の実行時間彼はまだ行うについてです同じになるだろう。そして再び、ここでセットアップは、彼があるということですサイズ1の8リストを始め。だから、彼はだ部分を見逃している実際にログnを、n個のログは、ログNをやっ入力の分割。 [ビデオの再生] - すなわち、ステップ1のためのそれだ。繰り返しステップ2、のためにリストのペアをマージ。 DAVIDマラン：フム。音声のみが来ている私のコンピュータのうち、。のは、再びこれを試してみましょう。 - ただ、任意になるを選ぶ - 今、私たちは4つのリストを持っている。前に学んでください。 DAVIDマラン：あり私達は行く。 - マージ108と15を、私たちは終わるポップアップリスト15、108と。我々は、50と4のマージ 4、50で終わる。我々は、8と42のマージ 8、42で終わる。そして、私たちは、23と16をマージ 16、23で終わる。これで、すべて私たちのリストには、サイズが2である。それぞれのことに注意してください 4つのリストがソートされます。だから我々は、マージを開始することができます再びリストのペア。我々は、15と108と4と50のマージまず、その15、4を取る 50、次に108。、8、42と16のマージ23、我々は最初に取るその後その後8、16、23、その後42。だから今我々は、サイズのちょうど2つのリストを持っているソートされてその各々4。だから今我々は、これらの2つのリストをマージします。まず、我々は4を取ること、そして私達は取る 8、次に我々は、その後、16その後、15を取るその後その後その後、23、42、50、108。 [ENDビデオ再生] DAVIDマラン：繰り返しになりますが、予告、彼は決して与えられたカップ2回以上触れそれを越えて前進した後。そこで彼は、繰り返すことのない。そこで彼は、いつも側に動いて、私たちはn個を得たところ、それはです。なぜ私が1アニメーションをプルアップすることはできませ我々は前に見たことが、今回マージソートにのみ焦点を当てています。私が先に行くと、拡大しましょうこのここにいます。まず、私はランダムな入力を選択してみましょうこれを拡大して、あなたが見るの並べ替えることができます我々は、付与された、以前にかかったのかマージソートは、実際にやっている。ですから、これらの半分を取得したりすることに気づくこれらの四半期またはこれらの8分問題はその突然良い形を取り始める。そして最後に、あなたはで見ること最後の最後そのBAM、すべてが一緒にマージされます。したがって、これらは、ちょうど3異なります同じ考え方になります。しかし、単に除算などの主要な洞察力、と、非常に最初のクラスで征服我々は何とか分割することを決めたということでした大きな何かに問題が、中に精神で同一の何かのソート、しかし小さく、より小さいと小さい。考える一種のようになりましたもうひとつの楽しい方法これらについては、にもかかわらず、それはありませんあなたと同じ直感を与えるつもり理解があり、次のアニメーション。だから、これは誰かが一緒に入れてビデオですその関連する異なるのための様々な操作で音挿入ソート、マージソートのために、と他人のカップルのため。だから瞬間に、私はプレーを打つつもりです。それは長い分についてです。そして、あなたはまだ見ることができるにもかかわらずパターンは、することができ、この時間が起こっまた、これらのアルゴリズムがどのように聞こえる異なるとして実行する多少異なるパターン。これは、挿入ソートです。 [TONESはPLAYING] DAVIDマラン：それは再試行されます各要素を挿入するそれが属する場所に。これは、バブルソートです。 [TONESはPLAYING] DAVIDマラン：そして、あなたは手触りの並べ替えることができますそれがやっている方法は比較的少ない作業各ステップで。これは、退屈は鳴るもののようです。 [TONESはPLAYING] DAVIDマラン：これは、選択ソートであり、我々は我々がすることによってする要素を選択する場所何度も何度も何度も通って行くそして冒頭でそれを置く。 [TONESはPLAYING] DAVIDマラン：これはマージソートであり、そのあなたが本当に感じるように開始することができます。 [TONESはPLAYING] [笑い] DAVIDマラン：ノームと呼ばれるもの我々は見ていないソート、。 [TONESはPLAYING] DAVIDマラン：だから、今、私は見てみましょうあなたがうまくいけばであるように気を取られ音楽、私は少しをすり抜けることができる場合ここで数学のビット。だから私たちにできること第四の方法はありませそれはこれらの何を意味するのかを考えるものより速くなるための関数我々は前に見てきた。そして、あなたはからコースで来ている場合数学の背景に、実際に既におそらく知っているあなたこのテクニックに言葉を平手打ちすることができます - すなわち再帰は、関数それは何とか自分自身を呼び出します。そして再び、そのマージソートを思い出す擬似コードは、ある意味で再帰的だったマージソートのステップのその1 ソートを呼び出すことだった - それは、それ自体である。しかし、ありがたいことに、我々は維持しているため呼び出しソート、またはマージソート、具体的には、小さく上最終的には、より小さいリスト、我々我々は呼ぶことに何の底入れおかげベースケース、ハードコードされた場合、その 2未満、リストが小さい場合には前記その場合は、単にすぐに戻ります。我々は特殊なケースを持っていなかった場合は、アルゴリズムは底打ち、決してそして、あなたは確かになるだろう本当に永遠に無限ループ。しかし、我々はすぐに入れたかったと仮定この上でいくつかの数字は、再び、Nを使用して入力の大きさ。そして、私は何、お聞きしたかったに関与して合計時間マージソートを実行している？またはより一般的には、何時間のそれのコスト？まあそれはそれを測定することは非常に簡単です。 nが2未満の場合、時間が関与 n個の要素をソートするには、 nが2である場合、0である。私達はちょうど戻るので。完了すべき仕事がありません。今、間違いなく、多分それは一歩または2の量を把握するための手順仕事、それが0に近い十分だ私は全く仕事がありませんと言うつもりですリストが非常に小さい場合に必要面白くする。しかし、このケースは、興味深いです。再帰的な場合は、支店であった他に言った擬似コード、ソート左半分は、右を並べ替える半分、半分ずつをマージ。今、この式はなぜその費用を表す？さて、nはTだけで意味 n個の要素を並べ替えるための時間。その後の右側にそこ等号、nはTが分割 2で何のコストを参照している？左半分のソート。 2分周nは他のTであるおそらくのコストを参照する右半分を並べ替える。そしてプラスさn？マージされています。なぜなら、2つのリストのいずれかを持っている場合サイズn 2以上と別のサイズのN 2かけ、あなたは本質的に触れなければならないただロブのように、これらの要素のそれぞれ、コップのそれぞれに触れた、とだけ我々はそれぞれに指摘したようにステージ上でボランティア。だからnはマージの費用です。さて、残念ながら、この式再帰的にも、それ自体である。 nがあれば、と言う、、質問をしそうだとすれば 16、ステージ上の16人がある場合ビデオ、どのように多くの合計16杯またはそれらをソートする手順は時間がかかりますかマージソートと？それは、実際に明白な答えはありません今、あなたは、ソートする必要があるため再帰的に次の式を答えます。私が提案させているのでしかし、それは、OKだ私たちは、次の作業を行うこと。 16人をソートしたりするために必要な時間 16カップが表現されようとしている一般的には16のTのように。しかし、それは私たちによると、等しい前の式、2倍の量時間がそれを並べ替えにかかる 8カッププラス16。そして再び、プラス16は、マージする時間ですと8のT 2回です左半分と右半分をソートする時間。しかし、再び、これは十分ではありません。我々はより深くに潜る必要があります。これは、我々が答えなければならないことを意味質問8のTは何ですか？まあ8のTは、ちょうど2である 4プラス8倍T。まあ、4のTは何ですか？ 4のTは、2プラス4のちょうど2倍のTです。まあ、2のTは何ですか？ 2のTは、1プラス2のちょうど2倍のTです。そして再び、我々は得ることのようなものだこのサイクルで立ち往生。しかし、それは、約ヒットするだいわゆるベースケース。 1のT何なので、私たちは主張したのですか？ 0。だから今ようやく、我々は後方に動作することができます。 1のTが0である場合、私は今まで1戻ることができますここにこの男へのライン、私はすることができます 1のTは0のプラグイン。だから、それが2回ゼロに等しいことを意味するそうでなければ0、プラス2として知られています。となるように式全体は2です。今、私は答え2のTを取る場合 2ですが、真ん中のライン、Tに差し込む 4の、それは私を2回与える 2プラス4,8そう。私は、前に8に接続する場合行、それは私を2回8、16を与えます。そして、私たちはその後、とそれを継続する場合 24は、16に追加して、我々は最終的に得る 64の値。今の、それ自体のソートが話すこと n個の表記には何もない、ビッグO、私たちがしたことをオメガについて話して。しかし、それは64が確かであることが判明 16、入力のサイズ、 16のベース2を記録。そして、これは、ちょっと不慣れである場合だけ背中と思うし、それが戻ってくる最終的にあなたに。これは、ログベース2の場合は、2のようなものだあなたに16を与えるものに上げて？ああ、それは4つなので、それは16倍4です。そして再び、それは大したことではありませんこの場合かすんでメモリの一種は今です。しかし、今のところ、信仰を取る 16ログ16が64であること。そして確かに、この単純な正気とチェックし、我々は確認しました - しかし、正式に証明されていない - そのマージの実行時間ソートは確かにあるN Nを記録。そんなに悪くない。それよりも間違いなく良いです我々はこれまで見てきたアルゴリズム、私たちが活用してきたので、それは、一つだ再帰と呼ばれる技術。しかし、それよりも興味深い、その分割と征服の概念。繰り返しになりますが、本当に0週のものという今でもで再発されてもっと説得力のある方法。あなたがしている場合はすぐに楽しい小さな運動、これをやったことがない - と、おそらくあなた通常の一種のため、持っていないでしょう人々はこれを行うには思わない。しかし、私はgoogle.comに行く場合となら私について何かを学びたい再帰は、入力します。 [笑い] [MORE笑い] DAVIDマラン：悪い冗談ゆっくり拡散。 [笑い] DAVIDマラン：念のために、それがある。私はそれが間違ってスペルしませんでした、と冗談はあり。わかりました。あなたの隣の人々にそれを説明する場合それはかなりただまだクリックされていません。しかし、再帰は、より一般的には言及呼び出し元の関数のプロセスにそれ自体、又はより一般的には、分割するすることができます何かに問題同じ解くことにより、少しずつ解決代表的な問題。まあ、みましょうチェンジギアちょっと。我々は、特定のcliffhangersに終了したいと、ように設定することから始めましょう舞台、数分間、非常にシンプルなアイデアで - 2つの要素をスワッピングのもの、右？我々がしてきたこれらのアルゴリズムのすべて過去のカップルの話講義では、いくつかを含むスワッピングの一種。今日、それは彼らが取得することによって可視化したアップする彼らの椅子のうち、と歩き回ったが、コードの中で、我々はだろう一つの配列から要素を取ると別のものにウンチそれ。だから我々はこれをやってどうやって行くのですか？まあ、私が先に行くと書いてみましょうここで簡単にプログラム。私が先に行くとするつもりですこの次のよう。これを呼び出してみましょう - 我々はこの1つを呼び出すために何をしたいですか？実際には、ない。私は巻き戻してみましょう。私はそれを行うにはしたくないまだ接戦。それは楽しみを台無しにします。代わりにこれを実行してみましょう。私は少しを書きたいと仮定プログラムは、それが今ではこれを包含再帰のアイデア。私は種類のそこに先んじて自分の得た。私は、次の操作を実行するつもりです。まず、クイックは、標準io.hののインクルード cs50.h.のと同様に、インクルードそして私は先に行くつもりですとint主無効を宣言通常の方法である。私は、私は、ファイルの名前が間違ってきた実現私はちょうどここにそう。C拡張を追加してみましょう我々はそれを正しくコンパイルすることができます。この機能をオフに起動します。私はかなり、書きたいと機能単に、尋ね一つですその後数のユーザーとは、加算その間のすべての数字番号と、言う、0。だから最初に私が先に行くつもりですとint nを宣言します。それから私はいくつかのコードをコピーしてその我々はしばらくの間使用してきました。何かが真である間。私は瞬間にそれに戻ってくる。私が何をしたいのですか？私はprintfの肯定言いたい整数でお願いします。そして私はするつもりです言うnはint型を取得し取得します。だからもう一度、いくつかの定型コード我々は前に使用したこと。そして、私はこれを行うつもりだ nが1未満でいる。だから、これは、ユーザーことが保証されます私に正の整数を与えます。そして今、私は次の操作を実行するつもりです。私は数字のすべてを追加したい Nまたは0であり、nは1〜と、同等に、合計を取得します。だから大きなシグマ記号あなたが思い出すかもしれない。だから私は、最初の呼び出しでこれを行うつもりだシグマと呼ばれる機能、 Nでそれを渡して、それから私はするつもりです printfの言う、答えはすぐそこです。だから要するに、私が取得し、ユーザーからint型。私はそれがポジティブだことを確認してください。私は、変数と呼ばれる答えを宣言その中にint型とストア復帰入力としてnを渡してシグマの値。そして私はその答えをプリントアウト。残念なことに、シグマが聞こえるにもかかわらずにあるかもしれない何かのように math.hはファイル、その宣言、それは実際にはありません。だからOKです。私はこれを自分で実装することができます。私はと呼ばれる機能を実現するつもりだシグマ、それは取ることになるだろうパラメータ - ただそれだけの男、呼んでみましょうので、それは違う。そして、ここまで、私が言おうとしてんだけど、 mが1未満であればよく、 - これは非常にプログラムを面白くない。だから私は先に行くつもりだとすぐに0を返す。それだけですべてを合計しても意味がありません 1とmの番号mの場合 0または負のそのものです。そして私は先に行くつもりですと非常に反復的にこれを行う。私は、古い学校のこの種のをするつもりですと私は先に行くつもりですと私はするつもりだと言う 0に合計を宣言します。それから私は持っているつもりです int型のループのために - と私はそれが私たちに合うようにやらせる流通コードするので、コピーを持っている自宅で。 int型のiは、最大で1を取得 iがより小さいまたはmに等しい。私はプラスプラス。そして内側のループのためにこのの - 我々は、ほとんどそこにいる - 和は合計プラス1を取得します。そして私は和を返すつもりです。だから私は、すぐにこれをしたかなり確か。しかし、再び、主な機能は、きれいです我々はしたコードに基づいて、簡単なこれまで書かれた。肯定を得るために二重のループを使用してユーザーからint型。私はその後、新しい関数にそのint型を渡す nは、再び、それを呼び出して、シグマと呼ばれる。と私は、戻り値は、答えを保存現在はブラックボックスから変数に、シグマとして知ら答えと呼ばれる。それから私は、それを印刷。私たちは今の話を続けると、シグマはどのように実装されている？私は、次のように実装することを提案する。エラーチェックの最初、少しユーザーがないことを確認し私と一緒にいじりとを渡すいくつかの負の値または0の値。それから私はと呼ばれる変数を宣言合計し、それを0に設定します。そして今、私は私が等しいから動き始める 1までであり、mを含むすべての方法、私はすべて含まれるようにしたいので M、包括を通じて1からの数字。と内側のforループは、この、私はただやる合計は、それが今は何でもなる、プラス iの値。プラスiの値。余談として、あなたがこれを見ていないした場合前に、いくつかのシンタックスシュガーはありこのラインのため。プラスは、私に等しいように私は、これを書き換えることができますただ自分自身にいくつかのキーストロークを保存すると少しクーラーを探すために。しかし、それはすべてです。それは機能的に同じものです。残念なことに、このコードのまだコンパイルするつもりはありません。私はどのようにシグマは0を、makeを実行する場合私は怒鳴ら取得するつもり？何が好きではないために起こっている？読者：[聞こえない]。 DAVIDマラン：ええ、私は宣言していない右上アップ機能、？ Cはそれだけという点で、愚かなの一種であるあなたはそれが何を言うことありませんし、そのためにはそれをしなければならない。私はここに入力してヒットした場合などは、私はするつもりですシグマについての警告が暗黙の取得宣言。ああ、問題ない。私は頂上まで行くことができ、私はすることができます大丈夫、と言う、ちょっと待って。シグマは返す関数です。 int型とそれは期待し入力、セミコロンとしてint型。または私は全体の機能を置くことができメイン上、しかし、一般的に、私は思いますそれはだから、それに対してお勧めいつも一番上にメインがあると便利あなたは右に飛び込むと知ることができるのかプログラムは最初にメイン読んでやっている。だから今、私は画面をクリアしましょう。リメイクシグマ0。すべてがチェックアウトするように思われる。私はシグマ0を実行してみましょう。正のインター。私はそれを数をあげるそれをシンプルに保つための3。だから私に3を与える必要がありますプラス2に1を加えたので、6。入力して、確かに私は6を得る。私は何か大きなものを行うことができます - 50、12、75。ただ接線として、私はするつもりです本当に大きなようなとんでもないもの番号、ああ、実際に働いた - ええ、私はそうだとは思わない。見てみましょう。実際にそれを台無しにしてみましょう。それが問題です。どうなってるの？コードは、悪くはない。それはまだ直線です。口笛はいえ、良い効果です。どうなってるの？私はそれを聞いたかどうかわからない。だから、判明 - とこれは脇の通りです。これは、コアではない再帰のアイデア。私がしようとしているので、それは判明、このような大きな数を表す最もおそらくそれが誤解されている正でない数としてCによって、しかし、負の数。我々はこれについて話が、それていない負の数があるが判明加えて、世界で正の数に。そして、あなたがすることができる手段負の数を表す本質的には、いずれかを使用しているを示すために、特別なビット負のオーバーポジティブ。それは、それよりも少し複雑だそれは基本的な考え方です。だから残念ながら、Cが1を混乱されている場合は実際の意味として、これらのビットの、ああ、これが、私のループ負の数であるここで、例えば、実際になることはありません終了する予定。私は実際に何かを印刷していたのであれば何度も何度も、我々はだろう全体の多くを参照してください。しかし、再び、この点以外にある。これは本当にただの一種である私たちが来ることを知的好奇心最終的にバックアップします。しかし、今のところ、これは正しいです我々は仮定した場合の実装ユーザが整数を提供するそのint型に収まる。しかし、私は率直に言って、そのコードを主張する、そんなにより簡単に行うことができます。手元の目標は数字を取るのであればのような、mとのすべてを追加それは1、あるいは逆の数字 1間と、私が主張私はマージこのアイデアを借りることができますソートは、問題を取った、持っていたこのサイズの、それを割る小さいものに。多分半分が、小さくないが、代表的に同じ。同じ考えですが、小さい問題。だから私は、実際にしている - 私は、このファイルを保存してみましょう異なるバージョン番号を持つ。私たちは、このバージョンを呼ぶことにします 1の代わりに0。そして私は私が実際にできることを主張この種でこれを再実装心曲げ方法。私は一人でその一部を残すつもりです。 mが小さければ私は言うつもりです 0に等しい以上、あるいは - 私はほんの少しになるつもりですもっと肛門今回 - 私のエラーチェックと私が先に行くと0を返すつもりです。これは任意である。私は、単にユーザかどうかを決定しています私に負の数を与え、私はよ 0を返します、そして、彼らは読んだことがあるはずドキュメントをより密接に。他の - 私がやろうとしているものに気づく。他の私は、Mプラスを返すつもりです - Mのシグマは何ですか？まあ、MプラスMマイナス1シグマ、プラスMマイナス2、プラスマイナス3メートル。私は、そのうちのすべてを記述する必要はありません。なぜ私はちょうどパントませんか？再帰的に少し自分自身を呼び出す小さい問題、セミコロン、その日を呼び出す？右？今ここでは、あまりにも、あなたが感じたり、心配かもしれませんこれは私がだと無限ループであること私が実装していますそれによって誘導、呼び出しシグマによってシグマ。しかし、それは私がいるので、完全にOKだどの行を追加先にと思った？読者：[聞こえない]。 DAVIDマラン：23から26、その私の場合の条件です。についての素晴らしい何ので私は続けるので、ここで減算、小さく、シグマより小さい問題を渡す問題は、小さい - そうではありません半分のサイズ。それは、小さいだけで赤ちゃんの一歩だそれはOKです。結局、我々はうまくいくのでダウンして1または0に我々の方法。そして、かつて我々は0を打つ、シグマではありませんもはや自分自身を呼び出すつもり。それはすぐに0を返すようになるだろう。だから効果は、風のソートこの場合まであなたの心に、Mプラスを追加することです Mマイナス1、プラスMマイナス2、プラスMマイナス 3、プラスドット、ドット、ドット、mはマイナス最終的に0と与え、M、効果は、すべてのを追加するには最終的にある一緒にこれらの事。だから私たちは、再帰ではなく、持っている我々はその問題解決前に解決することができませんでした。確かに、このバージョンの0、およびすべてのこれまでの問題は、解決可能であった単にループを使用してまたはwhile ループまたは類似の構造物。しかし、再帰が、私はあえて、私たちを与えるについて考える別の方法問題は、それによって我々が取ることができる場合問題は、何かからそれを分ける何かにやや大きいやや小さく、私たちはそれを解決することができていると主張おそらく、もう少しエレガントに言葉でデザインの、少ないコードで、そして多分だろうな問題を解決我々は最終的に説明するように、難しくなる純粋に反復して解く、を参照してください。私がしたことしかし接戦上で私たちを残したいのはこれだった。私が先に行くと、開いてみようからファイルをバックアップします - 実際に、私が手放すとこの本当の高速を行う。私が先に行くと提案してみましょう次。今日のコードの中では、このファイルはここにあります。ここではこのいずれか、NOSWAP。だから、これはその愚かな小さなプログラムです。私は、クレームがすることを手早く次。メインでは、それは最初に宣言しています int型は、Xと呼ばれ、それを割り当て 1の値。それはint型、yを宣言し、それに値2を割り当てます。それは、xとyが何であるかを出力します。それは、ドットドットドットを交換、と言います。それは関数を呼び出すことが主張 Xを渡し、スワップと呼ばれ、 yは、そのうまくなっているという考え方 xとyは戻ってくるだろう反対に、異なる。それはスワップ主張！感嘆符が付いた。それは、xとyを出力します。しかし、それはまさにこのことが判明簡単なデモダウンここでは実際にバグがある。私は一時的に宣言しているにもかかわらず変数と一時的に入れてそれは、私は再割り当てしています bの値 - その私がきたので、合理的な感じ温度でのコピーを保存した。それから私は平等に、Bを更新一時にどんなだった。移動のシェルゲームのこの種 BとBににこれを使用することにより気温が感じると呼ばれる中年の男完全に合理的。私はこれを実行したときにしかし、私はあることを主張コードは、私は今やるとして - 私が先に行くと、ここに貼り付けましょう。私はこのnoswap.cと呼ぶことにします。名前が示すようにと、これではありません正しいプログラムになるだろう。 NOSWAP。/いいえスワップを行いません。 xは1であり、yが2であり、スワッピング、スワップ。 xは1であり、yは2である。これがあっても、根本的に間違っているこれは完全にそうですけれども私には合理的。そして、そこに理由がありますが、私たちではないただまだその理由を明らかにする予定。私が欲しかった第二接戦今のところを残すためには、これですクーポンコードの一種のアナウンス。遅い日と私たちの技術革新は、今年非自明な番号を引き起こしている質問の、どのだったなく、私たちの意思。これらのクーポンコードの意図、それによってあなたは、問題の一部を行う場合、それによって余分な日を取得、早期に設定する君たちが助けて支援する実際にあった自分では、早期のソートを開始あなたを奨励することである。私たちは全体の負荷を分散させるのに役立ちます営業時間は、より良いようにそれは、win-winのようなものです。残念ながら、私は私の指示だと思いますそう、今日まで、非常に明確ではなかった私はこの週末に戻って、更新されに大きく、大胆なテキストでスペックこれらのような弾丸を説明します。そして、ちょうどすることにより、より多くの公的にそれを言うためにデフォルトでは、問題セットは木曜日によるものである正午に、シラバス当たり。あなたの一部を終え、早期に開始した場合 12:00水曜日まで設定問題 PM、クーポンに関し、一部コードは、アイデアは、あなたが拡張できるということですについては、締め切り Pは金曜日までセット。そのビットPの小さな部分から、ある一般的に何であるかを基準に設定する大きな問題は、あなたが買う自分で余分な日。繰り返しになりますが、それは考えるあなたを取得問題セットにあなたを取得営業時間は早くなります。しかし、クーポンコードの問題がまだあるあなたがそれを提出しない場合でも、必要とした。しかし、もっと説得力これです。（STAGEウィスパー）そして、それらの人々が残し早期にそれを後悔するつもりです。としてバルコニーに人々がいます。上の人々に、事前に私に謝罪なりの理由でバルコニーほんの一瞬でクリア。だから私たちは、次のいずれかを持っている幸運です CS50の元頭ティーチングフェローで dropbox.comという会社。彼らは非常に寛大に寄付していますこのくらいのスペースはこちらのクーポンコード、からなる次第ですいつもの2ギガバイト。だから私たちは、この上で行うだろうと思ったのか最後のノートでは、景品のビットを行うさほんの一瞬では、我々は明らかにすることにより、勝者と誰がクーポンを持っているあなたがして、それらに行くことができることをコードウェブサイトでそれを入力し、出来上がりは、取得あなたのための全体の多くのDropboxの容量アプライアンスとあなたの個人的なファイルのために。と参加したいと思います最初は、この図では？ [OK]を、今ではそれはそれはさらに楽しくなります。この25ギガバイトを受ける者クーポンコード - 遠いです後半よりも説得力のある今、おそらく日 - の上部に装着されているものであるが存在する下シートクッションそのクーポンコード。あなたは今、下に見えるかもしれませんあなたのシートクッション。 [ビデオの再生] - 1つ、2つ、3つ。 [SCREAMING] - あなたは車を取得！あなたは車を入手！ DAVIDマラン：我々は、表示されます水曜日にあなた。 - あなたは車を取得！あなたは車を入手！あなたは車を入手！あなたは車を入手！あなたは車を入手！ DAVIDマラン：バルコニー人々は、来るダウンここでフロントに、どこに私たちは余分を持っている。 - 誰もが車を取得！誰もが車を取得！ [ENDビデオ再生] ナレーター：次CS50で - SPEAKER 5：おやっおやっおやっおやっ私のああおやっおやっおやっおやっおやっおやっ - [ウクレレPLAYS]