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

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

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

Ιστορικό

Η σημασία της αποδοτικότητας με έμφαση στον χρόνο εκτέλεσης τονίστηκε από την Ada Lovelace το 1843 σχετικά με τη μηχανική αναλυτική μηχανή του Charles Babbage:

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

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

Οι σύγχρονοι υπολογιστές είναι πολύ πιο γρήγοροι από τους πρώτους υπολογιστές και έχουν πολύ περισσότερη μνήμη (gigabyte αντί για kilobyte). Ωστόσο, ο Donald Knuth τονίζει ότι η αποτελεσματικότητα παραμένει ένας σημαντικός παράγοντας:

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

Ανασκόπηση

Ένας αλγόριθμος θεωρείται αποτελεσματικός εάν η κατανάλωση πόρων (ή το κόστος πόρων) είναι σε ή κάτω από κάποιο αποδεκτό επίπεδο. Σε γενικές γραμμές, το "αποδεκτό" εδώ σημαίνει ότι "ο αλγόριθμος θα εκτελείται για εύλογο χρονικό διάστημα σε έναν διαθέσιμο υπολογιστή." Επειδή υπήρξε σημαντική αύξηση στην επεξεργαστική ισχύ και στη διαθέσιμη μνήμη των υπολογιστών από τη δεκαετία του 1950, το σημερινό «αποδεκτό επίπεδο» δεν ήταν αποδεκτό ούτε πριν από 10 χρόνια.

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

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

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

Θεωρητική ανάλυση

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

Ονομασία	Ονομα	Παραδείγματα
O(1) (\displaystyle O(1)\,)	μόνιμος	Προσδιορισμός εάν ένας αριθμός είναι άρτιος ή περιττός. Χρησιμοποιώντας έναν πίνακα αναζήτησης σταθερού μεγέθους. Χρήση κατάλληλης συνάρτησης κατακερματισμού για την επιλογή ενός στοιχείου.
O (log ⁡ n) (\displaystyle O(\log n)\,)	λογαριθμική	Εύρεση ενός στοιχείου σε έναν ταξινομημένο πίνακα χρησιμοποιώντας δυαδική αναζήτηση ή ισορροπημένο δέντρο, παρόμοια με πράξεις στον διωνυμικό σωρό.
O(n) (\displaystyle O(n)\,)	γραμμικός	Εύρεση ενός στοιχείου σε μια μη ταξινομημένη λίστα ή μη ισορροπημένο δέντρο (χειρότερη περίπτωση). Προσθήκη δύο n-αριθμοί bit χρησιμοποιώντας μεταφορά από άκρο σε άκρο.
O (n log ⁡ n) (\displaystyle O(n\log n)\,)	σχεδόν γραμμικό, λογαριθμικά γραμμικό	Υπολογίστε γρήγορο μετασχηματισμό Fourier, heapsort, quicksort (καλύτερη και μέση περίπτωση), συγχώνευση ταξινόμησης
O (n 2) (\displaystyle O(n^(2))\,)	τετράγωνο	Πολλαπλασιάζοντας δύο n-ψήφιοι αριθμοί με χρήση απλού αλγόριθμου, ταξινόμηση με φυσαλίδες (χειρότερη περίπτωση), ταξινόμηση κελύφους, γρήγορη ταξινόμηση (χειρότερη περίπτωση), ταξινόμηση επιλογής, ταξινόμηση εισαγωγής
O (c n) , c > 1 (\displaystyle O(c^(n)),\;c>1)	εκθετικός	Εύρεση (ακριβούς) λύσης στο πρόβλημα του πλανόδιου πωλητή χρησιμοποιώντας δυναμικό προγραμματισμό. Προσδιορισμός εάν δύο λογικές προτάσεις είναι ισοδύναμες χρησιμοποιώντας εξαντλητική αναζήτηση

Δοκιμές επαλήθευσης: Μέτρηση της απόδοσης

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

Ορισμένες δοκιμές αναφοράς παρέχουν συγκριτική ανάλυση διαφορετικών γλωσσών μεταγλώττισης και διερμηνείας, όπως η Συλλογή συγκριτικής αξιολόγησης υπολογιστή του Roy Longbottom και The Computer Language Benchmarks Gameσυγκρίνει την απόδοση των υλοποιήσεων τυπικών εργασιών σε ορισμένες γλώσσες προγραμματισμού.

Θέματα εφαρμογής

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

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

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

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

Μέτρηση χρήσης πόρων

Οι μετρήσεις συνήθως εκφράζονται ως συνάρτηση του μεγέθους της εισόδου n.

Οι δύο πιο σημαντικές διαστάσεις είναι:

• χρόνος: Πόσο χρόνο χρειάζεται ο αλγόριθμος στη CPU.
• Μνήμη: Πόση μνήμη εργασίας (συνήθως RAM) χρειάζεται για τον αλγόριθμο. Υπάρχουν δύο πτυχές σε αυτό: η ποσότητα μνήμης για τον κώδικα και η ποσότητα μνήμης για τα δεδομένα στα οποία λειτουργεί ο κώδικας.

Για υπολογιστές με μπαταρίες (όπως φορητούς υπολογιστές) ή για πολύ μεγάλους/μεγάλους υπολογισμούς (όπως υπερυπολογιστές), ενδιαφέρει ένα διαφορετικό είδος μέτρησης:

• Άμεση κατανάλωση ενέργειας: Απαιτείται ενέργεια για τη λειτουργία ενός υπολογιστή.
• Έμμεση κατανάλωση ενέργειας: Απαιτείται ενέργεια για ψύξη, φωτισμό κ.λπ.

