[Powered by Google Translate] [セクション3 - より快適]
[ロブボーデン - ハーバード大学]
>> [これはCS50です。 - CS50.TV]
>> だから最初の質問は、6888184されています。
GDBは、より具体的には、プログラムを "デバッグ"することができますが、、何それはあなたが何ができるのですか？
私はそのいずれかをお答えしましょう​​、私は、まさに予想のか分からない
ので、私はそれの線に沿って何かがあなたがステップバイステップでできますそれを推測している
それと対話すると、プログラムの中を歩く、変数の変更は、これらすべてのことを行う -
基本的には完全にプログラムの実行を制御
プログラムの実行の任意の部分を点検してください。
ので、これらの機能を使用すると、物事をデバッグできます。
オーケー。
なぜ二分探索は、配列がソートされている必要がありますか？
誰がそんなことに答えることを望んでいる？
[学生]配列がソートされていないなら、それは動作しませんので。 >>うん。 [笑い]
配列がソートされていないなら、それはそれを半分に分割することは不可能だ
その左に、すべてが小さく、右側にあるものをすべて知っている
中間値よりも大きくなっています。
だからそれは、ソートする必要があります。
オーケー。
なぜ乗nのOでバブルソートは何ですか？
誰でも、最初のバブルソートとは何かの非常に迅速な高レベルの概要を提供したいのですか？
[学生]あなたは基本的に各要素を通過して、最初のいくつかの要素を確認してください。
彼らはあなたがそれらを交換するところから出ている場合は、次のいくつかの要素などを確認してください。
あなたが最後に到達したとき、あなたは、最大の要素を末尾に配置されていることを知っている
ので、あなたは、1つが次にあなたが通過し続けることを無視する
そのたびにあなたは何も変更しなくなるまで、1小さい要素をチェックする必要があります。 >>うん。
あなたはその側に配列を反転した場合ので、上下だと、ため、これは、バブルソートと呼ばれる垂直
次に大きな値は底に沈んでしまうと小さな値topへバブルアップします。
それは、その名前を得た方法です。
そして、ええ、あなただけを通過します。
あなたは、大きい方の値を交換し、アレイを介し続ける
底に最大値を取得します。
>> なぜそれがnのOの二乗ですか？
まず、誰もがそれがnのO乗だからこそ言いたいのですか？
[学生]を実行するたびにそれがn倍になったので。
あなただけがすべての方法ダウン最大の要素を撮影したことを確認することができ、
その後、多くの要素として処理することを繰り返す必要があります。 >>うん。
だからビッグOは、どのような意味ビッグオメガ手段何を念頭に置いてください。
ビッグOは、それが実際に実行することができますどの程度遅いの上限のようなものです。
だから乗nのそれはOを言うことによって、それはnのOではないか、そうでなければ、実行することができるだろう
線形時間で、それはn乗のOです
それは、n乗のOに囲まれているからです。
それは乗n個のOで囲まれている場合、それをn乗しても囲まれている。
だからそれは、n乗であり、絶対的な最悪の場合はNの2乗よりも良い行うことはできません、
それはそれは乗n個のOである理由です。
だから、それはNの2乗であることが出てくる方法で若干の数学を見て
私たちは私たちのリストに5つのものを持っている場合、我々は潜在的に行う必要がある可能性がどのように多くのスワップ初めて
これを取得するためには？ただ、実際にしてみましょう -
どのように多くのスワップ我々は、配列をバブルソートの最初の実行時に行う必要がありますするつもりですか？
【学生】n - 1。 >>うん。
>> 1から5の要素がある場合は、nを作るために必要になるだろう。
それから二つ目にどのように多くのスワップ我々は行う必要がありますするつもりですか？
【学生】n - 2。 >>うん。
そして第三は、nであることを行っている - 3、その後の便宜のために、私は最後の二つを書きます
その後、我々は2スワップ、1スワップを作るために必要になるだろう。
私は最後の1、または実際に起こる必要があるかもしれませんと思います。
それはスワップのですか？知りません。
したがって、これらはスワップまたはあなたが作らなければ少なくとも比較の合計金額です。
あなたは交換しない場合でも、値を比較する必要があります。
配列を使用して、最初の実行で1比較 - だから、nが存在する。
あなたがこれらの事を再配置した場合、実際に6物事作るので物事がうまく積み重ねていきましょう、
そして私は、2、1〜3をやる。
だから、これらの金額を整理すると、私たちが作るどのように多くの比較が見たい
アルゴリズム全体インチ
だから我々はここで、これらの人をダウンさせた場合、
その後、我々はまだそこにあったが、多くの比較をサミングしている。
しかし、我々はこれらを合計し、我々はこれらを合計し、我々はこれらを合計した場合、
それはまだ同じ問題です。私達はちょうどそれらの特定のグループを合計します。
>> だから今我々は3 nのを合計している。それはちょうどn個の3ではありません。
それは常にn / 2 nのものになるだろう。
そこでここでは、6を持って起こる。
我々は10の事柄を持っていたなら、私たちは物事の5つの異なるペアは、このグループ化を行うことができます
とN + N + N + N + Nで終わる。
それで、あなたは常にn / 2 nのを取得するつもりだので、この私たちはnの二乗/ 2にそれを書き留めます。
そしてそれが入ってくるように起こるの半分の要因、言っても
アレイ上の各反復を通じて、私たちが1未満と比較しているという事実のために
その結果、我々は2の上を取得する方法ですが、それはまだNの2乗です。
我々は半分の一定の係数を気にしないでください。
このようなビッグOのものの多くは、数学のこのソートを行うだけの種類に依存しているので、
算術和と幾何学的なシリーズものをやって、
しかし、この過程で、それらのほとんどは非常に簡単です。
オーケー。
なぜnのオメガで挿入ソートは何ですか？オメガは何を意味するのか？
[一度に話す二人の学生 - 不明朗] >>うん。
オメガは、下限として考えることができます。
>> だからあなたの挿入ソートのアルゴリズムがどのように効率的に関係なく、
かかわらずに渡されたリストの、それは常に、少なくともn物事を比較する必要がある
またはそれはnの事を反復するために持っています。
これはなぜですか？
[学生]ため、リストが既にソートされていれば、最初の反復を通じ
あなただけの、非常に最初の要素が最小であることを保証することができます
そして2回目の反復では、あなたは、最初の2つがあることを保証できます
あなたは、リストの残りの部分がソートされていることを知らないので。 >>うん。
あなたが完全にソートされたリストを渡した場合、非常に少なくとも、あなたは、すべての要素の上に行かなければならない
何も周りに移動する必要がないことを確認します。
だからリスト上を通過すると、ああ、これはすでに、ソートされていると言って
あなたは、各要素を確認するまで、あなたがそれをソートの知っていることは不可能だ
彼らはソート順になっていることを確認します。
だから、挿入ソートの下界はnのオメガです。
マージソートの実行時間は最悪のケースは、何ですか
最悪の場合、再び大きなOであること？
だから、最悪のシナリオでは、マージソートはどのように動作しますか？
[学生] Nログn。 >>うん。
最速の一般的なソートアルゴリズムは、nログnです。あなたがうまくやることはできません。
>> そこに特殊なケースがあり、我々は今日、時間があれば - しかし、我々はおそらくwon't -
我々は、nログnよりも優れていますかを見ることができました。
しかし、一般的なケースでは、nログnよりも良い行うことはできません。
とマージソートではnログnですこのコースのために知っておくべき一つであることを起こる。
そして私たちは、実際には、今日実装されます。
そして最後に、3つ以下の文章では、どのように選択ソートの動作しますか？
誰かが答えたくない、と私はあなたの文章を数えます
なぜならあなたは3を超えた場合 -
誰もが選択ソートを覚えていますか？
選択ソートは、名前だけで覚えていることは通常は非常に簡単です。
あなただけの配列を繰り返し処理し、最大値であるか、最小のものは何でも見つける -
あなたはインチ選別している任意の順序
それでは、私たちは最小から最大に選別しているとしましょう​​。
あなたは、最小の要素が何であっても探して、配列を反復
それを選択してから、ちょうど最初の場所にあるもの、それを交換します。
そして、配列の上2番目のパスに、再び最小の要素を探します
それを選択し、次に2番目の位置にあるものでそれを交換します。
だから我々はちょうどピッキングと最小値を選択している
それがソートされるまで、アレイの前面に挿入する。
その上で質問がありますか？
>> これらは、必然的にあなたがpsetを提出している際に記入して、フォームに表示されます。
それらは基本的にはそれらへの回答です。
わかりましたので、今の問題をコーディング。
私はすでに、電子メールを介して送信される - 誰もがその電子メールを取得できませんでしたか？オーケー。
私はすでに、我々が使ってしようとしている電子メールを介して空間を送出
あなたが私の名前をクリックした場合と - ので、私は一番下になるつもりだと思う
後方rのために - しかし、あなたは私の名前をクリックした場合、2つのリビジョンが表示されます。
リビジョン1は、私はすでにスペースにコードをコピー＆ペーストしようとしている
検索の事のためには、実装する必要があるとしている。
とリビジョン2は、我々はその後実装ソートものになるでしょう。
だからあなたは私のリビジョン1をクリックして、そこから作業することができます。
そして今、我々は二分探索を実装したい。
>> 誰もがちょうど擬似コードハイレベルな説明を与えたくない
我々は、検索のために行う必要があるとしている何の？うん。
[学生]あなただけの配列の中間を取ると、あなたが探しているものかどうかを確認
それよりも小さいか、それ以上です。
そして、それはより少ないなら、あなたは、より少ないです前半に移動
それはより多くのだなら、あなたはさらに半分に行くと、あなたは一つのことだけを取得するまで繰り返すこと。
[ボーデン]うん。
当社の数字の配列が既にソートされていることに注意してください、
そして私たちはそれを活用することができ、我々が最初にチェックすることができたことを意味し、
さて、私は50番を探しています。
だから私は、真ん中に入ることができます。
真ん中のは、それが物事の数が偶数のときに定義するのは難しいです
しかしレッツはちょうど私達が常に真ん中に切り捨てるつもりだという。
そこでここでは、8のものを持っているので、真ん中は16となります。
私は50を探していますので、50は16より大きい。
だから今、私は基本的に、これらの要素のように私の配列を扱うことができます。
私は上の16からすべてのものを捨てる​​ことができます。
今私の配列はちょうどこれらの4つの要素である、と私は繰り返す。
それでは私は42になるだろうされ、再び真ん中を見つけたい。
42は、50歳未満であるので、私はこれらの2つの要素を捨てることができます。
これは私の残りの配列です。
私は再び真ん中を見つけるつもりです。
私はいつも左に物事を捨てていたので、私は、50が悪い例だったことを推測
しかし同じメジャーで、私が何かを探していた場合
そしてそれは、私が現在見ている要素より小さいです
その後、私は右にすべてを捨てるつもりです。
だから今我々はそれを実装する必要があります。
私達はサイズを渡す必要があることに注意してください。
我々はまた、ハードコードのサイズに必要することはできません。
我々は取り払うのであれば＃defineを -
オーケー。
どうすればきれいに数字の配列のサイズは現在あるものを見つけ出すことができますか？
>> numbers配列内の要素数ですか？
[学生]数字、括弧、。長さは？
[ボーデンは] Cに存在していないこと
必要があります長さ。
配列はプロパティを持っていないので、配列のないlengthプロパティはありません
それはちょうどそれがであることを起こるあなたがしかし、長い与える。
[学生]それが持っているどのくらいのメモリを参照し、どのくらいで割る - >>うん。
だから、どのように我々はそれが持っているどのくらいのメモリを参照してくださいすることができますか？ >> [学生]はsizeof。 >>うん、sizeof演算。
sizeofが数値配列のサイズを返すために起こっている子です。
としかし多くの整数になるだろう、ということがよく整数のサイズがあります
それはそれが実際に取っているどのくらいのメモリだから。
だから私は、配列内の多くのことをしたい場合は、
それから私は、整数の大きさによって分割したいつもりです。
オーケー。だから私はここにサイズを渡すことができます。
なぜ私はすべてでサイズを渡す必要がありますか？
なぜ私はここまでできないintサイズ=はsizeof（干し草の山）/ sizeof（int）を？
なぜこれが動作しませんか？
[学生]それはグローバル変数ではありません。
[ボーデン] Haystackが存在し、我々は干し草の山のように数字で渡している
これが来て何の伏線のようなものです。うん。
[学生] Haystackはちょうどそれへの参照であるので、その参照がどのように大きな返します。
うん。
私はあなたが本当に、まだ右のスタックを見てきた講演の中で疑う？
我々はそれについて話をした。
だからスタックは、あなたのすべての変数が格納しようとしているところです。
>> ローカル変数に割り当てられている任意のメモリがスタックに起こっている、
各関数は、スタック上に独自の空間を取得し、独自のスタックフレームは、それはと呼ばれるものです。
だから主は、そのスタックフレームを持っており、内部のそれのは、この数字の配列が存在するために起こっている
そしてそれは、サイズはsizeof（数字）のことになるだろう。
それは、要素のサイズで割った数字の大きさを持っているために起こっている
しかしメインのスタック·フレーム内のすべての住んでいるところだ。
我々は検索を呼び出すと、検索は、独自のスタックフレームを取得
そのすべてのローカル変数を格納するために、独自のスペース。
しかし、これらの引数は - ので干し草の山は、この配列全体のコピーではありません。
我々は、検索にコピーとして、配列全体を渡しません。
それはちょうど、その配列への参照を渡します。
だから検索は、この参照を介してこれらの番号にアクセスすることができます。
それはまだ、主のスタック·フレームの中に住んで物事へのアクセスだ
しかし、基本的に、我々はすぐにあるべきポインタ、、に到達したとき
これは、ポインタが何であるかです。
ポインタは、物事への参照であり、あなたは物事をアクセスするためにポインタを使用することができます
他のものの 'スタックフレームでということです。
数字は主にローカルであるにもかかわらずだから、私たちはまだ、このポインタを介してアクセスすることができます。
しかし、それは単なるポインタだし、それはあくまでも参考ですので、
はsizeof（干し草の山）はあくまでも参考自体のサイズを返します。
それは、それが指しているもののサイズを返しません。
それは数字の実際のサイズを返しません。
我々はそれがしたいようなので、これが仕事に行くのではない。
>> その上で質問がありますか？
ポインタが来て数週間でかなり多くの血みどろの詳細にに消えてしまいます。
そして、これは、なぜあなたが見ているものが多く、ほとんどの検索物事または後回しです
彼らはほとんどすべて、配列の実際のサイズを取ることが必要になるだろう
C言語であるため、我々は、配列のサイズが何であるか見当がつかない。
手動でそれをインチ渡す必要があります
あなただけの参照を渡しているので、手動で配列全体を渡すことができません
そして、それは基準からサイズを取得することはできません。
オーケー。
だから今我々は前に説明したものを実装したいと思います。
あなたは、分のためにそれに取り組むことができ
そしてあなたはすべて完璧に100％の作業を得ることを心配する必要はありません。
ちょうどあなたはそれが動作するはずですどのよ​​うに考えるかの半分の疑似コードを記述します。
オーケー。
まだ完全にこれを実行する必要はありません。
しかし、誰もが、彼らがこれまで何をして、快適に感じない
何かのように私たちは一緒に働くことができますか？
誰もがボランティアをしたいのですか？または私はランダムに選択されます。
それは右のいずれかの措置が、我々は作業状態に変更することができるものである必要はありません。
[学生]確かに。オーケー。>>
だからあなたは少し保存]アイコンをクリックして、リビジョンを保存することができます。
あなたは正しい、Ramyaね？ >> [生徒]うん。 >> [ボーデン]オーケー。
だから今私はあなたのリビジョンを表示することができ、誰もがリビジョンをプルアップすることができます。
そしてここで我々は持っている - オーケー。
だからRamyaは間違いなく有効なソリューションである再帰的なソリューション、一緒に行きました。
あなたはこの問題を行うことができる2つの方法があります。
あなたはどちらか、または反復して再帰的にそれを行うことができます。
あなたは再帰的に行われることに遭遇するほとんどの問題も反復して行うことができます。
そこでここでは、再帰的にそれをやった。
>> 誰かがそれは、関数が再帰的に何を意味するかを定義したいのですか？
[学生]は、機能を持っているときに自分自身を呼び出す
それが真実であり、真実で出てくるまで、その後自分自身を呼び出す。 >>うん。
再帰関数は、単に自分自身を呼び出す関数です。
再帰関数が持っていなければならない3大きいものがあります。
第一は明らかですが、それは自分自身を呼び出します。
第二は、基本ケースである。
だから、どこかの時点で関数は、自分自身の呼び出しを停止する必要があり、
それは、ベースケースが何のためにあるのかだ。
だからここに私たちは止めるべきであることを知っている、我々は我々の検索であきらめなければならない
startがendと等しいときに - 私たちはそれが何を意味するのかをみることにします。
しかし、最後に、再帰関数のための重要な最後の一つです：
機能は何とかベースケースに近づく必要があります。
2番目の再帰呼び出しを行ったとき、あなたが実際に何かを更新していない場合と同様に、
あなたは文字通り、同じ引数を持つ関数を再度呼び出している場合、
ず、グローバル変数は、変更されていませんか何かしている
あなたは、ベースケースに到達することはありません、その場合は残念だインチ
それは、無限再帰とスタックオーバーフローになります。
しかし、ここで我々は、我々が開始+終了/ 2を更新しているので、UPDATEが行われていることを参照してください
我々はここでstart引数を更新している、ここにend引数を更新しています。
だから、すべての再帰呼び出しで我々は何かを更新しています。オーケー。
あなたのソリューションを介して私たちを歩いてみませんか？ >>確かに。
私はすべての時間が私は、この関数の呼び出しを行うようにSearchHelpを使用しています
私は、配列内の探している場所の開始と終了を持っている
どこで、私は配列を探しています。
>> それがスタートです中央の要素、+エンド/ 2だと言っているのすべての段階で、
それは我々が探しているものと同じですか？
それがあるならば、我々はそれを発見した、と私は再帰のレベルを上に渡されると推測します。
それは本当ではないならば、我々は、配列のその中間の値が大きすぎるかどうかをチェック
その場合、我々は最初から真ん中のインデックスに行くことによって、配列の左半分を見てみましょう。
そうでなければ、我々は終わりの半分を行う。
[ボーデン]オーケー。
それは良さそうです。
わかりましたので、カップルの事、実際には、これは非常にハイレベルなものです
あなたはこのコースのために知っておく必要は決してありませんが、それは真実であること。
再帰関数は、常に彼らはひどい仕打ちだと聞いて
あなたは再帰的に自分自身が何回も呼び出す場合は、スタックオーバーフローを得るため
以来、私は前にも言ったように、すべての関数は独自のスタックフレームを取得します。
だから、再帰関数の各呼び出しでは、独自のスタックフレームを取得します。
あなたは千再帰呼び出しを行うのであれば、あなたは、千のスタックフレームを取得
かつ迅速にあなたはあまりにも多くのスタックフレームと物事が壊れることは持って​​いることにつながる。
再帰関数は、一般的に悪い理由だからです。
しかし、再帰関数の素敵なサブセットは、末尾再帰関数が呼び出された
これは、コンパイラがこれを気がつけば一つの例であることを起こる
あなたはそれを-O2フラグを渡した場合はClangの中に - そしてそれは、私が考えなければならない
それは、これは末尾再帰であることに気づくと物事が良いでしょう。
>> それは、各再帰呼び出しのために何度も何度も同じスタック·フレームを再利用します。
あなたが同じスタックフレームを使用しているので、それで、あなたは心配する必要はありません
今までにあふれ、同時に、あなたが前に言ったように積み重ね、
一度あなたがtrueを返す場合に、それはこれらのスタックフレームのすべてを返す必要があります
とSearchHelpへ第十コールは第九に戻す必要があり、第八に返す必要があります。
だから関数は末尾再帰しているときに発生する必要はありません。
そしてそう何、この関数の尾を再帰的に繰り返すことsearchHelpに任意のコールのためにあることに気づくさ
それは作っていることを再帰呼び出しでは、戻されるものです。
だからSearchHelpへの最初の呼び出しでは、我々は、すぐに、falseを返す
すぐにtrueを返すか、我々はSearchHelpに再帰呼び出しを行う
私たちが返していると、その呼び出しが返されているものです。
我々はint X = SearchHelp、リターン×* 2のような何かをしなかった場合、我々は、これを行うことができませんでした
ちょうどいくつかのランダムな変化。
>> だから今、このような再帰呼び出し、このint X = SearchHelp再帰呼び出し、
それが実際に返す必要がないため、もはや末尾再帰ではない
バック関数への前の呼び出しているので、以前のスタック·フレームへ
その後、戻り値を使って何かを行うことができます。
だから、これは末尾再帰ではありませんが、きれいに末尾再帰になる前に、我々は持っていたもの。うん。
[学生]は二塁のケースは最初にチェックすべきではありません
あなたはそれを引数を渡すような状況があるかもしれないので、
あなたは=エンドを起動しましたが、彼らは針値です。
端が針値です質問は、我々はその事件を実行することはできませんされました
または=エンドを起動して、適切に、=エンドを起動
そして実際に、まだその特定の値をチェックしていない
その後スタート+エンド/ 2がちょうど同じ値になるだろう。
しかし、我々はすでにfalseが返されてきたと我々は、実際に値をチェックすることはありません。
サイズが0の場合はだからせめて、最初の呼び出しで、その場合は偽を返すようにしたい。
大きさが1である場合しかし、その後スタートは、等しい終わりに行くされていません
そして我々は、少なくとも1つの要素をチェックします。
しかし、私はどこでスタート+エンド/ 2、私たちはケースに行きつくことができる点で、あなたは正しいと思う
開始はスタート+エンド/ 2、と同じされて終わる
しかし、我々は実際にその要素をチェックすることはありません。
>> だから、我々が最初にチェックした場合と、中央の要素は、私たちが探している値であり、
その後、我々はすぐにtrueを返すことができます。
それらが等しいなら、他の場合には、継続しても意味がありません
以来、私達はちょうど私達が単一要素の配列である場合に更新するつもりです。
で、単一の要素は、私たちが探しているものではない場合は、
その後、すべてが間違っている。うん。
[学生]のものは、大きさが配列内の要素数より​​も実際に大きいことです
既にオフセットがある - >>だから意志サイズ -
[学生]配列のサイズが0だった場合、その後SearchHelpが実際に0の干し草の山を確認すると言う
最初の呼び出しで。
うん>> - 配列のサイズが0であり、0になるように。
その別のものがあります - それは良いかもしれません。のは、考えてみましょう。
配列は10個の要素を持っていたし、我々はチェックするつもり真ん中はインデックス5であり、そうであれば
ので、我々は5をチェックしているし、その値が小さいことを言うてみましょう。
だから我々は5以降からすべてのものを投げている。
だから、スタート+エンド/ 2私たちの新たなエンドになるだろう、
そう、ええ、それは常に配列の終わりを越えて滞在する予定だ。
それが偶数か奇数であった場合、それはそうだとするなら、私たちは、、と言う、4をチェックすることになります
しかし我々はまだ捨てています -
そうそう、最後には、必ず実際の配列の末尾を超えてになるだろう。
我々が焦点を当てているので、要素は、最後には、必ずその後一つになるだろう。
スタートは今までに等しい終わりますかそうだとすれば、我々は、サイズが0の配列である。
>> 私が考えていた他の事は我々が開始する開始を更新しています+エンド/ 2であり、
どこスタート+エンド/ 2ので、これは、私がトラブルを抱えているのは、事実です
我々がチェックしている要素です。
Let 'sは、我々はこの10要素の配列を持っていたと言う。ものは何でも。
だから、スタート+エンド/ 2この1のようなものになるだろう、
そしてそれが価値ではない場合、我々は更新したいと言う。
値が大きいので、我々は、配列のこの半分で見てみたい。
だから我々はスタートを更新しているどのように、我々は現在、この要素になるようにスタートを更新しています。
しかし、これはまだ動作する可能性があります、または非常に少なくとも、あなたはスタート+エンド/ 2 + 1を行うことができます。
[学生]は、+エンドを起動する必要はありません[聞こえない] >>うん。
我々はすでに、この要素をチェックし、それは我々が探しているものではないと知っている。
だから我々は、この要素になるようにスタートを更新する必要はありません。
私達はちょうどそれをスキップして、この要素になるように開始更新することができます。
とケースはこれまで存在し、これが最後であったこと、としましょう​​、
このなるので、次に起動すると、+エンドを起動/ 2はこれであろう、
+エンドを起動 - ええ、私はそれが無限再帰で終わることができると思います。
レッツは、それだけでサイズ2かサイズ1の配列の配列だと言う。私は、これがうまくいくと思う。
だから現在、startは要素と終了がそれを超えて1であるということです。
だから我々はチェックしようとしている要素は、この一つであり、
その後、我々はスタートを更新するとき、我々は、0 +1 / 2であるとスタートを更新している
これは、スタートがこの要素であるとの私達に戻って終わろうとしている。
>> だから我々は何度も同じ要素をチェックしています。
だから、これは、すべての再帰呼び出しは実際に何かを更新する必要がありそうです。
だから我々は、大文字と小文字があるスタート+エンド/ + 1、あるいは2を実行する必要があります
ここで我々は、実際にスタートを更新していない。
誰もがそれを参照してください？
オーケー。
誰もがこの溶液またはそれ以上のコメントについての質問を持っていますか？
オーケー。誰もが、我々はすべてを見ることができることを反復解法を持っていますか？
我々はすべて再帰的にそれをしましたか？
あるいはまた、私はあなたが彼女を開いた場合、その後、あなたの前のものをオーバーライドしているかもしれないと思います。
それは自動的に保存しますか？私は肯定的ではない。
誰もが反復していますか？
私たちは一緒にそれを歩く場合はできません。
考え方は同じであることを行っている。
反復解法。
私たちは基本的に同じ考え方をしたいとしている
我々は、新しい配列の末尾のトラックと配列の新たなスタートをどこに置くか
それは何度も何度もやる。
そして、我々は開始と終了が今までのように交差を追跡しているものであれば、
その後、我々はそれを見つけられなかったこと、そして私たちは、falseを返すことができます。
だから私はそれをどのように行うのですか？誰も私をプルアップするための提案やコードをお持ちですか？
[学生]は、whileループを行います。 >>うん。
あなたは、ループを行いたいとしている。
>> あなたは、私がプルアップ可能性のあるコードを持っているか、またはあなたは何を示唆しようとしていた？
[学生]私はそう思います。 >>すべての権利。これは、物事が容易になります。あなたの名前は何でしたか？
[学生]ルーカス。
改訂1。オーケー。
ローは、我々は前に開始すると呼ばれるものです。
ここまでは前に、エンドと呼ばれるものとは限らないからです。
実は、年末には、配列内になりました。それは、我々が考慮すべき要素です。
非常に低いが0で、最大配列のサイズです - 1、
そして今我々はループしている、と我々はチェックしている -
私はあなたがそれを通って歩くことができると思います。
これを通じて、あなたの思考は何でしたか？あなたのコードを介して私たちを歩く。
[学生]確かに。真ん中に干し草の山の値を見て、針と比較します。
ああ、実際に、それは後方にする必要があります - それはあなたの針よりも大きいですので、もし、あなたがしたい。
あなたは、右半分を捨てるするつもりだ、とそう、ええ、それは方法でなければなりません。
[ボーデンは]だから、これは小さくなければなりません？あなたはそれを言っているのでしょうか？ >> [生徒]うん。
[ボーデン]オーケー。もっと少なく。
ですから、私たちが見ていることは我々が望むものよりも小さい場合、
それから、ええ、私たちは、左半分を捨てたい
これは、我々が検討しているすべてのものを更新していることを意味
配列の右側に移動させることにより、低。
これはよさそうだ。
私は、それは我々が以前のものによると、同じ問題を持っていると思う
低いが0で、最大1であれば、低+ / 2まで、再び同じことになるように設定するにはどこに向かっている。
>> そして、それがそうではない場合であっても、それはまだ非常に少なくとも、より効率的です
単に要素を捨てること私達はちょうど私達が間違っていることは知っているを見た。
/ 2までの非常に低い+ 1 - >> [学生]は、他の方法でなければなりません。
[ボーデン]またはこれがなければなりません - 1、もう一つは+ 1である必要があります。
[学生]と二重があるはず等号。 >> [ボーデン]うん。
[学生]うん。
オーケー。
そして最後に、今、私たちはこの+1を持っていること - 1の事を、
それは - それはないかもしれません - それは低いため、最大よりも大きい値になってしまうことがこれまで可能ですか？
私は起こることができる唯一の​​方法だと思います - それは可能ですか？ >> [学生]私は知らない。
しかし、それは切り捨て取得し、取得した場合、そのマイナスその後1 - >>うん。
[学生]それは多分めちゃくちゃになるだろう。
私はそれだけのために良いはずだと思う
それが低終わることのために、それらが等しくなければならないであろう、と思う。
それらが等しい場合でも、我々は、で始まるにwhileループを行わなかったであろう
そして我々は単に値を返したでしょう。だから私たちは今は良いだと思います。
この問題は再帰なくなったにもかかわらず、ことに注意してください、
私たちは、これがそう簡単に自分自身を貸すかを見ることができますどこにアイデアの同じ種類が適用されます。
我々だけで、何度も繰り返しインデックスを更新しているという事実によって再帰的なソリューションへ
我々は問題が小さく作っている、我々は、配列のサブセットに焦点を合わせている。
[学生]低が0で、最大1である場合、それらは両方とも、0 + 1/2、0になるだろう
その後1 + 1となる、1は次のようになります - 1。
[学生]僕らはどこ平等をチェックしている？
真ん中の1が実際に針の場合は好きですか？
我々は現在、ことをやっていないのか？ああ！
it's場合 -
はい。レッツは、最初の中間と言うので、私たちはここでダウンテストを行うだけではできません -
[学生]それは実際にバインドを捨てないようなものだ。
あなたがバウンドを捨てる場合そこで、まず最初にまたは何でもそれをチェックする必要があります。
ああ。うん。 >> [生徒]うん。
だから今我々は、我々が現在見て1を捨てて、
これは、我々は今も持っている必要があることを意味し
（干し草の山[（低+上）/ 2] ==針）するなら、私たちは、trueを返すことができます。
そして、私は誰置くかどうかだけなら、それは文字通り同じことを意味
これは真実では戻ってきてしまうからです。
もしそうなら私は他に置くことにしましょう​​が、それは問題ではありません。
>> ので、他の、これは、この他に、これは私が行う一般的なものである場合
どこでそれがすべてがここに良い場合であっても、
ローのようにより大きくなることはありません、それはそれが本当だかどうかについての価値推論ではありません。
ローがより小さいか等しい間、そうあなたにも言うかもしれません
または低未満である間
そう、彼らはこれまでと同等または低い場合を渡すことを起こる、
その後、我々はこのループから抜け出すことができます。
質問、懸念、コメント？
オーケー。これはよさそうだ。
今、私たちは、ソートをやってみたい。
私たちは私の第二の改正に行けば、私たちは、これらの同じ番号を参照してください
しかし、今、彼らは、ソートされた順番になりません。
そして、我々は、nログnのOの任意のアルゴリズムを使用してソートを実装したいと思います。
ですから、我々がここで実装する必要があり、どのアルゴリズムだと思いますか？ >> [生徒]マージソート。
[ボーデン]うん。マージソートをするように、我々がやろうとしているのはO（n log n）である。
そして問題は、かなり似ているために起こっている
どこでそれが簡単に再帰的なソリューションに適しています。
我々がしたい場合、我々はまた、反復解法思い付く
しかし、再帰はここではより簡単になり、私たちは、再帰を行う必要があります。
私は、我々が最初にマージソート順を追って説明します推測
マージソートの美しい映像はすでにありますが。 [笑い]
だからあるマージソート - 私はこの論文のあまりを無駄にしています。
ああ、唯一の1左はそこだ。
だからマージ。
ああ、1、3、5。
オーケー。
マージ結合は、2つの別々の配列を取ります。
個別にそれらの二つの配列がソートされます両方。
したがって、この配列は、1、3、5は、ソートされています。この配列には、0、2、4、ソートされています。
今何マージが行うべきこと自体がソートされている単一の配列にそれらを組み合わせることである。
だから我々はその中に、これらの要素を持っているとしている大きさ6の配列をしたい
ソートされた順序インチ
>> それで我々はこれら2つの配列がソートされているという事実を活用することができます
線形時間でこれを行うには、
、この配列はサイズxであり、これはサイズyであれば線形時間の意味
その後合計アルゴリズムはO（x + y）がなければなりません。オーケー。
だから提案。
[学生]は、我々は左から開始してもらえますか？
だから、あなたがダウンして最初にして1 0を置くことにしましょう​​し、ここであなたは2にいる。
だから、あなたが右に動いているタブを持っているようなものだ。 >> [ボーデン]うん。
私達はちょうど一番左の要素に注目すると、これらの配列の両方のために。
両方の配列がソートされているので、我々は知っているこれらの2つの要素
どちらアレイ内の最小要素である。
だから、それらの2つの要素の1が私たちのマージした配列内の最小の要素でなければならないことを意味します。
それはちょうどので、最小、右今回で一つであることを起こる。
0が1未満であるので、だから我々は、0を取る左に挿入し
ので、0を取る我々の最初の位置にそれを挿入した後、これを更新する
現在、最初の要素に焦点を当てる。
そして今、我々は繰り返す。
だから今我々は2と1を比較します。 1が小さくなるので、我々は1を挿入します。
我々はこの男を指すように、このポインタを更新する。
今、我々は再びそれを行う、2そう。これは、これらの2、3と比較し、更新されます。
その後、このアップデート、4と5。
だからそれはマージされています。
>> それは、我々は一度だけ各要素を渡って行くので、それは線形時間であることがかなり明白になります。
そして、それはマージソートを実装するための最大のステップは、これをやっているされています。
そして、それはそんなに難しいことではありません。
心配するカップルの事はしてみましょう私たちは1、2、3、4、5、6をマージしたと言う。
この場合、我々はこの1つは小さくなるだろうされているシナリオでは、結局、
それから私達はこのポインタを更新し、この1つは、これを更新して、小さいことになるだろう
この1つは小さいです、そして今、あなたは認識しなければならない
あなたが実際と比較するための要素が不足してきたとき。
我々はすでに、この全体の配列を使っているので、
この配列内のすべてのものが今まさにここに挿入されます。
我々はこれまで我々の配列のいずれかが完全に既にマージされたポイントに遭遇しそうだとすれば、
私たちはただ、他の配列のすべての要素を取得し、配列の末尾に挿入します。
だから我々はわずか6、4、5を挿入することができます。オーケー。
それは気をつけて一つのことです。
それは、ステップ1である必要があります実装。
それに基づいて、次にソートマージは、2つのステップ、2ステップ愚かだ。
ちょうどこの配列を与えてみましょう。
だから、マージソート、ステップ1は再帰的に半分に配列を分割することです。
だから半分に、この配列を分割します。
我々は今、4、15、16、50、8、23、42、108を持っています。
そして今、我々は再びそれを行うと、我々は半分にこれらを分割します。
私はこの辺でそれを行うだけでしょう。
50、4、15と16だから。
我々はここを介して同じことをするだろう。
そして今、我々は再び半分に分割します。
そして、我々は4、15、16、50を持っています。
だからそれは私たちのベースケースです。
配列のサイズは1であると、次に我々は、半分に分割すると停止します。
>> 今、私たちは、これで何をすればいいですか？
我々は、これはまた、8、23、42、および108に打破するに終わる。
だから今我々はこの点にいることを、今ではマージソートのステップ2は、単にリストにペアをマージすることです。
だから我々は、これらをマージしたい。私達はちょうどマージと呼びます。
私たちは、マージソートされた順序でこれらを戻すことがわかっている。
4、15。
今、私たちは、これらをマージしたい、そしてそれは、ソートされた順序でそれらを使用してリストを返します。
16、50。
我々は、それらをマージする - 私は書くことができません - 8、23、42、108。
だから我々は一度ペアをマージした。
今、私たちはもう一度マージ。
それ自体はそれぞれのこれらのリストがソートされていることに注意してください、
それから私達はちょうどソートされている大きさ4のリストを取得するには、これらのリストをマージすることができます
とソートされているサイズ4のリストを取得するためにこれらの2つのリストをマージします。
そして最後に、我々はソートされているサイズ8のいずれかのリストを取得するにはサイズ4のものと二つのリストをマージすることができます。
だから、これは全体的なnログnであることを確認するために、我々はすでにマージが線形であることを見て、
ので、我々はそうマージの全体的なコストのように、これらをマージを扱っているときに
これらの2つのリストのためだけに2があるためです -
またはよく、それはnのOですが、ここでnは、ちょうどこれらの2つの要素であるので、2です。
そして、これら2つの値は2になりますと、これらの2つの値は2になりますと、これらの2つの値は2になります
ので、私たちが行う必要があることをマージのすべてにわたって、私たちはnをやってしまう。
2のように+ 2 + 2 + 2 nである8、、です
ので、このセットにマージのコストはnです。
そして、ここにも同じこと。
そして、私たちは、これら2、これらの2つをマージします、個別にこのマージは、4つの操作がかかります
このマージは、これらのすべての間、再び4つの操作を取るしますが、
私たちは、マージN合計物事に終わるので、このステップは、nを取ります。
ので、各レベルがマージされて、n個の要素を取ります。
>> そして、どのように多くのレベルがありますか？
各レベルでは、我々の配列のサイズが2増加します。
ここに我々の配列はサイズ1のものであり、ここで、彼らはサイズ2のであれば、ここに彼らは、サイズ4のだ
そして最後に、彼らはサイズ8のだ。
それが倍増していますのでので、ログのnこれらのレベルの合計があるように起こっています。
だからログnレベル、個々のレベル取るn個の合計の操作と、
私たちは、常にn log nのアルゴリズムを取得します。
質問はありますか？
人々は、すでにこれを実装する方法についての進歩を遂げている？
誰もがすでに私はちょうど彼らのコードを引っ張ることができる状態になっていますか。
私は分を与えることができます。
この1つは長くなるだろう。
私は非常に再発をお勧めします -
マージ時に再帰を行う必要はありません
マージのために再帰を行うためには、異なるサイズの束を渡す必要があるとしている。
あなたはできますが、それは迷惑なんだ。
しかし、ソート自体の再帰はとても簡単です。
あなただけの文字通り右半分で並べ替え、左半分にソートを呼び出します。オーケー。
誰も私がまだプルアップすることができます何かを持っている？
さもないと私は分を差し上げます。
オーケー。
誰もが我々が働くことができる何かを持っている？
さもなければ私達はちょうどこのと連携し、そこから拡大していく。
>> 誰も私がプルアップすることができ、この以上のものを持っている？
[学生]うん。あなたは私をプルアップすることができます。 >>すべての権利。
うん！
[学生]の条件がたくさんあり​​ました。 >>ああ、撃つ。次のことができます -
[学生]私はそれを保存する必要があります。 >>うん。
だから我々は別々にマージんでした。
ああ、それはそれほど悪くはありません。
オーケー。
だからソートはちょうどmergeSortHelpを呼び出しそのものです。
mergeSortHelpが何を私達に説明してください。
[学生] MergeSortHelpはかなり多く、主に2つの手順を行い、
これは、配列の各半分をソートするために、次に、それらの両方をマージすることです。
[ボーデン]わかりましたので、ちょっと待ってて。
私はこれを考える - >> [学生]私がする必要がある -
うん。私は何かが欠けている。
マージでは、私は新しい配列を作成するために必要なことがわかります
私はその場所でそれを行うことができなかったからだ。 >>はい。それはできません。訂正してください。
[学生]だから私は、新しい配列を作成します。
私は再変更するマージの終了時に忘れていました。
オーケー。私たちは、新しい配列が必要です。
マージソートでは、これはほとんど常にtrueです。
良いアルゴリズム時間的コストの一部
ほとんど常に少しより多くのメモリを使用する必要があるされています。
だからここでは、あなたがマージソートを行う方法に関係なく、
あなたは必然的にいくつかの余分なメモリを使用する必要があります。
彼または彼女は、新しい配列を作成しました。
そしてあなたは終わりに我々だけで、元の配列に新しい配列をコピーする必要があると言う。
[学生]私はそう思う、うん。
それは、参照または何でカウントの面で動作するかどうか私は知らない -
うん、それは動作します。 >> [生徒]オーケー。
あなたはこれを実行してみましたか？ >> [生徒]いいえ、まだありません。オーケー。>>
それを実行してみて、その後私は2番目のためにそれについて話します。
[学生]私は右、しかし、すべての関数プロトタイプとすべてを持っている必要がありますか？
関数プロトタイプ。 [はい] - ああ、あなたはのような意味。
ソートはmergeSortHelpを呼んでいる。
>> mergeSortHelpを呼び出すための並べ替えのためのために、だから、mergeSortHelpが定義されている必要があり
ソート前または私達はちょうどプロトタイプが必要です。ちょうどそれをコピーして貼り付ける。
と同様に、mergeSortHelpは、マージを呼んでいる
しかし、マージはまだ定義されていないので、我々はちょうどmergeSortHelpに知らせることができます
それがマージのように見えるように何が起こっているかだし、それはそれだ。
mergeSortHelpだから。
我々はベースケースを持っていないところで私たちは、ここに問題があります。
MergeSortHelpが再帰的であるので、任意の再帰関数
それ自体を再帰的に呼び出しを停止するタイミングを知るために、ベースケースのいくつかの並べ替えが必要になるだろう。
私たちのベースケースはここで何をするつもりですか？うん。
[学生]大きさが1である場合？ >> [ボーデン]はい。
だから我々はすぐそこに見たように、我々は分裂アレイを停止
かつて我々は、必然的に自分自身をソートされているサイズ1の配列に入った。
サイズが1に等しいのであれば、我々は、配列が既にソートされて知っている
ので、単に返すことができます。
>> ボイドの通知は、私たちは特定の何かを返さない、私達はちょうど返す。
オーケー。だからそれは私たちのベースケースです。
私たちは、サイズが0の配列をマージすることが起こる場合、私たちの基本ケースにもなることができると思います
我々は、おそらく、どこかの時点で停止したい
ので、単に大きさが2未満または未満または1に等しいと言うことができます
ので、これは今どのような配列のために働くこと。
オーケー。
だからそれは私たちのベースケースです。
今、あなたは、マージを通して私たちを歩きたいのですか？
これらのすべての場合は何を意味するのでしょうか？
ここまで、私たちは、同じ考え方をしている -
[学生]私はすべてmergeSortHelp呼び出しでサイズを渡すことが必要である。
私は追加のプライマリとしてサイズを追加し、それは大きさ/ 2のような、そこにはありません。
[ボーデン]ああ、サイズ/ 2サイズ/ 2。 >> [生徒]うん、また同様に上記の関数インチ
[ボーデン]ここですか？ >> [生徒]ジャストサイズ。 >> [ボーデン]ああ。サイズ、サイズは？ >> [生徒]うん。
[ボーデン]オーケー。
私は一瞬考えてみましょう。
我々はこの問題に遭遇していますか？
我々は常に0として左を扱っている。 >> [生徒]いいえ
それはあまりにも間違っている。申し訳ございませんでした。それがスタートです。うん。
[ボーデン]オーケー。私はその方が好き。
と終了。オーケー。
だから今は、マージを通して私たちを歩きたいのですか？ >> [生徒]オーケー。
私はちょうど私が作成したので、この新しい配列を介して歩いている。
その大きさは、我々がソートさせたい配列の部分の大きさです
と私は、新しい配列のステップに置くべきだと要素を見つけようとする。
だから配列の左半分には、任意の複数の要素を持ち続けている場合は、最初の私がチェックしている、そんなことをして、
そうでない場合と、あなただけの言うことelse条件に下がる
大丈夫、それは右の配列でなければなりません、そして我々はnewArrayの現在のインデックスでそれを置くことにしましょう​​。
>> アレイの右側も終了されていて、その後、それ以外の場合は私がチェックしている、
その場合、私はちょうど左に置く。
それは実際には必要でないかもしれません。私はよく分からない。
しかし、いずれにせよ、2のどれが他の二つのチェックは、左または右に小さくなっている。
また、それぞれの場合において、私はインクリメント方プレースインクリメントしている。
[ボーデン]オーケー。
それはよさそうだ。
誰でもコメントや懸念や疑問を持っていますか？
またはそれは5のように見える - 私たちだけであることに何かをもたらすことを持っていることを4つのケースがそう -
しかし、我々は左の配列は、我々はマージする必要があるものがなくなっているかどうかを考慮する必要があります
右の配列は、我々はマージする必要があるものが不足しているかどうか -
私は何を指しています。
だから左配列はものがなくなっているか、または右の配列はものがなくなったかどうか。
それらは2つのケースがあります。
また、左のものが右のものよりも小さいかどうかの些細なケースを必要としています。
その後、我々は左のものを選びたい。
これらは例です。
だから、これは正しかった、ということになるよう。
配列が残っています。それは、1、2、3です。オーケー。そんなわけで、それらは我々がしたいと思うかもしれません4ものです。
そして、我々は反復解法上に行くことはありません。
私はお勧めしません -
マージソートは、再帰的な両方のテールではない関数の例です。
それは、それは末尾再帰にするのは簡単ではありません
だけでなく、それが反復するのは非常に簡単ではありません。
これは非常に簡単です。
マージソートの実装には、
マージ、あなたが何をするかに関係なく、あなたはマージを構築しようとしている。
>> だからマージの上に構築されたソートは再帰的にちょうどこれらの3行ですマージ。
反復的に、それはより多くの迷惑と考えるのがより困難である。
しかし、それはmergeSortHelp以来、末尾再帰ではないことに気づく - それはそれ自身を呼び出したときに -
それはまだこのような再帰呼び出しが戻った後のことを行う必要があります。
したがって、このスタックフレームはこのメソッドを呼び出した後であっても存在し続けなければなりません。
そして、あなたがこれを呼び出すと、スタックフレームが存在し続けなければなりません
でも、そのコールの後、我々はまだマージする必要があるためです。
そしてそれはこのテールと、再帰的に自明である。
質問はありますか？
かしこまりました。
だからソートするために戻って - ああ、私が見せたいものがふたつあります。オーケー。
ソートに戻って、我々はすぐにこの作業を行います。
または検索。並べ替え？並べ替え。うん。
ソートの始まりに戻って行く。
我々は、任意のアルゴリズムを使用して、その配列をソートするアルゴリズムを作成したい
n個のOインチ
それでは、どのようにこれは可能ですか？誰もが任意の並べ替えを持っていますか -
私は時前にほのめかし -
我々はnログnからnのOに向上させるために約ているのであれば、
我々は、我々のアルゴリズムの時間的に改善している
これは、我々はそのために補うために行う必要があるために何を行っているかを意味します
[学生]スペース。 >>うん。我々は、より多くのスペースを使用してすることになるだろう。
としないだけでも、より多くのスペース、それが指数関数的に多くのスペースです。
だから私はこのタイプのアルゴリズムは擬似何か、擬似多項式だと思う -
擬似 - 私は思い出すことができません。何か擬似。
しかし、我々はこれだけの容量を使用する必要があるので、それはだ
これは達成が、現実的ではないこと。
>> そして、どのように我々はこれを達成するの​​ですか？
我々が保証した場合我々は、これを達成することができ、そのアレイ内の特定の要素
一定以下の大きさです。
だから、ちょうどサイズが200であると言うてみましょう
配列内の任意の要素には、以下のサイズ200です。
そして、これは実際には非常に現実的である。
あなたは非常に簡単にあなたはそれのすべてを知っている配列を持つことができ
いくつかの数よりも少なくなるだろう。
あなたには、いくつかの絶対に大規模なベクトルか何かを持っている場合など
しかし、あなたは、すべてが0と5の間になるだろう知っている
それがこれを行うことが大幅に速くなるだろう。
とのいずれかの要素にバインドされ、5です
このバウンドので、それはあなたが使用しようとしているどのくらいのメモリである。
だからバインドは200です。
整数のみを最大4億円となりましたことができるので、理論的にはバウンドが常にあるので、
我々はスペースを使用しているはずだそれ以来、それは非現実的だ
40億のオーダーである。だからそれは非現実的である。
しかし、ここで我々はバウンドに言うよは200です。
n個のOでそれをやってのトリックは、我々は大きさのカウントはBOUNDと呼ばれる別の配列を作ることです。
だから、実際、これは次の内容のショートカットです - Clangのがこれを行う場合、私は実際にはわからない。
しかし、非常に少なくともGCCで - Clangの仮定 - 私は、あまりにもそれをしない -
これは単に0であることが、配列全体を初期化します。
私はそれを行うにはしたくないので、もし次に私が別個に行うことができます（int型私= 0;
I <BOUNDは、i + +）とカウント[I] = 0;
だから今はすべてが0に初期化されます。
私は、私の配列を反復
と私がやっていることは、私はそれぞれの数を数えている - ここに降りて行きましょう。
我々は4、15、16、50、8、23、42、108を持っています。
私は何を数えていると、それらの各要素の出現回数である。
実際にいくつか繰り返すと一緒にここにカップルより多く追加してみましょう。
我々がここにあるように、値の値は[i]の配列になるだろう。
だから、valは4または8または何でも可能性があります。
そして今、私は、私が見てきたどのように多く、その値の数えている
カウントしますので、[ヴァル] + +;
これが完了すると、カウントが0001のような何かを見に行くされています。
カウントを行いましょう[ヴァル] - + 1 BOUND。
>> 今では我々は0から開始しているという事実を考慮してばかりだ。
だから200が私たちの最大の数であることを行っている場合、
その後、0から200は201の事です。
我々は1つの4を持っているので、カウントだから、それは00001のように見えます。
その後、我々は、我々は数の第八インデックスに1を持っています0001があるでしょう。
我々は、カウント23日インデックスに2があるでしょう。
我々は、カウントの42インデックスに2があるでしょう。
だから我々は、カウントを使用することができます。
だからnum_of_item =カウント[I]。
とnum_of_itemが2であるので、もし、我々は番号iの2を挿入することを意味します
私たちのソートされた配列に変換します。
だから我々は、我々は配列にどのくらいずれているかを追跡する必要があります。
だからインデックス= 0。
アレイ - 私はちょうどそれを書こうと思います。
カウント -
配列[インデックス+ +] = I;
それは私が何をしたいですか？私はそれは私が欲しいものだと思います。
はい、これはよさそうだ。オーケー。
だから誰もが私のカウントアレイの目的が何であるかを理解するのでしょうか？
それは、これらの数値のそれぞれの出現回数をカウントしています。
それから私はその件数配列を反復処理しています、
とカウント配列内の​​i番目の位置
私のソートされた配列に表示されるはずだ、私は数です。
4の数が1であることを行っている理由です
8のカウントが1であることを行っている、23のカウントが2になるだろう。
だから私はソートされた配列に挿入したいどのようにそれらの多くのです。
その後、私はちょうどそれを行う。
私は私が私のソートされた配列に代入num_of_itemを挿入しています。
>> 質問はありますか？
我々は一度だけこれを反復処理しているのでので、再び、これは、線形時間である
それは、この数があると何が起こるかでも直線だ
ので、それは大いにあなたのバウンドが何であるかに依存します。
200のバウンドと、それはそれほど悪くはありません。
あなたのバウンドが10,000であることを行っている場合、そのことは、少し悪いです
あなたのバウンドが、4億ドルになるとしている場合、それは完全に非現実的だ
この配列は、現実的ではありませんサイズは4億円であることがあることを行っています。
だからそれはそれだ。質問はありますか？
[聞き取れない生徒の応答] >>オーケー。
我々が通過したとき、私はもうひとつを実現しました。
私はこの問題は、ルーカスさんと、おそらく我々が見てきたすべての単一の1であったと思います。
私は完全に忘れていました。
私がコメントしたかった唯一のものは、あなたがインデックスのようなものを扱っているということです
あなたは、forループを書くときにあなたは本当に、これを見ることはありません
しかし技術的には、いつでもあなたは、これらの指標を扱っている
あなたはかなり常に符号なし整数に対処しなければならない。
あなたは、符号付き整数を扱っているときに、この理由は、
そのため、2つの符号付き整数を持っていて、それらを一緒に追加した場合
そして、彼らが大きすぎる結局、その後は負の数になってしまう。
だから整数オーバーフローが何であるかです。
>> 私は2億円、10億ドルを追加した場合、私はマイナス1億ドルとなってしまう。
つまり、整数はコンピュータ上でどのように機能するかだ。
使用する場合の問題は、だから -
ローは20億であることを起こる、最大1億円が発生するかどうかは除いていいのよ
これは10億負になるだろうし、我々は2であることを分割するつもりだ
と負5億で終わる。
ですから、これは配列を検索することが起こる場合にのみ問題となります
物事の数十億の。
しかし、低+がアップするオーバーフローに起これば、そのことが問題だ。
とすぐに我々は彼らがunsigned作るとして、その後20億プラス10億は3億円です。
2で割った30億は1.5億ドルである。
だから、すぐに彼らは符号なしだとして、すべてが完璧です。
そしてそうそれはあなたがあなたのためにループを書くときにも問題だが、
そして実際に、それはおそらく、それを自動的に行います。
それは実際にちょうどあなたで叫ぶでしょう。
この数字は単なる整数であるには余りにも大きいですが、それは、符号なし整数に収まるであろうのであれば
それはあなたで叫ぶでしょう、あなたが本当に問題に遭遇したことがない理由だそう。
あなたは、インデックスが負になるだろうことはありませんされていることがわかります
ので、あなたは、配列を反復処理しているとき
あなたはほぼ常にunsigned int iを言うことができますが、あなたは本当に必要はありません。
物事も同様にかなり仕事に行くされています。
オーケー。 [ささやき]それが何時ですか？
私が見せたかったの最後のもの - と私はちょうどそれが本当に速いやる。
あなたは、私たちは第5か何かのようにMAXを定義することができるように、我々は＃defineしている方法を知っている？
MAXを行うことのないようにしましょう​​。 ＃200としてバインドを定義します。それは私たちが前にやったことだ。
ただコピーして貼り付けしようとしている定数を定義し、その
どこに私たちはBOUND書き込むために起こる。
>> だから我々は実際に＃定義でより多くのことを行うことができます。
我々は＃関数を定義できます。
彼らは本当に機能はないが、我々はそれらの関数と呼ぶことにします。
例がMAX（x、y）のようなものになるでしょうが（？：X X <Y Y）として定義されています。オーケー。
だからあなたは、三項演算子の構文に慣れる必要があります
しかし、xがyより小さいのですか？ yを返し、そうでなければxを返します。
それで、あなたは、あなたがこの別の関数を作ることができる見ることができる
これを返すブール値MAXは、2つの引数をもつように、関数がある可能性があります。
これは、私がこのように実行を参照してください最も一般的なものの一つです。我々はそれらのマクロを呼び出す。
これはマクロです。
これはちょうどそれのための構文です。
あなたがやりたいためにマクロを書くことができます。
あなたが頻繁にprintfが、ものをデバッグするためのマクロを参照してください。
printfのように、型、LINEは下線下線のようにC言語での特殊な定数がありますが、
2、LINEは下線下線
ともあり、私は2にFUNCアンダースコアだと思います。それはそれであるかもしれません。まあそんなところです。
それらのものは、関数の名前に置き換えられます
またはあなたがいることを行の番号。
頻繁に、あなたがダウンして、ここで私は、ちょうど書けデバッグprintfを書く
DEBUGとそれは私がにたまたまいる行番号と関数を出力します
それはそのデバッグステートメントが発生したこと。
そして、あなたはまた、他のものを印刷することができます。
だからあなたを警戒しなければならない一つのことは、私は＃DOUBLE_MAXを定義するために起こる場合です
2のようなものとして* yと2 * xになります。
何らかの理由でだから、あなたは多くのことをそんなことが起こる。
だからマクロ作る。
これは実際に壊れています。
私はDOUBLE_MAX（3,6）のような何かをすることによってそれを呼ぶだろう。
だから何を返すべき？
[学生] 12。
はい、12が返されるべきであり、12が返されます。
3 xには置換される、6はyの置き換え、そして我々は12で2 * 6、返却されます。
今度は何これは？何を返すべき？
[学生] 14。理想的には>> 14。
問題は、仕事を定義する方法をハッシュ、それは文字通りのコピー＆ペーストであることを忘れないことです
これはのように解釈されることに何が起こっているので、ほとんどすべての
1プラス6、2回1プラス6、2回3よりも3以下である。
>> したがって、この理由は、ほとんどの場合、括弧内のすべてを包む。
あなたは、ほとんどの場合、括弧内にラップする任意の変数。
私はここでそれを行う必要がないことを知っているようにあなたがする必要がないケースがあります
未満であるため、ほとんどはいつもちょうど仕事に行く、
それも真ではないかもしれません。
DOUBLE_MAX（1 == 2）のようなとんでもないものがある場合は、
その後、3分の1以下と置き換え得るために起こっていることは、2に等しい等しい
ので、それが1より小さい3をやろうとしている、その等しい2を行い、
それは我々が望むものではありません。
したがって、任意の演算子の優先順位の問題を防ぐために、
常に括弧で包む。
オーケー。そして、それはそれ、5:30です。
あなたはPSETの質問を有したら、私達に知らせてください。
それは楽しみであるべきであり、ハッカーのエディションには、はるかに現実的である
昨年のハッカー版よりも、私たちはあなた方の多くはそれを試すことを願っています。
昨年の非常に圧倒的でした。
>> [CS50.TV]