Που εργάζονται με αλγοριθμικές λειτουργίες - ανδρείκελα

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

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

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

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

Big O

συμβολισμός και συχνά συναντάτε αυτό το μικρό σύνολο λειτουργιών (τοποθετείται σε παρένθεση και προηγείται κεφαλαίο O >) που παριστάνουν την απόδοση των αλγορίθμων. Το σχήμα δείχνει την ανάλυση ενός αλγορίθμου. Ένα καρτεσιανό σύστημα συντεταγμένων μπορεί να αντιπροσωπεύει τη λειτουργία του όπως μετράται με προσομοίωση RAM, όπου η τετμημένη (η συντεταγμένη x) είναι το μέγεθος της εισόδου και η σειρά (η συντεταγμένη y) επακόλουθο αριθμό ενεργειών. Μπορείτε να δείτε τρεις αντιπροσωπευτικές καμπύλες. Το μέγεθος εισαγωγής έχει σημασία. Ωστόσο, η ποιότητα έχει επίσης σημασία (για παράδειγμα, κατά την παραγγελία προβλημάτων, είναι πιο γρήγορο να παραγγείλετε μια εισροή η οποία είναι ήδη σχεδόν διατεταγμένη).Συνεπώς, η ανάλυση παρουσιάζει μια χειρότερη περίπτωση, f

1 (n), μια μέση περίπτωση, f 2 μια καλύτερη περίπτωση, f 3 (n). Παρόλο που η μέση περίπτωση μπορεί να σας δώσει μια γενική ιδέα, αυτό που σας ενδιαφέρει είναι η χειρότερη περίπτωση, επειδή μπορεί να προκύψουν προβλήματα όταν ο αλγόριθμός σας δυσκολεύεται να φτάσει σε μια λύση. Η συνάρτηση Big O είναι αυτή που μετά από μια ορισμένη τιμή n0 (το κατώφλι για την εξέταση μιας μεγάλης εισόδου) οδηγεί πάντοτε σε έναν μεγαλύτερο αριθμό λειτουργιών που έχουν την ίδια είσοδο από τη συνάρτηση worst-case > f1. Έτσι, η λειτουργία Big O είναι ακόμα πιο απαισιόδοξη από αυτή που αντιπροσωπεύει τον αλγόριθμό σας, έτσι ώστε ανεξάρτητα από την ποιότητα της εισόδου, μπορείτε να είστε σίγουροι ότι τα πράγματα δεν μπορούν να χειροτερεύσουν.

Πολυπλοκότητα ενός αλγορίθμου σε περίπτωση καλύτερης, μέσης και χειρότερης περίπτωσης εισαγωγής. Πολλές πιθανές λειτουργίες μπορούν να οδηγήσουν σε χειρότερα αποτελέσματα, αλλά η επιλογή των λειτουργιών που προσφέρει η σημείωση Big Ο που μπορείτε να χρησιμοποιήσετε είναι περιορισμένη επειδή σκοπός της είναι να απλοποιήσει τη μέτρηση της πολυπλοκότητας προτείνοντας ένα πρότυπο. Συνεπώς, αυτή η ενότητα περιέχει μόνο τις λίγες λειτουργίες που αποτελούν μέρος της σημαντικής εγγραφής Big O. Η λίστα που ακολουθεί τις περιγράφει με αυξανόμενη σειρά πολυπλοκότητας: Συνεχής πολυπλοκότητα O (1): Την ίδια στιγμή, ανεξάρτητα από την ποσότητα εισόδου που παρέχετε. Στο τέλος, είναι ένας σταθερός αριθμός λειτουργιών, ανεξάρτητα από το πόσο χρόνο είναι τα δεδομένα εισόδου. Αυτό το επίπεδο πολυπλοκότητας είναι αρκετά σπάνιο στην πράξη. Λογαριθμική πολυπλοκότητα O (log n):

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

Γραμμική πολυπλοκότητα O (n):

