算法的复杂度（以 O 表示法表示）

Question

谁能告诉我以下算法的复杂度顺序？该算法执行以下操作：

给定一个具有重复数字的未排序整数数组，编写最有效的代码来打印数组中的唯一值。

我也想知道 此实现的硬件使用情况有哪些优点和缺点

 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();
    }

Answer 1

您有两个 for 循环，一个长度为 a.Length ，另一个长度为（如果我正确理解代码）a.Max() + 1代码>.所以你的算法复杂度是O(a.Length + a.Max())

Answer 2

算法的复杂度呈线性。

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

然而算法也是错误的，
除非你的整数可以被假设为正数。

它也有一个大整数的问题 - 你真的吗
想要分配 MAX_INT/8 字节的内存？

顺便说一句，这个名字让我感到畏缩。 IsXYZ() 应始终返回布尔值。

我想说，再试一次。

更正 - pavpanchekha 有正确答案。

Answer 3

O(n) 可能仅适用于有限/小整数域。每个人都会想到桶排序。哈希映射方法基本上不是 O(n) 而是 O(n^2)，因为最坏情况下插入哈希映射的时间复杂度为 O(n) 并且不是常数。

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

Answer 4

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

Answer 5

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

Answer 6

a.length 上的 O(n)

Answer 7

你的算法的复杂度是 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]);
    }

}