[音楽再生] DAVID J.マラン：これはCS50です。 そして、これを週に3回の開始です。 だから我々はエキサイティングなをたくさん持っています 今日カバーするもの。 多くの機会のための ステージに上がっボランティア。 そして最終的に、今日は、 ないコードに関するすべてで。 しかし、それは、アイデアについてですと それはアルゴリズムについてです、 実際の一部を戻します 週ゼロから学んだ教訓、 前記リコール、我々 この極悪非道を導入しました。 また、借入のインスピレーション それから、スタートへ これまで以上に洗練された解決するために アルゴリズム的な問題。 しかし、最初に、お知らせのカップル。 だから1、あなたが参加したい場合 昼食時CS50のスタッフとクラスメート 今週の金曜日、両方こことで ケンブリッジ、ニューヘブンで、 コー​​スのをご覧ください。 URLは見つけることができるウェブサイト。 この水曜日ます講義します サンダースここなりません。 それはとても、オンラインでのみとなります CS50のウェブサイトでで曲、 ここでケンブリッジのか またはニューヘブンにも。 そして、問題は2セット あなたの手の中に既にあります。 あなたはまだで潜っていない場合は、私を許可します 強い言葉で表現の提案を提供します 特に今、として、その 問題は、事前に設定し、 あなたは本当に、今そうでない場合は起動しますか 週末に少し手を出すか、前 彼らが最初に出て行くとき 金曜日、あなたはだろうから 彼らは必ずしもじゃないことを見つけます 長いまたはより挑戦的なあたりになっ SE。 私はあなたがそれを見つけると思いますが、中に 一般的に、彼らはおよそ取る傾向にあります 同じ時間のまわり。 しかし、それは確かに依存します 学生、およびその上に 考え方によって異なります これであなたはそれに近づきます。 しかし、常に、あなたが行っています いくつかの壁にぶつかるために、 あなたがヒットするつもりです いくつかのバグ、そしてあなただけです できるようにするつもりはありません いくつかの時点でそれを乗り越えます。 そして、それはできるように非常貴重です 離れたステップ、次の日に戻ってきて、 CS50に営業時間、ポストに行く話し合います 等が、実際にブロックされていない取得します。 だから、心の中でそれを維持します。 可能な限り最も早い開始 あなたができる最善のことです。 我々はスタート地点だからここです 0週目でオーバークラス。 そして、私たちはボランティアを得ることができます ここで私はマイクを見つけるには？ OK。 すでに立ち。 アップさあ。 それはそれが動作するように起こっているかだと思います。 あなたの名前は何ですか？ ALAN ESTRADA：アラン・エストラーダ。 DAVID J.マラン：アラン・エストラーダ。 アップさあ。 始めまして。 ALAN ESTRADA：はじめまして。 DAVID J.マラン：そして、あなたがここにいました もちろん、0週目で私達、と。 ALAN ESTRADA：私がいました。 私がいました。 DAVID J.マラン：だからあなたが行くことができます 先とマイク・スミスたちを見つけます、 早くすることができますように！ 早くすることができますように。 文字通り問題を引き裂きます 半分にあなたがする必要があるとして。 ALAN ESTRADA：ええと。 DAVID J.マラン：文字通り 半分に問題を引き裂きます。 ALAN ESTRADA：ああ。 mmです。 とても良い。 DAVID J.マラン：OK。 良い。 ありがとう。 ALAN ESTRADA：非常に良いです。 OK。 DAVID J.マラン：そして今、 あなたはそれを絞り込まました 問題の半分のサイズに。 今、私たちは四半期までです。 あなたが注意を払っています 我々はどちら側に維持していますか？ [笑い] ALAN ESTRADA：はい、私はthink-- DAVID J.マラン：我々はどのようなセクションにありますか？ ALAN ESTRADA：マフラー、そう。 DAVID J.マラン：OK。 しかし、マイク・スミスが起こっています マフラーの後になるように。 So-- [笑い] 大丈夫。 ALAN ESTRADA：どこを探していますか？ DAVID J.マラン：マイク・スミス。 ALAN ESTRADA：マイク・スミス。 DAVID J.マラン：今、私たちは、手術にしています。 今、医師。 Now-- ALAN ESTRADA：のは本当で手放しますLet's-。 レアル。 DAVID J.マラン：レアル。 OK。 あなたはレアルが必要な場合。 さて、マイク・スミスは、方法は何ですか？ ALAN ESTRADA：この方法です。 DAVID J.マラン：方法は？ ALAN ESTRADA：待ってください。 M is--ね？ 我々はwith--開始しました DAVID J.マラン：うん。 これらは、左ています。 あなたの右。 ALAN ESTRADA：うん。 DAVID J.マラン：だからマイクのここインチ ALAN ESTRADA：何？ [笑い] 悪い例、みんな。 ごめんなさい。 DAVID J.マラン：これはお教えします あなたの椅子から跳躍します。 ALAN ESTRADA：ああ。 ああ。 見つけた。 見つけた。 ああ。 ああ。 これは私があなたを持って、[OK]をis--。 右ここスミス？ DAVID J.マラン：スミスは、ありがとうございました。 だから私はスミスを見ておこうか！ ALAN ESTRADA：ああ、うん。 ダメダメダメ。 いや、ああ。 これは私のものです。 DAVID J.マラン：ああ、あなたはスミスを得ました。 OK。 ALAN ESTRADA：ええ、私 右ここでスミスを得ました。 申し訳ありませんが、みんな。 私はMichael--を考え、私たち マイケルを探していました。 ごめんなさい。 DAVID J.マラン：それはOKです。 すべての権利、今、私たちはしています Pacciniアンド・サンズへ。 ALAN ESTRADA：Pacciniと息子。 DAVID J.マラン：あなただけ そして私は、この上です。 OK。 私たちにマイク・スミスを検索します。 スミス。 ALAN ESTRADA：スミス。 DAVID J.マラン：スミス。 私たちは、ごみRにしています。 ALAN ESTRADA：酷いです。 ああ。 これは、しばらく時間がかかるとしています。 [笑い] DAVID J.マラン：靴。 私たちは、靴にしています。 ALAN ESTRADA：今、私たちはgonna--ています DAVID J.マラン：ニース。 ALAN ESTRADA：Which-- [笑い] ああ、これは素晴らしいです。 [笑い] DAVID J.マラン：それはOKです。 ALAN ESTRADA：ああ、これは良いです。 私はするつもりだとは思いません この後PSAT仲間を持っています。 DAVID J.マラン：良いです。 スポーツ。 ALAN ESTRADA：スポーツ。 UM、L、M、N、O、P。 DAVID J.マラン：OK。 それでは、半分にこれを引き裂くてみましょう。 大丈夫です。 マイクので、これは、とにかく不十分終了します スミスはイエローページになりません。 ALAN ESTRADA：おやおや。 DAVID J.マラン：いいえ、それはOKです。 しかし、ここでは次のようにふりをしましょう 彼はこのページにあります。 だから今、あなたがダウンして、問題を酔っぱらったしました 1ページに、我々はマイク・スミスを見つけました。 [応援] わかりました、ありがとうございます。 OK。 それが臨時ました。 しかし、それはまだ速かったです 線形検索よりも、 ここで我々が​​開始 この本の始まり、 左から右に、我々は我々の方法を移動し、 最終的にはマイク・スミスを探しています。 だから、もし電話帳 多分千ページを持っていました、 多分それはかかったでしょう 私たちの10かそこらのページの涙。 しかし、あなたが活用している可能性があり 仮定に触れました すべてのことの間に、それは言うことです 事前に電話帳が何でしたの？ 聴衆：ソートさ。 DAVID J.マラン：それはソートされています。 右？ それはとても、アルファベット順に並べ替えています これらの名前と番号のすべてのこと にAのから順にソートされ Zの、アルファベット順の間です。 しかし、今日、私たちは今尋ねます 質問、よく、 どのようにベライゾンまたは電話でした 同社は、その状態にそれを得ますか？ それは一つのことだから活用します その仮定、したがって、 の問題を解決します より効率的なアルゴリズム。 しかし、我々は決して本当に 週ゼロに尋ねた、よく、 値段はどれほどでした ベライゾンまたは他の誰か ソートされた順序でその電話帳を取得するには？ 右？ それは問題ではない場合 マイク・スミスを検索 それはあなたがかかる場合、超高速です 最初にページをソートする年。 右？ あなたにもちょ​​うどふるいにかけるかもしれません ランダム化された電話帳を経て、 それがスーパーになるだろう場合 それをソートするには高価。 だから我々は、他のボランティアを持つことができます。 のが取るでここに見てみましょう どのように我々はどのようにup--に来ますmight-- 我々はこれらのソートについては行くかもしれません。 そしてジョーダンが実際に可能性がある場合 ステージ上で、ここで私たちを参加。 ちょっとアップさあ。 あなたの名前は何ですか？ キャロライン：キャロライン。 DAVID J.マラン：キャロラインは、アップに来ます。 そして、あなたが参加することがあります ここで私とヨルダンこともできます。 キャロラインは、ありがとうございました。 大丈夫。 だから、我々はここに持っているもの キャロラインは26青冊です FASは、管理するために使用します 特定の期末試験。 これらは、見つけるのは難しいなっています 私たちは事前に何をやりましたか 私たちが誰かの名前を入れているということです これらの各々の前面に、 しかし、我々は、単純な、それを守ってきました その後、完全な名前を出します。 だから我々は名前で人を置きます L、D、J、B、すべての方法のAからZ、 しかし、彼らはランダムな順序にしています。 そして、あなたは、あなたの話をするかどう あなたのような問題を通じ方法 それは、あなたが先に行くことができないと Zに、私たちのためにこれらを並べ替えます 聴衆：[OK]を、ので、Lは真ん中、等です。 Cが始まっています。 B. L. Bの前にJ、Q。 DAVID J.マラン：それを保持 1秒間考えました。 そうでなければ、これは唯一であるため 私は、あなたに面白い、とジョーダン。 そうしよう。 聴衆：[聞こえません]。 R. DAVID J.マラン：OK。 あなたはなにをしているのですか？ キャロライン：MはOの後に来ます DAVID J.マラン：OK。 CAROLINE：O. DAVID J.マラン：O、グッド。 CAROLINE：E. DAVID J.マラン：E、F。うん。 キャロライン：T、U、V。 DAVID J.マラン：それはそうV、T、U、V。 あなたが続けるmaking--ているように見えます。 あなたが作っているように見えます こちらに大きな山、 そしてあそこに大きな山のようなもの。 だから、アルファベットの前半、 アルファベットの後半。 OK。 良い。 種類の二つに問題を分割します。 M、N、X。うん。 CAROLINE：K. DAVID J.マラン：OK。 K.は、だから、種類の選択しています それら次々、 左または右のいずれかにそれを入れて、 またはZは、床の上に起こっています。 OK。 キャロライン：Z​​は、床の上に起こっています。 DAVID J.マラン：OK。 Yは、床の上に起こっています。 今、私たちはXを置くことができます CAROLINE：G. DAVID J.マラン：Gさんは左に行きます。 Sは右起こっています。 すべての権利、Aは左のすべての方法を行っています。 CAROLINE：A、B、C、D. DAVID J.マラン：今、良いです。 我々が持っている、Bは、CのWのは、そこに行きます。 すべての権利、T. キャロライン：H、I、J。 DAVID J.マラン：H、I、Jグッド。 CAROLINE：センターでは、私はgonna--よ DAVID J.マラン：OK。 だから今、私たちは、種類になるだろう これらの様々な山をマージします。 そこで、Cを介して、私はDを参照し、 E、およびF、およびG、およびH、およびIニース。 J、Kそして、この山があります 逆さまに、それは大丈夫です。 確かに。 我々はいくつかのコーナーをカットすることができます。 OK。 そして、我々は、W、X、Y、Zを必要とします キャロライン：うん。 DAVID J.マラン：優秀。 だからビッグにありがとう これらをソートするためキャロライン。 [応援] ありがとう。 どうもありがとうございました。 だから今のは一瞬考えてみましょう どのキャロラインはそれをやって行きました、 そしてまさに我々 どのように我々to--ことができました それを解決することができました 我々だけだった問題 ランダム入力の全体の束を与えられました。 まあ、それはそこにのように見えます そこにシステムのビットでしたか？ 右。 だから、以前の文字は、 アルファベットで、彼女 左に置く、とされました アルファベットの後の文字、 彼女は右に入れていました。 そして、すぐに彼女が見られるように いくつかの近位文字、もの それは右隣同士に行きます、 彼女は順番にそれらを置きます。 そして、私たちは種類のこれらの小さなを持っていました 発生したソートされた入力の山。 そして、その結果は非常にどのようなものか 私たちのほとんどの人間は行うだろう。 我々は一種のそれを取捨選択だろう、 私たちは種類のメカニズムを持っていると思います。 しかし、それは書くことが難しいかもしれません それダウン式自体インチ それはもう少し有機よりも感じました。 だから我々は今、バインドできるかどうかを見てみましょう 少ない入力を持つ問題。 代わりに26の、してみましょう はるかに少ない何かを 直後の、7、と言うと これらのドアは、いわば。 わずか7の数字はありますか？ そして今の目標であれば 手の値を見つけることであり、 それでは、どのように効率的に見てみましょう 我々はこれをやって行くことができます。 そして、私たちが今できることなら見てみましょう いくつかの数値を適用するために開始し、 記述すると、またはいくつかの式 当社の電話帳の効率 アルゴリズム、私たちの試験の本アルゴリズム、および より一般的には、情報を見つけます。 このためだから、私は先に行かせて、 こちらにタッチスクリーン上に、 持っているWebブラウザを設置 正確にこれらの7つのドア。 そして、我々は他のものを得ることができれば こっちに来てボランティア、 私はここの上にこれらの同じドアを入れています。 クイックボランティア。 この選ぶ - デモが起こっています 今より速く、より迅速に。 ダウンさあ。 あなたの名前は何ですか？ TREVOR：トレバー。 DAVID J.マラン：トレバー？ すべての権利、トレバーは、ダウンに来ます。 だから、トレバーはこちらを志願しました 同様の問題が、だいずれかを実行します。 範囲が狭く、それが起こっています 私たちは今、形式化しようとすることを可能にします これらの数字をソートするためのプロセス。 だからトレバーは、はじめまして。 だからここにとても配列であり、 、7ドアのリストを話します。 前方に移動し、私たちに数50を見つけます。 そして事実の後、 あなたはそれを見つけた方法を教えて。 すべての権利をbe--する必要があります。 うん、これはここでは1ですか？ おっと。 OK。 あなたはそのいずれかをクリックしました。 良い。 そして、良いです。 今、あなたはそのいずれかをクリックしました。 そして、私はあなたにマイクを与えてみましょう、 あなただけの瞬間にそれを持っているようにします。 前方に移動し、クリックして あなたは予定隣。 いいね。 TREVOR：私はドアをunclickすることはできますか？ DAVID J.マラン：いいえ、あなたがunclickすることはできません。 TREVOR：[OK]をクリックします。 これです。 DAVID J.マラン：どこに行きたいですか？ どれ？ TREVOR：その1。 DAVID J.マラン：いいえ TREVOR：[OK]をクリックします。 これです。 DAVID J.マラン：はい。 それは良かったです。 大丈夫。 だからあなたのアルゴリズムは何だったのか これを行うための手順、トレバー？ TREVOR：私はちょうど通過しました ドア私は50を見つけるまで。 DAVID J.マラン：OK。 優れたアルゴリズム。 だから、大丈夫です。 実際に、私は明らかにしたらどうだから これらの二つの他のドアの後ろに、どのような 我々は、ということですここで見つけることができます 我々はランダムな入力を持っています。 だから、実際の通りでした あなたが得ることができるように良いです。 そして、実際には、あなたがより良くなりました 徹底的に配列全体を検索します、 それは実際にあったであろうので、 不運あなたは数を打つていた場合 非常に最後のドアで50。 しかしその代わりに、私たちの場合 あなたの仮定を与えました。 私は一種のすべての仮定します 周りのこれらのドア、 あなたが持っているように、 数字は、この時間をソートし、 今回はそれが実際です different--この時、 それは実際にあなたのために並べ替えられています。 そして今、手元にゴール 数50を打つことです。 TREVOR：[OK]をクリックします。 DAVID J.マラン：何が あなたのアルゴリズムでは、になるだろうか？ TREVOR：まあ、それはだ場合 ソート、それはどちらかだ行きます 最大の場合は最大にbe--します、 降順、それは最初のものになるだろう、 またはそれは反対だ場合、 それは最後の1になります。 だから、僕はこのドアをタップし、よ その後、ちょうど最後のドアをタップします。 DAVID J.マラン：優秀。 大丈夫。 だから我々は数50を発見しました。 だから、すぐにあなたが知っていたとして、 彼らは、私たちを選別し、 この仮定を活用することができました。 そこで、彼らは次のようにあまりにも多くのです 電話帳の例。 すぐに持っているように、偶数と このような小さな問題、 あなたの入力は事前にソートされ、我々はできます 実際に間違いなく値を見つけます より効率的に。 それがあった場合私はあなたを教えてくれませんでした ビッグに小さなソート、または小規模から大規模、 そしてそれは非常に合理的でした 一端または他に開始します 実際にその目標値を検索します。 だからだけでなくトレバーに感謝。 そして、私はうまく行っpropose--ます。 私たちは、その実際には、ほとんどのクリップを持っています CS50で私たちのお気に入りの瞬間の中で、 これにより、時々これらのデモ かなり計画に従って行っていません。 そして実際、今、私 誤ったインターフェイスをプルアップ タッチスクリーンを使用すると。 だから、私のせいではありました。 だから、これはためになります 来年のクリップと 私は自分の画面上でクリックした理由。 しかし、ここでは簡単に見てみましょう 昨年何が起こったかで ずっと、思いついたジェイと ここでトレバーのように、志願し、 この短いクリップでは、あなたが表示されます この同じデモは全くしませんでしたか 同じ教訓を明らかにしました。 [ビデオ再生] 私は、あなたが今何をしたい-allです 私のために、そして私たちのために見つけるために、 本当に、数50 一歩ずつ。 -The数50？ -The数50。 そして、あなたは何を明らかにすることができます これらのドアのそれぞれの背後にあります 単に指で触れることもできます。 畜生。 [笑い] [END再生] DAVID J.マラン：だから非常にうまくいきました。 それらはソートされていないドアでした。 そしてジェイ、もちろん、 あまりにも速く、すべてを発見しました。 トレバーは、はるかに良い仕事をしました 教えやすい瞬間の観点から、 そうでは今年、話すこと それを見つけるために長いを取ります。 もちろん、我々は与えました ジェイ二度目のチャンス、 それによって我々は、ドアをソート 私たちはトレバーのためにやったように、 そして、トレバーは、スーパーだけでなく、この時間をしました。 しかし、ジェイは半分にすぐにそれをやりました。 [ビデオ再生] -The目標は今もあります 私たちに数50を見つけ、 しかし、アルゴリズムそれを行うと、 あなたはそれについてつもり方法を教えて。 -OK。 あなたがそれを見つけた場合 - そして、あなたは映画を保ちます。 あなたはそれが見つからない場合、あなたはそれを返します。 -Man。 -oh！ - [聞こえない] [OK]をクリックします。 だから私は端をチェックするつもりです ああthere's--かどうかを判断する最初の。 [拍手] [END再生] DAVID J.マラン：OK。 だから、明らかにドアをソート 効率化につながります。 だから、二倍の速さ 私が何を意味するのかです。 そしてそうジェイは幸運両方の時間を得ました。 そして彼はまた、最後に幸運 今年、私はいくつかのBlu-rayディスクを注文 実際に出て得ました。 私は、今年ごめんなさい 同じ、トレバーを持っていませんでした。 しかし、より好ましくは数年前でした。 そして、あなたのいくつかはこのことを知っているかもしれません 彼はCS50にいた仲間、ショーン、 正確に挑戦されました 同じ問題、SDではあるが、 あなたはすぐに戻って一日で、表示されます。 そして、あなたがただけではないことがわかります 彼は、ジェイより少し時間がかかります トレバーよりも少し長く、それがありました 実際にこの素晴らしい機会 のほぼ全員を係合します 群衆ラ価格は奨励、右であります 彼は、私たちが求めていた番号を検索します。 のをしてみましょう。簡単に見てみ。 [ビデオ再生] -OK。 だからここにあなたの仕事、 ショーンは、以下の通りです。 私はこれらの背後に隠されています ドア数7。 しかし、これらのドアの一部に隠れて 同様に他の負の数値です。 そして、あなたの目標は、考えることです この数値の一番上の行の ちょうど配列、または同じように 紙の作品の順序 その背後にある番号を持ちます。 そして、あなたの目標は、上部のみを使用して、あります 配列ここで、私は数7を見つけます。 そして、私たちはその後、批評しようとしています どのようにあなたがそれをやって行きます。 -大丈夫。 、私たちの数7をください-find。 いいえ。 五、19、13。 [笑い] これはトリックの質問ではありません。 1。 [笑い] この時点で、あなたのスコアが非常にではありません 良いので、あなたにも続ける可能性があります。 3。 [笑い] 移動します。 率直に言って、私は助けることが疑問に思うことができません 何をしてもso--、考えています [笑い] 唯一の一番上の行なので、 次の3つの左を持っています。 だから、私は7を見つけます。 [笑い] 17。 セブン。 [拍手] 大丈夫。 [END再生] DAVID J.マラン：だから我々は可能性が 一日中、これらを見て。 のそしてもちろん、いくつかの おそらく今年のデモ 今すぐ次に終わります 今年のビデオなども。 だから今、実際にしてみましょう アルゴリズムに焦点を合わせます ここで、我々はできないかどうかを確認 今正式始めます どのように我々は、我々のデータを得ることについて行くことができます この状態に、それがソートだと、 最終的に、私たちが実際にすることができますように より効率的に検索します。 そして、私たちが行っているにもかかわらず、 かなり小さいデータセットを使用します、 8数字の私たちのように ボード上にここにあります、 最終的にこれらの同じ考えが適用できます 千入力に、百万の入力、 アルゴリズムのため40億の入力、 基本的には同じことを行っています。 そして、これは私たちの最後です ボランティアの機会今日、 しかし、おそらく最も関与する1つ、 これのために私たちは、8人のボランティアが必要 出てくるとを通して私たちを歩きます すぐにどうなるか仕分けのプロセス これらの音楽をすることは、ここに立っています。 私はここに戻ってみましょう。 だからturquoise--緑の中の1つは、それを何ですか？ あなたがコミットされていますか？ 2。 ダウンさあ。 OK。 3。 四。 5、me--がOKしてみましょう。 あなたの友人が指名されています。 6個、7個、8。 アップさあ。 大丈夫。 どうもありがとうございます。 アップさあ。 アップさあ。 大丈夫。 だから我々はhere--、これを持っているもの より厄介なものの一つです、 これは、あなたのユーモアを必要としますので、 時間のほんの少しのための私。 あなたはナンバーワンでなければなりません。 あなたの名前は何ですか？ アナン：アナン。 DAVID J.マラン：アナン。 デビッド。 あなたの名前は何ですか？ JOSEPH：ジョセフ。 DAVID J.マラン：ジョセフ、 あなたは数2​​つです。 セレナ：セレナ、数3。 ステファン、4番。 CYNTHIA：シンシア。 DAVID J.マラン：シンシア、数5。 [聞こえません] DAVID J.マラン：[聞こえません]。 デビッド、6番。 MATT：マット。 DAVID J.マラン：Mattの数7。 そして？ ウェイバリー：ウェイバリー。 DAVID J.マラン：ウェイバリー、数8。 大丈夫。 場合は、おっとをcould--。 あなたのように、あなたのすべての場合 そこに最初の課題、 8曲のスタンドは、 ここで観客に面しています。 あなたは上の数字を入れることができれば これらの音楽は、そのような方法で立っています 彼らが並ぶこと ボード上の同じ番号。 だから、自分がして、そのように見えるように これらの音楽をあなたの番号を入れて ここに立っています。 優れたこれまで。 優れています。 OK。 だから今、私たちは、依頼するつもりです いくつかの異なる方法で質問です。 どのように我々は、ソートについて行くことができます ここでこれらの人々アップ？ 我々はいくつかのアプローチを持っていたので 以前、それによって私たちがしました 二つの異なるバケットを作るようなもの。 そして、我々は一般的でした 物事を一緒に縫い合わせ。 すぐに我々は2つ​​の数値を見たように それは、一緒に属し 私たちは一緒にそれらを置きます。 一緒に属する2つの文字。 しかし、どうかを見てみましょう これを形式化することはできません、 我々は最終的に持っているように、 必要になりますいくつかの擬似コード、 これであなたは、これらの問題を解決することができます。 だから今、私は探しています ここではこれらの数値で。 そして、私はミスの全体の束を参照してください。 最終的に、私は上の1つが欲しいです 左右に8。 そして、私は見ています これらの2つ、4つおよび2。 そして、問題は明らかに、何ですか？ うん。 Soが 二つは明らかに前に来ます 4、あなたは何を知っていますか？ 私が最初に貪欲なアプローチを見てみましょう、 あなたがする場合は、問題のような多くの あなたからリコール場合選ぶ - 設定 問題セットの一つのスタンダード版、 ここで、私はローカルで問題を解決 それは私の目の前にここです それは私をリードし、どこを参照してください。 OK。 だから、2および4、私は手放します 先とちょうど2つのあなたを交換します。 あなたは物理的に移動することができた場合 自分と自分の論文、 私が得ているように見えます より良い状態にあるリスト。 今、彼らは良いしています。 私は、上に移動するつもりです 4と6は、よさそうです。 問題ありません。 シックス、8、[OK]をクリックします。 八一、別の問題。 8と約1本当だ何から？ 一つは、8つの前に来ます そのため、私たちは何をすべきでしょうか？ のは、これらの2つを交換してみましょう。 Oneと8。 そして今、私は続けるつもりです。 私は先に探し続けるつもりです。 そしてのは、何が起こるか見てみましょう。 八三、の もちろん、アウトオブオーダー。 スワップをしてみましょう。 もちろん八七、。 アウトオブオーダー。 スワップをしてみましょう。 八五、もちろん、交換しよう。 大丈夫。 リストがソートされます。 はい？ [OK]を、明らかではありません。 しかし、それは右、少し良いですか？ 通知は何が起こったかあるので。 私たちは、小さいのスワップを行ったびに 番号は、種類のその方法を浸透さ、 そして、大きな数 このように浸透させ、または私達はよ にバブリング言っ開始 左または右にバブリング。 今、それがあるため、十分ではありません せいぜい数のかもしれません 一つの場所を移動しました 前方、または最悪の場合、 数が場合があります さらに、1つの場所を移動しました。 だから、何を、この種の知っています これまでのところ、かなりうまくいきました。 私はもう一度それを試してみましょう。 2と4、彼らはOKです。 四六、彼らはOKです。 六一、アウトオブオーダー。 それでは、次の2つを交換しましょう​​。 そして今、問題のに気付きます 再び少し良くなり始め。 六三、アウトオブオーダー。 2つのあなたを交換しましょう​​。 六七、あなたは良いしています。 もちろん、注文のうち七五、。 七、8、ためです。 そして今、私がする必要があるかもしれません もっとこの数回行います。 そして、実際には、自分のためだと思います おそらく何回最大限に 私は前後に歩かなければならないのでしょうか？ 我々は戻ってそれに来ます。 だから、2と4はまだOKです。 四一、いや。 それでは、スワップをしましょう​​。 そして再び、視覚的に気付きます 1は、泡立ちの一種であります それがあるべき左へ。 四三スワップ。 四六。 六五スワップ。 六七。 セブンと8が良いです。 良い。 私たちも良くなっています。 それでは見てみましょう。 今、私たちは2と1を持っています。 もちろん、交換します。 二三、3と4、4、および 5、6と7、7、8。 良い。 そして、あなたは何を知っていますか？ 私はそこに1変更を行ったため、 私は1健全性チェックを行うことができます。 私はすべての道を行こう バック先頭に。 OK。 一つは、うんtwo--、参照してください？ 何かが間違っていました。 三つ、四つ、五つ、6個、7個、8個。 そして、この最後のパスでは、あります 私の今と快適ます それがソートされていると主張しますか？ OK。 視覚的には、それは絶対に本当です。 しかし、機能的に、どのような また、ちょうど起こりました あなたを可能にする最後のパスで このリストは実際にあることを確認するために、 ソート？ 私は何をしたか、この最後のパスをしませんか？ 聴衆：変更はありませんでした。 DAVID J.マラン：申し訳ありませんか？ 聴衆：変更はありません。 DAVID J.マラン：変化はなかったです。 だから、私への愚かなことだろう 再びその同じアルゴリズムを行います 私はをしなかった場合 初めて変更されます。 そして、状態が変更されていません。 確かに、私は作るつもりはありません 任意の二時間を変更します。 だから、それは今安全です 言って、リストがソートされます。 そして実際、これは今で 我々は一般的によ何か コー​​ルバブルソート、これにより、ペアごと、 あなたは、再び間違いを修正 そして再び、そして再び、あなた 前後に行き続けます、 そして前後に、あなたまで その時点で、そのようなスワップをしません あなたは、私は、ええ、自信を持つことができます ミスのすべてを固定し終えました。 のはリセットし、別のアプローチを試してみましょう。 あなたたちは、に戻って行くことができれば あなたは瞬間前だったため、 これはこのように見えました。 それでは、アプローチaを見てみましょう もう少し試験の本のように、 それによって我々は常にありました アルファベットの文字を選択 私達は種類の望んでいたこと 次に対処します。 多分それは高いの手紙でした、 A、または低い文字Zのような だから、誰もが戻って、この順序でです。 そして今、私はこれをしましょう​​。 それでは、私が知っている見てみましょう ここで8の数字。 私は先に行くつもりだと ただ意図的に選択します 最小要素。 右？ これも直感的なようです。 なぜ私は、最小を見つけることはありません 要素、それが属する場所に置きます、 その後、次の最小の要素を取得入れます それどこそれが属する、とだけ繰り返します。 直感的にあるため、 それはあまりにも動作するはずです。 だから4、それはかなり少数です。 私はこれがどこにあるか覚えておくつもりです。 ちょっと待って。 二つは小さくなる。 私は今、どこに2覚えましょう で、約4を忘れます。 我々は、後で対処します。 六、私は興味がありません。 エイトは、私が興味を持っていませんよ。 一つは、私の新しい少数です。 だから、私は1つがどこにあるか覚えておくつもりです。 三、興味を持っていません。 セブン、興味を持っていません。 五、興味を持っていません。 そこで脱落することなく、 ステージは今年、 私は数をつかむつもり選びます - そしてあなたの名前は再び何でしたか？ アナン：アナン。 DAVID J.マラン：アナン。 そして、あなたはで私に参加することができれば リストの先頭 あなたが属している場所の、あなたを入れてみましょう。 Unfortunately--あなたの名前は何ですか？ STEFAN：ステファン。 DAVID J.マラン：ステファンは方法です。 ステファンは、この問題を解決する前に 問題は、我々は何をすべきでしょうか？ 我々はステファンに何をしますか？ 聴衆：[聞こえません]。 DAVID J.マラン：OK。 だから我々はそれを行うことができます。 私たちは、ソートのステファンとを取ることができる彼の 4、ちょうど変数に入れて そして、のためにそれにしがみつきます ある程度の時間、 これにより、ナンバーワンのための部屋を作ります。 そして、それは悪くはありません。 私はなぜない、提案することができ 私たちはここでステファンを置きますか？ なぜこれが1に違反する可能性があります 私たちが始めたアイデアの 先週、前回の話？ うん？ 聴衆：[聞こえません]。 DAVID J.マラン：それにはインデックスがありません。 あなたのように、確かに、と考えるならば 配列、これは負のようなものです、 そう実際にはメモリがありません ここで、これは確かに配列の場合、 以下のような私たちは講義で先週宣言しました。 だから我々はこれを行うべきではありません。 私たちは、変数に格納することがあります。 それとも、何を知っていますか？ 私は他の誰かがそれを示唆して聞きました。 我々はステファンと他に何ができますか？ なぜ私たちは彼を立ち退かせず、 ナンバーワンがあった場所の上に彼を置きます。 あなたがあそこに行きたいのであれば。 そして実際、これは かなり良い解決策。 今一方では、私は種類ました 問題が悪化しました。 フォー遠くになりました それがあるべき場所から。 それは、この半分に向かってする必要があります。 しかし、あなたは何を知っていますか？ それは不運だったかもしれません。 たぶん数8はここにありました。 だから、多分私達は希望 ラッキー頂いております、 そして最後に近い8を押しました。 だから、一日の終わりには、 その種類のすべての平均値アウト。 私たちは4気にする必要はありません。 私は今気にすべてがあります 最小の要素を選択します。 そして今、私はするつもりだもの ナンバーワンを忘れますさん 永久に、私が知っているので 私の後ろにリストがソートされます。 だから、私のリストは、以前のサイズ8でした。 今は、サイズ7のです。 だから、私の問題を得ています 直線的ではあるが、小さいです。 だから今、私が選択するつもりです 現在の最小の要素、2。 六個、8個、4個、3、7、5。 それが最小の要素でした。 だから私は何をするつもりですwith-- あなたの名前は再び何でしたか？ JOSEPH：ジョセフ。 DAVID J.マラン：ジョセフ？ 我々は場所でジョセフを残すつもりです。 今、私はふりをするつもりです これらの人はよくare--こと、 私はこの二つのことを知っています すでにソートされています。 今度は、に焦点を当ててみましょう リストの残りの部分。 シックスは、現在最も小さいです。 エイトは大きいです。 フォー現在最も小さいです。 スリーは現在最も小さいです。 そして今、私は3を選択するつもりです、 誰があなたの名前は再び何is--？ セレナ：セレナ。 DAVID J.マラン：セレナ、あなたができれば あなたの番号とスワップをつかみますwith-- KALSANG：Kalsang。 DAVID J.マラン：Kalsang。 背面に来て、私たちはしています これら二つを交換する予定。 そして今、のは、自動操縦でこれを入れてみましょう。 私が行くと君たちに任せるつもりです 次の最小の要素を選択します。 ダン、焦げ茶色、焦げ茶色、焦げ茶色。 ナンバー4、あなたは何をすべきでしょうか？ 優れています。 今、私は別のパスを作るつもりです。 ダン、焦げ茶色、焦げ茶色、焦げ茶色。 私は5は次の最も小さい参照してください。 今、私は別のパスを取るつもりです。 ダン、焦げ茶色、焦げ茶色、焦げ茶色。 六が最も小さいです。 良い。 セブンは最も小さいです。 変更はありません。 八が最も小さいです。 完了。 だから我々は単に反復することによって何をやりましたか 他の後に一つの要素を選択します 私たちがしている何かを実装しています 選択ソートとして定式化する予定。 そして、それはあっても、おそらくです 説明するのは簡単な、 その中で、文字通りすべてのあなた やりたいだけで維持されています リストを前後に行きます 選択し、次の最小の要素、 あなたが行っているまで。 だから、おそらく、さらに簡単です 直感的に、最後のよりも。 それでは、最後の1を試してみましょう。 あなたたちは、自分をリセットすることができれば 以下の位置に 1最後の時間は、私たちができない場合を見てみましょう 今一つの他のアプローチを正式。 実際には、誰か そこに提案したいです 他にどのように我々はこれをやって行くのでしょうか？ 流行語や並べ替えを投げなければ 既に知られている回答の、 ただ直感的に、私たちは何ができますか？ 聴衆：[聞こえません]。 DAVID J.マラン：うん。 だから、いくつかの素晴らしい直感があります。 良いものは、これまで発生しているように見えます 我々は分割コンピュータサイエンスの および分割の問題を克服 それ半々と半分インチ だから確かに、我々 それを行うために開始することができます。 そして実際に、それはになるだろう、私たちはよ まだ、私たちの最高のソリューションのいずれかを参照してください。 しかし、ここでは、ずっと前に戻ってそれに来るように。 実際には、我々がやろうとしています 少し後今週こと。 我々はこれを解決するために他に何を行う可能性がありますか？ だからここに誰もがにあります 一見ランダムな順序。 あのね？ むしろ前後に行くよりも、 前後に、前後に たびに、これはのように感じています 私は歩行をたくさんやっています。 なぜ私だけで起動しません リストの先頭 そしてちょうどそれが属する4を入れて？ だから、私は瞬間のために仮定しましょう 私のリストは、この最初の要素です。 4つの時間的にこの時点でソートされ、 場合、私は気にすべてがすべてがここにいるのですか？ これは右、ソートの自明本当ですか？ 1番号を含むリスト、など その数4は明らかにソートされます。 だから、私はちょうど定めてみましょう このリストがソートされています。 しかし、今、私はこのリストの残りの部分を持っています。 だから今、私は2つに遭遇します。 2明らかにどこを行います 4に関して属していますか？ 4前。 だから私はここで何ができるのでしょうか？ もう一度あなたの名前は何ですか？ JOSEPH：ジョセフ。 DAVID J.マラン：ジョセフ、 あなたが一歩ことができれば あなたの番号とちょっと。 そして今、ステファンはここで何をすべきでしょうか？ のがここの上にステファンをシフトしてみましょう。 そして今、ヨセフはここに入って来てみましょう。 そして今、私はそれを主張してみましょう ここですべてがソートされます。 そこで、同様の結果が、A 根本的に異なるアプローチ。 私もそこに何があるか見ていません。 私はちょうどの要素を取っておきます 彼らは私に手渡しているように、 そしてそれらに対処。 だから今、私は数6を参照してください。 6番はどこに属しているのでしょうか？ 我々は2つ​​、4つ、6つがあります。 彼女は今、ある場所を正確に。 だから今のはその一人で残してみましょう、と リストのこの部分と主張 今ソートされます。 だから、これは根本的に感じています その内の異なる私はちょうどよ ここでリストを移動します 直線的に、私は戻って倍増することはありませんよ。 はい。 大丈夫。 だから8、どこに属しますか？ ここ。 パーフェクト。 だから今、1。 おっと。 それはだようにこれは感じています 高価になるだろう。 さて、以前のアルゴリズムで、 私は人を入れ替え。 だから私は彼にすべての方法を置く可能性があります 初めは、その後ヨセフを移動しました。 しかし、私は今、ジョセフを移動する場合 何が間違っていることになるだろうか？ 今、私は一種の私がしましたundone--ました 一歩前進して、撮影しました 一歩戻って、今理由 ヨセフは順不同であろう。 それでは、これを実行してみましょう。 あなたはナンバーワンを取ることができれば そして、ちょっとバックステップ。 どのように我々は何をすることができますput-- あなたの名前は再びでしたか？ アナン：アナン。 DAVID J.マラン：代わりにアナン？ 何が関連して発生する必要があります 2、4、6、8か？ 彼らはすべてシフトする必要があります。 だから8がシフトしたい場合 まず、6つ、4つ、2つ。 そしてアナン、あなたが希望の場合 良い、ここに来るのが好きです。 しかし、ここで、私たちはしました 種類の価格を支払っ アルゴリズムにおける異なるポイントで。 選択を前回のに対し 並べ替え、さらにはバブルソート、 私は戻って歩いていると、 前後、前後に、 確かに合算されています 時間的、そして文字通り段階的。 最初は挿入ソート、 一見、それはだように見えます スーパー賢く、その中で私はちょうどよ ゆっくりと、インクリメンタルに進展し、 私は、この前後には行きません。 しかし、誰かが実際にある場合 注文のうち、通知 私はしなければならなかったすべての作業。 私は、リストの半分を移動しなければなりませんでした ただナンバーワンのための部屋を作るために。 だから、同じ量です 仕事のこれまでそれを 仕事のちょうど別のタイプ、感じています。 それでは、続けましょう。 だから今、私たちは皆知っていること 1と8の間にソートされています。 ここで、私は数3を持っています。 あなたがピックアップしたい場合 数3は、1つ前のステップ。 そして、何あなたたちは何をする必要がありますか？ うん。 だからもう一つ、二つ、三つのステップです。 ただ、コスト、時間の3つのユニット 私は、3人は今収まることができるように。 最後に、7。 それでは、先に行くとしましょう あなたは、ステップバックを取ります。 これは私たちだけの費用としています 1時間の単位が、それは大丈夫です。 そして今、5のは、に行きます もう少し高価になります。 あなたはバックステップしたい場合。 我々は、8を移動する必要があります 七、6。 そして、誰もが今、ソートされます。 だからここに私たちのボランティアに大きな手。 どうもありがとうございます。 [拍手] みなさんありがとう。 みなさんありがとう。 それでは、今どれだけ見てみましょう 高価なすべてのことでした。 のは、おそらく考えてみましょう これらの最も簡単な、バブルソート。 そして、私は唯一のため、最も簡単なと言います あなただけのことで貪欲にそれを解決することができます ここでペアごとに問題を修正します。 ペアごとの問題を修正 ここでは、何度も何度も そして再び、多くの繰り返し あなたのような時間は、実際にする必要があります。 だから、ことが判明 バブルソートと、よく、 どのように多くの手順は、私が取る必要があるん このアルゴリズムの最初のパス？ 私は、のいずれかをsee--せtake--可能性があります 2つ、3つ、4つ、5、6、7。 そして、ここで8要素があります。 だから、のようなものだnはマイナス1のステップへ リストの先頭から取得 リストの最後に。 しかし、選択ソートで、私はことを思い出してください 何度も何度も要素を選択 そして再び、それは最も小さいのです、 私は、場所に入れています しかし、私はないんだけど 再び私の後ろに見て。 だから私はそれをもう少し明確だと思います その後、初めてということに、私はかもしれません すべてのnマイナス1のステップを取る必要があります 最小の要素を検索します。 それから私は、場所にそれらを置く、と私 以前ここにいた誰立ち退か。 しかし、私はする必要はありません この要素で探し続けます、 私はそれが知っているので、 既に最小。 だから今、私はちょうど7で見ることができます 要素は、6つの要素、 その後五行、4つの要素。 そのため、数学的、nがある場合 要素または番号の数 使い始めたことを、あなたが想像することができます これは、n -1と同じであること、 プラスNマイナス2段階、 プラスNマイナス3段階、 プラスNマイナス4段階、すべての あと一歩までの方法。 そして、私は私の最後の人にです。 そして、あなたは多くのことを思い出した場合 統計書籍や数学の本の これらの式を持っています ハードカバー背面または彼らの前、 それがこのシリーズのことが判明 より簡単に表すことができます。 n回nはマイナス2以上の1。 それがないなら、それは大丈夫です あなたの心の最前線に。 しかし、これは確かに真実です。 それはそれを書いているだけのシンプルな方法です。 それから、あなたが考える場合 バック小学校に、 あなただけの乗算を開始するとき 物事うち、このコースの、 ちょうどN乗マイナスnは、2で割っています。 私がやったすべてが拡大しています そこに表現。 そしてそうのはこれを書き換えてみましょう 少し違いました。 それは、N 2を2で割っマイナスN /平方です。 だからもう一度、私は一種の適用です そこにいくつかの算術ルール。 しかし、今気付くことの最大の用語 この式では、いわば、 nが乗ということです。 そうです、それは、n乗です 2、マイナスのn / 2で割りました。 一般的に、もしnが 大きな値になるだろう、 私は、nが平方主張するつもりです 支配的要因になるだろう。 それはちょうどになるだろう 大きな貢献者 N / 2よりもステップ数です。 だから私はこのとはどういう意味ですか？ でも、簡単な例を試してみましょう 数学は少し大きいを取得しますが。 だから我々は100万人を持っていたと仮定 ステージ上、または100万のもの 私たちは、ソートしたいということ。 のは万人をプラグしてみましょう まさにその式に それが総取りどのように多くの手順を確認し たとえば使用して百万の要素をソートするには、 選択ソート。 だから我々は、以前と同じ式を有するだろう。 私が得られるように、私は、百万プラグたいです 、2で割っ乗万人 マイナス2で割っ万人。 私は、事前にその計算を行う場合 ここで、我々は5000億を持っています マイナス500,000します 私たち4999.995億を与え、 これはかなりくそ大きいです。 実際には、あなたは今比較する場合 4990億999百万円 私たちの元の値に対して500,000 5000億、それはとても気近いです。 右？ nは2で与え割っ乗 us--いうか、nは2で割っ二乗 私たち5000億を与えました。 それはかなりくそ近いです 4999.995億に、 500,000オフ差し引くと言うことです、 またはより一般的には、減算します nは、本当に大したことがない乗。 これらを作るnが平方しました 数字は本当に速い成長します。 さて、これは重要である限り 我々として、コンピュータ科学者として、 一般的にはあまり気にするつもりはありません これらの式のニュアンスについて そしてまさに 正確な答えがあります。 私たちは、あなたが何を知っている、ということだけ気に？ 一日の終わりに、この式 二乗Nのオーダーです。 はい、私たちはそこに2で割るいます。 はい、私たちはオフのnマイナス2を引いています。 しかし、一日の終わりに、用語 それは本当に私たちを傷つける、私たちがかかります 手順の多くは、その正方形の用語です。 だから何コンピュータ科学者 一般的に行うために起こっています それらのすべてを無視しています 小さい次項、 そしてちょうどその1を見て コストに最も貢献しています。 我々はできるので、これは、いいです 今はるかに大きい一般に話します アルゴリズムについては、それらを比較することができます。 私はだと、実際 このOを使用すると、意図的です。 私は順番に言うとき 私は特にです 何かに言及 大きなO.とビッグOと呼ばれます そのコンピュータの表記があります 科学者は、記述するために使用しています 上位何かに結合しました。 ですから、アルゴリズムと言う場合 n個のビッグOで2乗さ、 私が提案されているようなだけ 先ほど、その手段 そのランニングの観点から 時間やその効率、 それがために取ります n個のステップを乗。 多分少なく、多分より。 しかし、それは、nの順に乗です。 そして、それは上限です。 それはあることを行っていません それよりももっと痛いです。 これは、n乗になるだろう、または2いません N、またははるかに大きなものに。 これが上限であります 何でそのコストがあります。 だから、みましょうことを考えると いくつかの例を考えてみましょう。 そして、これは単に有限リストです 非常に一般的な実行時間の であることを意味していアルゴリズムの 私たちがきたいくつかのものを例示します すでに見。 例えば、例でそう 選択ソート、私はここで何を主張しています その選択ソートの走行があります 時間は、N乗のオーダーです。 最悪の場合、私が持っているつもりです ここでは、乱数の全体の束。 そして、私たちが数学的に見たように、 私は歩き続ける場合 リストをスルー 次の最小を選択リスト、 幾度もの要素は、私の場合 実際の手順のすべてを書き留め 私はformulaically提案されているように私は取っています 前に、それは、N乗のオーダーです 私が取っている段階。 そしてそれは、そのバブルが判明 ソートと挿入ソート 最悪の場合、同じように遅いです。 例えば、考えてみて、挿入ソート、 我々はに対処最後のアルゴリズム、 これは、私たちは、要素を見ていました、 それが属している場所と、それを挿入します。 そして、我々は次の要素を見て、 それが属している場所、それを挿入します。 だから、可能な限り最高のシナリオを検討してください。 私は私のボランティアがラインアップしていたと仮定 文字通りこのような、8一通り、 すでにソート。 挿入ソートはどのように多くのステップであります 8人をソートするために連れて行きます、 彼らがステージに到着した場合 このように見て？ 8人はすでにソート。 そして、私は挿入ソートを使用します。 アルゴリズムのその最後。 さて、本当の高速をreenactてみましょう。 私はここから始めあれば、私は1つを参照してください。 1はどこに属しているのでしょうか？ それはここに属します。 私は2つを参照してください。 二人はどこに属しているのでしょうか？ ここ。 私は3を参照してください。 3人はどこに属しているのでしょうか？ ここ。 私は4を参照してください。 ここ。 5つ、6つ、7つ、8。 自分自身を繰り返す理由はありません。 だから、どのように多くの手順 すなわち、n個の点ですか？ これは、n個のオーダーです 手順は、右？ nはマイナス1。 しかし、私は線形数を取りました ステップの、そして今私は終わりです。 だから、しかし、最良の場合です。 何最悪の場合はどうですか？ 何8は、あそこにありました そして、7がダウンしました、 そして、1と2はそう、ここを超えていました リストは本当に逆転したこと？ さて、何が実際に起こります これは数ありますか？ そして、我々は例だけのカップルをやります。 何確かに、もし、数8 ここで、number--おっと。 だから何であれば、確かに、数 8は、こちらにすべての方法です、 私は挿入ソートを使用していますか？ OK。 私はそれが場所でだ瞬間に主張しています。 しかし、今、どこseven-- 7は行くのですか？ もちろん、それはここを乗り越えます。 だから私は、8人以上の場所を移動する必要があります。 今6、どこに行くのですか？ まあ、すべての権利。 今、私は8オーバーを移動する必要があります 場所、および場所の上に7、 そして私は6をドスンと座ります。 そこで初めて、コスト 物事を解決する私の一歩、 それは私に物事を修正するには、2つのステップを要しました。 それはどのように多くのステップであります 修正するために連れて行きます 正しい場所に5を置くためのもの？ 3。 今私がする必要があるため、 一、二、三を動かします。 どのように多くの手順は取るつもりされています 正しい場所に4を置きますか？ 4プラス5、プラス6、+ 7。 そしてそれは、数学的に同一のです 我々は、選択ソートのために記載するもの。 我々は、このシリーズを持っています それはただ増加しています。 1プラス2プラス3プラス4、 あるいは逆に、7プラス6 プラス5プラス4は、今日のためにアップ追加します n個のオーダー乗にする目的。 だから私もそれを規定しましょう バブルソートは、nの二乗でもあります。 バブルソートと、各ので、 私はリストを通過する時、 私は大体どのように多くのステップを取っていますか？ たびに私は、文字通り そこに、そこから歩いて？ おおよそnステップ。 しかし、どのように何回も私はかもしれません リストを通過する必要がありますか？ まあ、おおよそn個の時間。 たぶん、nはマイナス1であるが、おおよそn回。 まあ、それはなぜですか？ まあ、バブルソートと、もし 私たちは、バブルソートで始まります 最悪でリストを 再び完全な状況、 後方に、何が起こるだろうか？ 私はリストを通過し、その数 一つはあそこのすべての方法に属します。 しかし、バブルソートで、どの程度まで1を行います リストを私の最初のパスに移動しますか？ 彼はどのように多くのスポットを取得しません 正しい場所に近いですか？ 一つだけ。 だから、これを介して、あなたは親切の理由であれば、 このアルゴリズムを通じて毎回、 ダビデの服用およそnステップ。 しかし、どのように多くのパス リストをそれがあります バブルへのいずれかに連れて行きます それが属する左に？ 彼は、のように移動するために持っています n個のスペースがこの方法です。 だからリストのソートを行うには、 私は前後にn回を歩かなければなりません。 そして、それぞれの時間は、私はよ n個の要素を見て。 ように、n個のものをn回行います n個の順序は乗。 今、我々はいくつかに表示されます ショートパンツのこと CS50の次の問題に埋め込まれています これらに、別のアプローチを設定し、 しかし今のところ、ちょうど考えてみましょう 他のいくつかの実行時間、 仕分けものは取る場合は特に でシンクする時間を少し。 我々はすでに見てきたアルゴリズムは何ですか すなわち、n個のステップの順序をとりますか？ 線形数を取る必要がありますどのような 私たちがこれまで見てきたステップの？ あれは何でしょう？ 電話帳を検索します。 最初のアルゴリズム。 右？ 私たちは、直線的にしている場合には マイク・スミスをお探しですか？ 確かに。 0週目からは、私が始めたとき 一度に一つのページをめくります、 そして私もそれは親切だと言いました リニア感アルゴリズム、 私たちは上の画像を持っていました ストレート赤線とボード ストレートイエロー ライン、それらは確かにありま​​した n個のビッグOであるアルゴリズム。 電話でマイク・スミスを見つけるため、 最悪の場合、nページの本、 私のn措置をとることがあります。 出席を取ることについてはどう？ 一二三四五六。 これの実行時間は何ですか 出席を取るためのアルゴリズム？ なぜなら理論的には、nのビッグO、私は 部屋に全員を指すように持っています。 さて余談として、どの程度 0週目から他の最適化？ 2つ、4つ、6、8、10、12。 コンピューター科学者になります 実現、ちょっと待って、 それは、順番にい nは2段階で割りました。 右？ 私は一度に2人をやっているので。 しかし、我々は無視するつもりです これらの低次の項、 そして、私たちはするつもりです 2による除算を捨てます、 そして、だけ、言って、nのビッグO そのアルゴリズムのためにも。 これはどう？ 当社は、これらのいくつかをスキップが、何だろう n個のログだったアルゴリズムでしたか？ それはおよそログn個の手順を取りましたか？ 分割統治。 その通りです。 電話帳の例のように 0週目およびそれ以前の今日、 ここで、我々は問題を分割 何度も何度も何度も。 私たちは週にボードに描きました 湾曲した緑の線としてゼロ、 そして我々はそれがその日だったと述べました 対数アルゴリズム。 そして実際、ステップ数は、 分割統治を実行するのにかかります、 私たちは始めましょうとして、またはバイナリ検索 電話帳のように、それを呼び出して、 ログおよびステップのオーダーです。 そして、これは奇妙な1のビットです。 何が一歩を取り、 より具体的に ステップの定数？ 多分それは多分それは3ですが、2です、 しかし、コンピューター科学者だけ 1のビッグOとして、それを簡素化し、 手順のいくつかの定数。 あなたがそれを行うことが何か何 ステップの一定数を取りますか？ 拍手の実行時間は何ですか？ 一定の時間。 右？ 同様の実行時間は何ですか 一つだけを取る何かをやって 印刷F Hello Worldのような操作、。 すなわち、一定の時間であると言われるかもしれません 印刷Fと少ないコーナーケースでない限り、 何走行時間かもしれません 印刷のFは、実際にも？ なぜ？ その場合のn個の測定とは何ですか？ 聴衆：[聞こえません]。 DAVID J.マラン：その通り。 文字数 我々は、印刷したいです。 だから、非常に状況依存です。 今日、私たちは上の多くを集中してきました ボード上のここに文字と数字。 しかし、それはまたあるかもしれません 実際の文字列内の文字。 だから、別のがあると判明します 気に開始され、測定、 それは反対です ビッグOの、いわば。 それはオメガの表記です。 ビッグOは、何を意味するのに対し 上部のあなたの実行時間にバインドされましたか？ 最大限に、どれだけの時間 何かがかかるかもしれませんか？ Omega--申し訳ありません、これは来続けます up--はその反対で、 それによって、それが上下限です 何かがかかる場合があります時間の量。 Soが例えば、アルゴリズムは何ですか それはいつものn乗の手順を実行しますか？ さて、私たちはアルゴリズムのいずれかを見てきました 今日、実際には、それにもあるかもしれません。 選択ソート。 選択ソートかなり愚かです。 でもでも、algorithm--残念場合 配列が既にソートされている場合、 選択ソートをしようとしています リストを歩き続けます それは最も小さい持っていることを確認します 要素、何度も何度もして、もう一度。 そして、あなたは人間であっても 観客は、数分待つことを知って、 あなたは既に経過 最小要素、コンピュータ それが見えるまでことを知りません リストをすべての方法。 同様に、下側のことをバインド また考慮されるかもしれません 線形時間であるかもしれません。 それはどのくらいの時間をすることがかかります 最良でソートn個の要素 バブルソートのようなものを用いた場合？ あなたのリストがすでにソートされているとします。 私たちは、バブルソートをオンに取ると述べました n個の順序は、ステップを乗。 しかし、それはすでに何をソートしていますか？ あなたは何をした後に実現した場合 配列内を1パス あなたはスワップを行わなかったこと？ あなたがより多くのパスを作り続ける必要がありますか？ いいえ。 バブルソートのだから下界 線形であると言うことがあります。 n個のオメガ。 そして、私たちは見ることができ これらの他にも。 それでは、簡単に見てみましょう ここだけの可視化で これらは自分自身を区別する方法を確認します。 私はこの中に、ここでダウンして行くつもりです C50のウェブサイト上で利用可能なページ、 それが働いて得るために苦痛になり、 それはと呼ばれる技術を使用していますので、 あるJavaアプレット、 大部分がサポートされていない、これらの日、 少なくともChromeと特定の他者による。 そして、私が先に行くと、これを加速させます アップと何が起こっているかを説明します。 これは、バブルのデモです ソート、私たちが見た最初のアルゴリズム。 そして、各点での可視化です これらのバーの数を表します。 大きなバー、 数より大きい。 小さいバー、 数より小さい。 そしてあなたも、視覚的に見ることができるもの これは、超高速起こっているものの、 赤いバーは私のようであることで、 問題を修正する前後に歩きます。 あなたは大きな要素ということを見ることができます 確かに、右にバブルアップされています 小さい要素 左に湧き上がっています。 そして、ここでダウンして、私たちの場合 実際にはより密接に見て、 私たちは実際に数えることができます 比較とスワップの数 それが行われていました。 しかし、その代わりに、のは見てみましょう 第2のアルゴリズムで 私たちはして先を見て ボランティア、選択ソート。 視覚的に、それは持っています 非常に異なる効果。 しかし、それはでは、再び、非常に直感的です 我々は次の最小を選択しておくこと 要素、私たちは少し幸運。 それは基本的に速く感じました。 しかし、我々は何度も何度もこれを実行した場合 そして再び入力の多くが付いて、 我々はそれが確かだと見ることが まだn個の大きなOに乗。 それでは、最後のいずれかを実行してみましょう ここでは、挿入ソート、 これは第3のアルゴリズムました 我々は見て、リコール これは、扱っていること 要素それが彼らに遭遇すると、 しかし、それは多分にシフト 物事の上に部屋を作るために、 彼らが属している要素を挿入します。 そして、これはあまりにも与えてしまいます 最終的な結果。今、それらのすべての3つの かなり速いと感じました。 そして実際、私はそれらを実行しました かなり良いクリップで。 しかし、基本的に、彼らはすべてしています 正直に言うと、かなり恐ろしいです。 これらのアルゴリズムのすべてのこれまで N乗のビッグOでその実行 かなりのを取ります 最終的に実行するための時間。 そして実際、我々が見ることができます 最後にこれを感じます 私はこの3番目と最後のデモを引き上げます。 これは、別のあります 起こっているの可視化 左側のバブルソートを表示するには、 途中で選択ソート、 私たちの一つとして何か、 手が先に提案した発生させ、 右側の並べ替えをマージします。 分断攻略 右の戦略。 そして、それは私たちがしているもの、実際には、です 水曜日に見に行きます。 しかし、の並列で実行するために、これらの時間をしましょう​​。 それは大体同じ数です 要素は、全てが同時に実行されています。 選択対バブルソート マージソート対ソート。 今、彼らはすべて実行しています 同時に理論インチ CPUがで実行されています 同じ速度が、あなた これがどのように退屈を感じることができます 非常に迅速になろうと、 そしてどれだけ速くするとき 私たちは週のビットを注入 ゼロのアルゴリズムすることができます 我々は物事をスピードアップします。 そして今のは、比較してみましょう 最後の形でこれらの。 私は先に行くつもりです CS50のウェブサイトへ 我々は、今日のために、この最終的なリンクを持っています ここで、インターネット上の誰か 親切にすることを一緒にビデオを置きます 何異なるソートをキャプチャ アルゴリズムは次のように聞こえます。 これは、挿入ソートです。 [ビープ音] これによりあなたは周波数を適用しています バーバーの高さに基づいて。 これは、バブルソートです。 【反っビープ音] 今後is--次回来ます 次is--選択ソートアップ、 再び、我々はどこを選択しています 次の最小要素、 そして我々はそれが成長して見ることができます 左から右へ。 今日これまでの並べ替え、私たちの勝者をマージします。 それは物事を分割していますに注意してください [聞こえない]の半分と4分の1に。 私たちが持っていないノームソート、 話しました、そして視覚的に作成し、 とのビットをaudally 異なる形状と音。 前後に行きます、 物事をクリーンアップ。 また、ヒープソートをチェック この男のウェブサイトで。 そして、それはそれです。 私たちはあなたの次の時間が表示されます。 【WHOOSHINGと音楽]