すべての権利なので、計算の複雑さ。 警告のちょうどビット 私たちも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です。