Σε ορισμένες περιπτώσεις, χρειάζονται άλλες, λιγότερο κοινές μετρήσεις:

• Μέγεθος γραναζιού: Το εύρος ζώνης μπορεί να είναι ο περιοριστικός παράγοντας. Η συμπίεση μπορεί να χρησιμοποιηθεί για τη μείωση του όγκου των δεδομένων που μεταφέρονται. Η εμφάνιση ενός γραφικού ή μιας εικόνας (όπως το λογότυπο της Google) μπορεί να έχει ως αποτέλεσμα τη μεταφορά δεκάδων χιλιάδων byte (48K σε αυτήν την περίπτωση). Συγκρίνετε αυτό με τη μετάδοση των έξι byte στη λέξη "Google".
• Εξωτερική μνήμη: Απαιτείται μνήμη σε δίσκο ή άλλη εξωτερική συσκευή αποθήκευσης. Αυτή η μνήμη μπορεί να χρησιμοποιηθεί για προσωρινή αποθήκευση ή για μελλοντική χρήση.
• Χρόνος απόκρισης: Αυτή η ρύθμιση είναι ιδιαίτερα σημαντική για εφαρμογές σε πραγματικό χρόνο όπου ο υπολογιστής πρέπει να ανταποκρίνεται γρήγορα σε εξωτερικά συμβάντα.
• Συνολικό κόστος ιδιοκτησίας: Η παράμετρος είναι σημαντική όταν προορίζεται να εκτελέσει έναν μόνο αλγόριθμο.

χρόνος

Θεωρία

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

Μνήμη

Αυτή η ενότητα ασχολείται με τη χρήση της κύριας μνήμης (συχνά RAM) που χρειάζεται ο αλγόριθμος. Όπως και με την ανάλυση χρονισμού παραπάνω, η ανάλυση ενός αλγορίθμου συνήθως χρησιμοποιεί χωρική πολυπλοκότητα του αλγορίθμουγια να υπολογίσετε την απαιτούμενη μνήμη χρόνου εκτέλεσης ως συνάρτηση του μεγέθους εισόδου. Το αποτέλεσμα συνήθως εκφράζεται με όρους "Ο" μεγάλο.

Υπάρχουν τέσσερις πτυχές της χρήσης της μνήμης:

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

Οι πρώτοι ηλεκτρονικοί υπολογιστές και οι οικικοί υπολογιστές είχαν σχετικά μικρές χωρητικότητες μνήμης εργασίας. Έτσι, το 1949 το EDSAC είχε μέγιστη μνήμη εργασίας 1024 λέξεων 17-bit και το 1980 κυκλοφόρησε το Sinclair ZX80 με 1024 byte μνήμης εργασίας.

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

• Cache (συχνά στατική RAM) - τρέχει με ταχύτητες συγκρίσιμες με την CPU
• Κύρια φυσική μνήμη (συχνά δυναμική RAM) - λειτουργεί ελαφρώς πιο αργά από την CPU
• Εικονική μνήμη (συχνά σε δίσκο) - δίνει την ψευδαίσθηση της τεράστιας μνήμης, αλλά λειτουργεί χιλιάδες φορές πιο αργά από τη μνήμη RAM.

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

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

Παραδείγματα αποτελεσματικών αλγορίθμων

Κριτική για την τρέχουσα κατάσταση του προγραμματισμού

Τα προγράμματα γίνονται πιο αργά πιο γρήγορα από ότι οι υπολογιστές γίνονται πιο γρήγοροι.

Η May δηλώνει:

Σε ευρέως διαδεδομένα συστήματα, η μείωση κατά το ήμισυ της εκτέλεσης εντολών μπορεί να διπλασιάσει τη διάρκεια ζωής της μπαταρίας και τα μεγάλα δεδομένα παρέχουν μια ευκαιρία για καλύτερους αλγόριθμους: Η μείωση του αριθμού λειτουργιών από N x N σε N x log(N) έχει ισχυρό αποτέλεσμα για μεγάλα N... Για N =30 δισεκατομμύρια, αυτές οι αλλαγές είναι παρόμοιες με 50 χρόνια τεχνολογικών βελτιώσεων.

Διαγωνισμός για τον καλύτερο αλγόριθμο

Οι ακόλουθοι διαγωνισμοί προσκαλούν συμμετοχή στην ανάπτυξη των καλύτερων αλγορίθμων, τα κριτήρια ποιότητας των οποίων καθορίζονται από τους κριτές:

δείτε επίσης

• Η αριθμητική κωδικοποίηση είναι ένας τύπος κωδικοποίησης εντροπίας με μεταβλητό μήκος κωδικούγια αποτελεσματική συμπίεση δεδομένων
• Ένας συσχετιστικός πίνακας είναι μια δομή δεδομένων που μπορεί να γίνει πιο αποτελεσματική όταν χρησιμοποιείται δέντρα PATRICIAή Συστοιχίες Judy
• Δοκιμή απόδοσης - μια μέθοδος μέτρησης του συγκριτικού χρόνου εκτέλεσης σε ορισμένες περιπτώσεις
• Καλύτερη, χειρότερη και μέτρια περίπτωση- συμβάσεις για την εκτίμηση του χρόνου εκτέλεσης για τρία σενάρια
• Η δυαδική αναζήτηση είναι μια απλή και αποτελεσματική τεχνική για την αναζήτηση μιας ταξινομημένης λίστας
• Τραπέζι υποκαταστημάτων

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

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

Η κλασική δήλωση του N. Wirth «Ένα καλό πρόγραμμα είναι η ενότητα ενός καλά μελετημένου αλγορίθμου και αποτελεσματικών δομών δεδομένων».

