Διάφορα

Χρόνος πολυπλοκότητας: Γιατί ορισμένοι αλγόριθμοι τρέχουν για δισεκατομμύρια χρόνια

Χρόνος πολυπλοκότητας: Γιατί ορισμένοι αλγόριθμοι τρέχουν για δισεκατομμύρια χρόνια

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

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

Τι είναι η πολυπλοκότητα του χρόνου;

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

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

Πόσες λειτουργίες απαιτούν, χωρίς να γνωρίζουμε ποιο θα είναι το τελικό μέγεθος εισόδου, χρησιμοποιώντας μόνο τις αφηρημένες μεταβλητές Π και ε; Αυτό που κάνουμε είναι να τρέξουμε ένα βρόχος όπου αυξάνεται κάθε επανάληψη Π από ακριβώς 1 και το προσθέτει ρ. Έτσι φαίνεται ο αλγόριθμός μας όταν παρουσιάζεται κάπως πιο επίσημα:

1. ας ρ = 0
2. ενώ Π είναι <= προς το ε
3. ρ=Π+ρ
4. Π = Π+1
5. επιστροφή ρ

Όταν ορίζεται έτσι σε αυτό που αποκαλούμε ψευδοκώδικας, γίνεται πολύ πιο εύκολο να δούμε πόσες λειτουργίες θα χρειαστούν. Πηγαίνετε κάτω από τον αριθμό με τα βήματα και μετρήστε τις λειτουργίες. Το πρώτο είναι μια οδηγία, οπότε είναι μία λειτουργία. Η δεύτερη γραμμή, ωστόσο, είναι διαφορετική. Οι βρόχοι όπως αυτό επαναλαμβάνονται έως ότου ικανοποιηθεί η συνθήκη, στην περίπτωση αυτή, μία φορά Π είναι μεγαλύτερο από ε. Γνωρίζουμε τότε ότι συμπεριλαμβάνουμε ε και Π στο άθροισμα, έτσι ο αριθμός των επαναλήψεις μέσα από αυτό βρόχος είναι ίσο με q - (p - 1), Ποιο είναι το μέγεθος εισόδου για τον αλγόριθμό μας.

Αλλά αυτός είναι μόνο ο αριθμός των επαναλήψεων μέσω του βρόχου, πρέπει επίσης να μετρήσουμε τις λειτουργίες μέσα σε αυτό, που είναι όπου προσθέτουμε Π και ρ και αναθέτω το αποτέλεσμα να ρ και μετά προσθέτουμε Π και 1 και μετά εκχωρήστε το αποτέλεσμα σε Π. Οπότε παίζουμε δύο λειτουργίες για κάθε επανάληψη, και υπάρχουν q - (σελ - 1)επαναλήψεις Το μόνο που πρέπει να κάνουμε τώρα είναι πολλαπλασιασμός 2 λειτουργίες και q - (σελ - 1)επαναλήψεις να πάρω 2 * (q - (p - 1)) λειτουργίες για ολόκληρο τον βρόχο. Προσθέστε τις λειτουργίες στα 1. και 5., που μας δίνει μια τελική μέτρηση 2 * (q - (p - 1)) + 2 λειτουργίες για αυτόν τον αλγόριθμο.

Αυτή είναι μια γραμμική συνάρτηση δεδομένου ότι δεν υπάρχουν εκθέτες, έτσι το ρυθμός ανάπτυξης για τον αλγόριθμο αθροίσματος είναι συνδέεται άμεσα με ο εισαγωγή μέγεθος, το οποίο καλούμε γραμμική πολυπλοκότητα χρόνου. Κατά γενικό κανόνα, όποιος και αν είναι ο υψηλότερος όρος παραγγελίας σε έναν τύπο που καθορίζει την πολυπλοκότητα του χρόνου μας είναι αυτό που χαρακτηρίζει την ανάπτυξή του με την πάροδο του χρόνου, οπότε παίρνουμε τον υψηλότερο όρο παραγγελίας και απορρίπτουμε τα υπόλοιπα, αφήνοντας το q - (p - 1), το οποίο θα κλήση ν για λόγους απλότητας.

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

