[Powered by Google Translate] Πιθανόν να έχετε ακούσει ανθρώπους να μιλούν για ένα γρήγορο ή αποτελεσματικό αλγόριθμο για την εκτέλεση συγκεκριμένης εργασίας σας, αλλά τι ακριβώς σημαίνει αυτό για έναν αλγόριθμο για να είναι γρήγορη ή αποδοτικό; Λοιπόν, δεν είναι να μιλάμε για μια μέτρηση σε πραγματικό χρόνο, σαν δευτερόλεπτα ή λεπτά. Αυτό συμβαίνει επειδή το υλικό του υπολογιστή και το λογισμικό διαφέρουν δραστικά. Το πρόγραμμά μου θα τρέχει πιο αργά από τη δική σας, επειδή είμαι να τρέχει σε παλαιότερο υπολογιστή, ή επειδή τυχαίνει να παίζει ένα online παιχνίδι βίντεο την ίδια στιγμή, η οποία hogging όλα μνήμη μου, ή θα μπορούσε να τρέχει το πρόγραμμα μου με διαφορετικό λογισμικό η οποία επικοινωνεί με το μηχάνημα διαφορετικά σε χαμηλό επίπεδο. Είναι σαν να συγκρίνουμε μήλα και τα πορτοκάλια. Ακριβώς επειδή αργό υπολογιστή μου παίρνει περισσότερο από τη δική σας για να δώσει μια απάντηση πίσω δεν σημαίνει ότι έχετε την πιο αποδοτικό αλγόριθμο. 

Έτσι, δεδομένου ότι δεν μπορούμε να συγκρίνουμε άμεσα τα runtimes των προγραμμάτων σε δευτερόλεπτα ή λεπτά, πώς μπορούμε να συγκρίνουμε 2 διαφορετικές αλγορίθμων ανεξάρτητα από το υλικό τους ή το περιβάλλον του λογισμικού; Για να δημιουργήσετε ένα πιο ομοιόμορφο τρόπο μέτρησης της αποδοτικότητας αλγοριθμικής, επιστήμονες της πληροφορικής και μαθηματικοί έχουν επινοήσει έννοιες για τη μέτρηση της ασυμπτωτική πολυπλοκότητα ενός προγράμματος και μια σημειογραφία που ονομάζεται «Big Ohnotation» για την περιγραφή αυτή. Ο επίσημος ορισμός είναι ότι η συνάρτηση f (x) τρέχει της τάξεως των g (x) εάν υπάρχει κάποια (χ) τιμή, χ και ₀ κάποια σταθερά, C, για τις οποίες f (x) είναι μικρότερη ή ίση προς ότι η συνεχής χρόνοι g (x) για κάθε x μεγαλύτερο από x ₀. 

Αλλά δεν πρέπει να φοβάται μακριά από τον επίσημο ορισμό. Τι ακριβώς σημαίνει αυτό σε λιγότερο θεωρητικό επίπεδο; Λοιπόν, αυτό είναι ουσιαστικά ένας τρόπος ανάλυσης πόσο γρήγορα εκτέλεσης ενός προγράμματος αυξάνεται ασυμπτωτικά. Δηλαδή, όπως το μέγεθος των εισροών σας αυξάνεται προς το άπειρο, λένε, είστε διαλογή μια σειρά από μεγέθους 1000 σε σύγκριση με ένα πίνακα μεγέθους 10. Πώς το χρόνο εκτέλεσης του προγράμματος σας να αυξηθεί; Για παράδειγμα, υποθέστε μετρώντας τον αριθμό των χαρακτήρων σε μια σειρά ο απλούστερος τρόπος  με τα πόδια σε όλη τη σειρά γράμμα-από-γράμμα και προσθέτοντας 1 σε ένα μετρητή για κάθε χαρακτήρα. Αυτός ο αλγόριθμος λέγεται για να τρέξει σε γραμμικό χρόνο σε σχέση με τον αριθμό των χαρακτήρων, 'N' στη συμβολοσειρά. Με λίγα λόγια, τρέχει σε χρόνο O (n). Γιατί συμβαίνει αυτό; Λοιπόν, με την χρησιμοποίηση της προσέγγισης αυτής, ο χρόνος που απαιτείται να διασχίσει ολόκληρη τη συμβολοσειρά είναι ανάλογη προς τον αριθμό των χαρακτήρων. Μετρώντας τον αριθμό των χαρακτήρων σε μια συμβολοσειρά 20-χαρακτήρων πρόκειται να πάρει δύο φορές όσο χρειάζεται για την καταμέτρηση των χαρακτήρων σε μια συμβολοσειρά 10-χαρακτήρων, γιατί πρέπει να εξετάσουμε όλους τους χαρακτήρες και κάθε χαρακτήρας παίρνει το ίδιο χρονικό διάστημα για να δούμε. Όπως μπορείτε να αυξήσετε τον αριθμό των χαρακτήρων, ο χρόνος εκτέλεσης θα αυξηθεί γραμμικά με το μήκος εισόδου. 