Ανάλυση Αλγορίθμων
Οι έννοιες του «αλγορίθμου και των δομών δεδομένων» είναι κεντρικές στον τομέα της τεχνολογίας των υπολογιστών, αλλά για να ονομαστούν ορισμένες δομές δεδομένων και αλγόριθμοι «υψηλής ποιότητας και αποτελεσματικότητας», πρέπει να χρησιμοποιηθούν ακριβείς τεχνικές για την ανάλυσή τους. Ως φυσικό κριτήριο ποιότητας, είναι φυσικό να επισημανθεί, πρώτον, ο χρόνος εκτέλεσης. Σημαντική είναι επίσης η ποσότητα της μνήμης και του χώρου στο δίσκο που δαπανάται, η ταχύτητα πρόσβασης στα δεδομένα (αποτελεσματικότητα της δομής δεδομένων). Πρέπει επίσης να δοθεί προσοχή στην αξιοπιστία και αξιοπιστία των αποφάσεων, στη σταθερότητά τους.

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

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

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

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

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

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

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

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

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

Έτσι, φτάνουμε στην ανάγκη χρήσης γενικών μεθόδων ανάλυσης για την ανάλυση αλγορίθμων, η οποία επιτρέπει:

1) λαμβάνει υπόψη διάφορους τύπους δεδομένων εισόδου.

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

3) μπορεί να πραγματοποιηθεί σύμφωνα με την περιγραφή του αλγορίθμου χωρίς άμεση εφαρμογή ή πειράματα.

Η ουσία της γενικής ανάλυσης είναι ότι η συνάρτηση f=f(n1, .., nm) εκχωρείται σε έναν συγκεκριμένο αλγόριθμο. Στην απλούστερη μορφή του, είναι συνάρτηση μιας μεταβλητής n1 – του όγκου των δεδομένων εισόδου. Ωστόσο, μπορεί να υπάρχουν και άλλες μεταβλητές - για παράδειγμα, η ακρίβεια του υπολογισμού ή η αξιοπιστία του. Έτσι, για να προσδιοριστεί εάν ένας συγκεκριμένος αριθμός είναι πρώτος στην περίπτωση μεγάλων αριθμών (το μήκος της δυαδικής αναπαράστασης είναι περισσότερο από 200 bit), χρησιμοποιείται μια πιθανολογική μέθοδος, η αξιοπιστία της οποίας μπορεί να ποικίλλει. Οι πιο γνωστές συναρτήσεις είναι η γραμμική, η δύναμη και η λογαριθμική. Επομένως, θα πρέπει να αφιερώσετε χρόνο για να θυμηθείτε τα βασικά της συνεργασίας μαζί τους.

Κατά την κατασκευή αλγορίθμων, το πρώτο στάδιο συμβαίνει χρησιμοποιώντας όχι μια γλώσσα προγραμματισμού, αλλά μια περιγραφή σε ανθρώπινη γλώσσα. Τέτοιες περιγραφές δεν είναι προγράμματα, αλλά ταυτόχρονα είναι πιο δομημένες από το συνηθισμένο κείμενο. Συγκεκριμένα, οι περιγραφές «υψηλού επιπέδου» συνδυάζουν φυσική γλώσσα και κοινές δομές γλώσσας προγραμματισμού, καθιστώντας τις προσιτές αλλά και ενημερωτικές. Τέτοιες περιγραφές διευκολύνουν την ανάλυση υψηλού επιπέδου της δομής δεδομένων ή του αλγορίθμου. Τέτοιες περιγραφές ονομάζονται συνήθως ψευδοκώδικας. Θα πρέπει επίσης να σημειωθεί ότι ο ψευδοκώδικας είναι συχνά πιο χρήσιμος για ανάλυση από τον κώδικα σε μια συγκεκριμένη γλώσσα προγραμματισμού.

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

Μερικές φορές οι δηλώσεις γράφονται σε γενικευμένη μορφή: «Το σύνολο s περιέχει ένα στοιχείο x με ιδιότητα v. Για να αποδείξουμε αυτή τη δήλωση, αρκεί να δώσουμε ένα παράδειγμα x «ανήκει» στο s, που έχει αυτή την ιδιότητα. Σε μια τέτοια γενικευμένη μορφή, κατά κανόνα, γράφονται απίθανες δηλώσεις, για παράδειγμα: "Κάθε στοιχείο x του συνόλου s έχει την ιδιότητα P." Για να αποδείξουμε την πλάνη αυτής της πρότασης, αρκεί να δώσουμε απλώς ένα παράδειγμα: το x «ανήκει» στο s, το οποίο δεν έχει την ιδιότητα P. Στην περίπτωση αυτή, το στοιχείο x θα λειτουργήσει ως αντί-παράδειγμα.

Παράδειγμα:Αναφέρεται ότι οποιοσδήποτε αριθμός της μορφής 2^n - 1 είναι πρώτος εάν το n είναι ακέραιος μεγαλύτερος από 1. Η πρόταση είναι ψευδής.

Απόδειξη:Για να αποδείξετε ότι κάποιος κάνει λάθος, πρέπει να βρείτε ένα αντιπαράδειγμα.

Αυτό είναι ένα αντί-παράδειγμα: 2^4 - 1 = 15, 15= 3 * 5.

