Επεξήγηση αλγόριθμου Jump Jump

Μετάβαση στην αναζήτηση

Μια αναζήτηση άλματος εντοπίζει ένα στοιχείο σε μια ταξινομημένη σειρά με άλματα k itens και, στη συνέχεια, επαληθεύστε εάν το αντικείμενο που θέλετε βρίσκεται μεταξύ του προηγούμενου άλματος και του τρέχοντος άλματος.

Χειρότερη περίπτωση πολυπλοκότητας

O (√Ν)

Πως δουλεύει

  1. Ορίστε την τιμή του k, ο αριθμός άλματος: Το βέλτιστο μέγεθος άλματος είναι √N όπου το Ν είναι το μήκος του πίνακα
  2. Μεταβείτε στον πίνακα k-by-k αναζητώντας από την συνθήκη Array[i] < valueWanted < Array[i+k]
  3. Κάντε μια γραμμική αναζήτηση μεταξύ Array[i]καιArray[i + k]
Αναζήτηση άλματος 1

Κώδικας

Για να δείτε παραδείγματα εφαρμογής κώδικα αυτής της μεθόδου, μεταβείτε στον παρακάτω σύνδεσμο:

Jump Search - OpenGenus / cosmos

Πιστώσεις

Η εικόνα του πίνακα της λογικής