Τώρα, φανταστείτε αν αποφασίσετε ότι γραμμικό χρόνο, O (n), απλά δεν ήταν αρκετά γρήγορο για σένα; Ίσως είστε αποθήκευση τεράστιων χορδές, και δεν μπορείτε να δώσει το επιπλέον χρόνο που θα χρειαζόταν να διασχίσει όλα τους χαρακτήρες μετρώντας ένα-ένα. Έτσι, αν αποφασίσετε να δοκιμάσετε κάτι διαφορετικό. Τι θα συμβεί αν θα συμβεί ήδη να αποθηκεύσετε τον αριθμό των χαρακτήρων στη σειρά, ας πούμε, σε μια μεταβλητή που ονομάζεται 'λεν, " νωρίς στο πρόγραμμα, πριν αποθηκεύονται ακόμη και την πρώτη σε σειρά χαρακτήρα σας; Στη συνέχεια, το μόνο που θα έχετε να κάνετε τώρα για να μάθετε το μήκος συμβολοσειράς, είναι να ελέγξετε ποια είναι η τιμή της μεταβλητής είναι. Δεν θα πρέπει να εξετάσουμε την ίδια σειρά σε όλα, και την πρόσβαση στην τιμή μιας μεταβλητής, όπως λεν θεωρείται ασυμπτωτικά μια σταθερή λειτουργία του χρόνου, ή Ο (1). Γιατί συμβαίνει αυτό; Λοιπόν, θυμάστε τι ασυμπτωτική πολυπλοκότητα σημαίνει. Πώς λειτουργεί η αλλαγή χρόνου εκτέλεσης, όπως το μέγεθος εισόδους σας μεγαλώνει; 

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

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

Όπως μπορείτε να μαντέψετε, υπάρχουν πολλές διαφορετικές μεγάλες O runtimes για τη μέτρηση αλγορίθμων με. O (n) ² αλγόριθμοι είναι ασυμπτωτικά πιο αργή από αλγορίθμους O (n). Δηλαδή, καθώς ο αριθμός των στοιχείων (n) μεγαλώνει, τελικά O (n) ² αλγόριθμοι θα χρειαστεί περισσότερο χρόνο από O (n) αλγορίθμων για να τρέξει. Αυτό δεν σημαίνει O (n) αλγόριθμοι πάντα τρέχουν πιο γρήγορα από O (n) ² αλγορίθμων, ακόμη και στο ίδιο περιβάλλον, για το ίδιο υλικό. Ίσως για μικρά μεγέθη εισόδου,  ο O (n) ² αλγόριθμος μπορεί στην πραγματικότητα να λειτουργήσει πιο γρήγορα, αλλά, τελικά, όπως του μεγέθους της εισόδου αυξάνει προς το άπειρο, το O (n) χρόνο εκτέλεσης ² αλγορίθμου θα επισκιάσει τελικά το runtime του O (n) αλγόριθμο. Ακριβώς όπως και κάθε τετραγωνική μαθηματική συνάρτηση  θα ξεπεράσει τελικά κάθε γραμμική συνάρτηση, δεν έχει σημασία πόσο μεγάλο μέρος ενός κεφαλιού ξεκινήσει η γραμμική συνάρτηση ξεκινά με. Αν εργάζεστε με μεγάλες ποσότητες δεδομένων, αλγόριθμους που τρέχουν σε χρόνο O (n) ² χρόνο μπορεί πραγματικά να καταλήξετε επιβραδύνουν το πρόγραμμά σας, αλλά για μικρά μεγέθη εισόδου, τότε μάλλον δεν θα παρατηρήσετε ακόμη. 

Μια άλλη ασυμπτωτική πολυπλοκότητα είναι, λογαριθμική φορά, O (log n). Ένα παράδειγμα ενός αλγορίθμου που εκτελείται αυτό γρήγορα είναι το κλασικό αλγόριθμο δυαδικής αναζήτησης, για την εύρεση ενός στοιχείου σε ήδη ταξινομημένο κατάλογο στοιχείων. 

Αν δεν ξέρετε τι κάνει δυαδική αναζήτηση, Θα το εξηγήσω για σας πραγματικά γρήγορα. Ας πούμε ότι ψάχνετε για τον αριθμό 3 σε αυτή την συστοιχία των ακεραίων. Φαίνεται ότι στο μεσαίο στοιχείο του πίνακα και ρωτά, "Είναι το στοιχείο που θέλω μεγαλύτερη, ίση ή μικρότερη από αυτό;" Αν είναι ίσες, τότε μεγάλη. Βρήκατε το στοιχείο, και είστε έτοιμοι. Αν είναι μεγαλύτερη, τότε ξέρετε το στοιχείο πρέπει να είναι στην δεξιά πλευρά της συστοιχίας, και μπορείτε μόνο να δείτε ότι στο μέλλον, και αν είναι μικρότερο, τότε ξέρετε ότι πρέπει να είναι στην αριστερή πλευρά. Αυτή η διαδικασία επαναλαμβάνεται τότε με τη συστοιχία μικρότερο μέγεθος έως ότου η σωστή στοιχείο βρίσκεται. 