Υπάρχει και άλλος τρόπος, που βασίζεται στην απόδειξη με αντίφαση (χρησιμοποιώντας άρνηση). Οι κύριες μέθοδοι σε αυτή την περίπτωση είναι η αντίθεση και η αντίφαση. Η χρήση των μεθόδων αντίθεσης είναι παρόμοια με τον κατοπτρισμό: για να αποδείξουμε ότι «αν το x είναι αληθές, τότε το y είναι αληθές», θα ισχυριστούμε το αντίθετο, «αν το y είναι ψευδές, τότε το x είναι ψευδές». Από λογικής άποψης, αυτές οι δηλώσεις είναι πανομοιότυπες, αλλά η δεύτερη έκφραση, που είναι συμπαράθεση της πρώτης, είναι πιο βολική.

Παράδειγμα:Αν το a*b είναι περιττός αριθμός, τότε το a είναι περιττό ή το b είναι περιττό.

Απόδειξη:για να αποδείξετε αυτή τη δήλωση, σκεφτείτε την αντίθεση: «Αν το a είναι άρτιος αριθμός και το b είναι περιττό, τότε το a*b είναι άρτιος. Έστω a = 2*x, για κάποιο ακέραιο x. Τότε a*b = 2*i*b, και επομένως το γινόμενο a*b είναι άρτιο.

Όταν χρησιμοποιείτε μεθόδους απόδειξης με αντίφαση, είναι χρήσιμο να χρησιμοποιείτε τη λογική.

A ή b = απαιτεί το a ή το b να εκτελεστεί, ή και τα δύο a και b ταυτόχρονα.
. a και b = απαιτεί το a και το b να εκτελεστούν ταυτόχρονα.
. a xor b = απαιτεί την εκτέλεση του a, αλλά όχι του b, ή του b, αλλά όχι του a.

Όταν χρησιμοποιείται η μέθοδος της αντίφασης για να αποδείξετε ότι μια πρόταση q είναι αληθής, υποθέτουμε πρώτα ότι το q είναι λάθος και στη συνέχεια δείχνει ότι μια τέτοια υπόθεση οδηγεί σε αντίφαση (για παράδειγμα, 2 * 2<>4). Έχοντας καταλήξει σε μια τέτοια αντίφαση, μπορούμε να υποστηρίξουμε ότι μια κατάσταση στην οποία το q είναι ψευδές δεν υπάρχει και, επομένως, το q είναι αληθές.

Στις περισσότερες περιπτώσεις, οι δηλώσεις σχετικά με τον χρόνο εκτέλεσης του προγράμματος ή τη χρήση χώρου χρησιμοποιούν μια ακέραια παράμετρο n (που αντιπροσωπεύει το «μέγεθος» του προβλήματος). Στη συνέχεια, όταν διατυπώνουμε μια πρόταση x(n), τότε για ένα σύνολο τιμών n τέτοιες δηλώσεις είναι ισοδύναμες. Εφόσον αυτή η δήλωση ισχύει για ένα «άπειρο» σύνολο αριθμών, είναι αδύνατο να παρασχεθεί μια εξαντλητική άμεση απόδειξη. Σε τέτοιες περιπτώσεις, χρησιμοποιούνται μέθοδοι επαγωγής. Η μέθοδος επαγωγής βασίζεται στο γεγονός? ότι για οποιοδήποτε n > 1. Υπάρχει μια πεπερασμένη ακολουθία ενεργειών που ξεκινά με κάτι που είναι γνωστό ότι είναι αληθές και τελικά οδηγεί σε απόδειξη ότι το q(n) είναι αληθές. Έτσι, μια απόδειξη με επαγωγή ξεκινά με τη δήλωση ότι το q(n) είναι αληθές για n=1,2,3, κ.λπ. μέχρι κάποια σταθερά k. Στη συνέχεια αποδεικνύουμε ότι το επόμενο «βήμα» των επαγωγών q(n+1), q(n+2) ισχύει και για n > k.

Κατά την ανάλυση αλγορίθμων, τον υπολογισμό του αριθμού των πράξεων και του χρόνου εκτέλεσής τους, δεν πρέπει να λαμβάνονται υπόψη «μικρές λεπτομέρειες»· σταθεροί παράγοντες και σταθερές θα πρέπει να παραμελούνται. Στην πράξη, χρησιμοποιείται η έννοια της μεγάλης συνάρτησης ΣΧΕΤΙΚΑ ΜΕ. ας υποθέσουμε ότι υπάρχουν δύο συναρτήσεις f(n) και g(n), υποτίθεται ότι η f(n)<= O(g(n)) , т.е. функция О ограничивает сверху значения функции f, начиная с n=n0.

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

1) 20n3+7.2n2-21.78n + 5 περιγράφεται ως O(n3)

2)xn-2 + a(0) περιγράφεται ως O(xn).

2) 3*log(n) + log(log(n)) περιγράφεται ως O(log(n)).

3) Το 2100 περιγράφεται ως O(1)

4) 5/n περιγράφεται ως O(1/n).

Λάβετε υπόψη ότι η συνάρτηση o(n) περιορίζει τη συνάρτηση κόστους-στόχου χρόνου από πάνω, αλλά θα πρέπει πάντα να προσπαθείτε να επιλέγετε μια τέτοια συνάρτηση O(n) ώστε να υπάρχει μέγιστη ακρίβεια.

Οι πιο διάσημες συναρτήσεις O σε αύξουσα σειρά:

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

Ανάλογα με τον τύπο της συνάρτησης f(n), διακρίνονται οι ακόλουθες κατηγορίες πολυπλοκότητας αλγορίθμων.

Κατηγορίες πολυπλοκότητας αλγορίθμων ανάλογα με τη συνάρτηση πολυπλοκότητας
Προβολή f(n)	Χαρακτηριστικά της κατηγορίας των αλγορίθμων
	Οι περισσότερες εντολές για τις περισσότερες συναρτήσεις εκτελούνται μία ή περισσότερες φορές. Εάν όλες οι εντολές ενός προγράμματος έχουν αυτήν την ιδιότητα, τότε ο χρόνος εκτέλεσης του προγράμματος είναι σταθερός.
