Ας απλοποιήσουμε τις πολυπλοκότητες των αλγορίθμων!

Έχει περάσει αρκετός καιρός από τότε που άρχισα να σκέφτομαι να επιστρέψω στα βασικά και να ασχοληθώ με τις βασικές έννοιες της πληροφορικής. Και κατάλαβα, πριν πηδήξω στην ομάδα θεμάτων βαρέων βαρών όπως δομές δεδομένων, λειτουργικά συστήματα, OOP, βάσεις δεδομένων και σχεδιασμός συστήματος (σοβαρά, η λίστα είναι ατελείωτη); touch: αλγόριθμος Ανάλυση πολυπλοκότητας.

Ναι! Η ιδέα που παραβλέπεται τις περισσότερες φορές, επειδή η πλειονότητα των προγραμματιστών μας σκέφτεται: «Χμμ, πιθανώς δεν θα χρειαστεί να το ξέρω αυτό ενώ πραγματικά κωδικοποιώ!».

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

Τι είναι η ανάλυση αλγορίθμων ούτως ή άλλως και γιατί τη χρειαζόμαστε; ;

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

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

Ας πάρουμε ένα παράδειγμα. Ας υποθέσουμε ότι έχουμε ένα προϊόν συνάρτησης () το οποίο πολλαπλασιάζει όλα τα στοιχεία ενός πίνακα, εκτός από το στοιχείο στον τρέχοντα ευρετήριο, και επιστρέφει το νέο πίνακα. Αν περάσω [1,2,3,4,5] ως είσοδος, θα έχω αποτέλεσμα [120, 60, 40, 30, 24].

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

Μπορείτε να ακολουθήσετε; Μεγάλος!

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

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

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

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

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

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

  • Ανάλυση Apriori - Όπως υποδηλώνει το όνομα, στην apriori (προηγούμενη), κάνουμε ανάλυση (χώρος και χρόνος) ενός αλγορίθμου πριν τον εκτελέσουμε σε ένα συγκεκριμένο σύστημα. Ουσιαστικά, αυτή είναι μια θεωρητική ανάλυση ενός αλγορίθμου. Η αποτελεσματικότητα ενός αλγορίθμου μετράται με την υπόθεση ότι όλοι οι άλλοι παράγοντες, για παράδειγμα, η ταχύτητα του επεξεργαστή, είναι σταθεροί και δεν έχουν καμία επίδραση στην υλοποίηση.
  • Ανάλυση Apostiari - Η ανάλυση Apostiari ενός αλγορίθμου πραγματοποιείται μόνο μετά την εκτέλεση του σε ένα φυσικό σύστημα. Ο επιλεγμένος αλγόριθμος υλοποιείται χρησιμοποιώντας μια γλώσσα προγραμματισμού που εκτελείται σε μια μηχανή υπολογιστή προορισμού. Εξαρτάται άμεσα από τις διαμορφώσεις του συστήματος και τις αλλαγές από σύστημα σε σύστημα.

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

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

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

Βυθιστείτε στην πολυπλοκότητα με ασυμπτωτική ανάλυση

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

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

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

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

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

  1. Χρόνος : Η πολυπλοκότητα του χρόνου δίνει μια ένδειξη για το πόσο καιρό χρειάζεται να ολοκληρωθεί ένας αλγόριθμος σε σχέση με το μέγεθος εισόδου. Ο πόρος για τον οποίο ανησυχούμε σε αυτήν την περίπτωση είναι CPU (και ώρα ρολογιού).
  2. Space : Η πολυπλοκότητα του διαστήματος είναι παρόμοια, αλλά αποτελεί ένδειξη για το πόσο "μνήμη" απαιτείται για την εκτέλεση του αλγορίθμου σε σχέση με το μέγεθος εισόδου. Εδώ, αντιμετωπίζουμε τη μνήμη RAM του συστήματος ως πόρο.

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

Το Big oh (Big O)

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

Ας πάμε στη μαθηματική πλευρά του για να κατανοήσουμε τα πράγματα στον πυρήνα τους.

Ας εξετάσουμε έναν αλγόριθμο που μπορεί να περιγραφεί από μια συνάρτηση f (n). Έτσι, για να ορίσουμε το BigO του f (n) , πρέπει να βρούμε μια συνάρτηση, ας πούμε, g (n) , που την οριοθετεί. Δηλαδή, μετά από μια συγκεκριμένη τιμή, n0, η τιμή του g (n) θα ξεπερνούσε πάντα το f (n) .

Μπορούμε να το γράψουμε ως,

f (n) ≤ C g (n)

όπου n≥n0; Γ> 0; n0≥1

If above conditions are fulfilled, we can say that g(n) is the BigO of f(n), or

f(n) = O (g(n))

