Εισαγωγή στη χρονική πολυπλοκότητα των αλγορίθμων

Στην επιστήμη των υπολογιστών, η ανάλυση των αλγορίθμων είναι ένα πολύ σημαντικό μέρος. Είναι σημαντικό να βρείτε τον πιο αποτελεσματικό αλγόριθμο για την επίλυση ενός προβλήματος. Είναι δυνατόν να υπάρχουν πολλοί αλγόριθμοι για την επίλυση ενός προβλήματος, αλλά η πρόκληση εδώ είναι να επιλέξετε τον πιο αποτελεσματικό.

Τώρα το θέμα είναι, πώς μπορούμε να αναγνωρίσουμε τον πιο αποτελεσματικό αλγόριθμο εάν έχουμε ένα σύνολο διαφορετικών αλγορίθμων; Εδώ, υπάρχει η έννοια της πολυπλοκότητας χώρου και χρόνου των αλγορίθμων. Η πολυπλοκότητα χώρου και χρόνου λειτουργεί ως κλίμακα μέτρησης αλγορίθμων. Συγκρίνουμε τους αλγόριθμους με βάση το χώρο τους (ποσότητα μνήμης) και την πολυπλοκότητα του χρόνου (αριθμός λειτουργιών).

Το συνολικό ποσό της μνήμης του υπολογιστή που χρησιμοποιείται από έναν αλγόριθμο όταν εκτελείται είναι η πολυπλοκότητα του εν λόγω αλγορίθμου. Δεν θα συζητήσουμε την πολυπλοκότητα του χώρου σε αυτό το άρθρο (για να κάνουμε αυτό το άρθρο λίγο μικρότερο).

Χρόνος πολυπλοκότητας

Έτσι, η πολυπλοκότητα του χρόνου είναι ο αριθμός των λειτουργιών που πραγματοποιεί ένας αλγόριθμος για την ολοκλήρωση της εργασίας του (λαμβάνοντας υπόψη ότι κάθε λειτουργία χρειάζεται τον ίδιο χρόνο). Ο αλγόριθμος που εκτελεί την εργασία με τον μικρότερο αριθμό λειτουργιών θεωρείται ο πιο αποτελεσματικός από την άποψη της πολυπλοκότητας του χρόνου. Ωστόσο, η πολυπλοκότητα χώρου και χρόνου επηρεάζεται επίσης από παράγοντες όπως το λειτουργικό σας σύστημα και το υλικό, αλλά δεν τους συμπεριλαμβάνουμε σε αυτήν τη συζήτηση.

Τώρα για να κατανοήσουμε την πολυπλοκότητα του χρόνου, θα πάρουμε ένα παράδειγμα στο οποίο θα συγκρίνουμε δύο διαφορετικούς αλγόριθμους που χρησιμοποιούνται για την επίλυση ενός συγκεκριμένου προβλήματος.

Το πρόβλημα είναι η αναζήτηση. Πρέπει να αναζητήσουμε ένα στοιχείο σε έναν πίνακα (σε αυτό το πρόβλημα, θα υποθέσουμε ότι ο πίνακας ταξινομείται σε αύξουσα σειρά). Για να λύσουμε αυτό το πρόβλημα έχουμε δύο αλγόριθμους:

1. Γραμμική αναζήτηση.

2. Δυαδική αναζήτηση.

Ας υποθέσουμε ότι ο πίνακας περιέχει δέκα στοιχεία και πρέπει να βρούμε τον αριθμό δέκα στον πίνακα.

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; const search_digit = 10;

Ο γραμμικός αλγόριθμος αναζήτησης θα συγκρίνει κάθε στοιχείο του πίνακα με το search_digit . Όταν εντοπίσει το search_digit στον πίνακα, θα επιστρέψει αληθινό .

Τώρα ας μετρήσουμε τον αριθμό των λειτουργιών που εκτελεί. Εδώ, η απάντηση είναι 10 (αφού συγκρίνει κάθε στοιχείο του πίνακα). Έτσι, η Γραμμική αναζήτηση χρησιμοποιεί δέκα λειτουργίες για να βρει το δεδομένο στοιχείο (αυτοί είναι ο μέγιστος αριθμός λειτουργιών για αυτόν τον πίνακα. Στην περίπτωση της Γραμμικής αναζήτησης, αυτό είναι επίσης γνωστό ως η χειρότερη περίπτωση ενός αλγορίθμου).

Σε γενικές γραμμές, η Γραμμική αναζήτηση θα λάβει n αριθμό λειτουργιών στη χειρότερη περίπτωση (όπου το n είναι το μέγεθος του πίνακα).

Ας εξετάσουμε τον αλγόριθμο δυαδικής αναζήτησης για αυτήν την περίπτωση.

Η δυαδική αναζήτηση μπορεί εύκολα να γίνει κατανοητή με αυτό το παράδειγμα:

Πηγή: Learneroo

Αν προσπαθήσουμε να εφαρμόσουμε αυτήν τη λογική στο πρόβλημά μας τότε, πρώτα θα συγκρίνουμε το search_digit με το μεσαίο στοιχείο του πίνακα, δηλαδή 5. Τώρα, καθώς το 5 είναι μικρότερο από 10, τότε θα αρχίσουμε να ψάχνουμε το search_digit στα στοιχεία του πίνακα μεγαλύτερο από 5, με τον ίδιο τρόπο μέχρι να πάρουμε το επιθυμητό στοιχείο 10.

