>> すべての権利なので、計算の複雑さ。
警告のちょうどビット 私たちもfar--に飛び込む前に、
これはおそらくの間になるだろう ほとんどの数学重いもの
我々は、CS50にについて話しています。
うまくいけば、それはあまりにも圧倒的ではありません 我々は試してみて、ご案内します
プロセスを通じて、しかし、 公正な警告の少しだけ。
少しはあります 数学のここに関与。
すべての権利なので、作るために 私たちの計算リソースの使用
実際のworld--に、それは本当にです アルゴリズムを理解することが重要
そしてどのようにデータを処理します。
私たちは本当にしている場合 効率的なアルゴリズムは、我々
リソースの量を最小限に抑えることができ 我々はそれに対処するために利用可能です。
私たちは、そのアルゴリズムを使用している場合 多くの仕事を取るために起こっています
本当に処理します 大量のデータセットが、それはです
多くを必要としよう より多くのリソース、およびこれ
お金、RAM、もののすべてのそのようなものです。
>> だから、できることは分析します アルゴリズムは、このツールセットを使用して
基本的に、question--を要求 このアルゴリズムの規模をどうしますか
我々はそれでより多くのデータを投げるように？
CS50では、データの量をしています 作業はかなり小さいです。
一般的に、私たちのプログラムが行っています 第二又はless--で実行します
おそらくはるかに少ないです 特に早い段階で。
>> しかし、お得な情報会社について考えます 顧客の何百万、数百と。
そして彼らは、処理する必要があります その顧客データ。
顧客の数は、彼ら 持っているが、どんどん大きくなります
それが必要になるだろう より多くの資源。
どのように多くのより多くのリソース？
まあ、それはどのように依存します 我々はアルゴリズムを解析し、
このツールボックスのツールを使用して。
我々は複雑さについて話すとき algorithm--時にはあなた'LL
それは時間と呼ばれる聞きます 複雑またはスペース複雑
しかし、我々はちょうどつもりです complexity--呼び出すために
我々は、一般的に話をしています 最悪のシナリオ。
の絶対的な最悪の山を考えます 我々はそれを投げることができたデータ、
どのようにこのアルゴリズムはに起こっています 処理したり、そのデータを扱いますか？
当社は通常、最悪の場合を呼び出します アルゴリズムビッグOの実行時。
だから、このアルゴリズムは、に言ったことがあります 乗n個のNまたはOのOで実行されます。
かについて、より それらは、第二の平均。
>> しかし場合によっては、我々は注意して行います 最良のシナリオについて。
データは、我々が望んでいたすべてのものである場合 それがされるように、それは完璧でした
私たちは、この完璧を送信し、 私たちのアルゴリズムを介してデータのセット。
それはどのようにそのような状況に扱うのでしょうか？
私たちは時々ように、その参照してください ビッグオメガ、ビッグOとは対照的にそのように、
我々はビッグオメガを持っています。
最良のシナリオのためのビッグオメガ。
最悪のシナリオのためのビッグO。
一般的に、我々はについて話すとき アルゴリズムの複雑さ、
我々は話をしています 最悪のシナリオ。
だから、心の中でそれを維持します。
>> そして、このクラスでは、我々は一般的になるだろう 脇厳密な分析を終了します。
科学とフィールドがあります。 原料のこの種に専念。
我々は推論について語るとき アルゴリズムを通じ、
我々は多くのために少しずつやるします 私たちはクラスで話アルゴリズム。
私たちは本当にただの話をしています 常識とそれを通して推論、
ない式、または証拠と、 またはそのような何か。
だから、心配しないで、私たちはされません 大きな数学のクラスに回します。
>> だから私たちは複雑気に言いました それはどのように、質問をしますので、
私たちのアルゴリズムは、より大きなハンドル行い、 大きなデータセットは、彼らにスローされます。
さて、データセットは何ですか？
私はそれを言ったとき、私は何を意味するのですか？
それはほとんどの作るものは何でも意味します コンテキストのセンスは、正直に言うと。
我々は、アルゴリズムを使用している場合は、 我々は、おそらくだStrings--プロセス
文字列のサイズの話。
つまり、データですset-- サイズ、数
文字列を構成する文字の。
我々は話をしている場合 ファイルを処理するアルゴリズム、
私たちはどのように話して可能性があります 多くのキロバイトは、そのファイルを含みます。
そして、それは、データ・セットです。
我々は、アルゴリズムの話をしている場合 それは、より一般的にアレイを処理します
このようなソートアルゴリズムなど またはアルゴリズムを検索、
我々は、おそらく数の話をしています アレイを含む要素。
>> 今、我々は測定することができます 特にalgorithm--
私が言うとき、我々はできます 私は、アルゴリズムを測定
私たちはどのように測定することを意味 多くのリソースは、それが占めています。
これらのリソースがあるかどうか、どのように多くの RAM--のバイトまたはメガバイトのRAM
それは使用しています。
またはどのくらいの時間、それを実行するのにかかります。
そして、我々はこれを呼び出すことができます n個のfを、任意に、測定します。
nが数である場合、 データセット内の要素。
そして、n個のfが何代です。
どのように多くのリソースの単位ありません そのデータを処理するために必要とします。
>> 今、私たちは実際には気にしません ちょうどnのFものですについて。
実際には、我々は非常にまれwill--ありません 確かに私はこのclass--に決して
任意の本当に深い飛び込みます F Nが何であるかを分析します。
私達はちょうど何のFについて話をするつもりです nが約または何それは傾向があります。
アルゴリズムの傾向があります 最高次の項によって決定。
そして、私たちは何を私が見ることができます 取ることによって、それの意味
より具体的な例を見て。
>> それでは、私たちが持っているとしましょう 三つの異なるアルゴリズム。
そのうちの最初は、nを取ります 資源の三乗、一部のユニット
サイズnのデータセットを処理します。
我々はかかる第2のアルゴリズムを持っています 乗プラスのn乗資源のn
サイズnのデータセットを処理します。
そして、我々は三分の一を持っています そのin--実行するアルゴリズム
取りのn乗マイナス8N乗 リソースのプラス20 n個
アルゴリズムを処理します サイズnのデータセットを持ちます。
>> ここでもう一度、私たちは本当につもりはありません このレベルの詳細に取得します。
私は実際には、これらを持っています ここでのポイントの図のように
私はあることを行っていること 第二になっています
我々は唯一の本当に気ということです 物事の傾向について
データセットが大きくなるにつれて。
データセットが小さい場合ので、あり 実際にはかなり大きな違い
これらのアルゴリズムです。
そこに第3のアルゴリズム 13倍の時間がかかり、
リソースの13倍の量 最初のものに比べて実行​​します。
>> 我々のデータセットは、サイズ10である場合、その 大きいですが、必ずしも巨大ではありません、
我々はそこだと見ることができます 実際に差のビット。
第3のアルゴリズム より効率的になります。
それは実際に40％についてです - または60％より効率的。
これは、40％の時間を要します。
それが取ることができrun--できます リソースの400単位
サイズ10のデータセットを処理します。
最初のに対し アルゴリズムは、対照的に、
リソースの1,000台を取ります サイズ10のデータセットを処理します。
しかし、何が起こるか見てのように 私たちの数はさらに大きな取得します。
>> 今、違い これらのアルゴリズムの間
少し明らかになり始めます。
あることと事実 下位terms--というか、
下exponents--と用語 無関係になり始めます。
データセットのサイズである場合 1,000最初のアルゴリズム
億の手順で実行されます。
そして、第2のアルゴリズムがで実行されます 億100万ステップ。
そして、第3のアルゴリズムが実行されます 億ステップのちょうど内気インチ
これはかなり億の手順です。
これらの下位の用語が開始します 本当に無関係になるために。
そして、ちょうど本当にへ ホームハンマーpoint--
データ入力は、サイズAである場合 million--これらの3つのすべてのほとんどを
場合は、1つquintillion--を取ります 私の数学はcorrect--手順です
データ入力を処理します 万人規模の。
それはステップの多くのです。
実際には、そのうちの一つがかもしれません カップル100,000またはカップルを取る100
万人であっても少ないとき 我々は数の話をしています
それはそれは一種の無関係ですbig--。
彼らはすべて取る傾向にあります 約N乗、
そして私たちは、実際に参照することになり これらのアルゴリズムのすべてに
n個のオーダーであるとして キューブまたはn個の立方体のビッグO。
>> ここではより多くののいくつかのリストです 一般的な計算の複雑さのクラ​​ス
我々はで遭遇するだろうと アルゴリズム、一般的に。
そしてまた、特にCS50インチ
これらはから注文されています 一般的に上部の最速、
下部の一般最も遅いへ。
そこで、一定時間アルゴリズムは傾向 かかわらず、最速であることを
の大きさの あなたが渡すデータ入力。
彼らは、常に1つの動作を取りますか に対処するためのリソースの1単位。
それは、2かもしれないかもしれません 3であること、それは4であるかもしれません。
しかし、それは一定の数です。
それは変化しません。
>> 対数時間アルゴリズム やや優れています。
そして、本当に良い例 対数時間アルゴリズム
あなたはきっと、今では見たことがあります 電話帳の引き裂きます
電話帳にマイク・スミスを見つけることができます。
我々は半分に問題をカット。
nが大きくなるように そして、大きく、larger--
実際には、毎回あなたが倍増します nは、それだけで一歩を取ります。
だから、多くの方が良いでしょう より、たとえば、線形時間。
あなたはN二重かどうかは、どちらが ステップ数の2倍になります。
あなたは、nを3倍にする場合は、とり ステップ数を3倍に。
単位当たりの一歩。
>> その後、物事は少しを得ますmore-- 少し大きなそこから。
あなたは時々、線形リズミカルな時間を持っています ログ線形時間と呼ばれるか、単にN Nを記録します。
そして、我々は例よ そのアルゴリズムの
まだ良いですn個のログN、で実行されます 二次time--よりN乗。
あるいは多項式時間、N 2 2より大きい任意の数。
あるいは指数時間、どの でもworse-- C nにあります。
だから、いくつかの定数はに上げ 入力の大きさの力。
その場合1,000--があるかどうか データ入力は、サイズ1000であり、
それは第千パワーにCを取るだろう。
これは、多項式時間よりも多くの悪化です。
>> 階乗時間はさらに悪くなります。
そして、実際には、実際にそこを行います 無限時間アルゴリズムが存在し、
そのような、いわゆるとして愚かsort-- ジョブがランダムに配列をシャッフルすることです
して、どうかをチェック かどうか、それがソートです。
そして、それはランダムに、ではない場合 再配列をシャッフルします
それはソートされたのかどうかを確認してください。
そして、あなたはおそらくimagine--できますように あなたは状況を想像することができます
ここで、最悪の場合には、その意志 実際には配列で開始することはありません。
このアルゴリズムは永遠に実行されます。
そして、その結果は次のようになります 無限の時間アルゴリズム。
うまくいけば、書き込みされません 任意の階乗または無限時間
CS50でアルゴリズム。
>> それでは、もう少し見てみましょう いくつかの単純で具体的な表情
計算の複雑性クラス。
だから我々はexample--を持っています または二つの例here--
一定時間アルゴリズム、 これは、常に取ります
最悪の場合には単一の操作。
したがって、最初のexample-- 我々は機能を持っています
これは、あなたのための4と呼ばれます サイズ千の配列を受け取ります。
しかし、その後明らかに 実際に見ていません
it--は本当に何を気にしないで その中の、その配列の。
常にわずか4を返します。
だから、そのアルゴリズム、 それという事実にもかかわらず、
千の要素を取りません 彼らと何を行います。
ただ、4を返します。
それは、常に、単一のステップです。
>> 実際には、2 nums--を追加します 我々としてwell--前に見てきました
ちょうど2つの整数を処理します。
これは、単一のステップではありません。
これは、実際のカップルの手順です。
あなたが得る、あなたはBを取得し、あなたがそれらを追加 一緒に、あなたの出力結果。
だから、84ステップです。
しかし、それは、常に一定です かかわらず、またはBの。
あなたが取得する必要があり、Bを取得し、追加 一緒に、出力結果を。
だから、一定時間アルゴリズムです。
>> ここでの例です 線形時間algorithm--
それはとりgets--アルゴリズム 一つの追加のステップ、おそらく、
あなたの入力は1で成長として。
それでは、私たちが探しているとしましょう 配列の数5の内部。
あなたはどこに状況があるかもしれません あなたはそれがかなり早期に見つけることができます。
しかし、あなたはまた、可能性があり 状況どこに
配列の最後の要素であるかもしれません。
サイズ5の配列では、もし 我々は数5を探しています。
これは、5つのステップを取ることになります。
そして、実際には、そこだと想像します この配列ではない5どこでも。
我々はまだ実際に見ています 配列のすべての単一の要素
決定するために、 か否か5があります。
>> だから、ということです最悪の場合、中 要素は、配列の最後です
またはまったく存在しません。
我々はまだ見ています n個の要素のすべて。
だからこのアルゴリズム 線形時間で実行されます。
あなたがして、そのを確認することができます 言って少し外挿し、
我々は6要素の配列を持っていた場合 我々は、数5を探していました
それは6つのステップを取ることがあります。
我々は7要素の配列を持っている場合と、 我々は数5を探しています。
これは、7つのステップを取ることがあります。
私たちは、1つ以上の要素を追加します アレイは、それはもう一つのステップを取ります。
それは線形アルゴリズムです 最悪の場合です。
>> カップルのあなたのための迅速な質問。
何runtime--は何ですか 最悪の場合の実行時間
このコードの特定のスニペットの？
だから私は実行され、ここで4ループを持っています Jからはるばるメートルまで、0に等しいです。
そして、どのようなことを私はここで見ているあります ループの本体は、一定の時間で実行されます。
そうする用語を使用して、 我々はすでに何about--話しました
最悪の場合であります このアルゴリズムの実行時間？
秒を取ります。
ループの内側部分 一定の時間で実行されます。
との外側部分 ループがm回実行しようとしています。
そこでここでは、最悪の場合の実行時間は何ですか？
あなたはメートルのビッグOを推測しましたか？
あなたは正しいだろう。
>> どのように別のものでしょうか？
我々が持っているこの時間 ループの内側のループ。
私たちは、外側のループを持っています それは、ゼロからPに実行されます。
そして、我々は実行され、内側のループを持っています ゼロからpまで、その内、
私は身体と述べています ループは、一定の時間で実行されます。
だから、最悪の場合の実行時間は何ですか このコードの特定のスニペットの？
さて、もう一度、私たちは持っています p回を実行します外側のループ。
また、各time--反復 そのループの、むしろ。
我々は、内側のループを持っています それはまた、p回を実行します。
そして、その内部に、あります そこに一定のtime--少しスニペット。
>> だから我々はその外側のループを持っている場合 その内側にp回を実行しています
その内側のループ 何であるかtimes-- Pを実行します
最悪の場合の実行時間 このコードのスニペットの？
あなたは、pのビッグOの二乗と思いましたか？
>> 私はダグロイドです。
これはCS50です。