ημερολόγιο Ν	Όταν ο χρόνος εκτέλεσης ενός προγράμματος είναι λογαριθμικός, το πρόγραμμα γίνεται πιο αργό όσο αυξάνεται το Ν. Τέτοιοι χρόνοι εκτέλεσης συνήθως συνδέονται με προγράμματα που μειώνουν ένα μεγάλο πρόβλημα σε ένα σύνολο μικρότερων υποπροβλημάτων, μειώνοντας το μέγεθος του προβλήματος κατά κάποιο σταθερό παράγοντα σε κάθε βήμα. Η αλλαγή της βάσης δεν επηρεάζει πολύ τη μεταβολή της τιμής του λογάριθμου: n
Ν	Όταν ο χρόνος εκτέλεσης ενός προγράμματος είναι γραμμικός, συνήθως σημαίνει ότι κάθε στοιχείο εισόδου υφίσταται μικρή επεξεργασία.
Ν ημερολόγιο Ν	Ο χρόνος εκτέλεσης ανάλογος του N log N εμφανίζεται όταν ένας αλγόριθμος λύνει ένα πρόβλημα αναλύοντάς το σε μικρότερα υποπροβλήματα, λύνοντάς τα ανεξάρτητα και στη συνέχεια συνδυάζοντας τις λύσεις.
Ν 2	Όταν ο χρόνος εκτέλεσης ενός αλγορίθμου είναι τετραγωνικός, είναι χρήσιμος για πρακτική χρήση στην επίλυση σχετικά μικρών προβλημάτων. Ο τετραγωνικός χρόνος εκτέλεσης εμφανίζεται συνήθως σε αλγόριθμους που επεξεργάζονται όλα τα ζεύγη στοιχείων δεδομένων (ίσως σε έναν βρόχο διπλής ένθεσης).
Ν 3	Ένας παρόμοιος αλγόριθμος που επεξεργάζεται τριάδες στοιχείων δεδομένων (πιθανώς σε βρόχο τριπλής ένθεσης) έχει κυβικό χρόνο εκτέλεσης και είναι πρακτικά εφαρμόσιμος μόνο για μικρά προβλήματα.
2Ν	Μόνο λίγοι αλγόριθμοι με εκθετικό χρόνο εκτέλεσης έχουν πρακτικές εφαρμογές, αν και τέτοιοι αλγόριθμοι προκύπτουν φυσικά όταν επιχειρείται η άμεση επίλυση ενός προβλήματος, όπως η ωμή βία.

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

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

