>> DOUG LLOYD：だからCS50に、我々は、約学びました ソートや検索の様々な
アルゴリズム。
そして、時にはそれがすることができます 続けるには少しトリッキー
何アルゴリズムのトラックが何を行います。
私たちは本当にだけしました あまりにも表面を脱脂、
他の多くの検索があります およびアルゴリズムをソート。
だから、このビデオLETでの わずか数分かかります
試してみて、各アルゴリズムを蒸留します その中核的な要素まで
あなたがほとんどを覚えています それらについての重要な情報
そして、明確することができます 違い、必要に応じて。
>> 最初は、選択ソートです。
選択ソートの基本的な考え方 最小のソートされていない要素を見つけることです
配列内とでそれを交換 その配列の最初のソートされていない要素。
私たちは、最悪の場合のことを言いました その実行時間をn乗しました。
そして、あなたは理由を呼び出したい場合は、取ります 選択ソートのビデオを見て。
最良の実行時間 また、nは2乗さ。
>> バブルソート、その背後にある考え方 1は、隣接する対を交換することです。
だから、それはあなたを助ける重要なのです ここでの違いを覚えています。
ソートされているので、これまでの選択、 smallest--バブルを見つけます
ソートスワップ隣接する対です。
私たちは、隣接する対を交換 要素の彼らの場合
これは効果的に、順不同であります 右に大きな要素を泡、
同時に、それはまた始まり 左に小さい要素を移動します。
最悪のケースの場合は、ランタイム バブルソートのN乗されます。
最良の実行時間 バブルソートのnです。
そのような状況にあるため、 我々はactually--ません
我々はする必要はありません まったくスワップを行います。
私たちは、1つを行う必要があります すべてのn個の要素を通過。
>> 挿入ソートでは、 ここでの基本的な考え方は、シフトしています。
つまり、挿入ソートのキーワードです。
我々は、ワンススルーステップになるだろう 左から右に配列。
私たちがそうであるようにと、私たちはしています 要素をシフトするつもり
我々はすでにのためのスペースを作るために見てきました どこかにフィットする必要が小さいもの
バックそのソートされた部分です。
だから我々は、ソートされた配列を構築1 左から右に時間の要素、
私たちは部屋を作るために物事をシフトします。
の最悪の場合の実行時間 挿入ソートは、n乗されます。
最良の場合の実行時間はNです。
>> キーワードsort--マージ ここで分割し、マージされています。
私たちは、かどうか、完全な配列を分割 それは6つの要素、8要素ですが、
万elements--我々はそれを分割 半分、半分、半分にダウンして、
我々は、配列の下になるまで、 nは1素子アレイ。
nは1素子アレイのセット。
だから我々は1で開始 1000要素の配列、
我々は我々のポイントを取得 千一素子アレイを持っています。
その後、我々はそれらのサブ配列をマージし始め バック一緒に正しい順序です。
だから我々は2つ​​の1要素の配列を取ります そして、2要素の配列を作成します。
我々は2つ​​の2素子アレイを取ります そして、4素子配列を作成
などというように、我々はするまで 再び、1つのN要素の配列を再構築。
>> の最悪の場合の実行時間 ISマージソートn回のnを記録します。
我々は、n個の要素を有するが、 この再結合過程
ログ取りのnを取得するための手順 完全な配列にバックします。
時間を実行する最良の場合も、n個のログです nは、このプロセスは本当にないので、
アレイがあったかどうか気に ソートやないで開始します。
プロセスは同じですが、あります 短絡事に方法はありません。
だからN N最悪の場合にログインすると、 N N最良のケースでログインします。
>> 我々は2つ​​の話を 検索アルゴリズム。
だから、線形検索が反復処理についてです。
私たちは、アレイ全体進みます 一度、左から右に、
番号を検索しようとしています 私たちは、探していること。
最悪の場合の実行時間は、n個の大Oです。
これは、繰り返し処理私たちがかかる場合があります 一つ一つの素子の両端
我々が探している要素を検索します 以下のため、いずれかの最後の位置で、
ではない、またはまったく。
しかし、我々はそれまでを確認することはできません 我々はすべてのものを見てきました。
ベスト・ケースをM、我々はすぐに見つけます。
の最良の実行時間 線形探索は1のオメガです。
>> 最後に、二分探索がありました、 これは各種の配列を必要とします。
それは非常にです忘れないでください 考慮すべき重要なこと
二分探索で作業する場合。
それはit--使用するための前提条件です あなたが探している配列を介して
ソートする必要があります。
それ以外の場合は、キーワード 分割統治です。
半分に配列を分割し、 要素の半分をなくします
あなたを介して進むようたびに。
このため、分割統治の 半アプローチで分割のもの、
最悪の場合の実行時間 バイナリサーチの
実質的にこれは、nはログ 線形検索のnよりも優れています。
最良の実行時間はまだ一つです。
>> 我々はすぐにそれを見つけるかもしれません 初めて我々は、分裂を作るが、
再び、ということを覚えています バイナリ検索があるが、
線形検索よりも実質的に良好 ログであることのおかげでN N対、
あなたが仕事を通過する必要がある場合があります 、最初にあなたの配列をソートします
応じて、それはあまり効果的になるかもしれません ソートされた反復の大きさ。
>> 私はダグロイドだけど、これはCS50です。