[Powered by Google Translate] あなたは、おそらく人々が高速または効率的なアルゴリズムの話を聞いた あなたの特定のタスクを実行するため、 それが高速または効率的であるようにアルゴリズムのために正確に何を意味するのでしょうか？ まあ、それは、リアルタイムで測定について話していない 数秒または数分のような。 これは、コンピュータのハードウェア とソフトウェアが大幅に異なります。 私のプログラムは、あなたよりも処理が遅くなることがあり 私は、古いコンピュータ上でそれを実行しているので、 または私はオンラインゲームをプレイすることが起こるので、 同時に、それは、すべての私のメモリを占有している または私は別のソフトウェアを介して私のプログラムを実行している可能性があり これは低レベルで異なるマシンと通信します。 これは、リンゴとオレンジを比較するようなものだ。 ちょうど私の遅いコンピュータでは時間がかかるため、 マーケットは答えをお返しするより あなたはより効率的なアルゴリズムを持っているわけではありません。 

そこで、我々は直接プログラムの実行時間を比較することはできませんので、 数秒または数分で、 どのように我々は2つ​​の異なるアルゴリズムを比較してどう かかわらず、ハードウェアやソフトウェア環境の？ アルゴリズムの効率性を測定するのより統一的な方法を作成するには、 コンピュータ科学者と数学者が考案した プログラムの漸近的な複雑さを測定するための概念 "ビッグOhnotation 'と呼ばれ、表記法 これを記述するため。 正式な定義は、関数f（x）ということです オーダーg（x）の上で動作する いくつかの（x）の値が存在する場合は、x₀と いくつかの定数A、C、そのための f（x）は、より小さいか等しい その定数倍g（x）は X₀より大きいすべてのxについて。 

しかし、正式な定義によって離れて怖がってはいけない。 これは実際には理論的な観点から未満でどういう意味ですか？ まあ、それは基本的に分析する方法です プログラムの実行時には、漸近的に成長する速さ。 それは、無限大に向かってあなたの入力のサイズが大きくなるにつれて、ある 発言は、サイズ10の配列と比較して、サイ​​ズ1000の配列をソートしています。 あなたのプログラムの実行時間はどのように成長するのでしょうか？ 例えば、文字の数をカウントする想像 文字列内の最も簡単な方法  文字列全体を通って歩いて 字順と各文字のカウンタに1を加算する。 このアルゴリズムは、線形時間で実行するように言われています 文字数に関しては、 文字列中の 'N'。 要するに、それはO（n）で実行されます。 これはなぜですか？ さて、このアプローチを使用して、時間が必要 文字列全体をトラバースする 文字の数に比例します。 20文字の文字列の文字数を数える それが取るように2倍の時間がかかるために起こっている 10文字の文字列内の文字をカウントするため、 あなたはすべての文字を見ているので、 そしてそれぞれの文字が見て同じ時間がかかります。 あなたは文字の数を増やすと、 ランタイムは、入力の長さに比例して増加します。 

さて、あなたはその線形時間を決定した場合を想像し O（n）は、あなたのためだけに十分に速くはありませんでしたか？ たぶん、あなたは巨大な文字列を格納している、 そしてあなたはそれがかかる余分な時間の余裕がない 一つずつを数え、それらのすべての文字をトラバースする。 だから、あなたは別の何かをしようと決める。 あなたは既に文字数を格納するために起こるならば何 文字列で、 'は、len'という変数に、言う 早い段階で、プログラム内の、 あなたも、あなたの文字列の一番最初の文字を格納する前に？ 次に、すべてのあなたは、文字列の長さを見つけるために今しなければならないと思います 変数の値が何であるかを確認しています。 あなたは、まったく文字列自体を見なければならないでしょう とlenのように変数の値にアクセスすると考えられている 漸近的に一定時間操作、 またはO（1）。 これはなぜですか？まあ、漸近的複雑性が何を意味するのかを覚えています。 サイズなどの実行時の変更はどのように あなたの入力の成長？ 

あなたがより大きな文字列の文字数を取得しようとしたと言う。 まあ、それは、あなたが文字列を作るどのように大きな問題にならないだろう でも百万文字の長、 すべてのあなたは、このアプローチには、文字列の長さを見つけるためにしなければならないでしょう 、変数lenの値を読み出すことである そのあなたが既に作った。 入力の長さ、つまり、あなたが見つけようとしている文字列の長さ、 あなたのプログラムの実行速度は全く影響しません。 あなたのプログラムのこの部分は、1文字の文字列でも同じように速く走るでしょう 千文字の文字列、 そしてこのプログラムは一定の時間で実行されていると呼ばれる理由だ 入力サイズに関して。 

もちろん、欠点があります。 お使いのコンピュータ上で余分なメモリ空間を過ごす 変数を格納 それはあなたをとり、余分な時間 変数の実際の記憶を行うには、 しかしポイントはまだ立っている、 あなたの文字列があったかを調べること すべてでは文字列の長さに依存しません。 だから、それはO（1）または一定の時間で実行されます。 これは確かに意味する必要はありません あなたのコードは、1ステップで実行されること しかし、どんなに多くのステップがあり、 それは、入力の大きさに変更されない場合、 それはまだ私達はO（1）のように表すかを漸近的に定数です。 

