порядок сложности алгоритма в нотации 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

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

Answer 3

Сложность алгоритма линейная.

Поиск максимума линейный. Установка битов является линейной.

Однако алгоритм также неверен, , если только ваши целые числа не могут быть положительными.

У этого также есть проблема с большими целыми числами - вы действительно хотите выделить MAX_INT/8 байт памяти?

Название, кстати, заставляет меня съеживаться. IsXYZ() всегда должен возвращать bool.

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

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

Answer 4

O(n) на a.length

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), вероятно, возможно только для конечной/малой области целых чисел. Все думают о bucketsort. Подход Hashmap в основном не O (n), а O (n^2), поскольку вставка худшего случая в хэшмап есть O (n) и NOT constant.

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

Answer 7

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