>> [音楽再生]
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]