Αλγόριθμοι και πώς να αναλύσουμε την πολυπλοκότητά τους

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

Ας ανακαλύψουμε! :)

Τι είναι ένας αλγόριθμος;

Ένα σύνολο βημάτων που απαιτούνται για την εκτέλεση μιας εργασίας.

Τα προγράμματα υπολογιστών δεν είναι τα μόνα που εκτελούν αλγόριθμους, αλλά εκτελούνται και εφαρμόζονται από εμάς τους ανθρώπους.

Για παράδειγμα, σκεφτήκατε τον αλγόριθμο που εκτελεί τις ακόλουθες εργασίες;

  • Βούρτσισε τα δόντια σου
  • Κάνε ένα μπάνιο
  • Μάγειρας
  • Οδηγήστε για εργασία από το σπίτι

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

  1. Πάρτε στο αυτοκίνητό μου
  2. Οδηγήστε στο σπίτι ενός φίλου για να κάνετε μια βόλτα
  3. Πηγαίνετε στο γραφείο όπου δουλεύω
  4. Πάρκο το αυτοκίνητό μου στο γκαράζ

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

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

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

Για παράδειγμα, πώς θα έπρεπε ο αλγόριθμος που χρησιμοποιείται από το Waze και τους Χάρτες Google, που υπολογίζει την καλύτερη διαδρομή μεταξύ δύο τοποθεσιών; Τι γίνεται με τον αλγόριθμο του Netflix που προτείνει ταινίες και σειρές βασισμένες σε αυτό που έχετε παρακολουθήσει;

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

Τι είναι η πολυπλοκότητα του αλγορίθμου;

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

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

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

Και γιατί αυτή η ανάλυση είναι σημαντική;

  • Για να προσδιορίσετε ποιο αλγόριθμο είναι πιο αποτελεσματικό.
  • Να είναι σε θέση να αναπτύξουν πιο αποτελεσματικούς αλγορίθμους.
  • Να είναι σε θέση να αναλύσει αν η βιβλιοθήκη ενός αλγορίθμου, ή ακόμα και η πραγματική γλώσσα, είναι αποτελεσματική.

Συνοψίζοντας, η αποτελεσματικότητα είναι το σημείο!

Χρόνος Πολυπλοκότητα

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

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

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

Το αποτέλεσμα μιας ανάλυσης εκφράζεται ως εξής:

([συνάρτηση που εκφράζει το χρόνο]) = [Άθροισμα των μονάδων ώρας]

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

Η πρώτη συνάρτηση προσθέτει δύο ολόκληρους αριθμούς:

Μπορούμε να δούμε ότι, για την εν λόγω εργασία, ο εφαρμοσμένος αλγόριθμος εκτελεί μόνο ένα βήμα: το άθροισμα δύο αριθμών. Δεδομένου ότι αποδίδουμε μια τιμή για κάθε βήμα, το αποτέλεσμα είναι f (n) = 1.

Ας δούμε το επόμενο παράδειγμα, που είναι ένας αλγόριθμος που διαιρεί έναν ακέραιο με έναν άλλο ακέραιο αριθμό:

Παρά το γεγονός ότι είναι μια μαθηματική λειτουργία παρόμοια με την άθροιση, ο αλγόριθμος περιέχει περισσότερα βήματα επειδή χρειάζεται να ελέγξει εάν ο διαιρέτης είναι 0. αν συμβαίνει αυτό, η διαίρεση δεν θα πραγματοποιηθεί. Δεδομένου ότι έχουμε συνολικά τέσσερα βήματα και κάθε μία από αυτές έχει μια τιμή 1, το αποτέλεσμα είναι f (n) = 4.

Ο επόμενος αλγόριθμος συνοψίζει όλα τα στοιχεία μιας λίστας ακεραίων:

