Οδηγός για αρχάριους για Big O Notation

Το Big O Notation είναι ένας τρόπος για να αναπαριστάτε πόσο καιρό θα χρειαστεί ένας αλγόριθμος για την εκτέλεση. Επιτρέπει σε έναν μηχανικό λογισμικού να προσδιορίσει πόσο αποτελεσματικές είναι οι διαφορετικές προσεγγίσεις για την επίλυση ενός προβλήματος.

Ακολουθούν ορισμένοι συνηθισμένοι τύποι χρονικών περιπλοκών στη Σημείωση Big O

  • O (1) - Σταθερή χρονική πολυπλοκότητα
  • O (n) - Γραμμική πολυπλοκότητα χρόνου
  • O (log n) - Λογαριθμική χρονική πολυπλοκότητα
  • O (n ^ 2) - Τετραγωνική χρονική πολυπλοκότητα

Ας ελπίσουμε ότι μέχρι το τέλος αυτού του άρθρου θα μπορείτε να κατανοήσετε τα βασικά της Big O Notation.

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

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

var arr = [ 1,2,3,4,5];
arr[2]; // => 3

Άλλα παραδείγματα περιλαμβάνουν: λειτουργίες push () και pop () σε έναν πίνακα.

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

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

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

Παραδείγματα στο O (n) είναι η χρήση γραμμικής αναζήτησης:

//if we used for loop to print out the values of the arrays
for (var i = 0; i < array.length; i++) { console.log(array[i]);}
var arr1 = [orange, apple, banana, lemon]; //=> 4 steps
var arr2 = [apple, htc,samsung, sony, motorola]; //=> 5 steps

O (log n) - Λογαριθμική χρονική πολυπλοκότητα

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

//Binary search implementationvar doSearch = function(array, targetValue) { var minIndex = 0; var maxIndex = array.length - 1; var currentIndex; var currentElement; while (minIndex <= maxIndex) { currentIndex = (minIndex + maxIndex) / 2 | 0; currentElement = array[currentIndex]; if (currentElement  targetValue) { maxIndex = currentIndex - 1; } else { return currentIndex; } } return -1; //If the index of the element is not found.};
var numbers = [11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33];
doSearch(numbers, 23) //=>; 6

Άλλα παραδείγματα λογαριθμικής πολυπλοκότητας χρόνου περιλαμβάνουν:

Example 1;
for (var i = 1; i < n; i = i * 2) console.log(i);}
Example 2;
for (i = n; i >= 1; i = i/2) console.log(i);}

O (n ^ 2) - Τετραγωνική χρονική πολυπλοκότητα

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

Θα συναντήσετε τετραγωνική πολυπλοκότητα χρόνου σε αλγόριθμους που περιλαμβάνουν ένθετες επαναλήψεις, όπως ένθετο για βρόχους. Στην πραγματικότητα, οι βαθύτεροι ένθετοι βρόχοι θα έχουν ως αποτέλεσμα O (n ^ 3), O (n ^ 4) κ.λπ.

for(var i = 0; i < length; i++) { //has O(n) time complexity for(var j = 0; j < length; j++) { //has O(n^2) time complexity // More loops? }}

Άλλα παραδείγματα τετραγωνικής χρονικής πολυπλοκότητας περιλαμβάνουν είδος φυσαλίδων, είδος επιλογής και είδος εισαγωγής

Αυτό το άρθρο γρατζουνίζει μόνο την επιφάνεια του Big O Notation. Εάν θέλετε να καταλάβετε περισσότερα για τη σημείωση Big O, σας συνιστώ να ελέγξετε το Big-O Cheat Sheet.