Αλγόριθμοι στα απλά αγγλικά: πολυπλοκότητα χρόνου και σημειογραφία Big-O

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

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

Λοιπόν, τι είναι αλγόριθμος, ούτως ή άλλως;

Με απλά λόγια, ένας αλγόριθμος είναι μια σειρά από περιορισμένα βήματα, τα οποία ακολουθείτε για την επίτευξη κάποιου στόχου ή την παραγωγή κάποιου αποτελέσματος. Ας πάρουμε για παράδειγμα τη συνταγή της γιαγιάς σας για το ψήσιμο ενός κέικ. Περιμένετε, αυτό μετράει ως αλγόριθμος; Σίγουρα το κάνει!

function BakeCake(flavor, icing){ " 1. Heat Oven to 350 F 2. Mix flour, baking powder, salt 3. Beat butter and sugar until fluffy 4. Add eggs. 5. Mix in flour, baking powder, salt 6. Add milk and " + flavor + " 7. Mix further 8. Put in pan 9. Bake for 30 minutes 10." + if(icing === true) return 'add icing' + " 10. Stuff your face " } BakeCake('vanilla', true) => deliciousness

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

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

Το κύριο ερώτημα λοιπόν είναι: πώς θα αναλύσουμε ποιες λύσεις είναι πιο αποτελεσματικές;

Μαθηματικά για τη διάσωση! Η ανάλυση της πολυπλοκότητας του χρόνου στον προγραμματισμό είναι απλώς ένας εξαιρετικά απλοποιημένος μαθηματικός τρόπος ανάλυσης του χρόνου που θα χρειαστεί ένας αλγόριθμος με δεδομένο αριθμό εισόδων (n) για την ολοκλήρωση της εργασίας του. Συνήθως ορίζεται χρησιμοποιώντας τη σημειογραφία Big-O .

Τι είναι η σημείωση Big O, ρωτάτε;

Εάν υποσχεθείτε ότι δεν θα σταματήσετε και θα σταματήσετε να διαβάζετε, θα σας πω.

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

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

Regular Big-O 2 O(1) --> It's just a constant number 2n + 10 O(n) --> n has the largest effect 5n^2 O(n^2) --> n^2 has the largest effect

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

Παρακάτω είναι μερικές κοινές χρονικές περιπλοκές με απλούς ορισμούς. Μη διστάσετε να ρίξετε μια ματιά στη Wikipedia για πιο αναλυτικούς ορισμούς.

  • O (1) - Σταθερός χρόνος: Λαμβάνοντας υπόψη μια είσοδο μεγέθους n, χρειάζεται μόνο ένα βήμα για την ολοκλήρωση της εργασίας από τον αλγόριθμο.
  • O (log n) - Λογαριθμικός χρόνος: δεδομένης της εισόδου μεγέθους n, ο αριθμός των βημάτων που χρειάζεται για την ολοκλήρωση της εργασίας μειώνεται κατά κάποιο παράγοντα με κάθε βήμα.
  • O (n) - Γραμμικός χρόνος: Με δεδομένη την είσοδο του μεγέθους n, ο αριθμός των απαιτούμενων βημάτων σχετίζεται άμεσα (1 έως 1)
  • O (n²) - Τετραγωνικός χρόνος: Με δεδομένη την είσοδο του μεγέθους n, ο αριθμός των βημάτων που χρειάζεται για την ολοκλήρωση μιας εργασίας είναι τετράγωνο του n.
  • O (C ^ n) - Εκθετικός χρόνος: Λαμβάνοντας υπόψη μια είσοδο μεγέθους n, ο αριθμός των βημάτων που χρειάζεται για την ολοκλήρωση μιας εργασίας είναι μια σταθερά στην ισχύ n (αρκετά μεγάλος αριθμός).

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

let n = 16; O (1) = 1 step "(awesome!)" O (log n) = 4 steps "(awesome!)" -- assumed base 2 O (n) = 16 steps "(pretty good!)" O(n^2) = 256 steps "(uhh..we can work with this?)" O(2^n) = 65,536 steps "(...)"

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

Λοιπόν, πώς θα αναλύσουμε τον κώδικά μας με τη σημειογραφία Big-O;

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

Θα χρησιμοποιήσουμε τις παρακάτω δομές δεδομένων για τα παραδείγματα:

var friends = { 'Mark' : true, 'Amy' : true, 'Carl' : false, 'Ray' : true, 'Laura' : false, } var sortedAges = [22, 24, 27, 29, 31]

O (1) - Σταθερός χρόνος

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

//If I know the persons name, I only have to take one step to check: function isFriend(name){ //similar to knowing the index in an Array return friends[name]; }; isFriend('Mark') // returns True and only took one step function add(num1,num2){ // I have two numbers, takes one step to return the value return num1 + num2 }

O (log n) - Λογαριθμική ώρα

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

