Προγραμματισμός

* Γνώση Υπολογιστών >> Προγραμματισμός >> Προγραμματισμός Υπολογιστών Γλώσσες

Επεξήγηση του Big O Συμβολισμός

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

Big O συμβολισμός - επίσης γνωστό ως σύμβολο Λαντάου , μετά τη γερμανική εβραϊκή μαθηματικός , Edmund Landau - περιγράφει το ρυθμό αύξησης μιας συνάρτησης , επίσης γνωστή ως τους " , προκειμένου" εξ ου και η κεφαλαίο γράμμα " O" Big O συμβολισμός προορίζεται για τη μέτρηση της απόδοσης ενός αλγορίθμου η ίδια , παρά το υλικό στο οποίο τρέχει ο αλγόριθμος . Ένα κομμάτι του υλικού μπορεί να είναι ταχύτερη ή πιο αργή από ό, τι άλλο από ένα σταθερό συντελεστή , έτσι ώστε όλα τα σταθερά στοιχεία αφαιρούνται από Big O συμβολισμός .
Εικόνων Σταθερή Χρόνος λειτουργίας
Η

Ένας αλγόριθμος ότι παίρνει πάντα περίπου την ίδια ώρα για να τρέξει , ανεξάρτητα από το μέγεθος της εισόδου , ​​λέγεται ότι έχει " σταθερή " χρόνος τρέχει . Σε Big O σημειογραφία , αυτό το είδος του αλγορίθμου είναι γνωστό ως ένα αλγόριθμο " παραγγελία 1 » και συμβολίζεται με O ( 1 ) . Παραδείγματα O ( 1 ) αλγόριθμοι περιλαμβάνουν ώθηση ή βρεθώ δεδομένων προς και από μια στοίβα προγραμματισμού , και την ανάκτηση ένα μεμονωμένο στοιχείο δεδομένων από έναν πίνακα , όταν γνωρίζετε τη θέση της . Αυτοί οι αλγόριθμοι εκτελούν μόνο έναν ορισμένο αριθμό των βημάτων , δεν έχει σημασία πόσο μεγάλη η είσοδος γίνεται .
Εικόνων Γραμμική Χρόνος λειτουργίας
Η

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

Η Τετραγωνικός χρόνος λειτουργίας
Η

Ένας αλγόριθμος του οποίου αυξάνεται ο χρόνος τρέχει με συντελεστή n ^ 2 , όταν το μέγεθος των αυξήσεων των εισροών του κατά ένα παράγοντα " n" λέγεται ότι οι " τετραγωνική " χρόνος τρέχει . Σε Big O σημειογραφία , αυτό το είδος του αλγορίθμου είναι γνωστό ως μια σειρά ν ^ 2 αλγορίθμου , ή απλά μία τετραγωνική αλγόριθμο , και συμβολίζεται με O (n ^ 2 ) . Παραδείγματα O ( n ^ 2 ) αλγορίθμων περιλαμβάνουν αλγορίθμων ταξινόμησης , όπως η ταξινόμηση με εισαγωγή και bubble sort , στην οποία διπλασιάζοντας το μέγεθος της εισόδου τετραπλασιάζει το χρόνο λειτουργίας .
Η
εικόνων

Συναφής σύστασή

Πνευματικά δικαιώματα © Γνώση Υπολογιστών Όλα τα δικαιώματα κατοχυρωμένα