1

何

整数配列に重複する数値があるかどうかを見つけて削除する小さなコードを書きました。これには List を使用しました。

コード

    static int[] RemoveDuplicate(int[] input)
    {
       List<int> correctedList = new List<int>();

       for(int i = 0; i < input.Length; i++)
       {
           if (!correctedList.Contains(input[i]))
           {
               correctedList.Add(input[i]);
           }
           else
           {
               //skip
           }
       }

       return correctedList.ToArray();

    }

私の難しさ

書かれたこの小さなコードの時間計算量を見つける方法と、可能であればそれを最適化する方法を知る必要があります。

私は何を試しましたか

私はアルゴリズムの時間と空間の複雑さを計算する方法についてインターネットでいくつか読んだことがあります.これについて何人かの専門家に相談してください。

以下は私が試したことです。

List modifiedList = new List(); --> これは 1 回実行されます

int i =0; -->これは1回実行されます

int i < input.Length --> これは N 回実行されます

i++ --> これは N 回実行されます

if (!correctedList.Contains(input[i])) --> これは N 回実行される可能性があります

修正されたList.Add(input[i]); --> これは N 回実行される可能性があります

したがって、操作の総数 = 1 + 1 + N + N + N + N = 4N+2

これは O(N) に等しいですか?

時間の複雑さを計算する私の方法は正しいですか？

少し早いですがお礼を

4

1 に答える 1

4

呼び出したすべての操作自体が O(1) の場合、O(N) になります。リストの [Contains] が O(1) になる可能性は低いです。一般に、配列の検索は O(N) です。これは、アルゴリズムが O(N^2) であることを意味します (これはそうだと思います)。

最適化のオプション: 1) できる最善の方法は O(N) ですが、これは、O(1) である contains 関数が必要であることを意味します。これは、ハッシュ テーブル (またはハッシュ セット) を使用して行うことができます。ハッシュ テーブルには、O(1) の挿入と削除があります。

2) ソートされた順序を維持する構造 (バランス ツリーなど) に挿入できます。挿入は O(log N) になり、ソリューションの全体的なパフォーマンスは O(N log N) になります。

3) おそらく最も一般的で最も単純なアルゴリズムは、配列 O(N log N) を並べ替えてから重複をスキャンすることです。

于 2012-06-17T17:01:04.143 に答える