порядок сложности алгоритма в обозначениях 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 () всегда должен возвращать bool.

Я бы сказал, попробуйте еще раз.

Исправление - у павпанчеха правильный ответ.

Answer 3

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 4

O (n) возможно только для конечной / маленькой области целых чисел. Все думают о ведре сортировки. Подход Hashmap в основном не O (n), а O (n ^ 2), поскольку в худшем случае вставка в hashmap является O (n) и НЕ является постоянной.

Как насчет сортировки списка в O (n log (n)), а затем прохождения по нему и распечатки дублирующихся значений. Это приводит к O (n log (n)), что, вероятно, является истинной сложностью проблемы.

Answer 5

Сложность вашего алгоритма 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]);
    }

}

Answer 6

O(n) вкл. a.length

Answer 7

У вас есть две петли, каждая на основе размера n. Я согласен с Китом, но это должно дать вам хорошее начало.