Quel est le temps O pour déterminer si une valeur est dans un tableau trié?

Question

J'ai un tableau trié de 5000 entiers. À quelle vitesse puis-je savoir si un entier aléatoire est un membre du tableau? Une réponse en général, C et Ruby serait bien.

Les valeurs du tableau sont de la forme

c * c + 1

où c peut être un entier compris entre 1 et 5000.

Par exemple:

[2, 5, 10, 17, 26, 37, 50 ...]

Answer 1

Comme d'autres l'ont déjà mentionné, la recherche binaire est O (log2N) et peut être codée de manière récursive:

   BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = (low + high) / 2
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
   }

ou itérativement:

   BinarySearch(A[0..N-1], value) {
       low = 0
       high = N - 1
       while (low <= high) {
           mid = (low + high) / 2
           if (A[mid] > value)
               high = mid - 1
           else if (A[mid] < value)
               low = mid + 1
           else
               return mid // found
       }
       return -1 // not found
   }

Toutefois, si vous recherchez le moyen le plus rapide possible, vous pouvez configurer une table de consultation basée sur le sqrt (N-1) de vos numéros. Avec seulement 5 000 mots de mémoire, vous pouvez réaliser des recherches O (1) de cette façon.

Explication:

Puisque tous vos nombres sont de la forme N ^ 2 + 1 pour un entier N compris entre 1 et N, vous pouvez créer un tableau de N éléments. L'élément à la position i spécifiera si i ^ 2 + 1 est dans votre tableau ou non. La table peut être implémentée avec un simple tableau de longueur N. Il faudra O (N) pour construire et N mots d’espace. Mais une fois que vous avez la table, toutes les recherches sont O (1).

Exemple:

Voici un exemple de code en Python, qui se lit comme un pseudo-code, comme toujours: -)

import math

N = 5000
ar = [17, 26, 37, 50, 10001, 40001]

lookup_table = [0] * N

for val in ar:
    idx = int(math.sqrt(val - 1))
    lookup_table[idx] = 1

def val_exists(val):
    return lookup_table[int(math.sqrt(val - 1))] == 1

print val_exists(37)
print val_exists(65)
print val_exists(40001)
print val_exists(90001)

La construction de la table prend au plus O (N) et les recherches sont O (1).

Answer 2

log (n) pour la recherche binaire sur c

Answer 3

Je dirais que c'est O (const)! :)

Etant donné un nombre aléatoire r, il est facile de vérifier s'il s'agit d'un nombre pouvant être représenté sous la forme (n * n + 1). Il suffit de vérifier si le sqrt (r-1) est un entier ou non!

(Eh bien, cela pourrait être un peu plus compliqué que cela, car votre langage de programmation peut introduire une certaine complexité dans le traitement des nombres entiers par rapport aux nombres à virgule flottante, mais néanmoins: vous n'avez pas besoin de chercher dans le tableau: vérifiez simplement si le numéro est sous cette forme particulière.)

Answer 4

Techniquement, la complexité de la recherche d'un élément dans un tableau de taille fixe est constante, car log ₂ 5000 ne va pas changer.

Answer 5

La recherche binaire est O (log n)

WikiPedia

Answer 6

O (log n) si le tableau contient n éléments

Answer 7

Pour en savoir plus: il s'agit de lg n tests, c’est-à-dire journal ₂ n. Cela rend O ( journal n) . Pourquoi? parce que chaque essai d'une recherche binaire divise le tableau en deux; il faut donc lg n essais.

Answer 8

À l’aide d’une recherche binaire, c’est la durée de la recherche dans le journal (N).

bool ContainsBinarySearch(int[] array, int value) {
  return Array.BinarySearch(arrray, value) >= 0;
}

Answer 9

En Perl:

Je chargerais les valeurs dans un hachage statique, puis ce serait O (1).

Construire le hachage de recherche

lookup_hash {$ _} = 1 pour chaque (@original_array);

Syntaxe de recherche

($ lookup_hash {$ lookup_value}) & amp; & amp; print " trouvé dans O (1) - pas de boucle ici \ n ";