0

以下のアルゴリズムの複雑さの順序を教えてもらえますか? このアルゴリズムは、次のことを行います。

重複する数値を持つソートされていない整数の配列が与えられた場合、配列内の一意の値を出力する最も効率的なコードを記述します。

また、この実装のハードウェア使用のコンテキストでの長所と短所は何ですか

 private static void IsArrayDuplicated(int[] a)
    {
        int size = a.Length;
        BitArray b = new BitArray(a.Max()+1);
        for ( int i = 0; i < size; i++)
        {
            b.Set(a[i], true);
        }

        for (int i = 0; i < b.Count; i++)
        {
            if (b.Get(i))
            {

                System.Console.WriteLine(i.ToString());

            }
        }
        Console.ReadLine();
    }
4

7 に答える 7

5

for長さのループと長さのループの2 つがありますa.Length(コードを正しく理解していれば) a.Max() + 1。したがって、アルゴリズムの複雑さはO(a.Length + a.Max())

于 2009-10-29T11:56:49.903 に答える
4

線形アルゴリズムの複雑さ。

最大値の検出は線形です。ビットの設定は線形です。

ただし、整数が正であると想定できない限り、アルゴリズムも間違っています。

大きな整数にも問題があります。本当に MAX_INT/8 バイトのメモリを割り当てたいですか?

ところで、その名前は私をうんざりさせます。IsXYZ() は常に bool を返す必要があります。

もう一度やり直してください。

訂正- pavpanchekha に正解があります。

于 2009-10-29T11:57:42.033 に答える
1 
HashSet<int> mySet = new HashSet<int>( new int[] {-1, 0, -2, 2, 10, 2, 10});
foreach(var item in mySet) 
{
   console.WriteLine(item);
}
// HashSet guarantee unique values without exception
于 2010-11-11T18:12:34.433 に答える
1

O(n) は、おそらく整数の有限/小さなドメインでのみ可能です。誰もがバケットソートについて考えます。ハッシュマップへの最悪の場合の挿入は O(n) で定数ではないため、ハッシュマップ アプローチは基本的に O(n) ではなく O(n^2) です。

リストを O(n log(n)) でソートしてから、それを調べて重複した値を出力するのはどうですか。これは、おそらく問題の真の複雑さである O(n log(n)) になります。

于 2009-10-29T13:35:22.833 に答える
0

O(n)の上a.length

于 2009-10-29T12:09:45.430 に答える
0

アルゴリズムの複雑さは O(N) ですが、アルゴリズムが正しくありません。

  1. 数値が負の場合は機能しません
  2. 数が多い場合、メモリに問題が発生します

このアプローチを使用することをお勧めします。

private static void IsArrayDuplicated(int[] a) {
    int size = a.length;
    Set<Integer> b = new HashSet<Integer>();
    for (int i = 0; i < size; i++) {
        b.add(a[i]);
    }

    Integer[] T = b.toArray(new Integer[0]);

    for (int i = 0; i < T.length; i++) {
        System.out.println(T[i]);
    }

}
于 2009-10-29T13:22:14.513 に答える
0

それぞれ n のサイズに基づく 2 つのループがあります。私はwhaleyに同意しますが、それはあなたに良いスタートを与えるはずです.

于 2009-10-29T11:56:57.767 に答える