Was ist die O-Zeit bei der Bestimmung, ob ein Wert in einem sortierten Array ist?

Question

Ich habe ein sortiertes Array von 5000 Zahlen. Wie schnell kann ich feststellen, ob eine Zufallszahl Mitglied des Arrays ist? Eine Antwort im Allgemeinen, C und Ruby wäre schön.

Die Array-Werte sind von der Form

c * c + 1

wobei c beliebige ganze Zahl von 1 bis 5000 sein kann.

Zum Beispiel:

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

Answer 1

Binäre Suche, wie andere schon erwähnt haben, ist O (log 2 N) und kann entweder rekursiv codiert werden:

   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
   }

oder iterativ:

   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
   }

Wenn Sie jedoch für die schnellstmögliche Art und Weise suchen, können Sie eine Nachschlagetabelle basierend auf der sqrt(N-1) Ihrer Zahlen einrichten. Mit nur 5.000 Wörter des Speichers können Sie erreichen O (1) Lookups auf diese Weise.

Erklärung:

Da alle Zahlen der Form N sind ^ 2 + 1 für eine ganze Zahl N 1 bis N, können Sie eine Tabelle von N Elementen erstellen. Das Element wird an der Position angeben, wenn i i ^ 2 + 1 im Array ist oder nicht. Es dauert O (N) zu bauen, und N Worte des Raumes Die Tabelle kann mit einem einfachen Array der Länge N. implementiert werden. Aber sobald Sie die Tabelle haben, werden alle Lookups sind O (1).

Beispiel:

Hier ist Beispielcode in Python, die wie Pseudo-Code liest, wie immer: -)

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)

Der Aufbau der Tabelle nimmt O (N) höchstens und Lookups sind O (1).

Answer 2

log (n) für binäre Suche auf c

Answer 3

Ich würde sagen, es ist O (konst)! :)

eine Zufallszahl r gegeben, es ist trivial zu überprüfen, ob es sich um eine Zahl, die in der Form dargestellt werden könnte (n * n + 1). Genau prüfen, ob die sqrt (r-1) eine ganze Zahl ist oder nicht!

(Na ja, könnte es ein wenig komplizierter als das sein, da Ihre Programmiersprache einige Komplexität in den Umgang mit ganzen Zahlen vs Gleitkommazahlen vorstellen können, aber trotzdem: Sie brauchen nicht die ganze Array suchen: nur prüfen, ob die Zahl ist in dieser besonderen Form.)

Answer 4

Technisch gesehen ist der Komplexität eines Elements in einer festen Größe Array zu finden, ist konstant, da log ₂ 5000 wird sich nicht ändern.

Answer 5

Binäre Suche ist O (log n)

WikiPedia

Answer 6

O (log n), wenn das Array n Elemente besitzt

Answer 7

Sie hierfür auf das erweitern: es ist lg n Tests, das heißt log ₂ n. Das macht es O ( log n) . Warum? weil jeder Versuch einer Binärsuche teilt das Array in der Mitte; so nimmt es lg n Versuchen.

Answer 8

eine binäre Suche verwenden, es ist Log (N) Suchzeit.

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

Answer 9

In Perl:

I würde die Werte in einen statischen Hash laden und dann wäre es, O (1).

Build des Lookup-Hash

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

Lookup-Syntax

($ lookup_hash {$ lookup_value}) && print "Fand es in O (1) - keine Schleife hier \ n";