Qual è il tempo O nel determinare se un valore si trova in un array ordinato?

Question

Ho un array ordinato di 5000 numeri interi. Quanto velocemente posso dire se un numero intero casuale è un membro dell'array? Una risposta in generale, C e Ruby sarebbero carini.

I valori dell'array sono nella forma

c * c + 1

dove c può essere qualsiasi numero intero compreso tra 1 e 5000.

Ad esempio:

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

Answer 1

La ricerca binaria, come altri hanno già detto, è O (log2N) e può essere codificata in modo ricorsivo:

   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
   }

o iterativamente:

   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
   }

Tuttavia, se stai cercando il modo più veloce possibile, puoi impostare una tabella di ricerca basata sul sqrt (N-1) dei tuoi numeri. Con solo 5.000 parole di memoria puoi ottenere ricerche O (1) in questo modo.

Spiegazione:

Poiché tutti i tuoi numeri hanno la forma N ^ 2 + 1 per un numero intero N da 1 a N, puoi creare una tabella di N elementi. L'elemento nella posizione i specificherà se i ^ 2 + 1 è nel tuo array o no. La tabella può essere implementata con un semplice array di lunghezza N. Ci vorrà O (N) per costruire e N parole di spazio. Ma una volta che hai il tavolo, tutte le ricerche sono O (1).

Esempio:

Ecco un codice di esempio in Python, che si legge come pseudocodice, come sempre :-)

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 creazione della tabella occupa al massimo O (N) e le ricerche sono O (1).

Answer 2

log (n) per la ricerca binaria su c

Answer 3

Direi che è O (const)! :)

Dato un numero casuale r, è banale verificare se si tratta di un numero che potrebbe essere rappresentato nel modulo (n * n + 1). Basta controllare se sqrt (r-1) è un numero intero o no!

(Beh, potrebbe essere un po 'più complicato di così dato che il tuo linguaggio di programmazione può introdurre una certa complessità nella gestione di numeri interi o numeri in virgola mobile, ma comunque: non è necessario cercare l'array: controlla se il il numero è in questa forma particolare.)

Answer 4

Tecnicamente, la complessità di trovare un elemento in un array di dimensioni fisse è costante, poiché il log ₂ 5000 non cambierà.

Answer 5

La ricerca binaria è O (log n)

WikiPedia

Answer 6

O (registro n) se l'array ha n elementi

Answer 7

Solo per espanderlo: sono lg n test, ovvero log ₂ n. Questo lo rende O ( registro n) . Perché? perché ogni prova di una ricerca binaria divide la matrice a metà; quindi ci vogliono lg n prove.

Answer 8

Utilizzando una ricerca binaria, è tempo di ricerca Log (N).

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

Answer 9

In Perl:

Vorrei caricare i valori in un hash statico e quindi sarebbe O (1).

Crea l'hash di ricerca

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

Sintassi di ricerca

($ lookup_hash {$ lookup_value}) & amp; & amp; print " Trovato in O (1) - nessun loop qui \ n " ;;