アルゴリズムの時間複雑

Question

可能性の重複を計算する：私は今、4年間のプログラミングをやってきた
Plain English explanation of Big O

が、私は何時間複雑さに注目を支払ったことはありませんが密接です。私は明日のインタビューを持っていると私は彼らが私にそれに関する質問をしてくれることを知っている。誰か私は例を簡単に言えば時間の複雑さを理解することができますか？コードを見てどのようにその複雑さがO（n） log n）O（n）など？

Answer 1

ここでは複雑なトピックに移行しています;-)大学では、O記法の背後にある理論に長年を費やしています。

ループを含まないアルゴリズム（たとえば、コンソールへのテキストの書き込み、ユーザーからの入力の取得、コンソールへの結果の取得）は、O（1）、問題ありません何ステップか。アルゴリズムを実行するのにかかる時間は一定です（これはO（1）の意味です）。これはデータに依存しないためです。

アイテムのリストを1つずつ反復するアルゴリズムは、複雑さO（n）（nはリスト内のアイテムの数）を持ちます。連続するループで2回繰り返すと、アルゴリズムを実行する時間は依然としてアイテムの数だけに依存するため、O（n）のままです。

内部ループが何らかの形で外部ループに依存する2つのネストされたループを持つアルゴリズムは、（ネストされたループの数に応じて）O（n^x）クラスにあります。

ソートされたフィールドのバイナリ検索アルゴリズムは、O（log（n））クラスにあり、アイテムの数はすべてのステップで半減します。

上記はあまり正確ではないかもしれませんが、これが私が重要な値のいくつかを覚えようとした方法です。コードを見るだけで、複雑さを判断することは必ずしも容易ではありません。

さらに詳しい（より正確な）読み方については、David Heffernanのコメントは彼のコメントにリンクされているようです。ここ

Answer 2

は、一般的提案である：

が単一の反復は、反復変数が線形にインクリメントされている場合、それは、例えば、O（N） です反復変数は幾何学的に増加される場合

for(i=0;i<n;i++) //O(n) 
for(i=0;i<n;i = i + 4) // still O(n) 

、それはですO（ログn）の実装は、彼ら多分、ループを使用する必要はありません、ということ

例えば

for(i=1;i<n;i = i * 2) //O(log n) 

注意再帰を使用して実装されます。

複雑なO（n）ともう1つのO（logn）を入れ子にしたループがある場合、全体の複雑さはO（nlogn）です。

例えば

for(i=0;i<n;i++) // O(n) 
for(j=1;j<n;j=j*3) // O(log n) 
//Overall O(nlogn) 

これは指だけクロスガイドラインです。一般的には、複雑さを導き出すには良いコンセプトが必要です。そういうわけで、分析能力とコンセプトをテストするよう求められます。