あなたはおそらく想像できるように、 でアルゴリズムを測定するための多くの異なった大きなOランタイムがあります。 O（n）の²のアルゴリズムはO（n）のアルゴリズムより漸近的に遅くなります。 つまり、要素の数（n）が大きくなるにつれて、ある 最終的にはO（n）²のアルゴリズムはもっと時間がかかるだろう O（n）のアルゴリズムは、実行するよりも。 これはO（n）のアルゴリズムは常に高速に実行というわけではありません O（n）の²のアルゴリズムよりも、同じ環境で、 同じハードウェア上。 たぶん、小さな入力サイズの、  O（n）の²のアルゴリズムは実際に速く、うまくいくかもしれない しかし、最終的には、入力サイズが増加するにつれて、 無限大に向かって、O（n）で²アルゴリズムのランタイム 最終的にはO（n）アルゴリズムの実行時間を上回るでしょう。 ただの二次数学関数のように  最終的には、任意の線形関数を追い越すだろう 線形関数は、から始まりどのくらい頭の開始は関係ありません。 あなたは、大量のデータで作業している場合は、 （n）はOで実行するアルゴリズム²の時間は本当に、あなたのプログラムを遅くしてしまうことも しかし、小さな入力サイズの、 あなたはおそらく気付きさえしないでしょう。 

別の漸近的な複雑さがあり、 対数時間、O（log n）と。 迅速にこれを実行するアルゴリズムの例 、古典的な二分探索アルゴリズムである 要素のすでにソートされたリスト内の要素を見つけるため。 

あなたは、二分探索が何をするかわからない場合 私は本当にすぐにあなたのためにそれを説明しましょう​​。 Let 'sは、あなたが3番を探していると言う 整数のこの配列に保存します。 これは、配列の中央の要素を見 と "に等しい、またはこれよりも少ない、私はより大きくしたい要素ですか"と聞いた。 それは素晴らしい、次に等しいましょう。あなたは、その要素を見つけて、あなたは完了です。 それは大きいです場合は、要素を知っている 、アレイの右側になければならない そしてあなただけの、将来的にそれを見てすることができます それは小さいのならば、あなたはそれが左側になるように持って知っている。 このプロセスは、より小さいサイズの配列を用いて繰り返される 正しい要素が見つかるまで。 

この強力なアルゴリズムでは、各操作で半分に配列のサイズをカットします。 だから、サイズ8のソートされた配列内の要素を検索するには、 （₂8 log）が最大で、 これらの操作または3であり、 中央の要素をチェックして、その半分に配列を切断するが、必要になります サイズ16の配列は、（₂16を記録）かかるのに対し、 または4の操作。 それが唯一の倍サイズの配列の場合は1以上の動作です。 配列のサイズを2倍に このコードの唯一の1チャンクでランタイムを向上させます。 繰り返しになりますが、分割してから、リストの途中の要素をチェックします。 だから、それは、対数時間で動作するように言われています O（log n）で。 しかし、あなたが言う、待つ これは、リストにあなたが探している要素がどこにあるかには依存しません？ あなたが見て最初の要素は右に1であることを起こる場合は？ そして、それは、1動作のみを取り リストであるどんなに大きくはありません。 

コンピュータ科学者は、以上の単語を持っている理由まあ、それはだ ベストケースを反映するための漸近的な複雑さ そして最悪の場合のアルゴリズムの性能。 より正確には、上限と下限 ランタイム上で。 二分探索のための最良のケースでは、我々の要素である 右が真ん中に、 とは、一定の時間でそれを得る 配列の残りの部分がどのくらいの大きさは関係ありません。 このために使用される記号はΩです。 だから、このアルゴリズムはΩ（1）で実行するように言われています。 最良のケースでは、それは、すぐに要素を見つける 配列がどのようにビッグに関係なく、 しかし、最悪の場合には、 それは（log n）のスプリット·チェックを実行する必要があります 配列の適切な要素を見つけることができます。 最悪の場合の上限は、あなたが既に知っていることは大きな "○"と呼ばれています。 だから、それはO（log n）であるが、Ω（1）です。 

線形探索は、対照的に、 あなたは、配列のすべての要素を歩くた あなたが欲しいものを見つけるために、 Ωは、（1）最高の状態でです。 繰り返しになりますが、あなたがしたい最初の要素。 だから、それは配列がどのように大きな問題ではありません。 最悪のケースでは、配列の最後の要素です。 だから、あなたは、それを見つけるために、アレイ内のすべてのn個の要素を介して歩かなければならない あなたは3を探していた場合などが挙げられる。 だから、それはO（n）時間で実行され それは、配列内の要素数に比例だから。 

使用されるもうひとつのシンボルは、Θです。 これは最高と最悪の例のアルゴリズムを記述するために使用できる 同じです。 これは、我々は以前の話を文字列長のアルゴリズムの場合である。 我々の前にそれを変数に格納する場合です 我々は、文字列を格納し、後で定数時間でアクセスします。 何があっても数 我々はその変数に格納している、我々はそれを見なければならないでしょう。 最良のケースでは、我々はそれを見て と文字列の長さを見つける。 だからΩ（1）またはベスト·ケースの時定数。 最悪のケースは、ある 我々はそれを見て、文字列の長さを見つける。 だから、O（1）または最悪の場合には一定の時間。 だから、最良のケースと最悪のケース以来、同じです これはΘ（1）時間で実行するように言うことができる。 

要約すると、我々はコード効率に関する理由に良い方法を持っている 彼らが実行するのに要する実世界の時間については何も知らなくても、 外部要因の多くが影響を受けている、 異なるハードウェア、ソフトウェアを含む またはコードの仕様。 また、それは、私たちは何が起こるかについてよく推論することができます 入力時のサイズが大きくなります。 

あなたはO（n）²のアルゴリズムで実行している場合 または悪いことに、O（2ⁿ）アルゴリズム、 最も急成長しているタイプのいずれか、 あなたは本当に減速に気づくことから始めましょう あなたは、より大量のデータを使用した作業を開始するとき。 

それは漸近複雑だ。ありがとうございます。