Σε αυτόν τον αλγόριθμο, ένα από τα βήματα περιλαμβάνει για, μια εντολή για επανάληψη. αυτό σημαίνει ότι ο κώδικας μέσα στο for θα εκτελεστεί αρκετές φορές. Δεδομένου ότι ο αριθμός των εκτελέσεων εξαρτάται από το μέγεθος των δεδομένων, αποδίδουμε την τιμή του n ως μονάδα χρόνου. Το αποτέλεσμα είναι f (n) = 2n + 3.

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

Ως αποτέλεσμα έχουμε f (n) = 2n² + 2n + 3.

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

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

Για παράδειγμα, ποιος είναι ο κυρίαρχος όρος του αθροίσματος του τρίτου αλγορίθμου;

f (n) = 2n + 3

Σε αυτή την περίπτωση, ο κυρίαρχος όρος στο 2 * n, και θα εξηγήσω γιατί!

Σε κάθε περίπτωση όπου το n είναι μεγαλύτερο από 1 (n> 1), το προϊόν (το αποτέλεσμα του πολλαπλασιασμού) θα είναι ήδη πολύ υψηλότερο από το δεύτερο όριο του ποσού.

Δοκιμάστε κάτι: αντικαταστήστε το n με οποιοδήποτε ακέραιο αριθμό μεγαλύτερο από 1 και εκτελέστε τον πολλαπλασιασμό.

Τι γίνεται με τον κυρίαρχο όρο του αθροίσματος του τελευταίου αλγορίθμου;

f (n) = 2n2 + 2n + 3

Σε αυτή την περίπτωση, ο κυρίαρχος όρος είναι 2 * n², διότι όταν n> 1, το προϊόν θα είναι πάντοτε μεγαλύτερο από το δεύτερο και τρίτο όρο του ποσού. Πάρε μπροστά, δοκιμάστε το!

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

Αυτό είναι όπου η σειρά της πολυπλοκότητας μπαίνει στο παιχνίδι, επίσης γνωστή ως Notation-O ή Big-O.

Σημείωση Big-O

Χρησιμοποιείται για την ταξινόμηση ενός αλγορίθμου λαμβάνοντας υπόψη τον ρυθμό ανάπτυξης των εργασιών καθώς αυξάνεται ο αριθμός των επεξεργασμένων στοιχείων.

Η σημείωση Big-O ορίζει επίσης μια συνάρτηση που εκφράζει την πολυπλοκότητα ενός αλγορίθμου. Για το σκοπό αυτό, το n χρησιμοποιείται ως συνάρτηση του γράμματος O.

Οι πιο συνηθισμένες κατηγορίες είναι:

  • O (1) - Συνεχής, ο αριθμός των πράξεων δεν αυξάνεται καθώς ο αριθμός των στοιχείων αυξάνεται
  • O (log n) - Logarithmic, ο αριθμός των πράξεων είναι μικρότερος από τον αριθμό των στοιχείων
  • O (n) - Γραμμικός, ο αριθμός των πράξεων αυξάνεται αναλογικά με τον αριθμό των στοιχείων
  • O (n²) Τετραγωνικό, ο αριθμός των λειτουργιών θα είναι μεγαλύτερος από τον αριθμό των στοιχείων
  • O (2 ^ n) - Exponencial, ο αριθμός των πράξεων αυξάνεται ταχέως σε σύγκριση με τον αριθμό των στοιχείων
  • O (n!) - Factorial, ο αριθμός των λειτουργιών αυξάνεται πολύ, πολύ γρήγορα, ακόμα και για ένα μικρό αριθμό στοιχείων

Παρακάτω, έχουμε ένα γραφικό που απεικονίζει τον ρυθμό ανάπτυξης των πράξεων x Ποσότητα στοιχείων:

Το γραφικό ταξινομείται ως εξής:

  • Η κόκκινη ζώνη είναι τρομερή, αποφύγετε!
  • Πορτοκαλί ζώνη είναι κακό, αποφύγετε επίσης!
  • Η κίτρινη ζώνη είναι δίκαιη, λογική!
  • Η ανοιχτό πράσινη ζώνη είναι καλή, δροσερή!
  • Η σκοτεινο-πράσινη ζώνη είναι εξαιρετική, Συγχαρητήρια!

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