Can we apply the same to analyze an algorithm? This basically means that in worst case scenario of running an algorithm, the value should not pass beyond a certain point, which is g(n) in this case. Hence, g(n) is the BigO of f(n).

Let’s go through some commonly used bigO notations and their complexity and understand them a little better.

  • O(1): Describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.
function firstItem(arr){ return arr[0];}

The above function firstItem(), will always take the same time to execute, as it returns the first item from an array, irrespective of its size. The running time of this function is independent of input size, and so it has a constant complexity of O(1).

Relating it to the above explanation, even in the worst case scenario of this algorithm (assuming input to be extremely large), the running time would remain constant and not go beyond a certain value. So, its BigO complexity is constant, that is O(1).

  • O(N): Describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. Take a look at the example below. We have a function called matchValue() which returns true whenever a matching case is found in the array. Here, since we have to iterate over the whole of the array, the running time is directly proportional to the size of the array.
function matchValue(arr, k){ for(var i = 0; i < arr.length; i++){ if(arr[i]==k){ return true; } else{ return false; } } }

This also demonstrates how Big O favors the worst-case performance scenario. A matching case could be found during any iteration of the for loop and the function would return early. But Big O notation will always assume the upper limit (worst-case) where the algorithm will perform the maximum number of iterations.

  • O(N²): This represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N³), O(N⁴), etc.
function containsDuplicates(arr){ for (var outer = 0; outer < arr.length; outer++){ for (var inner = 0; inner < arr.length; inner++){ if (outer == inner) continue; if (arr[outer] == arr[inner]) return true; } } return false;}
  • O(2^N): Denotes an algorithm whose growth doubles with each addition to the input data set. The growth curve of an O(2^N) function is exponential — starting off very shallow, then rising meteorically. An example of an O(2^N) function is the recursive calculation of Fibonacci numbers:
function recursiveFibonacci(number){ if (number <= 1) return number; return recursiveFibonacci(number - 2) + recursiveFibonacci(number - 1);}

Are you getting the hang of this? Perfect. If not, feel free to fire up your queries in the comments below. :)

Moving on, now that we have a better understanding of the BigO notation, let us get to the next type of asymptotic analysis which is, the Big Omega(Ω).

The Big Omega (Ω)?

The Big Omega(Ω) provides us with the best case scenario of running an algorithm. Meaning, it would give us the minimum amount of resources (time or space) an algorithm would take to run.

Let’s dive into the mathematics of it to analyze it graphically.

We have an algorithm which can be described by a function f(n). So, to define the BigΩ of f(n), we need to find a function, let’s say, g(n), which is tightest to the lower bound of f(n). Meaning, after a certain value, n0, the value of f(n) would always exceed g(n).

We can write it as,

f(n)≥ C g(n)

where n≥n0; C> 0; n0≥1

If above conditions are fulfilled, we can say that g(n) is the BigΩ of f(n), or

f(n) = Ω (g(n))

Can we infer that Ω(…) is complementary to O(…)? Moving on to the last section of this post…

The Big Theta (θ)?

The Big Theta(θ) is a sort of a combination of both BigO and BigΩ. It gives us the average case scenario of running an algorithm. Meaning, it would give us the mean of the best and worst case. Let’s analyse it mathematically.

Considering an algorithm which can be described by a function f(n). The Bigθ of f(n) would be a function, let’s say, g(n), which bounds it the tightest by both lower and upper bound, such that,

C₁g(n) ≤ f(n)≤ C₂ g(n)

whereC₁, C₂ >0, n≥ n0,

n0 ≥ 1

Meaning, after a certain value, n0, the value of C₁g(n) would always be less than f(n), and value of C₂ g(n) would always exceed f(n).

Now that we have a better understanding of the different types of asymptotic complexities, let’s have an example to get a clearer idea of how all this works practically.

Consider an array, of size, say, n, and we want to do a linear search to find an element x in it. Suppose the array looks something like this in the memory.

Going by the concept of linear search, if x=9, then that would be the best case scenario for the following case (as we don’t have to iterate over the whole array). And from what we have just learned, the complexity for this can be written as Ω(1). Makes sense?

Similarly, if x were equal to 14, that would be the worst case scenario, and the complexity would have been O(n).

What would be the average case complexity for this?

θ(n/2) => 1/2 θ(n) => θ(n) (As we ignore constants while calculating asymptotic complexities).

So, there you go folks. A fundamental insight into algorithmic complexities. Did it go well with you? Leave your advice, questions, suggestions in the comments below. Thanks for reading!❤️

References:-

  • A nice write-up by Dionysis “dionyziz” Zindros: //discrete.gr/complexity/
  • Μια καλή σειρά αλγορίθμων και δομών δεδομένων: //interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/WhatIsAlgorithmAnalysis.html