Τώρα, προσπαθήστε να μετρήσετε τον αριθμό των λειτουργιών που χρειάστηκε η δυαδική αναζήτηση για να βρείτε το επιθυμητό στοιχείο. Χρειάστηκαν περίπου τέσσερις εργασίες. Τώρα, αυτή ήταν η χειρότερη περίπτωση για δυαδική αναζήτηση. Αυτό δείχνει ότι υπάρχει μια λογαριθμική σχέση μεταξύ του αριθμού των λειτουργιών που εκτελούνται και του συνολικού μεγέθους του πίνακα.

αριθμός πράξεων = log (10) = 4 (περίπου)

για τη βάση 2

Μπορούμε να γενικεύσουμε αυτό το αποτέλεσμα για δυαδική αναζήτηση ως:

Για έναν πίνακα μεγέθους n , ο αριθμός των λειτουργιών που εκτελούνται από την Binary Search είναι: log (n)

Η σημειογραφία Big O

Στις παραπάνω δηλώσεις, είδαμε ότι για έναν πίνακα μεγέθους n , η γραμμική αναζήτηση θα εκτελέσει n λειτουργίες για την ολοκλήρωση της αναζήτησης. Από την άλλη πλευρά, η Δυαδική αναζήτηση πραγματοποίησε αρχείο καταγραφής (n) αριθμό λειτουργιών (και οι δύο για τις χειρότερες περιπτώσεις) Μπορούμε να το αντιπροσωπεύσουμε ως γράφημα ( άξονας x : αριθμός στοιχείων, άξονας y : αριθμός πράξεων).

Πηγή: Techtud

Είναι σαφές από το σχήμα ότι ο ρυθμός με τον οποίο αυξάνεται η πολυπλοκότητα για τη Γραμμική αναζήτηση είναι πολύ πιο γρήγορος από αυτόν για τη δυαδική αναζήτηση.

Όταν αναλύουμε έναν αλγόριθμο, χρησιμοποιούμε έναν συμβολισμό για να αντιπροσωπεύσουμε την πολυπλοκότητα του χρόνου και ότι ο συμβολισμός είναι ο συμβολισμός Big O.

Για παράδειγμα: η πολυπλοκότητα του χρόνου για τη Γραμμική αναζήτηση μπορεί να αναπαρασταθεί ως O (n) και O (log n) για Binary search (όπου, n και log (n) είναι ο αριθμός των λειτουργιών).

Η χρονική πολυπλοκότητα ή οι σημειώσεις Big O για μερικούς δημοφιλείς αλγόριθμους παρατίθενται παρακάτω:

  1. Δυαδική αναζήτηση: O (log n)
  2. Γραμμική αναζήτηση: O (n)
  3. Γρήγορη ταξινόμηση: O (n * log n)
  4. Ταξινόμηση επιλογής: O (n * n)
  5. Ταξιδιωτικός πωλητής: O (n!)

συμπέρασμα

Εκτιμώ πραγματικά τις προσπάθειές σας εάν διαβάζετε ακόμα αυτό το άρθρο. Τώρα, πρέπει να σκέφτεστε - γιατί είναι πολύ σημαντική η κατανόηση της πολυπλοκότητας του χρόνου;

Γνωρίζουμε ότι για έναν μικρό αριθμό στοιχείων (ας πούμε 10), η διαφορά μεταξύ του αριθμού των λειτουργιών που εκτελούνται από τη δυαδική αναζήτηση και τη γραμμική αναζήτηση δεν είναι τόσο μεγάλη. Αλλά στον πραγματικό κόσμο, τις περισσότερες φορές, αντιμετωπίζουμε προβλήματα που έχουν μεγάλα κομμάτια δεδομένων.

Για παράδειγμα, εάν έχουμε 4 δισεκατομμύρια στοιχεία για αναζήτηση, τότε, στη χειρότερη περίπτωση, η γραμμική αναζήτηση θα χρειαστεί 4 δισεκατομμύρια λειτουργίες για να ολοκληρώσει το έργο της. Η δυαδική αναζήτηση θα ολοκληρώσει αυτήν την εργασία σε μόλις 32 λειτουργίες. Αυτή είναι μια μεγάλη διαφορά. Τώρα ας υποθέσουμε ότι εάν μία λειτουργία διαρκεί 1 ms για ολοκλήρωση, τότε η δυαδική αναζήτηση θα διαρκέσει μόνο 32 ms ενώ η γραμμική αναζήτηση θα διαρκέσει 4 δισεκατομμύρια ms (δηλαδή περίπου 46 ημέρες). Αυτή είναι μια σημαντική διαφορά.

Αυτός είναι ο λόγος για τον οποίο η μελέτη της πολυπλοκότητας του χρόνου καθίσταται σημαντική όταν πρόκειται για τόσο μεγάλο αριθμό δεδομένων.

Πόροι

Αλγόριθμοι Grokking - από τον Aditya Y Bhargava

Εισαγωγή στη σημείωση Big O και την πολυπλοκότητα του χρόνου - από τον CS Dojo