Γνωρίζουμε εδώ και πολύ καιρό ότι το άθροισμα του όλαοι αριθμοί από 1 και ε δίνεται από τον τύπο (q * (q + 1)) / 2. Γνωρίζουμε επίσης ότι τοανταλλακτική ιδιότητα της προσθήκης μας λέει ότι το αποτέλεσμα του (p-1 * (p)) / 2 αφαιρείται από (q * (q + 1)) / 2 απλώς βγάζει το μέρος του αθροίσματος που περιλαμβάνει τα πάντα 1 προς το Π-1, αφήνοντας το άθροισμα των αριθμών από Π προς το ε πίσω, αυτό είναι ακριβώς αυτό που θέλουμε.

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

1. ρ = (p-1 * (p)) / 2
2. ε
= (q * (q + 1)) / 2
3. ΕΠΙΣΤΡΟΦΗ ( q -Π )

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

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

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

Τι είναι η σημείωση Big O;

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

Υπάρχουν και άλλα Μεγάλες σημειώσεις για το καλύτερη περίπτωση και μέση περίπτωση, αλλά αυτό που έχει σημασία είναι το στη χειρότερη περίπτωση; αυτά είναι αυτά που μπορούν να συντρίψουν τον υπολογιστή σας - ή χειρότερα, το αυτοκίνητό σου ή το αεροπλάνο σας. Πηγαίνουν δεξιά στην καρδιά του γιατί χρονική πολυπλοκότητα έχει σημασία και επισημαίνω γιατί μερικοί αλγόριθμοι απλά δεν μπορεί να λύσει ένα πρόβλημα χωρίς να πάρει μερικά δισεκατομμύρια χρόνια να το κάνω.

Λοιπόν, πώς χρησιμοποιούμε Μεγάλη σημειογραφία; Το παραπάνω διάγραμμα σας δείχνει πώς διαφέρουν Big O Σημειώσεις Κοιτάξτε στην πράξη, με το άξονας x είναι η συμβολή σας και το δικό σας γ-άξονας ο χρόνος που απαιτείται για να τελειώσει. Για λίγο περισσότερες λεπτομέρειες, θα βρείτε μια γρήγορη λίστα όλων των Big O Σημειώσεις αυτό έχει σημασία για τώρα και το χρονική πολυπλοκότητα αντιπροσωπεύουν:

* Ο (1): Πολυπλοκότητα σταθερού χρόνου- Αυτή είναι η αποτελεσματικά υπολογιστική δωρεάν κάρτα για την οποία μιλήσαμε προηγουμένως. Αυτό δεν σημαίνει απαραίτητα ότι είναι ταχύτερη. Σημαίνει απλώς ότι το χρονική πολυπλοκότητα δεν σχετίζεται με το μέγεθος της εισόδου.

* O (ημερολόγιο n): Λογαριθμική χρονική πολυπλοκότητα- Αυτά είναι πιο συνηθισμένα όταν χρησιμοποιείτε ένα στρατηγική διαίρεσης και κατάκτησης σε ένα σύνολο δεδομένων, όπου κάθε λειτουργία απορρίπτει ένα μεγάλο μέρος της εισόδου που έχει αποκλείσει ότι δεν έχει τη λύση. Το κλασικό παράδειγμα είναι η αναζήτηση μιας λέξης σε ένα λεξικό: Ανοίξτε τυχαία, ελέγξτε σε ποια ενότητα γραμμάτων βρίσκεστε και, στη συνέχεια, αγνοώντας το μέρος όπου γνωρίζετε ότι δεν θα είναι η λέξη σας και υποδιαιρέστε αναδρομικά και απορρίψτε τις υπόλοιπες ενότητες έως ότου βρείτε ο λόγος σου.

* Επί): Γραμμική πολυπλοκότητα χρόνου- Αυτός ήταν ο αρχικός μας αλγόριθμος από την αρχή.

* O (n log n): Γραμμική αριθμητική πολυπλοκότητα- Η εκτέλεση ενός γρήγορου μετασχηματισμού Fourier είναι O (n Log n) αλγόριθμος, όπως είναι το Mergesort.

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

* Επίντο, γ> 1): Πολυωνυμική χρονική πολυπλοκότητα- Πολυωνυμική χρονική πολυπλοκότητα είναι πολύ σημαντικό γιατί περισσότερο ή λιγότερο αντιπροσωπεύει το άνω όριο σε τι α κλασικός υπολογιστής μπορεί να λύσει σε πρακτικό χρονικό διάστημα.