2. Μια κατηγορία ορθολογικών ή πολυωνυμικών αλγορίθμων, η συνάρτηση πολυπλοκότητας των οποίων προσδιορίζεται πολυωνυμικά από τις παραμέτρους εισόδου. Για παράδειγμα, Ο(Ν), Ο(Ν 2, Ο(Ν 3).

3. Μια κατηγορία υποεκθετικών αλγορίθμων με βαθμό πολυπλοκότητας O(N log N).

4.Κλάση εκθετικών αλγορίθμων με βαθμό πολυπλοκότητας O(2 N).

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

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

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

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

• Η πολυπλοκότητα της κατασκευής «Ακολουθεί» είναι το άθροισμα της πολυπλοκότητας των μπλοκ που ακολουθούν το ένα το άλλο: f=f 1 +f 2 +...+f n .
• Η πολυπλοκότητα του σχεδιασμού "Διακλάδωσης" καθορίζεται μέσω της πιθανότητας μετάβασης σε καθεμία από τις οδηγίες, που καθορίζεται από τη συνθήκη. Ταυτόχρονα, ο έλεγχος της κατάστασης έχει επίσης μια ορισμένη πολυπλοκότητα. Για τον υπολογισμό της πολυπλοκότητας της χειρότερης περίπτωσης, μπορεί να επιλεγεί το μπλοκ διακλάδωσης που έχει τη μεγαλύτερη πολυπλοκότητα· για την καλύτερη περίπτωση, μπορεί να επιλεγεί το μπλοκ με τη μικρότερη πολυπλοκότητα. f αν =f 1 +f τότε p και τότε +f άλλο (1-p τότε)
• Η πολυπλοκότητα της κατασκευής "Loop" προσδιορίζεται με τον υπολογισμό της συνθήκης τερματισμού του βρόχου (συνήθως της τάξης 0(1)) και του γινόμενου του αριθμού των ολοκληρωμένων επαναλήψεων του βρόχου από τον μεγαλύτερο δυνατό αριθμό λειτουργιών του σώματος του βρόχου. Εάν χρησιμοποιούνται ένθετοι βρόχοι, η πολυπλοκότητά τους πολλαπλασιάζεται.

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

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

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

Βιβλιοθήκη προγραμματιστή

"Εάν η αποσφαλμάτωση είναι μια διαδικασία αφαίρεσης σφαλμάτων, τότε ο προγραμματισμός θα πρέπει να είναι μια διαδικασία εισαγωγής τους"

E. Dijkstra

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

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

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

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

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

Και τρίτον, η μελέτη αλγορίθμων είναι επίσης μια απίστευτα ενδιαφέρουσα διαδικασία που αναπτύσσει τις μαθηματικές μας ικανότητες και τη λογική σκέψη.

1.3. Αποδοτικότητα αλγορίθμων

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

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

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

Όπως σημειώθηκε παραπάνω, αυτή η ενότητα θα επικεντρωθεί στην εργασία ταξινόμησης. Ο πρώτος αλγόριθμος που θα εξεταστεί, η ταξινόμηση συμπερίληψης, απαιτεί χρόνο για να εργαστεί, η ποσότητα του οποίου εκτιμάται ως c 1 n 2, όπου n είναι το μέγεθος των δεδομένων εισόδου (αριθμός στοιχείων στην ακολουθία που πρόκειται να ταξινομηθούν), c Το 1 είναι κάποια σταθερά. Αυτή η έκφραση δείχνει πώς ο χρόνος εκτέλεσης του αλγορίθμου εξαρτάται από τον όγκο των δεδομένων προέλευσης. Στην περίπτωση της ταξινόμησης συμπερίληψης, αυτή η εξάρτηση είναι τετραγωνική. Ο δεύτερος αλγόριθμος, merge sort, απαιτεί χρόνο, το ποσό του οποίου υπολογίζεται ως 2 nLog 2 n. Συνήθως, η σταθερά ταξινόμησης συμπερίληψης είναι μικρότερη από τη σταθερά ταξινόμησης συγχώνευσης, δηλαδή, το c12 αυξάνεται ταχύτερα καθώς το n αυξάνεται από τη συνάρτηση Ilog 2 n. Και για κάποια τιμή n = n 0 θα επιτευχθεί μια στιγμή όταν η επίδραση της διαφοράς στις σταθερές παύει να έχει σημασία και στο μέλλον η συνάρτηση c 2 nLog 2 n θα είναι μικρότερη από c 1 n 2 για οποιοδήποτε n > n 0.

Για να το αποδείξετε αυτό, σκεφτείτε δύο υπολογιστές - τον Α και τον Β. Ο υπολογιστής Α είναι πιο γρήγορος και εκτελεί τον αλγόριθμο ταξινόμησης και ο υπολογιστής Β είναι πιο αργός και εκτελεί τον αλγόριθμο ταξινόμησης συγχώνευσης. Και οι δύο υπολογιστές πρέπει να ταξινομήσουν ένα σύνολο που αποτελείται από ένα εκατομμύριο αριθμούς. Ας πούμε ότι ο υπολογιστής Α εκτελεί ένα δισεκατομμύριο λειτουργίες ανά δευτερόλεπτο και ο υπολογιστής Β μόνο δέκα εκατομμύρια, υπάρχει το Α που τρέχει 100 φορές πιο γρήγορα από το Β. Για να γίνει πιο αισθητή η διαφορά, ας πούμε ότι ο κώδικας για τη μέθοδο ενεργοποίησης γράφτηκε από τον καλύτερο προγραμματιστής στον κόσμο χρησιμοποιώντας οδηγίες στον επεξεργαστή και για να ταξινομήσετε n αριθμούς με αυτόν τον αλγόριθμο πρέπει να εκτελέσετε 2n 2 λειτουργίες (δηλαδή C 1 = 2). Η ταξινόμηση συγχώνευσης στον υπολογιστή Β γράφτηκε από έναν αρχάριο προγραμματιστή χρησιμοποιώντας μια γλώσσα υψηλού επιπέδου και ο κώδικας που προκύπτει απαιτεί 50nlog 2 n λειτουργίες (δηλαδή c 2 = 50). Έτσι, για να ταξινομήσει ένα εκατομμύριο αριθμούς, θα χρειαζόταν ο υπολογιστής Α

και στον υπολογιστή Β -

Επομένως, η χρήση κώδικα του οποίου ο χρόνος εκτέλεσης αυξάνεται πιο αργά, ακόμη και με κακό υπολογιστή και κακό μεταγλωττιστή, απαιτεί μια τάξη μεγέθους λιγότερο χρόνο CPU! Για την ταξινόμηση 10.000.000 ψηφίων, το πλεονέκτημα της ταξινόμησης συγχώνευσης γίνεται ακόμη πιο αισθητό: ενώ η ταξινόμηση συμπερίληψης απαιτεί περίπου 2,3 ημέρες για μια τέτοια εργασία, στη συνέχεια για την ταξινόμηση συγχώνευσης χρειάζονται λιγότερο από 20 λεπτά. Ο γενικός κανόνας είναι ότι όσο μεγαλύτερος είναι ο αριθμός των στοιχείων προς ταξινόμηση, τόσο μεγαλύτερο είναι το πλεονέκτημα της ταξινόμησης συγχώνευσης. Το παραπάνω παράδειγμα δείχνει ότι οι αλγόριθμοι, όπως το λογισμικό υπολογιστή, είναι τεχνολογία. Η συνολική απόδοση του συστήματος εξαρτάται τόσο από την αποτελεσματικότητα του αλγορίθμου όσο και από την ισχύ του υλικού.

Έτσι, εξετάζονται διάφορες επιλογές για υπολογιστικές μηχανές, από τις απλούστερες μηχανές Turing έως ένα ομοιογενές υπολογιστικό περιβάλλον. Όλα αυτά μπορούν να χρησιμοποιηθούν για την επίλυση των προβλημάτων για τα οποία υπάρχει αλγόριθμος. Με βάση αυτά τα μοντέλα, κατασκευάζονται πιο εξειδικευμένα μοντέλα υπολογισμού, και συγκεκριμένα: αριθμητικά προγράμματα χωρίς διακλάδωση, υπολογισμός bitwise, δυαδικός υπολογισμός διανυσμάτων και δέντρα αποφάσεων.

Οι αλγόριθμοι έχουν τα ακόλουθα χαρακτηριστικά:

α) πολυπλοκότητα·

β) ένταση εργασίας.