Αυτό το ισχυρό αλγόριθμο κόβει το μέγεθος του πίνακα στο μισό με κάθε λειτουργία. Έτσι, για να βρείτε ένα στοιχείο σε ένα ταξινομημένο πίνακα μεγέθους 8, το πολύ (log ₂ 8), ή 3 από τις πράξεις αυτές, ελέγχοντας το μεσαίο στοιχείο, στη συνέχεια κοπή τη συστοιχία στο μισό θα απαιτείται, ενώ μια σειρά από μέγεθος 16 παίρνει (log ₂ 16), ή 4 ​​λειτουργίες. Αυτό είναι μόνο 1 επιπλέον λειτουργία για μια σειρά διπλασιαστεί σε μέγεθος. Διπλασιάζοντας το μέγεθος της συστοιχίας αυξάνει το χρόνο λειτουργίας του μόνο 1 κομμάτι αυτού του κώδικα. Πάλι, ελέγχοντας το μεσαίο στοιχείο του πίνακα, τότε σχισίματος. Έτσι, λέγεται για να λειτουργήσει σε λογαριθμική χρόνο, O (log n). Αλλά περιμένετε, λέτε, αυτό δεν εξαρτάται από όπου στη λίστα το στοιχείο που αναζητάτε είναι; Τι θα συμβεί αν το πρώτο στοιχείο κοιτάς συμβαίνει να είναι η σωστή; Στη συνέχεια, παίρνει μόνο 1 λειτουργία, Δεν έχει σημασία πόσο μεγάλη είναι η λίστα είναι. 

Λοιπόν, γι 'αυτό οι επιστήμονες υπολογιστών έχουν περισσότερους όρους για ασυμπτωτική πολυπλοκότητα που αντικατοπτρίζουν την καλύτερη περίπτωση- και στη χειρότερη περίπτωση παραστάσεις ενός αλγορίθμου. Πιο σωστά, τα άνω και κάτω όρια στο χρόνο εκτέλεσης. Στην καλύτερη περίπτωση για δυαδική αναζήτηση, στοιχείο μας είναι εκεί στη μέση, και μπορείτε να το πάρετε σε συνεχή χρόνο, ανεξάρτητα από το πόσο μεγάλη είναι η υπόλοιπη της συστοιχίας είναι. Το σύμβολο που χρησιμοποιείται για το σκοπό αυτό είναι Ω. Έτσι, ο αλγόριθμος αυτός λέγεται να τρέχει στο Ω (1). Στην καλύτερη περίπτωση, βρίσκει το στοιχείο γρήγορα, Δεν έχει σημασία πόσο μεγάλη είναι η σειρά είναι, αλλά στην χειρότερη περίπτωση, που πρέπει να επιτελεί (log n) έλεγχοι διάσπαση του πίνακα για να βρείτε το σωστό στοιχείο. Τα χειρότερη περίπτωση άνω φράγματα που προβλέπονται με το μεγάλο "O" που ήδη γνωρίζετε. Έτσι, είναι O (log n), αλλά Ω (1). 

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

Ένα ακόμη σύμβολο που χρησιμοποιείται είναι Θ. Αυτό μπορεί να χρησιμοποιηθεί για να περιγράψει αλγορίθμων όπου οι καλύτερες και τις χειρότερες περιπτώσεις είναι τα ίδια. Αυτή είναι η υπόθεση της συμβολοσειράς μήκους αλγόριθμοι μιλήσαμε για νωρίτερα. Δηλαδή, αν θα το αποθηκεύσει σε μια μεταβλητή πριν αποθηκεύουμε το string και η πρόσβαση αργότερα σε σταθερό χρόνο. Δεν έχει σημασία ποιος είναι ο αριθμός είμαστε αποθήκευση σε αυτή τη μεταβλητή, θα πρέπει να το δει κανείς. Η καλύτερη περίπτωση είναι, κοιτάμε και βρείτε το μήκος του string. Έτσι Ω (1) ή καλύτερη περίπτωση σταθερό χρόνο. Η χειρότερη περίπτωση είναι, το δούμε και να βρούμε το μήκος του string. Έτσι, O (1) ή σταθερό χρόνο στη χειρότερη περίπτωση. Έτσι, δεδομένου ότι η καλύτερη περίπτωση και χειρότερες περιπτώσεις είναι τα ίδια, αυτό μπορεί να λεχθεί για να τρέξει σε Θ (1) ώρα. 

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

Αν τρέχετε σε χρόνο O (n) αλγόριθμο ², ή, ακόμη χειρότερα, ένας O (2 ⁿ) αλγόριθμος, ένας από τους ταχύτερα αναπτυσσόμενους τύπους, πραγματικά θα αρχίσετε να παρατηρείτε την επιβράδυνση όταν αρχίσετε να εργάζεστε με μεγαλύτερα ποσά των δεδομένων. 

Αυτό είναι ασυμπτωτική πολυπλοκότητα. Ευχαριστώ.