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循环，一个是长度a.Length，一个是长度（如果我正确理解代码的话）a.Max() + 1。所以你的算法复杂度是O(a.Length + a.Max())

于 2009-10-29T11:56:49.903 回答
4

算法的复杂度是线性的。

找到最大值是线性的。设置位是线性的。

但是该算法也是错误的，除非您的整数可以被假定为正数。

大整数也有问题——你真的要分配 MAX_INT/8 字节的内存吗？

顺便说一句，这个名字让我畏缩。IsXYZ() 应该总是返回一个布尔值。

我会说，再试一次。

更正- pavpanchekha 有正确的答案。

于 2009-10-29T11:57:42.033 回答
1

O(n) 可能仅适用于有限/小整数域。每个人都会想到桶排序。Hashmap 方法基本上不是 O(n) 而是 O(n^2)，因为最坏情况下插入 hashmap 是 O(n) 并且不是恒定的。

如何在 O(n log(n)) 中对列表进行排序，然后通过它并打印重复值。这导致 O(n log(n)) 这可能是问题的真正复杂性。

于 2009-10-29T13:35:22.833 回答
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 回答
0

您有两个循环，每个循环都基于 n 的大小。我同意鲸鱼的观点，但这应该会给你一个好的开始。

于 2009-10-29T11:56:57.767 回答
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 回答