γ) αξιοπιστία κ.λπ.

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

Ο χρόνος που χρειάζεται ένας αλγόριθμος ως συνάρτηση του μεγέθους του προβλήματος ονομάζεται χρονική πολυπλοκότητααυτόν τον αλγόριθμο. Η συμπεριφορά αυτής της πολυπλοκότητας στο όριο καθώς αυξάνεται το μέγεθος του προβλήματος ονομάζεται ασυμπτωτική χρονική πολυπλοκότητα. Ομοίως ορίζεται χωρητική πολυπλοκότηταΚαι πολυπλοκότητα ασυμπτωτικής ικανότητας.

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

4.1.1. Μηχανές πλαισίου και πλαισίου*

Εξετάστε δύο αυτοκίνητα:

1. Μηχανήματα με τυχαία πρόσβαση στη μνήμη (μηχάνημα διεύθυνσης ίσης πρόσβασης - RAM) μοντελοποιούν έναν υπολογιστή με έναν αθροιστή, στον οποίο οι οδηγίες του προγράμματος δεν μπορούν να αλλάξουν μόνες τους.

2. Το αποθηκευμένο μοντέλο προγράμματος είναι ένα μηχάνημα με τυχαία πρόσβαση στη μνήμη και δυνατότητα τροποποίησης οδηγιών (RAM*).

Εικ.2.9 Δομή μηχανών RAM (RAM*)

Για τη μνήμη RAM, το πρόγραμμα δεν είναι γραμμένο στη μνήμη, επομένως το πρόγραμμα δεν τροποποιείται από μόνο του. Ένα πρόγραμμα είναι μια ακολουθία εντολών με ετικέτα. Υπάρχουν αριθμητικές εντολές, εντολές εισόδου/εξόδου, έμμεσες οδηγίες διευθυνσιοδότησης και οδηγίες διακλάδωσης. Όλοι οι υπολογισμοί εκτελούνται στον καταχωρητή r 0 (αθροιστής), ο οποίος, όπως κάθε άλλος καταχωρητής μνήμης, μπορεί να αποθηκεύσει έναν αυθαίρετο ακέραιο. Κάθε εντολή αποτελείται από δύο μέρη - έναν κωδικό λειτουργίας και μια διεύθυνση. Οι εντολές PAM είναι ένα υποσύνολο εντολών γλώσσας Assembly. αυτό το υποσύνολο μπορεί να επεκταθεί κατά βούληση, αλλά η σειρά πολυπλοκότητας των εργασιών δεν θα αλλάξει.

Ο τελεστής μπορεί να είναι ένας από τους παρακάτω τύπους:

1. =iσημαίνει ολόκληρος ο ίδιος ο αριθμός Εγώκαι ονομάζεται κυριολεκτική?

2. Εγώ- καταχωρήστε τα περιεχόμενα Εγώ (Εγώπρέπει να είναι μη αρνητικό).

3. *Εγώσημαίνει έμμεση διεύθυνση, δηλαδή η τιμή του τελεστή είναι τα περιεχόμενα του καταχωρητή ι,Οπου ι- ένας ακέραιος αριθμός που βρίσκεται στο μητρώο Εγώ;Αν ι<0, το αυτοκίνητο σταματά.

Μπορείτε να προσδιορίσετε την αξία του προγράμματος Rχρησιμοποιώντας δύο αντικείμενα: μια αντιστοίχιση c από ένα σύνολο μη αρνητικών ακεραίων σε ένα σύνολο ακεραίων και έναν «μετρητή εντολών», ο οποίος καθορίζει την επόμενη εντολή που θα εκτελεστεί. Η συνάρτηση γ είναι οθόνη μνήμης,και συγκεκριμένα γ(i)-ακέραιος που περιέχεται στον αριθμό μητρώου Εγώ (περιεχόμενοκανω ΕΓΓΡΑΦΗ Εγώ).

Στην αρχή σ(i)=0για όλα Εγώ 0 , ο μετρητής προγράμματος έχει ρυθμιστεί στην πρώτη εντολή στο P και η ταινία εξόδου είναι άδεια. Μετά την εκτέλεση κη ομάδα από Rο μετρητής μεταβαίνει αυτόματα σε (k+1)-η (δηλαδή στην επόμενη) εντολή, αν κ-Η ομάδα μου δεν ήταν μια ομάδα όπως το JUMP, HALT, JGTZ και τα παρόμοια.

Το πρόγραμμα RAM* βρίσκεται σε καταχωρητές μνήμης. Κάθε εντολή RAM* καταλαμβάνει δύο διαδοχικούς καταχωρητές μνήμης: ο πρώτος καταχωρητής περιέχει τον κωδικό λειτουργίας, ο δεύτερος - τη διεύθυνση. Το σύνολο εντολών για τη μνήμη RAM* συμπίπτει με το αντίστοιχο σύνολο για τη μνήμη RAM σε όλα εκτός από την έμμεση διευθυνσιοδότηση, η οποία αποκλείεται: Η RAM* μπορεί να προσομοιώσει την έμμεση διευθυνσιοδότηση αλλάζοντας οδηγίες κατά την εκτέλεση του προγράμματος.

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

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

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

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

Οι κύριες λειτουργίες είναι:

l O(1) - μια τέτοια συνάρτηση πολυπλοκότητας υποδεικνύει ότι ο χρόνος εκτέλεσης του προγράμματος είναι σταθερός για οποιαδήποτε αρχικά δεδομένα.

l O(N) - ο αριθμός των πράξεων αυξάνεται αναλογικά με το N (εδώ το N μπορεί να είναι είτε μια παράμετρος εργασίας είτε ο αριθμός των στοιχείων στον πίνακα).