• Οι λειτουργίες αυξάνονται με την είσοδο σε αναλογία 1: 1. Ένας τυπικός αλγόριθμος είναι η επανάληψη, η οποία είναι όταν σαρώνετε την είσοδο μία φορά και εφαρμόζετε μια λειτουργία σε κάθε στοιχείο της. Γραμμική πολυπλοκότητα O (n log n):
• Η πολυπλοκότητα είναι ένα μίγμα μεταξύ λογαριθμικής και γραμμικής πολυπλοκότητας. Είναι χαρακτηριστικό για ορισμένους έξυπνους αλγόριθμους που χρησιμοποιούνται για την παραγγελία δεδομένων, όπως το Mergesort, το Heapsort και το Quicksort. Τετραγωνική πολυπλοκότητα O (n
• 2 ):
• Οι πράξεις αναπτύσσονται ως ένα τετράγωνο του αριθμού των εισροών. Όταν έχετε μια επανάληψη μέσα σε μια άλλη επανάληψη (ένθετες επαναλήψεις, στην επιστήμη των υπολογιστών), έχετε τετραγωνική πολυπλοκότητα. Για παράδειγμα, έχετε μια λίστα με ονόματα και, για να βρείτε τα πιο παρόμοια, συγκρίνετε κάθε όνομα με όλα τα άλλα ονόματα. Μερικοί λιγότερο αποτελεσματικοί αλγόριθμοι παραγγελίας παρουσιάζουν μια τέτοια πολυπλοκότητα: είδος φυσαλίδας, είδος επιλογής και είδος εισαγωγής. Αυτό το επίπεδο πολυπλοκότητας σημαίνει ότι οι αλγόριθμοί σας μπορούν να εκτελούνται για ώρες ή ακόμη και ημέρες πριν φθάσουν σε μια λύση. Κυβική πολυπλοκότητα O (n
• 3 ^): Οι λειτουργίες αναπτύσσονται ακόμα ταχύτερα από την τετραγωνική πολυπλοκότητα, επειδή τώρα έχετε πολλές επαναλαμβανόμενες επαναλήψεις. Όταν ένας αλγόριθμος έχει αυτή τη σειρά πολυπλοκότητας και πρέπει να επεξεργαστείτε μια μέτρια ποσότητα δεδομένων (100, 000 στοιχεία), ο αλγόριθμός σας μπορεί να τρέξει για χρόνια.Όταν έχετε πολλές λειτουργίες που είναι μια δύναμη της εισόδου, είναι συνηθισμένο να ανατρέχετε στον αλγόριθμο ως που εκτελείται σε πολυωνυμικό χρόνο.
• Εκθετική πολυπλοκότητα O (2 ⁿ ): Ο αλγόριθμος λαμβάνει διπλάσιο αριθμό προηγούμενων λειτουργιών για κάθε νέο στοιχείο που προστέθηκε. Όταν ένας αλγόριθμος έχει αυτή την πολυπλοκότητα, ακόμη και μικρά προβλήματα μπορεί να πάρουν για πάντα. Πολλοί αλγόριθμοι που κάνουν εξαντλητικές αναζητήσεις έχουν εκθετική πολυπλοκότητα. Ωστόσο, το κλασικό παράδειγμα αυτού του επιπέδου πολυπλοκότητας είναι ο υπολογισμός των αριθμών του Fibonacci. Παραγοντική πολυπλοκότητα O (n!):
• Ένας πραγματικός εφιάλτης πολυπλοκότητας λόγω του μεγάλου αριθμού πιθανών συνδυασμών μεταξύ των στοιχείων. Φανταστείτε: Εάν η είσοδος σας είναι 100 αντικείμενα και μια λειτουργία στον υπολογιστή σας διαρκεί 10 ^-6 δευτερόλεπτα (μια λογική ταχύτητα για κάθε υπολογιστή, σήμερα), θα χρειαστείτε περίπου 10 140
• χρόνια να ολοκληρώσει επιτυχώς την εργασία (ένα αδύνατο χρονικό διάστημα από την ηλικία του σύμπαντος εκτιμάται ότι είναι 10 14 ^{χρόνια). Ένα διάσημο πρόβλημα παράγοντα πολυπλοκότητας είναι το πρόβλημα των μετακινούμενων πωλητών, στο οποίο ένας πωλητής πρέπει να βρει τη συντομότερη διαδρομή για να επισκεφτεί πολλές πόλεις και να επιστρέψει στην αρχική πόλη.}