Senior
Ποια είναι η πολυπλοκότητα του αλγορίθμου δυαδικής αναζήτησης O;
sobes.tech AI
Απάντηση από AI
Η πολυπλοκότητα του αλγορίθμου δυαδικής αναζήτησης είναι O(log n).
Εξήγηση:
- Η δυαδική αναζήτηση λειτουργεί σε έναν ταξινομημένο πίνακα, διαιρώντας κάθε φορά την περιοχή αναζήτησης στη μέση.
- Σε κάθε βήμα, ο αριθμός των στοιχείων που εξετάζονται μειώνεται στο μισό.
- Επομένως, ο αριθμός των βημάτων είναι ανάλογος του λογαρίθμου του μεγέθους του πίνακα.
Παράδειγμα: αν ο πίνακας έχει 1.000.000 στοιχεία, η δυαδική αναζήτηση θα πραγματοποιήσει περίπου 20 συγκρίσεις (log₂(1.000.000) ≈ 20).