* O (γν, n> 1, c> 1): Εκθετική πολυπλοκότητα χρόνου- Εδώ αρχίζετε να παίρνετε το Αλγόριθμοι δισεκατομμυρίων ετών. Οποιαδήποτε στιγμή α μονάδα εισαγωγής σε προκαλεί διπλασιάστε τον αριθμό των λειτουργιών που πραγματοποιήθηκαν σε σχέση με τον αριθμό που εκτελείται εάν η είσοδος είναιν-1, έχεις εκθετική πολυπλοκότητα χρόνου. Το πιο κοινό παράδειγμα που χρησιμοποιούν οι περισσότεροι άνθρωποι προσπαθεί να απαριθμήσει κάθε πιθανό υποσύνολο ενός συνόλου, αλλά Βίαια βία ένα Κλειδί κρυπτογράφησης 128-bit συνήθως εντάσσεται σε αυτήν την κατηγορία.

* Επί!): Παραγοντικότητα του Παραγοντικού Χρόνου- Αυτοί είναι αλγόριθμοι που πιθανότατα θα μπορούσαν να τρέξουν μέχρι τον θερμό θάνατο του Σύμπαντος, εάν του δοθεί ένα μέτριο μέγεθος εισόδου μερικών χιλιάδων. Κάθε φορά που έχετε κάτι όπως «πόσους διαφορετικούς τρόπους μπορείτε να οργανώσετε αυτήν την ακολουθία», έχετε ένα πρόβλημα παραλλαγής και το ωμή-εξαναγκασμό του δρόμου σας σε μια απάντηση απαιτεί τη δημιουργία ν! διαφορετικές τιμές, οι οποίες δίδονται από το αποτέλεσμα: n * (n - 1) * (n - 2) * ... * 3 * 2 * 1. Αυτοί είναι οι αλγόριθμοι που τρέχουν σχεδόν παράλληλα με το γ-άξονας στο παραπάνω διάγραμμα.

Γιατί δεν μπορούμε απλώς να βρούμε καλύτερους αλγόριθμους

Δεν είναι για έλλειψη προσπάθειας. Όλο το πεδίο του θεωρητική επιστήμη υπολογιστών έχει να κάνει με την προσπάθεια εύρεσης των περισσότερων αποτελεσματικός αλγόριθμος για ένα συγκεκριμένο πρόβλημα, αλλά μερικές φορές απλά δεν γνωρίζουμε τα μαθηματικά. Και όχι μόνο εσείς και εγώ, μιλάμε για τους νικητές του Field Medal που αντιμετώπισαν ορισμένα προβλήματα όπως το Ο (2ν) και Επί!) και η εικασία τους είναι τόσο καλή όσο η δική μας.

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

Ο λόγος που κλασικοί υπολογιστές δεν μπορεί να επιλύσει αποτελεσματικά αυτά τα προβλήματα είτε είναι ενσωματωμένο στα κυκλώματα του μηχανήματος. Κάθε οδηγία που δίνεται πρέπει να ολοκληρωθεί προτού ξεκινήσει την επόμενη. Τα συστήματα πολλαπλών πυρήνων ή τα μηχανήματα πολλαπλών επεξεργαστών μπορούν να επιταχύνουν τα πράγματα, αλλά μάλλον θα χρειαστείτε ένα ή δύο τρισεκατομμύρια χρόνια για να έχουμε ένα αποτέλεσμα αφού ρίξουμε όλους τους επεξεργαστές μας μαζί και τους αφήσουμε χαλαρούς σε ένα Επί!) πρόβλημα πού ν ήταν κάτι σαν 500.

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

Τα καλά νέα είναι ότι ξέρουμε ότι είναι δυνατόν, στο τουλάχιστον μία περίπτωση, για να βρείτε έναν αρκετά αποτελεσματικό αλγόριθμο για να βρείτε την απάντηση σε ένα από αυτά Ο (2ν) προβλήματα στο πολυωνυμική χρονική πολυπλοκότητα. Εάν μπορεί να γίνει μία φορά, τότε είναι δυνατό να το ξανακάνετε. χρειάζεται μόνο παρακάμπτοντας ολόκληρο το πράγμα «φυσική».

Το τέταρτο άρθρο της σειράς μας σχετικά με τους αλγόριθμους και τον υπολογισμό, Πώς ο αλγόριθμος του Peter Shor Dooms RSA Encryption to Failure, μπορείτε να βρείτε εδώ.


Δες το βίντεο: ΚΑΡΤΑ - ΚΛΑΣΕΙΣ ΣΥΝΑΡΤΗΣΕΩΝ ΠΟΛΥΠΛΟΚΟΤΗΤΑΣ (Δεκέμβριος 2021).