Αν έχουμε μια λίστα $n$ αριθμών $x_1, \ldots, x_n$ που είναι αποθηκευμένη σε μορφή διπλά συνδεδεμένης λίστας που είναι όμως αποθηκευμένη σε ένα array ώστε να μπορούμε σε σταθερό χρόνο να πάρουμε ένα τυχαίο (ομοιόμορφα) στοιχείο της λίστας τότε με τον παρακάτω τρόπο μπορούμε να αναζητήσουμε τον αριθμό $x$ στη λίστα σε μέσο χρόνο $O(\sqrt{n})$. Σημειωτέον ότι αν επιμείνουμε σε ντετερμινιστικό αλγόριθμο εύκολα μπορεί κανείς να δείξει ότι απαιτείται χρόνος τουλάχιστον $n$, άρα χρησιμοποιώντας πιθανοθεωρητικό αλγόριθμο έχουμε σαφή βελτίωση, τουλάχιστον όσον αφορά το μέσο χρόνο αναζήτησης.
Ας είναι $k$ το ακέραιο μέρος του $\sqrt{n}$. Επιλέγουμε τυχαία και ομοιόμορφα $k$ στοιχεία της λίστας, έστω τα υπ' αριθμόν $i_1, \ldots, i_k$. Για να βρούμε το $x$ βρίσκουμε πρώτα τους δύο δείκτες $a, b \in \{i_1, \ldots, i_k\}$ που είναι τέτοιοι ώστε (α) το $x$ να είναι ανάμεσα στα $x_a$ και $x_b$ και (β) να μην υπάρχει άλλο από τα $x_{i_1}, \ldots, x_{i_k}$ που να είναι ανάμεσα στα $x_a$ και $x_b$. Με άλλα λόγια το $x$ βρίσκεται ανάμεσα στα $x_a$ και $x_b$ στην λίστα μας. Ξεκινάμε λοιπόν από το στοιχείο $a$ της λίστας μας και προχωράμε κάθε φορά στο επόμενο στοιχείο έως ότου βρούμε τη θέση του $x$.
Το κρίσιμο σημείο εδώ είναι ότι τα στοιχεία $x_a$ και $x_b$ της λίστας μας απέχουν κατά μέσο όρο $O(\sqrt{n})$, άρα ο χρόνος αναζήτησης είναι κατά μέσο όρο $Ο(\sqrt{n})$.
Δείτε λεπτομέρειες εδώ, σελ. 2.
Υλοποίηση φαίνεται παρακάτω.
import numpy as np
n=100
x = np.random.uniform(0, 1, n) # αριθμοί που θα είναι στη λίστα
y = np.sort(x) # σε αύξουσα σειρά
ide=n*[0] # η ταυτοτική απεικόνιση {0, ..., n-1} -> {0, ..., n-1}
for i in range(n): ide[i] = i
# μια τυχαία μετάθεση {0, ..., n-1} -> {0, ..., n-1}
# σε αυτές τις θέσεις θα μεταφερθούν τα στοιχεία της λίστας ide
new = np.random.permutation(ide)
yy = n*[0]
for i in range(n-1):
yy[new[i]] = y[i]
# Η λίστα yy περιέχει τώρα τους τυχαίους μας αριθμούς
# με τον τρόπο που τη φτιάξαμε μπορούμε εύκολα να βρούμε πού είναι ο επόμενος
# αριθμός από τη θέση i και πού ο προηγούμενος
# αυτοί αποθηκεύονται στις λίστες nex και prev.
# Όταν δεν υπάρχει προηγούμενος ή επόμενος το βάζουμε None
nex = n*[0]; prev = n*[0]
for i in range(n-1):
nex[new[i]] = new[i+1]
# Π.χ., το στοιχείο y[n-1] (το μεγαλύτερο) έχει πάει τώρα
# στη θέση yy[new[n-1]], άρα το επόμενο της θέσης new[n-1] είναι None.
nex[new[n-1]] = None
for i in range(1,n):
prev[new[i]] = new[i-1]
prev[new[0]] = None
k = int(np.sqrt(n)) # k είναι η ρίζα του n στρογγυλοποιημένη προς τα κάτω
loc = np.random.randint(0, n, k) # παίρνουμε k τυχαίες θέσεις από το {0,..,n-1}
x = 0.32 # ο αριθμός που αναζητούμε στη λίστα yy
# m και M θα είναι οι θέσεις στον πίνακα yy όπου βρίσκονται αποθηκευμένοι
# ο μικρότερος και ο μεγαλύτερος αριθμός από τους αριθμούς yy[loc[i]]
# για i=0,...,k-1
m = M = loc[0] # αρχικές τιμές για τα m, M
# οι τρέχουσες τιμές για το ελάχιστο και το μέγιστο από τα yy[loc[i]]
# που έχουμε δει μέχρι στιγμής
minv = maxv = yy[loc[0]]
for i in range(1,k):
if minv > yy[loc[i]]:
minv = yy[loc[i]]; m = loc[i]
if maxv < yy[loc[i]]:
maxv = yy[loc[i]]; M = loc[i]
# yy[loc[m]], yy[loc[M]] είναι τα ελάχιστο και μέγιστο από αυτά που διαλέξαμε
# Οι θέσεις A, B θα είναι οι θέσεις στον πίνακα yy όπου βρίσκονται αποθηκευμένα
# οι δύο αριθμοί από τους yy[loc[i]] που εγκλωβίζουν το x που ψάχνουμε
foundAB = False # το κάνουμε true όταν έχουμε βρει τα A, B
if x < minv: # x από την αρχή έως το πρώτο
A = None
B = loc[0]
foundAB = True
if x > maxv: # x πέρα από το τελευταίο
A = loc[k-1]
B = None
foundAB = True
if not foundAB: # χ όχι στα άκρα
maxlocbeforex = m; maxvalbeforex = yy[maxlocbeforex]
minlocafterx = M; minvalafterx = yy[minlocafterx]
for i in range(k):
if yy[loc[i]] < x and yy[loc[i]] > maxvalbeforex:
maxlocbeforex = loc[i]
maxvalbeforex = yy[loc[i]]
if yy[loc[i]] >= x and yy[loc[i]] < minvalafterx:
minlocafterx = loc[i]
minvalafterx = yy[loc[i]]
# το x βρίσκεται ανάμεσα στις θέσεις maxlocbeforex και minlocafterx της λίστας yy
A = maxlocbeforex
B = minlocafterx
if A != None and B != None: # το x δεν είναι στα δύο διαστήματα των άκρων
i = A # Ξεκινάμε από τη θέση A και ψάχνουμε το x έως τη θέση B
while(True):
if i == B: # φτάσαμε στο τέλος, αναφέρουμε αυτό ως θέση του x
xloc = B
break
if yy[i] < x:
i = nex[i] # προχωράμε στο επόμενο στοιχείο
continue
xloc = i # μόλις περάσαμε το x και αναφέρουμε αυτό ως θέση
break
elif A == None: # είμαστε στο αριστερό άκρο
i = B # ψάχνουμε από τα δεξιά προς τα αριστερά
while(True):
if prev[i]==None: # φτάσαμε στην αρχή -- αναφέρουμε αυτήν ως θέση του x
xloc = i
xloc = "L" # L σημαίνει ότι το x είναι μικρότερο από το ελάχιστο
break
if yy[prev[i]] < x:
xloc = i
break
i = prev[i]
else: # είμαστε στο δεξί άκρο
i = A
while(True):
if nex[i] == None:
xloc = i
xloc = "R" # R σημαίνει ότι το x είναι μεγαλύτερο από το μέγιστο
break
if yy[i] < x:
i = nex[i]
continue
xloc = i
break
print(A, B, xloc)