Ο πρώτος αλγόριθμος είχε σαν αποτέλεσμα f (n) = 1; που σημαίνει ότι, ανεξάρτητα από την αύξηση των στοιχείων, ο αλγόριθμος εκτελεί μόνο μία ενέργεια. Έτσι, μπορούμε να ταξινομήσουμε τον αλγόριθμο ως Constant - O (1).

Ο δεύτερος αλγόριθμος είχε σαν αποτέλεσμα f (n) = 4; πράγμα που σημαίνει ότι ανεξάρτητα από την αύξηση των στοιχείων, ο αλγόριθμος θα εκτελέσει τέσσερις λειτουργίες. Έτσι, μπορούμε να ταξινομήσουμε αυτόν τον αλγόριθμο ως Constant - O (1).

Το αποτέλεσμα του τρίτου αλγορίθμου ήταν f (n) = 2n + 3. που σημαίνει ότι ο αριθμός των πράξεων θα αυξηθεί αναλογικά με τον αριθμό των στοιχείων, βλέποντας πώς το n χρησιμεύει ως μεταβλητή σε αυτή τη λειτουργία. Έτσι, μπορούμε να ορίσουμε αυτόν τον αλγόριθμο ως Γραμμικό - O (n).

Το αποτέλεσμα του τελευταίου αλγορίθμου είχε σαν αποτέλεσμα το f (n) = 2n² + 2n + 3, που σημαίνει ότι ο αριθμός των πράξεων θα αυξηθεί περισσότερο από τον αριθμό των στοιχείων. Σε αυτή την περίπτωση, το n χρησιμεύει επίσης ως μεταβλητή, αλλά αυξάνεται στη δεύτερη ισχύ (τετράγωνο). Έτσι, μπορούμε να ορίσουμε αυτόν τον αλγόριθμο ως Quadratic - O (n²).

Ο παρακάτω πίνακας απεικονίζει την αύξηση του αριθμού των πράξεων, καθώς σχετίζεται με την αύξηση του αριθμού των στοιχείων.

Παρατηρήστε ότι σε έναν εκθετικό αλγόριθμο, 16 στοιχεία θα είχαν ως αποτέλεσμα τουλάχιστον 65,5536 πράξεις. Αρκετά ενοχλητικό, σωστά;

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

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

  • Οι αλγόριθμοι που δεν έχουν επαναληπτικό βρόχο τείνουν να είναι σταθεροί - O (1)
  • Οι αλγόριθμοι που έχουν επαναλαμβανόμενες θηλιές, εφόσον δεν είναι ένθετοι, τείνουν να είναι γραμμικές - O (n)
  • Οι αλγόριθμοι που έχουν δύο βρόχους επαναλήψεως τείνουν να είναι τετραγωνικοί - O (n2)
  • Η άμεση πρόσβαση στο δείκτη ενός πίνακα είναι συνήθως O (1) (σταθερή)
  • Οι μέθοδοι επέκτασης λίστας είναι κατά μέσο όρο O (n). Για παράδειγμα: οποιοδήποτε, άθροισμα και φίλτρο.
  • Αλγόριθμοι ταξινόμησης όπως η Ταξινόμηση Bubble, η Ταξινόμηση Εισαγωγής και η Ταξινόμηση επιλογής είναι συνήθως O (n²).

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

Ελπίζω να έχω εκπληρώσει το στόχο αυτής της θέσης, που ήταν να δώσω μια επισκόπηση των αλγορίθμων και της ανάλυσης τους χρησιμοποιώντας τις μεθόδους Frequency Count και Big-O.

Έχω αφήσει κάποιες αναφορές παρακάτω ως πρόσθετο υλικό ανάγνωσης!

Βιβλιογραφικές αναφορές:

Vídeos 1 έως 1.7

Θέλετε να φέρει την καινοτομία στην αγορά δανείων μέσω της τεχνολογίας; Ψάχνουμε πάντα νέους ανθρώπους να ενταχθούν στο πλήρωμά μας!

Δείτε τα ανοίγματα μας εδώ.