l O(log N) - ο αριθμός των πράξεων αυξάνεται ανάλογα με τον λογάριθμο του N (αυτή είναι ακριβώς η πολυπλοκότητα, για παράδειγμα, της μεθόδου των μισών κατά την αναζήτηση ενός στοιχείου σε έναν διατεταγμένο πίνακα). Καθώς το N αυξάνεται κατά τάξη μεγέθους, ο αριθμός των πράξεων αλλάζει κατά μία. Η βάση του λογάριθμου συνήθως δεν προσδιορίζεται· μας ενδιαφέρει η φύση της ανάπτυξης (γρήγορη/αργή) και όχι η ακριβής τιμή του χρόνου.

l O(N2) - ο αριθμός των πράξεων αυξάνεται ανάλογα με το τετράγωνο του N. Γενικά, μπορεί να είναι O(Nk) ανάλογα με την πολυπλοκότητα του προβλήματος.

l O(N!) - ο αριθμός των πράξεων αυξάνεται ανάλογα με το παραγοντικό N.

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

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

Παράδειγμα: ας υπολογίσουμε την πολυπλοκότητα ενός προγράμματος που εισέρχεται σε έναν πίνακα από το πληκτρολόγιο και βρίσκει το μεγαλύτερο στοιχείο σε αυτόν.

Ας προσθέσουμε τον αριθμό των πράξεων N+(N-1)+1=2N. Δηλαδή, υπάρχει μια τέτοια σταθερά που για οποιοδήποτε N ο αριθμός των πράξεων δεν υπερβαίνει το CN. Επομένως, η πολυπλοκότητα του αλγορίθμου είναι O(N).

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

Ο αλγόριθμος αποτελείται από τα ακόλουθα βήματα:

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

Στην καλύτερη περίπτωση, αυτός ο αλγόριθμος θα απαιτήσει N+2 πράξεις (είσοδος ολόκληρου του πίνακα, μία σύγκριση, έξοδος), στη χειρότερη περίπτωση (όταν δεν υπάρχει τέτοιο στοιχείο - 2N+1 πράξεις). Εάν το N είναι ένας μεγάλος αριθμός, για παράδειγμα περίπου 106, τότε η ενότητα μπορεί να παραμεληθεί. Επομένως, η πολυπλοκότητα του αλγορίθμου είναι O(N).

Παράδειγμα: ας προσδιορίσουμε τη συνάρτηση πολυπλοκότητας ενός αλγόριθμου κρυπτογράφησης λέξης μήκους L χρησιμοποιώντας τη μέθοδο αντικατάστασης. Ας υπάρχει ένας πίνακας στον οποίο για κάθε χαρακτήρα του αλφαβήτου αναγράφεται ο χαρακτήρας με τον οποίο πρέπει να αντικατασταθεί. Ας υποδηλώσουμε τον αριθμό των γραμμάτων του αλφαβήτου S.

Ο αλγόριθμος αποτελείται από τα ακόλουθα βήματα:

Εισαγωγή βρόχου λέξης (μία λειτουργία) σε όλους τους χαρακτήρες

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

2. έξοδος του συμβόλου που βρέθηκε

Τέλος του κύκλου

Ο συνολικός αριθμός πράξεων είναι 1+(S+1)*L. Στην περίπτωση των αρκετά μεγάλων μονάδων S και L μπορούν να παραμεληθούν, αποδεικνύεται ότι η συνάρτηση πολυπλοκότητας αυτού του αλγορίθμου είναι O(S*L).

Παράδειγμα: ας ορίσουμε τη συνάρτηση πολυπλοκότητας του αλγορίθμου για τη μετατροπή του φυσικού αριθμού N στο δυαδικό σύστημα αριθμών (χωρίς πράξεις εισαγωγής και εξόδου δεδομένων).

Ο αλγόριθμος αποτελείται από τα ακόλουθα βήματα:

Κάντε βρόχο μέχρι το αποτέλεσμα της διαίρεσης ενός αριθμού με το 2 να είναι 0

1. Διαιρέστε τον αριθμό με το 2 και θυμηθείτε το υπόλοιπο

2. πάρτε το αποτέλεσμα της διαίρεσης ως νέο αριθμό

Τέλος του κύκλου

Ο συνολικός αριθμός πράξεων δεν υπερβαίνει το 1+log2N. Επομένως, αυτός ο αλγόριθμος έχει πολυπλοκότητα O(log N).

Εάν ένα πρόγραμμα αποτελείται από πολλά μέρη με διαφορετικές συναρτήσεις πολυπλοκότητας, τότε ΟΗ μεγαλύτερη συνάρτηση πολυπλοκότητας θα «απορροφήσει» τις μικρότερες. Για παράδειγμα, εάν κάνετε εισαγωγή πίνακα O(N), ταξινόμηση O(N2) και έξοδο O(N) του ταξινομημένου πίνακα, τότε μπορείτε να πείτε ότι ολόκληρο το πρόγραμμα έχει πολυπλοκότητα O(N2).

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

Ερωτήσεις

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

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

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

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

4. Προσδιορίστε τη συνάρτηση πολυπλοκότητας του αλγορίθμου για την προσθήκη δύο φυσικών αριθμών σε μια στήλη (έστω Α ο αριθμός των ψηφίων του πρώτου αριθμού, Β ο αριθμός των ψηφίων του δεύτερου).

5. Προσδιορίστε τη συνάρτηση πολυπλοκότητας του αλγορίθμου για τον πολλαπλασιασμό δύο φυσικών αριθμών σε μια στήλη.