//You decrease the amount of work you have to do with each step function thisOld(num, array){ var midPoint = Math.floor( array.length /2 ); if( array[midPoint] === num) return true; if( array[midPoint]  only look at second half of the array if( array[midpoint] > num ) --> only look at first half of the array //recursively repeat until you arrive at your solution } thisOld(29, sortedAges) // returns true //Notes //There are a bunch of other checks that should go into this example for it to be truly functional, but not necessary for this explanation. //This solution works because our Array is sorted //Recursive solutions are often logarithmic //We'll get into recursion in another post!

O (n) - Γραμμικός χρόνος

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

//The number of steps you take is directly correlated to the your input size function addAges(array){ var sum = 0; for (let i=0 ; i < array.length; i++){ //has to go through each value sum += array[i] } return sum; } addAges(sortedAges) //133

O (n²) - Τετραγωνικός χρόνος

Το ένθετο για βρόχους είναι τετραγωνικός χρόνος, επειδή εκτελείτε μια γραμμική λειτουργία σε μια άλλη γραμμική λειτουργία (ή n * n = n²).

//The number of steps you take is your input size squared function addedAges(array){ var addedAge = []; for (let i=0 ; i < array.length; i++){ //has to go through each value for(let j=i+1 ; j < array.length ; j++){ //and go through them again addedAge.push(array[i] + array[j]); } } return addedAge; } addedAges(sortedAges); //[ 46, 49, 51, 53, 51, 53, 55, 56, 58, 60 ] //Notes //Nested for loops. If one for loop is linear time (n) //Then two nested for loops are (n * n) or (n^2) Quadratic!

O (2 ^ n) - Εκθετικός χρόνος

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

//The number of steps it takes to accomplish a task is a constant to the n power //Thought example //Trying to find every combination of letters for a password of length n

Θα πρέπει να κάνετε ανάλυση χρονικής πολυπλοκότητας όποτε γράφετε κώδικα που πρέπει να τρέχει γρήγορα.

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

Για να σας βοηθήσουμε στη διαδικασία επίλυσης προβλημάτων, ακολουθούν μερικές απλές ερωτήσεις που πρέπει να κάνετε:

1. Επιλύει αυτό το πρόβλημα; Ναι =>

2. Έχετε χρόνο να εργαστείτε σε αυτό

Ναι => προχωρήστε στο βήμα 3

Όχι => Επιστρέψτε σε αυτό αργότερα και προχωρήστε στο βήμα 6 για τώρα.

3. Καλύπτει όλες τις ακραίες περιπτώσεις; Ναι =>

4. Οι πολυπλοκότητες μου είναι όσο το δυνατόν χαμηλότερες;

No => επανεγγραφή ή τροποποίηση σε νέα λύση -> επιστρέψτε στο βήμα 1

Ναι => προχωρήστε στο βήμα 5

5. Είναι ο κωδικός μου ΞΗΡΟΣ; Ναι =>

6. Χαίρομαι!

No => Make it D.R.Y, then rejoice!

Analyze time complexity any and all times you are trying to solve a problem. It’ll make you a better developer in the log run. Your teammates and users will love you for it.

Again, most problems you will face as programmer — whether algorithmic or programmatic — will have tens if not hundreds of ways of solving it. They may vary in how they solve the problem, but they all still solve that problem.

You could be making decisions between whether to use sets or graphs to store data. You could be deciding whether or not to use Angular, React, or Backbone for a team project. All of these solutions solve the same problem in a different way.

Given this, it’s hard to say there is a single “right” or “best” answer to these problems. But it is possible to say there are “better” or “worse” answers to a given problem.

Using one of our previous examples, it might be better to use React for a team project if half your team has experience with it, so it’ll take less time to get up and running.

The ability to describe a better solution usually springs from some semblance of time complexity analysis.

In short, if you’re going to solve a problem, solve it well. And use some Big-O to help you figure out how.

Here’s a final recap:

  • O(1) — Constant Time: it only takes a single step for the algorithm to accomplish the task.
  • O(log n) — Logarithmic Time: The number of steps it takes to accomplish a task are decreased by some factor with each step.
  • O (n) - Γραμμικός χρόνος: Ο αριθμός των απαιτούμενων βημάτων σχετίζεται άμεσα (1 έως 1).
  • O (n²) - Τετραγωνικός χρόνος: Ο αριθμός των βημάτων που χρειάζεται για την εκτέλεση μιας εργασίας είναι τετράγωνο του n.
  • O (C ^ n) - Εκθετικό: Ο αριθμός των βημάτων που χρειάζεται για την ολοκλήρωση μιας εργασίας είναι μια σταθερά στην ισχύ n (αρκετά μεγάλος αριθμός).

Και εδώ είναι μερικοί χρήσιμοι πόροι για να μάθετε περισσότερα:

  • Βικιπαίδεια
  • Το Big O Cheat Sheet είναι ένας εξαιρετικός πόρος με κοινές αλγοριθμικές πολυπλοκότητες χρόνου και γραφική αναπαράσταση. Τσέκαρέ το!