アルゴリズムのBig O解析 - ジョブインタビュー

Question

最近、私はインタビューの質問をして、配列を解析し、重複する数値を返すアルゴリズムを書いた。

私の強引なソリューションでした：

public static ArrayList getDuplicates (int[] input){ 
     ArrayList duplicates = new ArrayList(); 
     int marker = 0; 
     for (int i = marker + 1; (i < input.length) && (marker < input.length - 1); i++){ 
      if (input[marker] == input[i]){ 
       duplicates.add(input[marker]); 
       marker++; 
       continue; 
      } else { 
       if (i == input.length - 1){ 
        marker++; 
        i = marker; 
       } 
       continue; 
      } 
     } 
     return duplicates; 
    } 

は徹底的な分析がなければ、私はビッグOは、（ログ（N））のn *であるとの回答を与えました。

インタビュー後、もう一度チェックし、正解ではないことがわかりました。

混乱する部分は、アルゴリズムが繰り返されますが、n回ではなく、k = {1..n-1}のn-k回のすべてのサイクルです。これは、移動インデックスをリセット一部です：

   if (i == input.length - 1){ 
       marker++; 
       i = marker; 
      } 

は正しいビッグO機能を見つけるために、このアルゴリズムを解析するための最良の方法は何ですか？

Answer 1

私は分析これをだろう方法は、任意のパターンが出てくるかどうかを確認し、その後、エッジケースをプラグインすることです：

1. を使用すると、すべてのマッチの配列を持っている場合はどうなりますか？ この場合、毎回重複の最初の項目をヒットするため、O（N）です。
2. 重複はありません。 はその後、（N^2）

このことから、我々はあなたの最高の場合はO（N）と悪化していることがわかりますOので、あなたの、全体配列N^2/2倍をスキャンするには、O（Nです^ 2）また、平均的なケースもO（N^2）になると言います。

Nest for-loopsを使用した場合、N^2の動作ははるかに簡単になります。元のデータスキャン、重複スキャンのスキャンを実行します。

代わりに、あなたはOでコンテナに各項目を追加した場合は（1）能力（ハッシュテーブル）を追加し、あなたのアルゴリズムは非常に簡単になる：

1. foreachの項目入力配列、追加しようとする試みでハッシュテーブルへの値。
2. 値がすでにハッシュ内に存在する場合は、複製配列にプラグインします。
3. foreachスキャンを完了し、重複した配列を返します。