Big-O περιγράφει πώς ο χρόνος εκτέλεσης ή η μνήμη ενός αλγορίθμου μεγαλώνει καθώς το μέγεθος εισόδου n μεγαλώνει. Καταγράφει τη χειρότερη περίπτωση ασυμπτωτική συμπεριφορά, αγνοώντας σταθερές και όρους χαμηλότερης τάξης.
Μας ενδιαφέρει ο ρυθμός ανάπτυξης, όχι ο ακριβής αριθμός βημάτων. O(2n + 5) είναι απλώς O(n) επειδή καθώς το n μεγαλώνει, οι σταθερές και οι μικρότεροι όροι σταματούν να έχουν σημασία.
| Big-O | Όνομα | Παράδειγμα |
|---|---|---|
| O(1) | σταθερή | αναζήτηση ευρετηρίου πίνακα |
| O(log n) | λογαριθμική | δυαδική αναζήτηση |
| O(n) | γραμμική | σάρωση μιας λίστας |
| O(n log n) | γραμμικολογαριθμική | ταξινόμηση συγχώνευσης |
| O(n²) | τετραγωνική | ένθετοι βρόχοι |
| O(2ⁿ) | εκθετική | αφελής υποσύνολα |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Το Big-O κρύβει σταθερές: ένας αλγόριθμος O(n) με μια τεράστια σταθερά μπορεί να χάσει από O(n log n) σε μικρές εισόδους. Επίσης παρακολουθήστε την πολυπλοκότητα του χώρου, όχι μόνο του χρόνου.
Το Big-O σας επιτρέπει να συγκρίνετε αλγορίθμους χωρίς να τους εκτελέσετε ή να ανησυχείτε για το υλικό.
Προβλέπει ποιες λύσεις επιζούν όταν οι είσοδοι μεγαλώνουν από εκατοντάδες σε εκατομμύρια — η διαφορά μεταξύ ενός χαρακτηριστικού που κλιμακώνεται και ενός που λήγει.
Είναι το λεξιλόγιο που κάθε μηχανικός χρησιμοποιεί για να συλλογιστεί για τη απόδοση.