[音楽再生] 教授：すべての権利。 これはCS50であり、これは 週3の終わり。 だから我々はないサンダースに、今日ここにいます 代わりにWeidnerライブラリの劇場、。 これの内部スタジオ ハウザーメーカーとして知られています、 または私達はメーカーHを言う、または条ばなりません あなたがそのジョークを楽しんでいる場合、私たちは、say-- それから、実際のです 同級生、マーク、オンライン、 誰がTwitterでできるだけ多くを示唆しました。 今は約クールなものです スタジオでここにいます 私はこれらの緑に囲まれているということです 壁、グリーンスクリーンやクロマキー、 そうCS50のことを意味し、話すこと 私には知られていない制作チーム、 今、パッティングすることができ 私ほとんどの世界のどこかで、 良くも悪くもため。 今どのような問題が設定され、待ち受け 二人は、この一週間のためにあなたの手の中にあります しかし、問題に設定 3この来週、 あなたが挑戦されます 15のいわゆるゲーム、 その古いパーティーの好意 あなたが受信思い出すかもしれません 全体の束を持っている子として 上下にスライドできる数の、 左右、および1つのギャップがあります パズルの中、あなたのその中に 実際に、これらのパズルのピースをスライドさせることができます。 最終的にあなたがこれを受け取ります いくつかのセミランダムな順序でパズル、 そして目標はです ソートそれ、上から下へ、 1から、左から右へ 最大15までのすべての方法。 残念ながら、実装 あなたは手元にあります ソフトウェアになるだろう ベースではなく、物理的に。 あなたが実際に書き込みする必要があるとしています コー​​ドを使用して、学生やユーザ缶 15のゲームをプレイ。 そして、実際には、ハッカーで 15のゲームの版、 あなたが実装することが課題になるだろう、 この古い学校だけではなく演奏 ゲームではなく、解決 それを、神モードを実装し、 その結果、実際に、話すこと 人間のためのパズルを解き、 ヒントを提供することにより、 ヒント後に、ヒントの後。 だから、より多くのその次の週に。 しかし、それは先にあるものです。 今のことを思い出して、今週初めに あなたがする場合は、我々は、この接戦を持っていました、 それによって私たちはソートしていた最高の 賢明は、nのO大の上限でした 乗。 換言すれば、バブルソート、 選択ソート、挿入ソート、 それらのすべて、異なるしばらく それらの実装において、 実行中の乗n個に権限を委譲 非常に最悪の場合の時間。 そして、我々は一般的にあると仮定 ソートするための非常に最悪のケース そのあなたの入力の一つです 完全に後ろ向きになります。 そして実際、それは非常にいくつかの手順を取りました これらのアルゴリズムのそれぞれを実装します。 今クラスの最後に リコール、我々はバブルソートを比較しました 他の1に対して選択ソートに対する 我々は一度にマージソートと呼ばれています、 私はそれが取っていることを提案します 週のレッスンの利点 ゼロ、分割統治。 そしてどういうわけかのいくつかの種類を達成 対数最終的に時間を実行して、 代わりに何かの それは純粋に二次です。 そしてそれは、かなり対数ではありません それはそれよりもう少しです。 しかし、あなたはクラスから思い出すと、 それははるかに速く、はるかにました。 我々は中断した場所を見てみましょう。 選択対バブルソート ソートマージソート対。 今、彼らはすべての中で、実行しています 理論、同時に。 CPUが同じ速度で実行されています。 しかし、あなたはこれをどのように退屈を感じることができます 非常に迅速になろうと、 そしてどれだけ速く、我々は注入時 0週目のアルゴリズムのビット、 我々は物事をスピードアップすることができます。 だからマークソートは素晴らしい見えます。 どのように我々は、順番に、それを活用することができます より迅速に数字を並べ替えることができます。 まあさんが戻って考えてみましょう 我々成分に のことを、週にゼロに戻っていました 電話帳の誰かを探して、 そして、思い出し 私たちが提案した擬似コード、 これを介して、我々は見つけることができます マイク・スミスのような人、 このような小さなものを見ました。 今、特に見てみましょう ラインで7,8、および10と11、 我々が保持することによりれ、そのループを誘導 再び3行目に行くと、再び、 そして再び。 しかし、それは私たちが見ることができることが判明しました このアルゴリズムは、ここで擬似コードで、 もう少し全体的に。 実際に、私は何を探しています ここで、画面上で、 検索するためのアルゴリズムであります ページのいくつかのセットの中マイク・スミス。 そして実際、我々はこれを簡素化することができ これらの行7と8で、アルゴリズム、 10と11は、ちょうど、これを言って これは私が黄色でここに提示しました。 換言すれば、マイク スミスは、以前の本の中で、 私たちはステップを指定する必要はありません ステップによって、今どのように彼を見つける行きます。 私たちは、指定する必要はありません 3行目に戻って、 なぜ我々はだけではなく、しません、 たとえば、より一般的には、 にマイクを検索 本の左半分。 逆に、マイクがある場合 実際、後に本の中で、 私達はちょうど引用終わり検索を引用していない理由 本の右半分にマイク用。 つまり、なぜ私たちはしません 自分が言うのとパントの並べ替え、 この中にはマイクを検索 本のサブセット、 私たちの既存のに任せます 私たちに伝えるためのアルゴリズム マイクでの検索方法 この本の左半分。 言い換えれば、私たちの このアルゴリズムは、それが動作するかどうかです こののこの厚さの電話帳、 厚さ、またはいかなる厚さ。 だから我々は再帰的にすることができます このアルゴリズムを定義します。 言い換えれば、上 ここで画面は、アルゴリズムであります マイク・スミスを検索します 電話帳のページ間。 だから、7行目および10に、してみましょう まさにそればかり言います。 そして、私はこの言葉の瞬間を使用 前、実際、再帰 今の流行語であり、 それは、このプロセスです 何とかによって周期的な何かをすることの あなたが既に持っているコードを使用して、 そして、それを再び呼び出します そして再び、そして再び。 今では重要になるだろう 我々は何とか底こと アウト、無限に長いことはしてはいけません。 そうでなければ我々はするつもりです 確かに無限ループを持っています。 しかし、我々はこのアイデアを借りることができるかどうかを見てみましょう 再帰の、再び何かをすること そして、何度も何度も、解決するために マージソート経由問題 並べ替え、すべてのより効率的に。 だから私は、あなたがマージソート与えます。 のは、見てみましょう。 そこでここでは擬似コードとは 私たちは、ソートを実装する可能性があります、 マージソートと呼ばれるこのアルゴリズムを使用して。 そしてそれは非常に単純にこれです。 n個の要素の入力時に、 言い換えれば、あなたがしている場合 与えられたn個の要素と数字と 入力されたか、どのような文字、 あなたはn個の要素、もし与えられている場合 nが2未満である、単に返します。 右？ なお、nが2未満であれば理由 つまり、要素の私のリスト サイズ0または1のいずれかであり、かつ これらのささいな例の両方で、 リストはすでにソートされています。 リストがない場合は、ソートされています。 そして、長さのリストがあるかどうか 図1に示すように、それは明らかにソートします。 だから、このアルゴリズムは、次の目的にのみ必要 本当に面白い何かをします、 我々は2つ​​以上を有する場合 私たちに与えられた要素。 それでは、次に、魔法を見てみましょう。 それ以外の要素の左半分を並べ替えます、 その後、要素の右半分を並べ替えます、 その後、ソートされた半分をマージします。 曲げ心のようなものは何ですか ここで、私は本当にないことです あなたに言っているように見えます まだ何も、右か？ すべての私は、のリストを与えられて言いました n個の要素は、左半分を並べ替えます、 右半分は、 ソート半分をマージし、 しかし、ここで実際の秘密のソースは何ですか？ アルゴリズムはどこですか？ まあそれは、これらの二行ことが判明 まず、素子の一種左半分 要素のソート右半分、 再帰呼び出しがあり、いわば。 結局、この時 時点、私が持っています へとアルゴリズム 要素の全体の束を並べ替えますか？ はい。 それはここです。 これは、画面上で右ここだし、 私はステップの同じセットを使用することができます 左半分をソートするには、 私は右半分できますように。 そして実際、再び、そして再び。 だから、どうやら、私たちはすぐによ この、マージソートの魔法を見ます その非常に最終的に埋設されています ライン、ソートされた半分をマージします。 そして、それはかなり直感的なようです。 あなたは、あなたを半分ずつを取り、 何とか、それらを一緒にマージし、 私たちはこれを参照してくださいよ 具体的瞬間インチ しかし、これは完全なアルゴリズムです。 そしてのは、正確な理由を見てみましょう。 さて、我々はこれらの同じを与えられていると仮定 画面上でここに8要素、1 8を介して、しかし、彼らはしています 一見ランダムなためです。 そして、手元の目標です これらの要素をソートします。 さてどのように私は約行くことができます 再び、使用してそれをやって、 この擬似コードごとに、マージソート？ そして再び、この中に深く根付きました あなたの心、ちょっと。 最初のケースはかなりあります 些細な、それが2未満だと、 ただなすべき仕事は決してありません、戻ります。 だから、実際には3あります 本当に心に留めておくべき手順。 ここでも、再度、私は 持つようにするつもり 左半分をソートするには、 右半分を並べ替えます、 して、その一回 二つの半分は、ソートされています 私はそれらを一緒にマージしたいです 1ソートされたリストに。 だから、心の中でそれを維持します。 そこでここでは、元のリストです。 それでは、としてこれを扱いましょう 配列、我々が始めました 2週では、これは メモリの連続ブロック。 この場合には、8つを含みます 数字は、背中合わせにバックアップします。 そして今度は、マージソートを適用してみましょう。 だから私は最初にソートしたいです このリストの左半分、 、したがって、してみましょう 4、8,6、および2に焦点を当てます。 今どのように私は約行きます サイズ4のリストをソートしますか？ さて、私は今考えなければなりません 左半分の左を並べ替え。 ここでも、のはちょっと巻き戻してみましょう。 擬似コードは、これである場合、 私は、8つの要素が与えられています、 8は明らかに大きく、 よりまたは2に等しいです。 だから、最初のケースでは適用されません。 だから、最初の8つの要素は、私をソートします 要素の左半分を並べ替えます 私は、私は、マージ、右半分を並べ替えます 2つのソートの半分、サイズ4の各。 OK。 しかし、あなたはちょうど私に言ってきた場合には、並べ替えます 今サイズ4である左半分、 どのように私は左半分を並べ替えるのですか？ さて、私が持っている場合 四つの要素の入力、 私は最初の左を並べ替えます 2、右2、 そして私はそれらを一緒にマージされます。 だから、再び、それは少しになります ここでゲームを曲げ心の、 あなたは、一種の、する必要があるため、 あなたが物語のどこにいるかを覚えて、 しかし、一日の終わりに、 任意の数の要素が与えられ、 あなたが最初にソートしたいです 左半分、右半分、 その後、それらを一緒にマージされます。 のは、まさにそれを行うために始めましょう。 ここでは8要素の入力です。 今、私たちはここで左半分を見ています。 どのように私は、4つの要素をソートしていますか？ さて、私は、最初の左半分を並べ替えます。 今どのように私は左半分を並べ替えるのですか？ さて、私は2つの要素を与えられてきました。 それでは、この2つの要素をソートしてみましょう。 2は以上 もちろん、2に等しいです。 だから、最初のケースでは適用されません。 だから私は今、左をソートする必要があり この2つの要素の半分。 左半分には、もちろん、わずか4です。 それでは、どのよう私は1つの要素のリストをソートしますか？ さて、その特別な基本ケース トップアップ、いわば、適用されます。 1は2未満であり、私の リストには、実際のサイズ1のです。 だから、僕は返します。 私は何もしません。 そして実際、私がしてきたことを見て 行われ、4がすでにソートされています。 私はすでにてるよう ここでは部分的に成功。 今では種類の愚かなようです 主張するが、それは本当ですします。 図4は、大きさ1のリストです。 これは、すでにソートです。 それは左半分です。 今、私は右半分を並べ替えます。 私の入力は8、一つの要素であります 同様に、すでにソート。 あまりにも、愚かな、しかし、再び、 この基本原理 私たちは今、構築できるように起こっています この成功したの上に。 4は現在、8がソートされ、ソート その最後のステップは何でしたか？ だから、3番目と最後のステップ、任意の リスト、リコールをソートしている時、 二つの部分をマージすることでした、 左右。 それでは、まさにそれをやらせます。 私の左半分には、もちろん、4です。 私の右半分は8です。 それでは、これを実行してみましょう。 最初に私は割り当てするつもりです いくつかの追加のメモリ、 私はここに表すだろうと、 ただ、二次配列として、 それは、これをフィットするのに十分な大きさです。 しかし、あなたは延長想像することができます その長方形の全長、 我々はより多くの後に必要がある場合。 私は4取り、8、およびマージするにはどうすればよいです サイズ1のものと二つのリスト一緒に？ ここでは、あまりにも、非常にシンプル。 4は、その後、最初に来る8を付属しています。 私はソートする場合ので、 左半分、右半分、 次にそれらの二つの部分をマージ 一緒に、ソート順で、 4は、その後、最初に来る8を付属しています。 だから、私たちも、進歩しているように見えます 私は実際の作業を行っていないのに。 私達は物語の中でどこでも覚えています。 私たちは、もともと8要素を取りました。 私たちは4で左半分を、ソート。 その後、我々は左半分をソート 2であった左半分の。 そしてここで私達は行きます。 私たちはそのステップで完了です。 だから我々は、ソートした場合 我々は今、2の左半分 2の右半分をソートする必要があります。 だから2の右半分であります ここでこれらの2つの値、6 2。 それでは、今のサイズの入力をみましょう 図2は、その後、左半分を並べ替えると、 右半分、その後、 それらを一緒にマージされます。 さてどのように私は、サイズのリストを並べ替えます 1、ちょうど数6を含みますか？ 私はすでに行われています。 サイズ1のそのリストがソートされます。 私は別のリストをソートするにはどうすればよいです サイズ1、いわゆる右半分。 まあそれは、あまりにも、すでにソートされています。 数2は一人です。 だから今、私は二つの部分を持って、左と 右、私はそれらを一緒にマージする必要があります。 私は自分自身にいくつかの余分なスペースを与えてみましょう。 そして、そこに2を入れ その後、6そこに、それによって、 そのリストを並べ替え、左右 そして最終的に、それを一緒にマージします。 だから私は少し良い形でね。 私は、行っているためではないよ、明らかに4、8、2、 図6は、私が欲しい最後の順序ではありません。 しかし、私は今、その大きさ2の2つのリストを持っています 両方、それぞれ、ソートされています。 だから今、あなたはあなたの心の中に巻き戻した場合 目、それは私たちを残しましたか？ 私はその後、8要素で開始私 、4の左半分に絞り込ま その後、2の左半分と、 2の右半分、 私は左を並べ替え、したがって、終了しました 2の半分、及び2の右半分、 ので、ここで3番目と最後のステップは何ですか？ 私は一緒にマージする必要があります サイズ2の二つのリスト。 それでは、先に行きましょう。 そして、ここで画面上に、与えます 私いくつかの追加のメモリ、 技術的にも、私がしたことに気づきます トップアップ空白の全体の束を持って そこ。 私は特にになりたい場合 効率的なスペース賢いです、 私は要素の移動を開始できました 前後に上下。 しかし、単に視覚的に分かりやすくするために、 私は、以下のそれを置くつもりです きれいなものを維持します。 だから私は、サイズ2の2つのリストを持っています。 最初のリストには、4​​と8を持っています。 第2のリストは、2と6を有します。 それでは、それらをマージしてみましょう 一緒にソートされたためです。 図2は、もちろん、最初に来ます その後4、その後6、その後8。 そして今、我々はなっているように見えます どこか興味深いです。 今、私はの半分をソートしました リスト、そして偶然、それはです すべての偶数が、その 、確かに、単なる偶然です。 そして、私は今、左をソートします 半分、それは2、4、6、8だように。 何も順不同でません。 それは進行中のように感じています。 私はたような今では感じています 今永遠に話をされて、 したがって、この場合に見られることを残るもの アルゴリズムは、実際に、より効率的です。 しかし、我々はを通じてつもりです スーパー念入りこと。 コンピュータは、もちろん、 そのようにそれを行うだろう。 だから我々はどこにいますか？ 我々は、8つの要素から始まりました。 私は4の左半分をソート。 私はそれで行われているように見えます。 だから今、次のステップはにあります 4の右半分を並べ替えます。 そして、この部分は、私たちが行くことができます もう少しを通して すぐに、あなたがしているものの、 ただ、巻き戻しや一時停止することを歓迎 でそれを通して考えます 自分のペースが、何 我々は今持っているの機会です 4上の正確な同じアルゴリズムを実行します 異なる番号。 それでは、先に行きましょう、とに焦点を当てます 私たちはここにいる右半分、。 その左半分 右半分、そして今 左の左半分 その右半分の半分、 どのように私は、サイズのリストを並べ替えます 1だけ番号1を含みますか？ これはすでに行われています。 私は、リストのために同じことを行うにはどうすればよいです わずか7を含むサイズ1の？ これはすでに行われています。 この半分のためのステップ3 これら2つの要素をマージすることです サイズ2、1,7の新しいリストに。 すべてを行っているようには見えません。 それほど面白い作品。 それでは、次に何が起こるか見てみましょう。 私はただの左半分をソート 私の元の入力の右半分。 今度は右の並べ替えましょう 5および3が含まれています半分、。 それでは、再び左を見てみましょう 半分、ソート、右半分、ソート、 そして、これらの2つを一緒にマージし、 いくつかの追加の空間に、 3は、最初に来る5を付属しています。 そして今、私たちはソートしています 右半分の左半分 元の問題の、および 右半分の右半分 元の問題の。 3番目と最後のステップは何ですか？ よく一緒に、これらの二つの部分をマージします。 だから、私は自分自身いくつかを取得してみましょう 再び余分なスペースが、私は、 トップをその予備のスペースを使用している可能性があります。 しかし、我々は維持するつもりです 視覚的にそれは簡単。 私は今1にマージしてみましょう、と 次に3、次に5、次に7。 これにより、今では私を残します 元の問題の右半分 それは完全にソートされます。 だから何が残りますか？ 私が言い続けるような気が 同じものを再度、再度、 それはの反射です 我々は再帰を使用しているという事実。 使用方法 アルゴリズムを再度、再度、 の小さいサブセットに 元の問題。 だから私は今、左にソートします 元の問題の半分。 私は右のソートされた半分を持っています 元の問題の。 3番目と最後のステップは何ですか？ ああ、それはマージです。 それでは、それを行うことができます。 それでは、いくつかの追加を割り当ててみましょう メモリが、私の神、私たちは 今どこにでも置くことができます。 我々は、利用可能なので、多くのスペースを持っています 私たちに、私たちはそれをシンプルにしておこう。 代わりに帰るのと など当社独自のメモリを搭載しました、 のはそれをやらせます 視覚的にダウンしてここで以下、 マージ仕上げるします 左半分と右半分。 だからマージすることで、何をする必要がありますか？ 私は順序で要素を取りたいです。 だから、左半分を見て、 私は、最初の数は2である参照してください。 私は右半分を見て、 私は最初の番号を参照してください そう明らかに、1であります 数は、私は摘み取るしたいです 私の最終的なリストの最初に置きますか？ もちろん、1。 今私は、同じ質問をしたいと思います。 左半分には、私はしました まだ数2を得ました。 右半分に、 私は数3を持っています。 どれ私が選択したいですか？ もちろん、数2、 今の候補者に気付きます 右に左に4,3です。 のは、もちろん、3を選択してみましょう。 今の候補は4は上にあります 右に左、5。 私たちは、もちろん、4を選択します。 右に左、5の6。 私たちは、もちろん、5]を選択します。 左側の6、右側に7。 私たちは、6を選択し、次に我々 7を選択し、我々は8を選択します。 出来上がり。 言葉のだから膨大な数の後に、我々 8要素のリストをソートしています 8一通りのリストに、 それは、各ステップで増加してい しかし、どのくらいの時間がなかったです それはそれを行うために私たちを取ります。 さて、私は意図的にしました 絵のことを打ち出しました ここで、我々は一種のことができますように 除算を参照するか、感謝 征服にそれが起こっています。 確かにあなたはウェイクを振り返るならば、 私は、これらの点線のすべてを残してきました プレースホルダでは、次のことができ、 種類の、逆の順序で、参照してください。 あなたは親切なのに戻って見れば 歴史今、私の元のリスト サイズ8の、もちろんです。 そして、以前、私がいました サイズ4の二つのリストを扱います、 して、サイ​​ズ2の4つのリスト、 して、サイ​​ズ1の8のリスト。 だから、これはどのような行い、 種類の、のことを思い出させますか？ のまあ、確かに、任意の 私たちがきたアルゴリズム これまで見どこ 分割、および分割、および分割、 再び物事を持っておくと、 再び、この一般的な考え方になります。 それで何かがあります 対数は、ここで起こって。 そしてそれは、nのかなりのログはありませんが、 対数コンポーネントがあります 我々だけで何をやったかと。 今度は、それが実際にどのように考えてみましょう。 そこで再び、n個のログでした 偉大な実行時間、 我々は次のように何かをしたとき バイナリ検索、我々は今それを呼び出すように、 分割統治戦略 これを介して、我々はマイク・スミスを見つけました。 今技術的に。 それがあっても、n個のログベース2です ほとんどの数学のクラスで、しかし、 10は通常、あなたがとる基本です。 しかし、コンピュータ科学者、ほとんどの場合、 考え、ベース2の観点で話します、 私たちは、一般的にただのログを言います N、Nの代わりにログベース2の、 しかし、彼らは正確に一つとしています コンピュータの世界でも同じ 科学、脇など、 一定の係数があります 両者の違い、それはですので、 より正式な理由のために、とにかく議論の余地。 しかし、今のところ、我々は何を気に この例です。 それでは、例により証明わけにはいきませんが、で 少なくとも数字の例を使用 あなたがする場合は、健全性チェックとして手元に。 だから、以前の式には、ログベースでした Nの2が、この場合のnは何ですか。 I nは、元の番号を持っていた、または8 元の数の具体的。 今ではほとんどされています しばらく、私はかなりよ 必ずそのログベース2 8は3値の、 実際、何がそれは約うれしいです その3回の正確数であり、 リストを分けることができます 長さ8の再び、そして再び、 そして再び、あなたは左だまで ジャストサイズ1のリストがあります。 右？ 8,2に進み、4に進み 1に行く、それはです まさにそれの反射 私たちはちょっと前に持っていた絵。 どこにするように少しの健全性チェック 対数が実際に関与しています。 だから今、他に何ここに関与していますか？ N。 だから、すべてのことに注意してください 時間は、私はリストを分割し、 歴史の中で逆の順序ではあるが ここで、私はまだ、n個のことをやりました。 ことを必要としたことをマージするステップ 私は、数字の一人一人に触れます それをスライドさせるために その適切な場所。 だから、たとえこのの高さ 図は、サイズログnのnまたは3であります 具体的には、換言すれば、 私はここで3つの部門をしました。 私は水平方向にどのくらいの仕事をしました このチャートたびに沿って？ まあ、私がやったn個のステップ 私がしている場合ので、仕事 四つの要素と四つの要素を持って、 私はそれらを一緒にマージする必要があります。 私が通過する必要があります これら4およびこれらの4、 最終的にそれらをマージします バック8要素に。 逆にした場合、私は8本の指を持っています 私はそうでない、こっち、および8 fingers-- sorry--私がしている場合 こっち4本の指を持って、 これは私が、4本の指を行います こちらに、私はこれは、 その後、それは同じです 例として前、私が行った場合 中ものの8本の指を持っています 私は、一種の、行うことができます合計。 私は正確に、ここで行うことができます その後、私は確かにすることができます これらのリストのすべてをマージ サイズ1の一緒に。 しかし、私は確かに見ています 各要素で一度だけ。 したがって、このプロセスの高さは、ログnは このプロセスの幅は、そのように、話します nがあるので、私たちは見えるもの 有するように、最終的に、あります サイズn回の実行時間は、nをログに記録します。 言い換えれば、我々は、分割 リスト、ログn回、 しかし、我々はそれをしたたびに、私たちは持っていました 要素の一つ一つに触れ それらをマージするために、 すべて一緒に、これ 、ステップをN、私たちは持っているn回のnを記録しました またはコンピュータ科学者が言うように、 漸近的に、これは ビッグワードになります アッパーを説明します 実行時にバインドされ、 私たちは大きなOで実行されています ログnは時間の、いわば。 さて、これはので、重要です 実行時間は何であったかを思い出します バブルソート、選択と ソート、挿入ソート、 そして、存在していてもいくつかの他、 nが私達がでたところだったの二乗しました。 そして、あなたは、この種の、ここではこれを見ることができます。 nが平方した場合、明らかであるn回 Nが、ここで我々が​​持っているn回ログn、 私たちはすでに一週間から知っています ゼロ、そのログnは、対数、 リニアなものよりも優れています。 結局、絵を思い出します 赤と黄色と 私たちが描いたと緑の線、 緑の対数線ははるかに低かったです。 したがって、より良い、より速く ストレート黄色と赤の線よりも、 n回ログnは、確かに、良いです nよりn倍、あるいはn乗。 だから我々は持っているように見えます アルゴリズムのマージを同定し はるかに実行されますソート 確かに時間の短縮、および、 それがなぜ、今週初めに、ときです 我々はバブル間のコンテストを見ました ソート、選択ソート、およびマージ ソート、ソート本当に、本当に勝ったマージ。 そして実際、私たちも待ちませんでした バブルソートや選択ソートのための 終了します。 今度は、一つの他のパスを見てみましょう この時、もう少しから 正式な視点だけで 場合は、これは、より良好な共振します より高いレベルの議論より。 だからここにアルゴリズムが再びです。 のは、自分自身を聞いてみよう、 何走行時間 これは様々なステップをアルゴリズムのでしょうか？ それでは、最初にそれを分割してみましょう ケースと第2ケース。 IFの場合は、IFとELSE、 nが2未満であれば、単に返します。 一定の時間のように感じています。 これは、2つのステップのように、種類の、です、 nが2未満である場合、返さ。 しかし、我々は月曜日に言ったように、 一定時間、または1のビッグO、 二段階三することができ ステップ、でも千手順。 重要なのは、それがあるということです ステップ一定数。 だから黄色は擬似コードを強調 ここで実行され、我々はそれを呼ぶことにします、 一定の時間。 だからより正式に、と 私たちはこのto--つもりです 我々程度になります n個のT now--この権利を正式な、 問題の実行時間 それは、入力として、n個の代をとり、 、1の大きなOに等しいです nが2未満である場合。 だから、その上の条件です。 nがより小さいのであれば、明確にします 2、私たちはその後、非常に短いリストを持っています nは走行時間、n個のT、 1または0、この非常に特殊な場合には、 それだけで一定の時間になるだろう。 これは、1を取るために起こっています ステップ、2ステップ、何でも。 これは、工程の固定数です。 だから、ジューシーな部分が確実でなければなりません 擬似コード内の他のケース。 ELSEケース。 ソート右の要素のソート左半分、 要素の半分は、ソートされた半分をマージします。 これらのステップのそれぞれはどのくらいかかりますか？ さて、実行している場合 n個の要素をソートする時間 である、のはそれを非常に呼びましょう 一般的に、T nは、 その後、左のソート 要素の半分 言うような、一種の、あります、 2で割ったn個のT、 同様に右半分をソート 要素の言うような、一種の、あります、 n個のTは2分割した後、 ソート半分をマージします。 さて、私が持っている場合、一部の ここで要素の数、 4、およびいくつかの数のような ここで要素の、4のように、 私は、これらの4つのそれぞれをマージする必要があります で、これら4 1、内の各 他の後に、そのよう 最終的に私は8要素を持っています。 それはそれはnステップのO大だように感じていますか？ 私は指とのそれぞれのnを持っていれば それらの場所にマージする必要があり、 それはまた別のnステップのようなものです。 だから確かにformulaically、 我々は、これを表現することができます 最初は少しゾッとするほどではあるが 一見、それは何かであります それは、まさにそのロジックをキャプチャします。 走行時間、T Nの、IF N 2以上です。 この場合、ELSEの場合には、n個のTで 、2で割った、プラスNのTは2で割りました n個のプラスビッグオー、いくつかの ステップの線数、 多分ちょうどn、多分2回 nは、それは、おおよそn個の順序です。 どのように我々はできる、あまりにも、なるように、 formulaicallyこれを表現。 今、あなたがなければ、これを知っているだろう あなたは、あなたの心にそれを記録してきました またはでそれを見て その教科書の裏、 少しがあるかもしれません 最後に、シートをカンニング、 これは、実際に起こっています NログnのOビッグ私たちに与えて、 その再発理由 あなたは、画面上でここに見ています あなたが実際に、それを行った場合 例の無限の数、 または、あなたはformulaicallyそれをやった、あなたが希望 この式から、このことを見ます 自身のトンで、再帰的です nは右の何かの上に、 左側に渡ってn個のトンと、これはすることができます 実際に発現され、最終的に、 Nログnの大きな行くように。 確信していない場合、それがです ただ、今の罰金 確かに、それはだと、信仰を取ります、 その再発につながるもの、 これは、もう少しです 探しに数学的なアプローチ マージソートの実行時 一人で、その擬似コードに基づきます。 今度は、少してみましょう すべてのことから息抜き、 とを見てみましょう 特定の元上院議員、人 少し見覚えかもしれませんが、 Googleのエリックに座っ人 インタビューのためのいくつかの時間前シュミット、 ステージ上で、全体の束の前で 人々の、最終的に話して かなり今おなじみだトピック。 のは、見てみましょう。 エリック・シュミット：今上院議員、 あなたは、Googleのここにいます 私は考えるのが好き 就職の面接など大統領。 今では社長として仕事を得るのは難しいです。 オバマ大統領：右。 エリック・シュミット：そして、あなたがしています 今[聞こえない]何をするつもり。 それはGoogleの仕事を得ることも困難です。 オバマ大統領：右。 エリック・シュミット：私たちは、質問があります、 そして私たちは候補者の質問を、 この1は、ラリー・シュワイマーからです。 オバマ大統領：[OK]をクリックします。 エリック・シュミット：何？ 君たちは私が冗談だと​​思いますか？ それはここです。 最も効率的な方法には​​どのようなものです 百万32ビット整数を並べ替えますか？ オバマ大統領：Well-- エリック・シュミット：時々、 多分私は申し訳ありませんが、maybe-- オバマ大統領：いや、いや、 いや、いや、いや、私はthink-- エリック・シュミット：それはないですit-- オバマ大統領：私 思う、私はバブルを考えます ソートはどこへ行くか、間違った方法であろう。 エリック・シュミット：さあ。 誰がこの彼に言いましたか？ OK。 私はコンピュータサイエンスなかったですon-- オバマ大統領：我々はしました そこに私たちのスパイを得ました。 教授：すべての権利。 それでは、私たちを残してみよう アルゴリズムの理論的な世界 漸近解析で 、およびそれらのいくつかのトピックに戻ります 週0と1、スタートから いくつかの補助輪を削除するには、 あなたがする場合。 あなたが本当に理解するように 最終的に地面、何から ときに、ボンネットの下に起こって 記述、コンパイル、およびプログラムを実行します。 これがあったことを、具体的に思い出して 私たちが見た最初のCプログラム、 標準的な、簡単なプログラム 一種の、相対的に言って、 ここで、それは、Hello Worldのを印刷します。 そして、私は、プロセスを言ったことを思い出してください そのソースコードを通過 まさにこれは。 あなたは、ソースコード、パスを取ります それコンパイラを通して、クランのように、 そして、出て、そのオブジェクト・コードは、来ます この、0と1のようになります。 コンピュータのCPU、中央その 処理装置や脳、 最終的には理解しています。 それはそれはだということが判明 単純化し過ぎのビット、 私たちが今していること 位置が離れていじめます 本当にをされているかを理解します ボンネットの下に起こっています あなたが実行するたびに 打ち鳴らす、またはより一般的には、 毎回あなたは、プログラムを作ります 作成し、CF 50 IDE使用して。 具体的には、もののように これが最初に生成され、 あなたが最初のプログラムをコンパイルするとき。 言い換えれば、ときに あなたのソースコードを取ります そして最初の何、それをコンパイル クランによって出力されます アセンブリ・コードとして知られているものです。 そして実際に、それはまさにこのようになります。 私はでコマンドを実行しました 以前のコマンドライン。 クランダッシュ資本のhello.cに、 これはファイルを作成しました 私と呼ばれるhello.sため、 その内側に正確でした これらのコンテンツ、およびもう少し 上記ともう少し以下、 私はジューシーに置かれています ここで画面上の情報。 あなたが密接に見れば、あなたが表示されます 少なくともいくつかの馴染みのキーワード。 私たちは、一番上のメインを持っています。 私たちは途中でダウンしているのprintf。 そして、我々はまた、世界ハロー持っています 下方に引用符でバックスラッシュnを。 そして、ここで他のすべて 非常に低レベルの指示であります コンピュータのCPUが理解できます。 メモリを移動するCPU命令 周りに、メモリからのロード文字列、 そして最終的に、印刷 画面上のもの。 今何が後にかかわらず起こります このアセンブリコードが生成されますか？ 最終的に、あなたは確かに、行います、 まだオブジェクトコードを生成します。 しかし、実際に持っているのステップは ボンネットの下で起こっされて もう少しこのように見えます。 ソースコードはアセンブリコードとなり、 これは、オブジェクトコードとなり、 ここで手術の言葉であり、その あなたがソースコードをコンパイルすると、 アウト後、アセンブリコードは付属しており、 あなたは、アセンブリコードをアセンブルするとき、 アウトオブジェクトコードが付属しています。 今クランは、超洗練されています コンパイラの多くのように、 そしてそれは、これらのステップをすべて行います 一緒に、それは必ずしもありません 出力任意の中間 あなたも見ることができるファイル。 それは物事をコンパイルし、 これは一般的な用語であること このプロセス全体を説明しています。 しかし、あなたが本当にしたい場合は 特にであることが、あります 多くは、よりそこにも起こっています。 しかし、それでは、また、今でも考えてみましょう その超簡単なプログラム、hello.cに、 関数と呼ばれます。 これは、printfのと呼ばれます。 しかし、私は、確かに、printfのを書いていません それはいわば、Cが付属しています。 それはだ機能のリコールです 標準io.hで宣言され、これは ヘッダーファイルは、あります ここでは、私たちが実際にありますよ 長い前に、より多くの深さに飛び込みます。 しかし、ヘッダファイルです 一般的に伴います コー​​ド・ファイル、ソースコードファイル、そうすることによって 標準io.h.が存在するのと同じよう いつか前に、誰かが、 または誰かの、また書きました で、標準io.cと呼ばれるファイル これは実際の定義は、 またはprintf関数の実装では、 およびその他の機能の房、 実際に書き込まれます。 だから我々はことを検討した場合、その与えられました ここで左に、hello.cを、ときに コンパイル、場合でも、私たちにhello.sを与えます クランは、所定の位置に保存する気にしません 我々はそれを見て、そのアセンブリコードすることができます 、hello.oに組み立てれます デフォルトの名前は、確かに、あります あなたがソースをコンパイルするたびに与えられました オブジェクトコードにコードが、そうではありません まだそれを実行するのは非常に準備ができて、 別のステップのため 起こることがあり、持っています 過去数のために起こって 週間、あなたにおそらく知られず。 具体的にどこか CS50 IDEで、この、 あまりにも、少しになります 一瞬のために単純化し過ぎ、 ある、または時間にありました、 標準io.cと呼ばれるファイル、 誰かがにコンパイルすることを 標準io.sまたは同等の、 その誰かが、その後組み立て 標準io.oに、 またはそれはに判明します わずかに異なるファイル 異なるフォーマットを持つことができます 完全ファイル拡張子、 しかし、理論的には概念的に、正確に これらの工程は、何らかの形で発生していました。 その今、言ってどれ 私はプログラムを書いているとき、 ただ世界がこんにちは、と言うのhello.c、 そして、私は誰かの他の人のコードを使用しています 上にかつてのprintfのような 時間、標準io.cと呼ばれるファイルで、 その後、何とか私を取る必要があります オブジェクトコード、私の0と1、 そして、その人のオブジェクト コー​​ド、または0と1、 何とかにそれらを一緒にリンクします 1最終的なファイル、ハローと呼ばれる、その 持っているゼロのすべてと 私の主な機能からのもの、 0のすべて そして、printfのためのもの。 そして実際、その最後のプロセスがあります あなたのオブジェクトコードをリンクする、と呼ばれます。 出力はの 実行可​​能ファイルです。 で、公正でそう 一日の終わりに、何もありません 1週間以降に変更された、ときに我々 最初のプログラムをコンパイルを開始しました。 確かに、このすべてがされています ボンネットの下に起こって、 しかし、今、我々は位置にいます ここで、我々は実際にすることができます これらの様々なステップを離れていじめます。 そして実際、最後に 日の、我々はまだです 0と1を残し、どの 今実際に素晴らしいセグエです Cの別の能力に、その 我々は、ほとんど活用していたていませんでした 現在までに、ビット演算子として知られています。 つまり、これまで、いつでも我々はしました C言語でCまたは変数内のデータを扱って、 私たちはのようなものを持っていました 文字や山車とイン そして、longとdouble型等が挙げられるが、 それらのすべては、少なくとも8ビットです。 我々はまだできていたことがありません 個々のビットを操作し、 さらには個々のビット、しかし、我々 知っている、0と1を表すことができます。 今では、C言語で、あなたことが判明 個々のビットへのアクセスを得ることができ、 次の構文を知っていれば、 これでそれらを取得します。 それでは、見てみましょう ビット演算子で。 だから、いくつかのシンボルがここに描かれています 我々は、一種の、一種の、前に見てきました。 私は、垂直​​にアンパサンドを見ます バー、同様にいくつかの他、 そのアンパサンドアンパサンドをリコール 我々の前に見てきたものです。 あなたが持っている論理AND演算子、 二人一緒に、または論理OR オペレータ、あなた 2つの垂直バーを持っています。 ビット演算子は、我々はよ 、個々のビットを操作するを参照してください。 単に1つのアンパサンドを使用して、 単一の垂直バー、キャレット記号 少し、次に来ます チルダし、左 ブラケットは、ブラケットを左、 右ブラケット右ブラケット。 これらのそれぞれは、異なる意味を持ちます。 実際には、のは見てみましょう。 今日は古い学校に行きましょう、と使用 往年のタッチスクリーン、 ホワイトボードとして知られています。 そして、このホワイトボード 私たちを可能にするために起こっています いくつかの非常に単純なシンボルを表現するために、 あるいはむしろ、いくつかの非常に単純な式、 我々は最終的にそれからできること レバレッジ、順番に 個別にアクセスします Cプログラム内のビット。 言い換えれば、はこのやろう。 用してみましょう最初の話 アンパサンド回りのモーメント、 これはビット単位のAND演算子です。 言い換えれば、これは ことができ、オペレータ 私は左側の変数を持っています 典型的には、右側の変数 または個々の値、その場合、私たちと 一緒には、私の最終的な結果を提供します。 だから私は何を意味していますか？ プログラムでは、変数を使用している場合 これらの値の1店舗という、 あるいは単に、簡単なそれを維持させて、 個別に0と1を書き出します、 ここでは、アンパサンド演算子はどのように動作するかです。 0アンパサンド0は0に等しいとしています。 さて、なぜそのようになるのですか？ それは非常に似ていると ブール式、 ことを、私たちはこれまで説明してきました。 あなたはすべての後と思われる場合は、0です 偽、0は、偽偽および偽であります 我々が議論してきたように、あります 論理的に、また偽。 だから我々はここにも0を得ます。 あなたは0アンパサンドを取る場合 1、よく、あまりにも、その このためので、0になるだろう 左側の発現は、真または1であることが それが本当の、真であることが必要です。 しかし、ここで我々が​​持っている偽 真、または0と1。 ここでもう一度、私たちは1アンパサンドを持っている場合 0、、あまりにも、0になるだろうことを、 私たちは1アンパサンド1を持っている場合、 最後に、私たちは1ビットを持っています。 だから、他の言葉で、私たちはやっていません この演算子と何も面白いこと まだ、このアンパサンド演算子。 これは、ビット単位のAND演算子です。 しかし、これらは成分であります これを介して我々が行うことができます 我々はすぐにわかるよう面白いこと、。 今度は1つだけを見てみましょう ここに右のオーバー垂直バー。 私は0ビットと私を持っている場合 それともと、ビット単位 OR演算子、他の0ビット、 それは私に0を与えるために起こっています。 私は0ビットを取るとか、場合 1ビット、私は1を取得するつもりです。 そして実際に、ちょうどのための 透明度は、私は戻って行きましょう、 そのように私の垂直バー 1のと間違えていません。 私はすべてを書き換えてみましょう 私の1の小さなより 明らかに、私の場合、私たちは次のように参照してください。 1または0、すなわち1になるだろうしています、 私は1 OR 1があれば、 あまりにも、1になるだろう。 だからか、その論理的に見ることができます オペレータは非常に動作が異なります。 これは私0または0を私に0を与える与えるが、 それ以外のすべての組み合わせは私に1を与えます。 限り、私は内の1つの1を持っているとして、 式は、結果が1になるだろう。 ANDと対照的に オペレータ、アンパサンド、 私は中2 1のを持っている場合にのみ、 式は、私が実際に1アウトを得るのですか。 今いくつかの他のがあります 事業者にも。 そのうちの一つは、もう少し複雑です。 だから私は先に行くと、消去せ これは、いくつかの領域を解放します。 そしてのは、見てみましょう ちょっとキャレット記号、。 これは、典型的には あなたが入力できる文字 キーボード保持シフトにと あなたの米国の上の数字の後、1 キーボード。 だから、これは排他的です OR演算子、排他的論理和。 だから私たちはただ、OR演算子を見ました。 これは、排他的論理和演算子です。 実際の違いは何ですか？ まあちょうど式を見てみましょう、 そして最終的に原料として使用します。 0 XOR 0。 私は常に0であると言うつもりです。 それは排他的論理和の定義です。 0 XOR 1が1になるだろう。 1 XOR 0は1になるだろう、 1 XOR 1になるだろうか？ 間違いましたか？ または右？ 知りません。 0。 今ここで何が起こっているの？ まあについて考えます この演算子の名前。 排他的論理和、ように 名前は、一種の、示唆しています、 答えは唯一であることを行っています 1入力は排他的である場合には、 排他的に異なります。 だからここに入力があります 同様に、出力が0であるので。 ここで入力があります 同様に、出力が0であるので。 ここで彼らは、出力が異なるものです 排他的であるので、出力は1です。 だから、と非常によく似てい そして、、それは非常に似ています、 か、それは非常に似ていると ORが、唯一の排他的な方法です。 これは、もはや1ではありません 我々は、2つの1のを持っているので、 そして、排他的ではない、それらのひとつ。 大丈夫。 何他の人はどうですか？ まあチルダは、一方、あります ありがたいことに、実際にはいいとシンプル。 そして、これが単項であります 意味オペレータ、 それは、ただ1つの入力に印加されています、 一方のオペランド、いわば。 ていない左右に。 言い換えれば、あなたは、チルダを取る場合 0、答えは反対になります。 そして、あなたは1のチルダ取る場合、 答えは反対があるでしょう。 だから、チルダ演算子です ビットを否定する方法、 またはからのビットを反転 0から1、または1から0。 そして、それは最終的に私たちを残します ちょうど2つの最終事業者と、 いわゆる左シフトし、 右シフト演算いわゆる。 それでは、どのようにそれらの作業を見てみましょう。 書かれた左シフト演算子、 そのような2アングルブラケットと、 以下のように動作します。 左に、私の入力、または私のオペランドの場合 シフト演算子は、非常に単純に1です。 そして、私は、その後にコンピュータを伝えます 1は、7ヶ所を言うことを、左シフト 結果は私かのようです その1を取り、それを移動させます に渡って7ヶ所 左、およびデフォルトでは、 我々はそれを仮定するつもりです 右側のスペース ゼロでパディングされようとしています。 言い換えれば、1が起こっているシフト7を残し 私に1が続く、1、2、3を与えるために、 4、5、6、7ゼロ。 だからのように、それはあなたがすることができます 1のような少数を取り​​ます、 そして、明らかにはるかにそれを作ります このようにはるかに大きな、ずっと、 しかし、我々は実際に見に行くしています それのためのより多くの巧妙なアプローチ 代わりに、同様に、 大丈夫。 それを週に3回は終わりです。 私たちはあなたの次の時間が表示されます。 これはCS50ました。 [音楽再生] SPEAKER 1：彼はスナックにありました バーでは、ホットファッジサンデーを食べます。 彼はすべての彼の顔の上にそれを持っていました。 彼は、ひげのようにそのチョコレートを着ています SPEAKER 2：あなたは何をしているのか？ SPEAKER 3：うーん？ 何？ SPEAKER 2：あなただけのダブルディップましたか？ あなたは二重のチップを浸しました。 SPEAKER 3：すみません。 SPEAKER 2：あなたは、チップを浸し 一口を取って、あなたは再び浸しました。 SPEAKER 3： SPEAKER 2：だから、パッティングのようなものです ディップであなたの全体の口の右側。 次回は、チップを取ります 一度だけ、それを浸し、それを終了します。 SPEAKER 3：あなたは、何ダンを知っていますか？ あなたがディップしたい方法を浸します。 私はディップしたい方法を浸します。