Tip:
Highlight text to annotate it
X
>> [音楽再生]
>> DAVID J.マラン:すべての権利。
だから戻って歓迎します。
これは、CS50であり、である 週3の終わり。
>> だから、過去数週間でリコール 我々はかなりの出費してきた
Cで、プログラミングの、構文上の時間。
もしまだなら、それは、かなり普通のこと であるためには、問題のセット2に苦しんで
壁に頭を強打。
それは不可解に見えるエラーメッセージだ あなたこととバグ
かなり追いかけることはできません。
なぜなら、安心、という点で、まさに 数週間の時間あなたに戻って見てみましょう
カエサルのようなもの、と[? V-genair、?] 多分キズ、
あなたが来てどれだけ遠くに実現 短時間である。
それはどんな慰めだのであれば、 今のところそこにハングアップ。
>> 今日は、しかし、我々は移行し始める ものより高いレベルに。
そして、私たちは当たり前のように始めること 君たちは、プログラムする方法を知っている、またはで
少なくとも始まりの その快適さのレベル。
そして、我々はどのように我々ができる考慮することから始めましょう 複数のプログラムを設計に取り掛かる
効果的に。
私たちは、最適化に取り掛かることができますか 我々のアルゴリズムの効率化、
一般的に、よりを解く 興味深い問題。
と、という当たり前のように開始 我々がしたい場合、我々は、任意のをコーディングすることができ
我々は心を持っている例。
今日のように、我々は、キーボードに触れないでください コードの任意の形式のために。
これは、はるかに高いレベルにあり、よ 最終的には、問題解決について。
>> だから、その点に到達するために、私が提案してみましょう その次の7つの
長方形は後ろ、7扉を表す の全体の束である
数字は、その中に数50です。
私は、この上でこれを投影してみましょう 同様にここに画面が表示されます。
そして、我々はにボランティアを必要とすることを提案する 私の前の数字を見つけるのを助ける
見るためにここにインターネット。
ピンクで、上昇に来る。
わかりました。
あなたの名前は?
>> JENNIFER:[聞こえない]
>> DAVID J.マラン:申し訳ありませんが?
>> JENNIFER:ジェニファー。
>> DAVID J.マラン:ジェニファー。
すべての権利、ジェニファー。
よろしくね。
までさあ。
したがって、これらはここで7の扉であり、どのような 私はあなたがここに私たちのためにやりたい、
クラスメートのすべての前に、 私達に数、50を見つけることです。
番号を見つけるためには、後ろにのぞくことができます 単にタップして、これらのドアのいずれか
扉の1つに、それ その番号を明らかにする。
そして、どのように迅速に見てみましょう 私達に数、50を見つけることができます。
>> 15。
16。
50。
うまく行って。
わかりました。
ジェニファーのために拍手。
>> [拍手]
>> わかりました。
だから、あなたのための戦略は何だった 、50の番号を見つける?
>> JENNIFER:うーん、私は多分あればと思った -
[聞こえない]
>> DAVID J.マラン:ああ。
それを一秒を与える。
だから、あなたのための作戦のようだった 、50の番号を見つける?
>> JENNIFER:だから私はちょうどで始まる 見始めて何を最初の番号
多分あれば、あった、そして私は思った それらをソートしている、私はしておこう
上位にタップ?
>> DAVID J.マラン:OK。
そして、私たちは発見したように見える このケースのように。
が、裏のレイヤーをしてみましょう 少しだけ、あなたが行きたい
先に他のドアを明かす あなたが選択しただろうか?
>> JENNIFER:ああ、親愛なる。
>> DAVID J.マラン:ああ。
>> JENNIFER:だから私はただ幸運。
>> DAVID J.マラン:だからあなたは幸運。
わかりました。
そんなに悪くない。
しかし、それは興味深い 洞察力、右?
あなたが想定し、あなたは手に入れた場合は、 そこに確かに、ちょっとラッキー。
しかし、あなたは数字があったと仮定した場合 ソートされた、あなたは、より正確にすることができます
それが影響を受けた方法として あなたの行動?
>> JENNIFER:だから彼らがソートされた場合、I 小さい方から大きい方へ多分思った。
>> DAVID J.マラン:OK。
>> JENNIFER:それともこれが終わった場合であること 最小にその後最大、本当に大きい。
>> DAVID J.マラン:OK。
だから最小に最大、または 小さい方から大きい方へ。
しかし、あなたが持っていたと仮定し、私は提案してみましょう 不運得、そして彼らと仮定
、実際には、並べ替えられていなかった、どのように多くの あなたは覗きにそれらの扉を持っていたかもしれない
その最悪の場合には後ろに?
>> JENNIFER:それらのすべて。
>> DAVID J.マラン:それらのすべて。
それでは、nとそれを一般化することができます。
そこに7であることを起こるが、レッツより 一般にn個のドアがあると言う
ここに画面が表示されます。
だから、最悪の場合には、あなたが持っているでしょう 7ドア、またはnドアの後ろに見えるように。
そしてこれは実際にそれがのビットです、です 運は、今日、それは本当に線形だ
ある種のアルゴリズム、たとえあなた 周りのスキップの親切でした。
その公正ですか?
>> JENNIFER:うん。
>> DAVID J.マラン:まあ、私はあなたの場合を見てみましょう 私は私たちに移動する場合の戦略の変化
ここで私たちの第二の例 7種類のドア。
同じ数字が、この 時間は、それらが並べ替えられています。
になるだろうここにあなたの戦略は何ですか あなたの心の外に置くことをしようとして何
他の番号であった -
>> JENNIFER:OK。
>> DAVID J.マラン: - 以前の?
>> JENNIFER:レッツスタート 最初のものである。
>> DAVID J.マラン:すべての権利。
最初の1で始まる。
4。
今、どこに行くつもり、なぜ?
>> JENNIFER:4は本当に小さいです。
彼らはソート多分最小いるのであれば 最大にするには、すべき
- 二度あること、となる。
>> DAVID J.マラン:OK。
あなたが考えている、見てみましょう?
>> JENNIFER:最後の1をお試しください。
ニース。
>> DAVID J.マラン:非常にうまくやった。
わかりました。
>> [拍手]
>> DAVID J.マラン:OK。
だから、実際にこれをやっている 恐ろしく、あなただから
非常によくそれをやって。
どちらにできない私たちを残し 特定のポイントを作る。
だからここにロールバックしてみましょう。
>> JENNIFER:OK。
>> DAVID J.マラン:非常によく それにもかかわらず、行って。
だから、初めに開始 それは、その後、あなた4だったことを見た
最後に移動。
しかし、あなたは幸運取得していないと仮定し 、そこにあるとし50
どこか別の場所だった。
何があなたの第三段階であった?
>> JENNIFER:先頭に戻ります。
>> DAVID J.マラン:戻る 先頭に。
[OK]を、ので、あなたが触れただろう 8だったこのドア、。
わかりました。
だから、50ではありません。
どこで次のを見たでしょう?
>> JENNIFER:私はしませんでした場合 それらがソートを知っています。
>> DAVID J.マラン:正しい。
さて、あなたはやったかどうかを知る それらはソートされた -
>> JENNIFER:ああ、ええ、知っていた。
>> DAVID J.マラン: - しかし、あなたはしませんでした 50はまだだったどこに知っていますか?
>> JENNIFER:ちょうど続ける。
>> DAVID J.マラン:すべての権利。
OK。
続ける。
OK、その私が扱うことができます。
>> JENNIFER:OK。
>> DAVID J.マラン:今、あなただけなら 続けるために行く、あなたは何ですか
にバックアップ委譲アルゴリズム。
>> JENNIFER:リニア - 。
>> DAVID J.マラン:それは線形の一種である。
しかしせ、私が提案してみましょう 私はその場に置く。
私はページをリフレッシュしてみましょう。
同じ番号、同じ配列、 同じドア。
しかしのその最初の日に戻ると思います 我々は電話帳を引き裂いたクラス
半分、のソート、何だった そこに私たちの戦略?
>> JENNIFER:中央にスタート。
>> DAVID J.マラン:OK。
だから途中から始まります。
それでは、先に行くとそれをシミュレートしてみましょう。
半ばまでに開始 そのドアを明らかに。
だから数16。
だから強い男は何をしただろう、 誰が、半分に電話帳を引き裂いた
次の推測に取得するには?
>> JENNIFER:この半分に移動します。
>> DAVID J.マラン:なぜ右に?
>> JENNIFER:彼らは最小の一種だったら 最大にし、50は次のようになります
その終わりに。
>> DAVID J.マラン:良い。
完全に合理的。
だから、電話帳のように、あなたがに行く 右、左とは対照的に、ここで
キー持ち帰りです。
これで、捨てる、またははがすことができます この問題の半分は、あなたをしないまま
7ドア付きますが、本当にただ3。
の約半分である 問題の大きさ。
わかりました。
だから今、あなたが持っている何 あなたが右に行く後に行う?
>> JENNIFER:だから16は、まだかなり小さいです 50に対してので、多分私は、試してみます
このいずれか、のような。
>> DAVID J.マラン:すべての権利。
42。
ので、今大丈夫、あなたは何ですか 本能はあなたを伝える?
>> JENNIFER:私は捨てることができます この後、ただ -
>> DAVID J.マラン:OK。
良い、あなたは離れて投げることができる そこに左半分。
>> JENNIFER: - この一つを選ぶ。
>> DAVID J.マラン:そして右。
>> JENNIFER:うん。
>> DAVID J.マラン:だからそれが難しい場合でも、 のみがあるときは、おそらく見て
7ドア、今、考える、 の一貫性
あなただけ適用されたアルゴリズム。
以前のケースでは、あなたがした 偉大だった、幸運を得る。
しかし、あなたは、ヒューリスティックを使用していたのか 私は言うでしょう。
あなたの本能のようなものを使用し、 それはかなりの場合、それは、並べ替えを知る
初めに小さな、明らかに、我々はしました 右にもっと行くようになった。
しかし、いくつかの意味で、あなたは幸運 多分これは、100番だったので、
そして多分50は途中で以上であった。
多分50はこっちでもあった。
>> しかし、あなたは少し異なるものでした この時間は、あなたが同じ事をしただった
何度も何度も。
そして、私は何をあなただけのことを主張するだろう 電話での影響を受けながらも、やった
本例では、ずっと何か より多くのアルゴリズム、および大いに
少ない特殊で同棲。
はるかに少ない本能。
だから一日の終わりに、どのようにだろう あなたの効率を記述する
あなたが行った最初のアルゴリズム、 左から右へ、対
ここで第2のアルゴリズム?
>> JENNIFER:こちらは、多分、好きなはず 時間を半減、あるいはそれ以上、うん。
>> DAVID J.マラン:OK、多分もっと。
その上で少しハードにプッシュしてみましょう。
本当に何が、我々はこれを継続する場合 ロジックは、我々は間違いなく半減
この第2のアルゴリズムとの時間を実行している の半分を捨てることによって
数字が、我々は次の何をした ジェニファーは明らかに繰り返し、
二番目の数字?
>> 我々は再びドアの数を半減。
そして我々は、その後何をした場合 一緒にプレイするより多くのドアがあった?
我々は、それらを再度半減し、なる そして再び、再び。
そして、これはすべてただ皆さんのようだった の最初の週に立っ
クラス、座ってあなたの半分、半分 あなたの、あなたの半分を座っ
1単独まで、座っ 魂が立っていた。
そして、私たちによるとの実行時間 こと、それがかかったステップ数だった
何のために?
>> SPEAKER 1:[聞こえない]
>> DAVID J.マラン:だから、ログベースのn 2、 またはちょうどより簡単に、n個のログ。
対数だから何か。
とグラフが直線ではなかった ただ悪化し、悪化したこと、それがあった
しませんでしたこの興味深い曲線 時間をかけてそんなに悪く得る。
それでは、このアイデアを保持しましょう。
ジェニファーに感謝しましょう。
アップ時に来て本当にありがとうございました。
と、1秒。
いいえデスクランプない今日が、私たち CS50ストレスボールを持っている。
>> JENNIFER:イェーイ。
>> DAVID J.マラン:すべての権利、ここに。
負担していただきありがとうございます ここでストレスまで。
わかりました。
だから我々は今、できないかどうかを確認してみましょう もう少しこれを正式なもの。
だからもう一度、私たちがちょうどやっていた 我々がしたように本質的には同じこと
その最初の週である。
しかし、だけではなく、直線で終わる 私たちが描かれたアルゴリズム、
以前にこの直線として、 それによって、我々は上の1つ以上のドアを置けば
画面には、その後ジェニファーはでしょう 、潜在的に、見てきた
もう一つのドアの後ろに。
我々は、さらに2つのドアを置く場合は、彼女が持っているかもしれません さらに2つのドアの後ろに見えるように。
>> そして、この直線があった のサイズの関係
x軸、言う、上の問題と、 それに要する時間
Y上解決する。
しかし、私はをほのめかしていた絵 以前この緑色のラインがあった。
なぜなら、故意にグリーン それはちょうど良い感じ。
我々はそれをやった理論的には、アルゴリズム、 電話帳で、ときに我々はそれをやった
君たちはお互いを数えると、と 後者の場合に、時だけジェニファー
ここでそれをやった、それがものだった 根本的に良いの。
それはちょうど倍の速さではなかったので。
それも、高速の4倍ではなかった。
それは何に完全に依存していた 入力の大きさはどのように多くのように、だった
それが最終的に取った手順。
>> そして、我々はすべてのかかったように、このシンプルなアイデア 電話帳で付与するため、
同様に適用することができる このような何かに。
そして、これはもっとさりげなくあるかもしれない あなたかもしれませんが、として知られている
分割統治、想像してみてください。
ではない私たちがやったこととは違って、もちろん、 電話帳と。
>> しかし、擬似コード、リコールは、これだった。
だから我々は再びこれを行うが、思い出すことはありません 最初の週に、私たちのすべてが立ち上がっていること
その後、あなたの半分は半分の、座っ あなたの半分は座って、座った。
そのアルゴリズムで実装されました それ、で不正行為の方法のビット、
私のひとつは、カウントされませんでした 基本的に、より効率的に。
その場合は、私が活用していた セカンダリリソース。
並べ替え、複数のCPU、複数の脳、 で複数のスマートな人々
部屋には何かから私が得る助けた 何かに線形
何かから、対数 緑色の何かに赤。
>> しかし、このケースでは、一人でジェニファーができます 根本的に改良
彼女の最初のアルゴリズムの性能によって、 再び、ほんの少し難しく考える。
そして今、それを実装するための時間が来るとき これらの事を、考え出す
何がそのような書くことができますコードの行 あなたはそれらを再度繰り返し、できること
再び、再び、ソートの ループのファッションである。
あなたが持ってするつもりはないので ジェニファーのような贅沢は、するために、最初はなかった
ただ、IFSの全体の束を持っていると言う うーん、もしこの最初の数字が4である、
私は最後まですべての方法をジャンプしてみましょう。
その数が大きすぎる場合には、ああ、 私は勝手に戻って移動することができ
二番目の要素に。
あなたはそれがたくさんになるだろうことがわかります 難しく正式に私たち人間
非常に合理的なように当たり前の ヒューリスティックが、コンピュータがあるだけで
あなたがしなければ、それを言うことをするつもり。
>> さて、これは非常に興味深いものがある 意味合い。
このグラフは、ソートの一種のことを意図している 視覚的に圧倒、しかし予告、どこ
このグラフの直線のですか?
線形グラフはどこです 我々はnを呼んでいる?
まあ、それは下の方にソートのだ この写真の、右?
だから私たちがやったすべては、我々は一種のをしましたです x軸とにズームアウト
何の感覚を取得しようとするために、y軸 曲線の他のタイプのように見える。
>> と数学の仕様 今日はそう問題ではないでしょう表現
多くの、しかし、多くのがあることに気付く よりもはるかに悪化しているアルゴリズム
リニアだもの。
確かに、乗nがかなり悪い見える。
2 nにはかなり悪いよう。 乗nがかなり悪い見える。
そして、私たちはそれらのどのようないくつか表示されます 現実には今日かもしれない。
およびログnが悪いように感じるのではなく、 nより良いnのログベース2です。
しかし、あなたが知っている、それもあったであろう ジェニファー場合、あるいは我々であればもっと素晴らしい、
その最初の週、思い付くしていた n個のログのログですか。
>> だから、他の言葉で、この全体はあり への可能な解決策の範囲
問題は、しかし、ここでも、予告 何が起こるだろう。
これらの曲線の私がズームアウトすると、その 絶対であることを証明するために起こっている
今、画面上のものの最悪?
だからN乗がきれいに見える 現時点では悪い。
しかし、我々はズームアウトするとの詳細を参照する場合 ために起こっているxとy軸、
最終的に支配する?
だから、実際にはその2が判明 nと、あなただけのことで、これを把握することができます
一部ますます大に差し込む 数字、あなたはわかりますその2〜
nは、確かに、大きくはるかに速くなります。
私たちは本当にに、2をズームアウトする場合 nのアルゴリズムでは、絶対に吸う。
私はこれがかかるとしていることを意味 ためにかなりの時間
を通じて解約するコンピュータ。
>> しかし、あなたは特に、時間をかけて表示されます 将来の問題セットを持つとさえ
最後のプロジェクトは、あなたのデータであり、 セットには、すべての権利を大きくなる?
でも、フェイスブックの最初のバージョンで、 友人の数、など
登録ユーザー数は、大規模だ あなたは、携帯電話でのそれを並べ替えることができますし、
、線形探索で何かを実装する または非常に単純なソート
今日我々が見るようにアルゴリズム。
あなたが難しく考え始めなければならない これらの問題について難しい。
そして問題の場所の種類のような フェイスブック、およびGoogleとMicrosoft、
とで動作する他の人はこれらの正確です 質問のビッグデータソートのソート
ますます、これらの日。
>> わかりました。
その第二にジェニファーの成功だから アルゴリズムは、率直に言って、彼女は驚くほどでした
よく初めて、しかしみましょう それは運のように書いているので、
このポイントを作ることができます。
第二のケースでは、彼女が活用 再び繰り返されるとアルゴリズム
再び、彼女は当たり前のかかった 我々は許可されている一定の前提
彼女が、彼女はいくつかの詳細を悪用し 彼女が持っていなかった二度目
初めて。
何がどのようでしたか?
>> リストがソートされている。
だから、すぐにリストがソートされたとして、我々 ジェニファーは行うことができたと主張している
根本的に良い。
7ドア、はい、その興味深いものではありません、 しかし、それは我々が700万扉だと仮定します。
n個のログは間違いなく起こっている 、はるかを実行する
長期的にはより速く。
しかし、彼女は持っていた ドアは彼女のために並べ替え。
今、私はそれを行うための自由を取った コンピュータ画面上で、事前に
ここが、そのジェニファーと仮定 彼女自身それを行う必要があった?
と仮定し、その質問にドア 表され、データベース内のデータ、または
フェイスブックに登録され、または友人 インターネット上の任意のWebページにその
様々なウェブサイトでは、必要があるかもしれません インデックス以上検索する。
>> あなただけの生データを持っていたと仮定し 設定し、それがあなたに残された、またはする
ジェニファーはそのソートを行うには?
むしろ、我々は答えを必要とすることに、 質問、まあ、どのくらいの時間
ジェニファー、あるいは私を、かかったでしょう 事前にこれらの数字をソートするので、
彼女はそれを活用することができること?
右?
もちろん含意は、、であるため それは、並べ替えることが私にかなり時間がかかる場合
一体あなたのことを気に数字、 50のような数が非常に速く見つけることができる、
ジェニファーの場合のように、我々は以上の場合 合計時間の量を圧倒
それは、事前に物事をソートした?
>> だから我々はできないかどうかを確認してみましょう ここで絵を描く。
私は全体の束より多くのストレスを持っている ボール、場合に役立ちます
ここで氷を砕く。
そして、あなたは気にしないならば、我々 7ボランティアを必要とする -
OK、上に。
うわー。
だから私たちは費やす必要はありません デスクランプに、それは思われる。
わかりました。
それでは、どのように前にあなたについて2。
あなたはどう後ろに二人。
だから4だ。
いかがでしょうか前に 5、6と7。
すぐそこ。
あなたの友人は、あなたを指している ので、あなたは賞金を得る。
>> わかりました。
までさあ。
そして、なぜ私たちはあなたの持っていない みんなこっちに来る。
私はあなたに、それぞれの番号を与えるつもりです。
と先に行くと自分をアレンジ 同じだもの
画面に描かれた。
>> [介在VOICES]
>> DAVID J.マラン:OOP、申し訳ありません。
バグ。
わかりました。
さて、ここで私達は行く。
番号5。
番号6。
一つ、二つ、三つ、四つ、 5、6、7。
ああ、これは厄介です。
>> SPEAKER 2:私はちょうど買ってあげる - 。
>> DAVID J.マラン:良い取引。
わかりました。
参加していただきありがとうございます。
>> [拍手]
>> OK。
わかりました。
だから我々は、4、2、6を持って オン、3個、7、5。
私たちは7人のボランティアを持っているので、パーフェクト ここまで幅が等しい人
私たちが演奏していることを配列 以前と。
そして、私は理由のために7を選んだ それはちょうどになります
少しで便利。
そして、私はそれを最初に提案するつもりです 私たちは、これら7つのボランティアを並べ替える。
あなたは、最初に、ご希望の場合 でも挨拶する。
これがあることを行っているので、 ぎこちない数分。
自己紹介を。
>> GRACE:こんにちは、私はグレースだ。
私はLeverettハウス年生だ。
>> BRANSON:こんにちは。
私はブランソンだ。
私は溶接で新入生だ。
>> GABE:こんにちは。
私はゲイブだ。
私はカボットで後輩だ。
>> NEIL:私はニールだ。
私はマシューズで新入生だ。
>> JASON:私はジェイソンだ。
私はグリーノーで新入生だ。
>> MIKE:私はマイクだ。
私はグレーで新入生だ。
>> JESS:私はジェスだ。
私はLeverett 2年生だ。
>> DAVID J.マラン:エクセレント。
わかりました。
さて、私たちのすべてに感謝 これまでここでボランティア。
そして今、手元に挑戦は起こっている これらの人のようなものになるが、そのために
我々は少し考える必要があるとしている どのように効率的に我々実際には約ハード
それらを並べ替え。
それでは、最初にこれを試してみましょう。
君たちはお互いの数字を見ることができます ただコーナーの周りに置くことによって。
先に行くと、数秒かかる、と 上の小さいものから自分自身を並べ替える
右側に最大に残しました。
行く。
>> OK。
グッド。
それは本当にくそ速かった。
今ここに誰か、アルゴリズムは何だった これらの人は適用した?
>> SPEAKER 1:最大の少ない。
>> DAVID J.マラン:OK。
最大の少ない、本当にのようなものです 客観的な、私はだとわからないんだけど
本当にアルゴリズム。
少なくとも最大に教えてくれない 私は何をすべきかをステップ·バイ·ステップ。
うん?
>> SPEAKER 1:[聞こえない]
>> DAVID J.マラン:OK。
ですから、より小さい人を見たら あなたの番号、その後に移動
それらの右側。
だから今では、より表現になってきている あなたのために、アルゴリズムのようなより
その、これであれば、言うことができます。
だから我々はいくつかの種類を持っている 条件付き構造。
そして、これらの人は、いくつかのことを行うように見えた 回、あなたのいくつかのビットを移動したため
距離の。
だから、おそらくいくつかの種類のがあった 彼らの心で起こってループ。
>> しかし、それを形式化してみましょう。
君たちが戻ってリセットすることができれば この配置に。
我々はこの定式化ができないかどうかを確認してみましょう 少ししてから、質問をする、
これがどのように効率的ですか?
もちろん、我々はよりゆっくりとこれを行う際に、 それはのように良い感じになるだろう
アルゴリズムが、私達ができれば見てみましょう 正確なステップに私たちの指を置く。
>> だから二人には4つのと2つです。
または、正しいか正しくないため?
明らかに間違った。
だからスワップ。
今、私は脇に移動するつもりです ここと六から四、言う。
あなたは、正しいか間違っている?
>> GABE:正しい。
>> DAVID J.マラン:正しい。
六一?
いや。
スワップ。
だから2スワップだ。
六三?
いや。
スワップ。
6と7?
よさそうだ。
七と5?
>> JESS:[聞こえない]
>> DAVID J.マラン:OK、交換。
と並べ替え。
わかりました。
だから、明らかにしない、右?
だから、もっと上があるつもりだった。
しかし、確かに、これらの人も、 ただ本能的に。
移動保管。
彼らはちょうど彼らに一度、停止しませんでした 一つの問題を修正しました。
だから。
確かに、私が持っているつもりです 同じことを行う。
私は戻って巻き戻しのようなものする必要がありますするつもりです この問題の先頭に、
この配列の先頭または 人々は、それらを呼び出しましょう。
>> そして今、何をすべき私のアルゴリズム 番目のパス上にある?
>> SPEAKER 1:同じこと。
>> DAVID J.マラン:同じこと。
そして、これは、私は右の、好きになり始めている?
あなた自身がやって見つけることができるとすぐに 何度も何度も同じこと、だ
、より多くのアルゴリズムのようになってき と少ない人間の本能。
>> だから今、ここに私達は再度行く。
2〜4?
いいえ。
四一?
ああ、いくつかのは確かにあった 行われるように、まだ働いています。
用と3?
グッド。
4〜6?
六と5?
6と7?
[OK]を、今、行って。
いや、OK。
私は戻って行かなければならない。
>> だから今、再び、我々はこれをやっている もう少し慎重に。
そして今、一つの脳はあり このアルゴリズムを実行する。
つのCPU、可能ならば。
と率直に言って、それが唯一の資源だ 私たちは、へのアクセス権を持っているつもりです。
そして、かつて私たちは、キーボードに戻って行くのですか と私たちにCのような何かを持って
処分、我々は唯一のプログラムを書いている それは、一度に一つのことを行うことができます。
一瞬前にこれらの人、一方で、我々 彼らの集団的知力レバレッジ
あなたのように人は、0週目になりました。
だから、これをやり続けるみましょう。
>> 二一。
二、三。
3と4。
4および5。
五六。
6と7。
完了?
だから私は、しかし、私が遊ばせて 悪魔の代弁者。
私は、コンピュータのようなものだけで行う この配列を通過しました
人々は、私が行ってることを知っている?
>> SPEAKER:1号
>> DAVID J.マラン:なぜ?
私は何をするためにしなければならないでしょう 私が行っているということ決定的に結論?
おそらく1つ以上のパス。
右?
すべての私はその前から知っているので、 パスは、私は間違いを訂正したことである。
そして、その手段が、多分そこだ まだ別の間違い
私は修正する必要がある。
したがって、僕は唯一の巻き戻しすることにより確認することやすることができ その後、チェックを一から二、2と
3、3と4、4、5、 5と6、6と7。
[OK]を、今、私は仕事もしなかった。
>> 私は確かに私がしたないことを覚えていることはできません 変数のようなものとの仕事、
int型が好きです。
それはスワップと呼び、スワップは私一度0である場合 ここで取得し、それはその後、0から開始
私はちょうど続けるために愚かなことでしょう 前後に、再度チェック、および
再び、再び、右?
あなたは、いくつかにはまり込むので 無限ループのようなもの。
0スワップは、ありそうとすぐに 我々はこのことを主張することができます
アルゴリズムは確かに完了です。
>> それでは、これに名前を入れてみましょう。
私はちょうど私たちを提案するアルゴリズム 実装バブルと呼ばれるものです。
その意味でそのように知られている並べ替え、 大きな種のある数字
までトップにバブル自分の道を、または最大 数値の配列の末尾に。
しかし、このアルゴリズムは、どのように効率的でしたか?
私は物理的にどのように多くの手順を持っていなかった これらを並べ替えるには、例えば、取る
7人間?
>> 四つに5?
[OK]を、あまりにも多く、最終的にはある 答えになるだろう。
しかし、その後、具体的な数 とても面白くないです。
それnは一般化してみましょう。
だから私はここで人々をn、およびそれらいた場合 にランダムな順序で、ソートのあった
その元の順序で、始まる。
さて、どのように多くの手順を私は持っていなかった 最初のパスで取るには?
それは1つ、2つ、3つ、4つ、5つであった そう6、彼らは7人だ、
それが、6 7だ - 、Nだそう マイナス1のステップは初めて。
>> さて、どのように多くの手順を私は持っていなかった 私は巻き戻したときに取るには?
さて、私たちは実際に倍増する可能性のある場合 私たちは、本当にしたかったが、今のところ、私はよ
ただ、すべての権利を言おうとしてい 別のnはマイナス1。
nはマイナス1が取得する予定ですので、 を追跡するのが面倒なので、してみましょう
わずかに切り上げます。
だから、2n個のステップ。
だから14ステップ、与えるか、または取る。
>> 私は何回かかりました ステップ次回?
まあ、それは3Nです。
本当に。
そして今、最悪の場合には、用 例えば、何回私が持っているでしょう
、前後に、前後に行っ スワッピング、このアルゴリズムを実行する
各パス上の人、大体?
それは、右実際にN乗のですか?
>> 最悪のケースでは、種類ができるので 直感的にこれについて考えるの、
それは少しかかることがありますにもかかわらず、 インチシンクする時間のビット
最悪の場合には、何だろう、これらの 7人中、ように見えた
契約の条件 その数の?
完全に後方、右?
そして、ちょうど、それをシミュレートする あなたの名前は再び何でしたか?
>> MIKE:マイク。
>> DAVID J.マラン:マイク?
OK、マイク、あなただけの私を参加することができます ここだけ1秒?
実際には、ない。
申し訳ありませんマイク、巻き戻してみましょう。
あなたの名前は何です再び?
>> NEIL:ニール。
>> DAVID J.マラン:ニール。
OK、ニール、あなたは付属している 私、あなたが気にしない場合。
だから、僕はのために、提案するつもりだ ニールは彼に今あるシンプルさ、
最悪のケース。
しかし、私はどのように実装さ思い出す 私のアルゴリズム。
私は、比較の比較、比較しています、 ああ、比較、比較。
今、これらの人が出ている オーダーのため、私が修正してください。
だからみんなスワップ。
しかし、どのくらい遠く、今考える ニールは、行かなければならないのでしょうか?
それは大体Nだ。
あなたはそれが実際にNはないが、知っている。
それはのように、n個から1を引いた値だが、私は取得しています 少しのイライラを追跡
数は、そうちょうどそれがn個呼び出してみましょう。
>> ニールは、最大限にそれぞれ一歩を動かすのであれば 時間、ニール一歩を移動するには、
私はこれは本当に退屈なパスをしなければならない 前後に、これはおおよそである
、、nステップ、n回の合計はこれをやって それは私を取るために起こっているので、
多くの手順はニールすべてを取得すること 彼が属している場所への道。
君たちなら皆おろか すべて同様に誤発注された。
>> それでは、バブルソートnの二乗を呼び出してみましょう。
このアルゴリズムの実行時間、 このアルゴリズムの性能は、
このアルゴリズムの効率性 私達はちょうどより多くを記述しなければならない
一般的にnの二乗。
私は可能性があるため、どちらが、いいです 8人、9と同じ例
人、万人、その 答えは変更するつもりはない。
>> 皆さんが気にしないならばそう、みましょう あなたが始めるところにあなたをリセットします。
と他の2つのアプローチを試してみましょうと 我々は根本的に行うことができないかどうかを確認
これよりも良い。
今回だから、私が提案するつもりです 異なるアルゴリズムの一種。
つまり、前回の私たちの非常に巧妙だった そして皆さんが持って正しかった
だけの種類の右側の本能 ペアを入れ替えるの。
しかし、私は本当にこれをアプローチしたい場合 単に、私の目標は、移動させることである
少し数字この方法のすべて、および その大きな数字のすべてをプッシュする
方法、なぜ私はただでそれをしないでください 可能な限り最も素朴な方法と私かどうかを確認
だったものよりも良い行うことができます かなり複雑なアルゴリズム?
>> それでは見てみましょう。
四つはかなり数が少ないですので、私はよ そこに瞬間あなたを残そう。
ああ、ナンバー2は、さらに良いです。
だから、あなただけ踏み出すことができます 一瞬のために?
これは現在、私の最も小さい番号が付けられています 候補者、と私は覚えているつもりです
変数、のように、とのこと。
しかし、私はチェックし続けるつもりです。
その誰かがありますか 数字が小さくなる?
六、ない。
ああ、再びニールあり。
>> だから私はあなたをプッシュバックするつもりです 概念的には、一種の。
ニールは、前方に来るでしょう。
そして今、私が使用していることを変数 最小を持っている人を追跡
番号が含まれるように更新される ニールの位置。
まあ、見てみましょう。
三、七、五。
[OK]を、私はニールが最小だった知っている。
最も簡単な方法は何ですか 私のために今何をするか?
私はちょうどで私の時間を無駄にするつもりはない 左にニール一つの場所をバブリングする。
ここで彼はなぜただニールを入れてはいけません もちろん、どこにある、所属?
>> 初めにすべての方法。
ニールだから、私と一緒に来る。
そして、あなたの名前は再び何でしたか?
>> GRACE:グレース。
>> DAVID J.マラン:グレース。
OK。
グレースだから、残念ながら、あなたがしている 方法での一種。
では、どのようにこの問題を解決するのですか?
右?
これが配列の場合、そこ わずか7箇所。
ロブとのことを思い出して、私たちの話 年齢を宣言し、我々は唯一持っていた
年齢の有限数?
ここで同じ考え。
我々は唯一のintの有限の数を持っている。
グレースは、私たちのようなものである 方法は、我々はそうする方法を修正するのですか?
>> 最も簡単な方法は、のようです グレース、申し訳ありません。
あなたが上に行くために必要があるとしている 私たちは部屋をそこにすることができます。
さて、あなたは多分、これを考えれば 我々だけで、問題が悪化させた。
そして多分私達は、何をしたかであれば理由 グレースは、適切な場所にあった?
しかし、我々は彼女がいないと知っている、なぜなら そうしないと、彼女はあったであろう
前方に立っているではなく、 この時ニール、右?
我々はすでに彼女の電話番号をチェックアウト。
>> わかりました。
だから今、ニールは、適切な場所でだと、 私は若干の最適化を行うことができます。
次の分のために、私は無視するつもりです すべて一緒にニール、ないように
彼の時間を無駄にしたり、誤って 間違った場所に彼をスワップ。
だから今、どのように私は次のを見つけるのですか 最小の要素?
二つ。
場合には、かなり良い番号だ あなたは、前進したいと
私はあなたを覚えているだろう。
六、ダメ。
フォー、3、7、5、ダメ。
だから私はあなたに移動してみましょう あなたの右の場所。
そして、私たちはちょうどこの時間は幸運。
>> さて、私はこれらを無視するつもりです 二人の男、そして今もう一つの操作を行い
これを通過します。
六、そのかなり少数。
前進さあ。
あ、ごめん。
グレースの数は、優れている とても楽しみに踏む。
四つ。
申し訳ありませんが、グレース。
再び戻る。
3番が良いです。
七。
ファイブ。
そして今、あなたの名前は再び何ですか?
>> JASON:ジェイソン。
>> DAVID J.マラン:ジェイソン。
だからジェイソンは現在、最小で 要素私が選択した。
彼はどこへ行くのだろう?
だからここで6です。
そして、あなたの名前が再び?
>> GABE:ゲイブ。
>> DAVID J.マラン:ゲイブ。
ゲイブは道であります。
行うための最も簡単なものは何ですか?
この二人を入れ替えて続行します。
だから今見てみましょう。
誰が最も小さいのですか?
四つ。
チートだけの種類、私をしましょう。
ファイブは、最小になるだろう。
は、ステップ実行したい場合、私は、次を見つける 前方に、私はをどうするかがありますか
ゲイブとこれらの人、?
再び交換します。
だから今は、まだわずかに注文。
私は、ゲイブが最小であることが判明 私はあなたたちを上を移動、彼を飛び出す。
およびdone。
>> だから、答えは同じです。
最終的な結果は同じです。
これら二つのアルゴリズムのどちら 良いですか?
もう一つは、私が聞いた。
なぜですか?
>> SPEAKER 3:それはステップをNさん[聞こえない]。
>> DAVID J.マラン:それはせいぜいnステップだ。
興味深い。
だから、にもかかわらずです?
だから私はどのように見つけた 最小の要素?
どのように多くのステップ私が取らなければならなかった 最小の要素を見つける?
私はすべての道を見ていた 最後に、右?
その最悪の場合には、どのようなので、 ニールはここで終わった場合はどうなりますか?
だから最小の要素を見つける 私nステップ、またはnマイナス1をとります。
しかし、OK。
だからニールを修正。
つまり、分ほど前に覚えておいてください。
>> しかし、どのように私は次のを見つけました 最小の要素?
それは、本当にNから1を引いた値、またはnマイナス2だ ステップ数から。
それでOK。
だから私は、nマイナス2しました。
わかりました。
だから少し良い感じ。
わかりました。
次回はどのように多くの手順 3番を見つけるには?
だからnはマイナス4。
だから、少ないものを減少だ 各反復でのステップ。
だから、これは正しい、良い感じでしょうか?
最後の時間なら、それは、およそn回Nだった 今回はそれがnマイナス1、プラスNマイナスだ
2、プラスNマイナス3、プラスN マイナス4、ドット、ドット、ドット。
しかし、あなたはあなたの高校を思い出した場合 教科書、少しチート
数式を持って背面にシート、もし あなたには、数字のこのシリーズを追加
総ステップ数は何ですか 私はここで取ることになるだろう?
>> これは、それらの一つであるように、n個のマイナス 2で割った1回N、。
だから私は引っ張ることができるなら、私は見てみましょう ちょっとこれまで。
そして再び、私はいくつかの丸めのようなものだ 数字だけで私たちの生活をシンプルに保つため、
しかし、私は思い出すように、それは、ifのようなものだ 私はその後、Nから1を引いた値のことを行うnのマイナス
次いで2、nはマイナス3は、略だ 2の上にこのような何か、と私なら
これを掛けて、そのう 実際にnの二乗。
それはあまりにも良い感じていない。 2以上nを引いたN。
>> しかし、ここでは、ことだ。
コンピュータサイエンス、問題で 面白くするために起動したときにnが
本当に大きくなる。
、nが本当に大きくなったとき、そのうちの これらの値はすべてを支配しようとしている
他人の?
それは右、乗、nのようなものだ?
はい、2で割ると、かなり良いです。
しかし、あなたは何十億の話をしている場合 データの断片、あるいは数兆の
データの部分は、[OK]を、ので、 あなたには、倍の速度です。
しかし、誰が本当に、その大きな数あれば気 この要因は、取得するのかである場合
どんどん大きく。
そして確かに、それはより多くを作る この男より違い。
だから君たちは右であるにもかかわらず、 第2のアルゴリズムは、我々はそれを呼ぶことにします
選択ソート、現実の世界では、ある 少し速く潜在的に、私はいるので
服用少なく 毎回繰り返します。
>> それは本当に根本的に速くはありません。
なぜなら私たちは実際にこれを外に再生する場合 の終わりに、nの値が大きい、
日は、十分に大きなnに対して、それはまだだ かなり遅い感じになるだろう。
さて、私が1つをみましょう その時点で最後のパス。
それは私が呼ぶようなものだ 選択ソート。
君たちは、自分自身をリセットすることができます 最後にもう一度?
そして、この最後のケースでは、私は行くよ 何かを提案する
挿入ソートと呼ばれる。
という挿入ソート、概念的に、 少し異なる。
>> 前後に行くというより 最小の要素を選択し、私は私
ただこれらのそれぞれに対処するつもり 私は彼らに遭遇して、挿入すると男
それらを正しい場所に。
だから、僕は、グレースで開始するつもりだ と私は彼女が4番だということを参照してください。
4番はどこに属しているのでしょうか?
私は、何も選別開始していない そうグレースはすぐそこに滞在することを得る。
そして今、私は、あなたができれば、請求するつもりです これは、あなたの右に一歩を踏み出す
私のソートされたリストは、これは私のです ソートされていない残りのリスト。
だから今、私は、次の続行するつもりです そしてあなたの名前は何です再び?
>> BRANSON:ブランソン。
>> DAVID J.マラン:ブランソン。
だからブランソンはナンバー2である。
だから私はあなたを取るつもりです 一瞬外。
そして今、あなたはどこに属しますか この配列内の?
だからグレースの右側に。
だからもう一度、我々は作るの一種だ グレースは、ここで多くの作業を行う。
私たちはあなたをどこに置けばいい?
だから我々は、にあなたをスライドさせるつもりだ 左、そこブランソンを挿入します。
しかし、今私はそれを主張する 君たちが行われています。
しかし、通知は、私は余分なスペースを使用していないよ。
それはまだ2つの要素だ ここで、こっち5。
合計配列のサイズは7ですので、私はよ すべての権利、浮気しない?
>> だから今我々は、ここでゲイブと、持っている 番号6、あなたが属していますか?
あなたは再び幸運。
だから、すぐそこにとどまることを得る。
ちょうど右にわずかな一歩を踏み出す ただあなたがソートしていることを明確にする。
そして今、我々は、再び数をニールを持って 1、あなたはどこに行くのですか?
我々はそれを見ることから始めましょうどことなりました しかし最初にこのアルゴリズム、
一目では、かなりスマートな感じ、見 起こることを約何。
あなたは前進することができれば。
>> どこに私たちはニールを入れたいですか?
だから、明らかにここにいるので、どのように 我々はそこにニールを得るのですか?
このステップバイステップを実行してみましょう。
あなたが行く必要があるかゲイブ、?
うん、そう、一つの大きな一歩を踏み出す または2つのハーフの手順が作る
あそこに一歩。
あなたが行くグレース、?
グッド。
だから、もう一歩。
そして最後に、ブランソン?
もう一つのステップ。
そして今、我々は場所にニールを置くことができます。
>> だから今、このロジックを続ける。
我々はニールをシフトされていないにもかかわらず、 以上、過、および彼を配置するには、上
どこに彼が行く、最悪の場合、 我々は、発生する可能性のある次の番号でし
数である、と言う、数があった ゼロ、次に我々は、すべてをシフトするつもりだ
これらの人。
負の、番号があると仮定 一方は、次に我々はシフトする必要があります
これらの人のすべて。
だから、私たちは本当に反転だけの種類だ 私たちがしていることなど、周りの問題
から経費を転送 選択プロセスそう挿入
君たちがちょうど持っていたようなプロセス、 大体nのマイナス何かを移動する
ステップ数。
そしてステップその数だけ起こっている 私は以上の数字を選択すると、増加する
私はあなたたちを無理に勧め維持する必要がある場合 バック、バック、バック。
>> とても悲しい事は今やこれらの全てです アルゴリズムは乗nです。
のは、先に行くと、これらのおかげでみましょう みんな、これらのビットを可視化
異なる。
非常によくやった。
>> [拍手]
>> わかりました。
そこに行く。
ありがとうございました -
>> BRANSON:[聞こえない]数字を維持。
>> DAVID J.マラン:いいえ、あなたは可能性があり 同様の数字を維持。
わかりました。
うまく行って。
わかりました。
だから我々は今、まとめることができないかどうかを確認してみましょう より迅速に、そしてより多くの視覚的、
ただ何が起こったかを正確に ここでは、次のとおり。
私が先に行くつもりです とFirefoxをプルアップ。
私たちは、このデモをリンクします もちろんのウェブサイトで。
Javaは動作させるために少し迷惑です 一部のブラウザでは、これらの日。
あなたは自宅でこれで遊んでないのであれば、 Firefoxを使用する必要があるかもしれません実現
それが動作して取得する。
そして、私はこれをやろうとしているもの デモは以下の通りです。
>> 下部には、私は全体の束を持っている スタートを含むメニューオプション、
ボタンを停止します。
また、余談として、があるように思われる これらのプログラムのバグは、それによって
実際にスタートを参照するか、または停止することはできません ボタン[コマンドまたはAltキーを保持していない限り
プラスとズームで、不思議なことに あなたに複数のボタンを示しています。
あなたがプレイする場合だからFYI これで自宅で。
今、私はちょうどにスタートをクリックするつもりです 瞬間、の遅延を指定した後、
ただ、ここでは200ミリ秒、のような 従って我々は何が起こるかを見ることができます。
>> だから私は、これが可視化であることを主張する 最初のアルゴリズムの
これらの人は、それによって、バブルソートをした 我々は人々のペアワイズスワップ。
この可視化するための鍵の洞察 ことは、バーの高さ
数字のサイズを表す。
だから、バー背 大きな数字。
短いバー、少数。
あなたが気づくならば、我々は通過しています このアルゴリズムの最初の反復、
大小の数字を入れ替えるので、 少数は最初に来ると
大きな数字が右に行く。
>> そしてできるだけ早く我々は配列の最後を得るよう 7よりも多くの数字から、我々はしている
先頭に戻って行く。
これを期待しています。
左端に、その小さな男は起こっている 側にスワップし、これに
プロセスが繰り返されます。
今、この可視化はすぐに取得する 退屈なので、私が先に行くと停止させ
それは、はるかに遅れ何かを変更 速いだけで、今の感触を得るために
このアルゴリズム。
>> 私はそれをスピードアップしましたので、あっても、これは 私のプロセッサをアップグレードするように、購入
新しいコンピュータ。
私は根本的に変わっていない私 アルゴリズムが、あなたは確かに多くを見ることができます
明らかに人間と比べて、その大きな 数字は、一番上までバブリングさ
と小さな数字はバブリングさ ダウンの下へ。
そして今、このことはここで並べ替え。
そして余談として、正方形で、そこ そこにはいくつかの簿記
、あなたはどのように多くの比較を数える役立つ またはどのように多くのスワップは、持っている
実際に行われて。
>> まあ、のはのいずれかを試してみましょう 我々が見た他の人。
私はここでバブルソートをクリックしてみましょう、と 私が選択させ、そしてこの全体のWebページ
少しバグがある。
リスクを受け入れてみましょう し、再度実行してください。
そうしよう。
だから選択ソートを行うてみましょう。
私にはわからない理由メニュー そこの上に表示されます。
ことを修正するためにズームしてみましょう バグは、50に変更。
ああ、実際に行うみましょう そのはるかに高速。
5ミリ秒かそこら、とスタート。
>> だから、これは選択ソートです。
だからもう一度、私たちを考える ここまで人間とやった。
私たちは、配列を経て、選択 再び最小要素、
そして再び、再び。
今私はまだかなり悪かったと主張。
それは、与えるか、または取る、まだN乗であった しかし、それは、現実の世界では、ビットだった
速く、私は確かに取っていたので、 やや少ない手順毎回。
しかし、我々は唯一の何を話している?
ここで多分40かそこらのバー?
我々は4000万話していない。
だから、と私には全く明らかではない 確かにかなりの利益であった。
>> 私は今、戻って我々に変更してみましょう 選択された第三のアルゴリズム、
挿入ソート。
そして今、それは本当にバグだから メニューには、実際にそこにあってはならない。
だから今我々はここに戻って上にスクロールします このアルゴリズムを開始します。
叫び声を上げる、起動と停止。
だから、この一種類のはかなりパターンを持ってい そこに、それによって我々は再びだ
ヒトの挿入、またはで この場合、棒状に
彼らの適切な場所。
そしてそれはすでに前に行っている 私が振り向く。
しかし、このいずれも、理論的には、 まだ乗nです。
>> だから我々はまとめることができないかどうかを確認してみましょう これらは以下の通り。
私が先に行くようにとだけ与えるつもりだ 私たち話の一般的な方法のようなもの
これらのことについて、私が紹介させて ここに表記の少しだけ。
あなたは大きなと呼ばれるものを参照しようとしている O、それは文字通りですので、大きな
O.そして、これは、そのコンピュータの方法です 科学者や数学者でも使用してい
実行時間を記述する いくつかのアルゴリズムの。
それは実際にどのように多くの手順がかかりますか?
>> 今私は自分自身を困らせるつもり 一瞬でここに私の手書き。
しかし、私が先に行くとのことを言わせて これはここに大きなOになります。
そして、私は、他のものをご紹介しましょう シンボル、資本オメガ。
オメガは、反対であることを行っている 本質的に、ビッグO一方ビッグOの
最悪の場合の手段、、どのくらいの時間 いくつかのアルゴリズムは、かかるかもしれませんで
nは、オメガの用語はに起こっている どのくらいの時間が場合がございます
最良のケースで取る。
そして、我々は何を意味わかります 一瞬で最高のケース。
>> だから、単純な何かを始めましょう。
私は線形探索から始めましょう。
だからソートしない。
私たちは、この線形探索と呼ぶことにします。
そして今、少し作る この外のテーブル。
そして今、線形探索の場合には、 最悪の場合には、どのように多くのステップである
それを見つけるために私を連れて行く 任意の選択肢の数は?
そして、そこのnの合計ドア またはn総数。
最悪のケース。
どのように多くのステップ私がする必要がありますするつもりです 配列内の数字50を見つけるために取る
n個のドアの?
そして、なぜ?
それはすべての可能性があるため 末尾にオーバー方法。
そんなにジェニファーが遭遇のように、 番号50はそうで、上のすべての方法であった
最悪の場合、線形探索 nは大きなOであり、我々は言うでしょう。
>> 最良の場合はどうでしょう、 あなたは本当にラッキー得れば?
それはちょうど、1歩を踏み出すことになるだろう ステップまたは定数。
だから我々は、1としてあることを説明します。
だから、これはかなり良いです。
今、我々は何かをやっている場合 バイナリ検索を好きですか?
最悪でだからバイナリ検索、 場合、どのくらいの時間がかかった?
>> [介在VOICES]
>> DAVID J.マラン:だから実際に、私は カップルの場所でそれを聞いた。
だから、それは実際に、n個のログを与えるか、または取ることだ 我々は半分にリストを分割するようなので、
再び、再び、再び、我々はできるだ 、最終的には、値を見つけるために、
それはありますが、キャッチがあれば。
我々が持っているという仮定は何ですか バイナリ検索に当たり前?
それは、ソートする必要があります。
これは、ソートされていないです、あなたはものを分割することができます 何度も何度も半分にし、
左に行くことができ、あなたが右に行くことができ、 あなたには、左と右に行くことができますが、している
要素を検索する場合に行っていない リストがソートされていない、なぜなら
あなたはそれを見逃す可能性があります。
あなたのヒューリスティックので、左に行くために または右にそれがあれば欠陥であることを行っている
確かにソートされません。
だから隠れたコストのようなものはあり このようなものを使用する。
>> それでは、我々のソートに手放す アルゴリズムは、検索しない -
ああ、実際のこの空白で手放す。
最良のケースでのバイナリ検索?
それだけであるために発生した場合にも1である 配列の非常に途中で、または
電話帳の真ん中。
今、バブルソートを行うてみましょう。
だから、もう一度、今、私たちは、入力している 並べ替えではなく、検索します。
>> 最悪の場合には、どのように多くの手順は、我々をしました 請求バブルソートは、取るために起こっている?
nの2乗。
だから私はそれを描くつもりです。
ああ、私の筆跡はさらに悪く見える それがあの大きな投影いるときに。
わかりました。
だからですnの二乗。
とバブルソートの最良のケースで、 どのように多くのステップには、取るために起こっている?
1、私は聞いた。
>> SPEAKER 1:N。
>> DAVID J.マラン:nは、私が聞いた。
>> SPEAKER:1 2。
>> DAVID J.マラン:2、私は聞いた。
私は3つのを聞くのですか?
わかりました。
だから私は、n、2、1を聞いてきましたが、ピックましょう それらの離れて少なくとも最初
提案、1。
それがあるため、悪い本能ではありません の種類は、ここでパターンに従います。
しかし、どのように、それは、1歩を踏み出している場合にのみ 世界は私が主張することができ、そのリスト
私が唯一許されている場合はどうするため、ソートされている 1歩を踏み出すことを、どのように多くの要素
私は実際にことを確認してくださいだろうか?
nがあることを意味まあ、ただ1、 の外になる可能性がマイナス1の要素
順序、および私はちょうど後信仰に行くよ その1要素を見て
ものがソートされます。
だから1はここで正解ではありません。
だから最低限、どのように多くの 私が見なければならないのですか?
>> [介在VOICES]
>> DAVID J.マラン:本当にNから1を引いた値、または、 nは、私はすべてを見てする必要があるため
ことを確認する要素 それは、順不同ではありません。
しかし、再び、私たちは波のようなものでしょう 小さい数字で、手や
nが大きくなるように、彼らがしている、と仮定する とにかく面白くない。
だからバブルソートです。
そして今、最後の2つを行うてみましょう。
選択ソートしてから、我々はよ 挿入ソートを行う。
そして、我々はあなたを爆破する ずっと何か心
これらのすべてのよりも良い。
わかりました。
>> 最悪の場合は何を実行している 選択ソートの時間?
>> SPEAKER 4:nの二乗。
>> DAVID J.マラン:nの正方形は、私が聞いている。
しかし、なぜnは直感的に、乗?
>> SPEAKER 4:我々はただそれをやっているので。
>> DAVID J.マラン:我々はただそれをやっているので。
OK。
答えはグッド。
しかし、直感的に、なぜ選択がある ソートnの二乗?
我々は何をすべきかを持っていなかった 何度も何度も?
我々は、を通してスキャン続けなければならなかった あなた最小、あなたは
最小は、最小である。
と付与、我々は、nを取ることができました その後のステップ、その後Nマイナス1、nはマイナス2。
しかし、あなたはどのようなものすべてを追加した場合、 または、私が追加した信仰にそれを取る
事前にそれらまで、我々は、n大体得る いくつかのより小さい数字マイナス乗。
だから私は、このnが乗呼ぶつもりです。
しかし、最良の選択ソートと 場合、それがどのように多くのステップである
私を取るつもり?
>> SPEAKER 5:[聞こえない]
>> DAVID J.マラン:それは残念なことだ まだN乗、右?
私は最小を選択している場合があるため 要素、そして我々は、ここで7人を持っていた
私が唯一知っている、かつて私は、非常に得る 私は最小のを見つけたことを終わり、
数字、どこ彼または 彼女はあったかもしれない。
しかし、どのように私は次を見つけるのですか 最小数?
私は別のパスをしなければならない。
だから、最良の場合で、何か 選択ソートへの入力?
それは、すでにソートリスト、ナンバーワンだ ナンバー2、ナンバー3、4番。
しかし、私はコンピュータです。
私は唯一の1を見ることができます 時のもの。
私は一歩を踏み出すに並べ替えることはできません 背中人間と言うように、
oohのは、これは正しく見える。
>> 私だけで正当性を裁くことができます 選択することにより、選択ソート
最小数。
しかし、私はナンバーワンが最初に見つけたとしても、 私は約何がわからない場合
私はしない他の数字、すべてのI 私は配列を渡してきたことを知っている
である背後のドアまたは一連 数字、私はその1つを知っている唯一の方法
最小でしたか?
私はここにすべての方法を取得し、実現した場合、 いまいましい、1は確かに最も小さかった。
>> しかし、どのように私はそのことを決定しない 二人は次の最小である?
同じ非効率を実行して、 何度も何度も。
だから最終的には、挿入ソートと、 どのように、最悪の場合には、
我々はそれが実行すると言ったのですか?
それはあまりにも乗nです。
そして、どのようにについての最もよいケース付き?
私たちは、クリフハンガーとしてそれを残しておきます。
我々は、その空白次回に記入します しかし、最初に私たちことを提案させて
根本的によりよくする これらすべて、大丈夫?
>> だから、自分のために何を考えて挿入 ソートは、になるだろう。
まあ、それは、非常に劇的ではなかった 私は一人ですので、
それは変化を見た。
うわー。
OK。
そこでここでは多少持っている 別のデモ。
私はここにズームインした場合は、その上を見ることができます で、我々はバブルソートを持って左
我々は選択ソートを持って中間、上 右端に、我々は何かを持って我々
まだ見ていない マージソートと呼ばれる。
しかし、我々がしてきたかを検討 今日はこれまでここでやって。
ジェニファーは、最初のステージに上がってきたとき、 私たちは、数値の配列を経て
再び、再び、線形探索と、 そして我々は大きなO、線形実行時間を得た
nは、いわば。
>> 我々は現在の最初の週を考えると クラス、我々は分割統治していたとき、
そして我々は、涙の電話帳を持っていた とジェニファー、そして我々をまとめて
にあったキー洞察、そのレバレッジ で何度も何度も自分自身を繰り返す
何とか、捨て、捨て 、捨て問題の半分、または
一般に、半分に分割する問題を、 その後の小さい部分を治療する
概念的には同等の問題 他に、我々は何とかやった
根本的に良い。
しかし、バブルソートと、選択に ソートは、挿入ソートで、我々は可能性をしました
ジェニファーがやっていることはそのような洞察力はありません。
我々はかなりちょうど戻って歩いて、 等倍の全体の束、そして我々
微調整のものは少し、スワッピング この順序で、多分
挿入または選択する。
しかし、一日の終わりに、私は多くのことをやった ぎこちないウォーキングの前後に。
私たちは本当に活用する何かをしなかった ジェニファーのようにスマートでは分割のようでした
と征服。
>> だからソートマージ、対照的に、その我々 来週までは表示されません、それが起こっている
レバレッジ割ってそのキーアイデアへ 入力した後、半分にしてから、
半減、その後半減。
そして、そのループの各反復で、 左半分をソートし、右
半分、左半分のその後左半分、 次に左の右半分、
右半分の左半分、および 右半分の右半分。
と何度も何度も繰り返す。
>> だから、視覚的にこれを見るが、このよ 来週私たちを待っているものです。
一般的に、ときに我々は少し考える そのような問題で少し難しい。
我々は左側に乗N、Nた 中間の二乗であり、n
右側にn個を記録。
だからあなたの本当の接戦はあり。
私たちは、月曜日にお会いしましょう。
>> [拍手]