ordre de complexité de l'algorithme en notation O

Question

Quelqu'un peut-il me dire l'ordre de la complexité de l'algorithme ci-dessous? Cet algorithme doit faire ce qui suit:

Étant donné un tableau non trié d'entiers avec des nombres en double, écrivez le code le plus efficace pour imprimer des valeurs uniques dans le tableau.

Je voudrais aussi savoir Quels sont les avantages et les inconvénients dans le contexte de l'utilisation du matériel de cette implémentation

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

Vous avez deux for boucles, l'une de la longueur a.Length et une longueur (si je comprendre le code correctement) a.Max() + 1. Donc, votre complexité algorithmique est O(a.Length + a.Max())

Answer 2

Vous avez deux boucles, chacune basée sur la taille de n. Je suis d'accord avec Whaley, mais cela devrait vous donner un bon début.

Answer 3

La complexité de l'algorithme linéaire.

La recherche du maximum est linéaire. La définition des bits est linéaire.

Cependant, l'algorithme est également erroné, sauf si vos entiers peuvent être supposés positifs.

Il a également un problème avec les grands entiers - avez-vous vraiment voulez allouer MAX_INT/8 octets de mémoire? Le nom, btw, me fait grincer des dents. IsXYZ() devrait toujours retourner un booléen.

Je dirais, essayez à nouveau.

Correction - pavpanchekha a la bonne réponse.

Answer 4

O(n) sur a.length

Answer 5

complexité de votre algorithme est O (N), mais l'algorithme est incorrect.

1. Si les chiffres sont négatifs, il ne fonctionnera pas
2. Dans le cas d'un grand nombre, vous aurez des problèmes avec la mémoire

Je vous suggère d'utiliser cette approche:

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) est probablement seulement possible pour un domaine fini/petit d'entiers. Tout le monde pense à bucketsort. L'approche Hashmap n'est fondamentalement pas O (n) mais O (n^2) puisque l'insertion du pire cas dans une hashmap est O (n) et NON constante.

Que diriez-vous de trier la liste dans O (n log (n)) puis de le parcourir et d'imprimer les valeurs en double. Cela résulte en O (n log (n)) qui est probablement la vraie complexité du problème.

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