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