Vereinfachen wir die Komplexität von Algorithmen!

Es ist schon eine Weile her, dass ich darüber nachdachte, zu den Grundlagen zurückzukehren und die wichtigsten Konzepte der Informatik aufzufrischen. Und ich dachte mir, bevor ich in den Pool schwergewichtiger Themen wie Datenstrukturen, Betriebssysteme, OOP, Datenbanken und Systemdesign einspringe (im Ernst, die Liste ist endlos), sollte ich wahrscheinlich das Thema aufgreifen, das wir alle irgendwie nicht wollen touch: Algorithmus Komplexitätsanalyse.

Ja! Das Konzept, das die meiste Zeit übersehen wird, weil die meisten von uns Entwicklern denken: "Hmm, das muss ich wahrscheinlich nicht wissen, während ich tatsächlich codiere!"

Ich bin mir nicht sicher, ob Sie jemals das Bedürfnis hatten zu verstehen, wie die Algorithmusanalyse tatsächlich funktioniert. Aber wenn ja, hier ist mein Versuch, es so klar wie möglich zu erklären. Ich hoffe es hilft jemandem wie mir.

Was ist überhaupt eine Algorithmusanalyse und warum brauchen wir sie? ?

Bevor wir uns mit der Analyse der Algorithmuskomplexität befassen, wollen wir zunächst eine kurze Vorstellung davon bekommen, was eine Algorithmusanalyse ist. Die Algorithmusanalyse befasst sich mit dem Vergleich von Algorithmen basierend auf der Anzahl der von jedem Algorithmus verwendeten Rechenressourcen.

Was wir mit dieser Praxis erreichen wollen, ist die Möglichkeit, eine fundierte Entscheidung darüber zu treffen, welcher Algorithmus im Hinblick auf eine effiziente Nutzung der Ressourcen (Zeit oder Speicher, je nach Anwendungsfall) ein Gewinner ist. Macht das Sinn?

Nehmen wir ein Beispiel. Angenommen, wir haben eine Funktion product (), die alle Elemente eines Arrays mit Ausnahme des Elements am aktuellen Index multipliziert und das neue Array zurückgibt. Wenn ich [1,2,3,4,5] als Eingabe übergebe, sollte ich als Ergebnis [120, 60, 40, 30, 24] erhalten.

Die obige Funktion verwendet zwei verschachtelte for- Schleifen, um das gewünschte Ergebnis zu berechnen. Im ersten Durchgang nimmt es das Element an der aktuellen Position. Im zweiten Durchgang multipliziert es dieses Element mit jedem Element im Array - außer wenn das Element der ersten Schleife mit dem aktuellen Element der zweiten Schleife übereinstimmt. In diesem Fall wird es einfach mit 1 multipliziert, um das Produkt unverändert zu lassen.

Kannst du folgen? Toll!

Es ist ein einfacher Ansatz, der gut funktioniert, aber können wir ihn etwas verbessern? Können wir es so ändern, dass wir verschachtelte Schleifen nicht zweimal verwenden müssen? Vielleicht das Ergebnis bei jedem Durchgang speichern und davon Gebrauch machen?

Betrachten wir die folgende Methode. In dieser modifizierten Version gilt das Prinzip, dass für jedes Element das Produkt der Werte rechts berechnet wird, die Produkte der Werte links berechnet werden und diese beiden Werte einfach multipliziert werden. Ziemlich süß, nicht wahr?

Anstatt verschachtelte Schleifen zur Berechnung der Werte bei jedem Lauf zu verwenden, verwenden wir hier zwei nicht verschachtelte Schleifen, wodurch die Gesamtkomplexität um den Faktor O (n) verringert wird (wir werden später darauf zurückkommen).

Wir können sicher schließen, dass der letztere Algorithmus eine bessere Leistung als der erstere erbringt. So weit, ist es gut? Perfekt!

An dieser Stelle können wir auch einen kurzen Blick auf die verschiedenen Arten der Algorithmusanalyse werfen, die es gibt. Wir müssen nicht auf die Details der Minutenebene eingehen, sondern nur ein grundlegendes Verständnis des Fachjargons haben.

Abhängig davon, wann ein Algorithmus analysiert wird, dh vor oder nach der Implementierung, kann die Algorithmusanalyse in zwei Stufen unterteilt werden:

  • Apriori-Analyse - Wie der Name schon sagt, führen wir im April (vorher) eine Analyse (Raum und Zeit) eines Algorithmus durch, bevor wir ihn auf einem bestimmten System ausführen . Grundsätzlich handelt es sich also um eine theoretische Analyse eines Algorithmus. Die Effizienz eines Algorithmus wird unter der Annahme gemessen, dass alle anderen Faktoren, beispielsweise die Prozessorgeschwindigkeit, konstant sind und keinen Einfluss auf die Implementierung haben.
  • Apostiari-Analyse - Die Apostiari-Analyse eines Algorithmus wird erst durchgeführt, nachdem er auf einem physischen System ausgeführt wurde. Der ausgewählte Algorithmus wird unter Verwendung einer Programmiersprache implementiert, die auf einem Zielcomputer ausgeführt wird. Dies hängt direkt von den Systemkonfigurationen und Änderungen von System zu System ab.

In der Branche führen wir selten Apostiari-Analysen durch, da Software im Allgemeinen für anonyme Benutzer erstellt wird, die sie möglicherweise auf verschiedenen Systemen ausführen.

Da die zeitliche und räumliche Komplexität von System zu System variieren kann, ist die Apriori-Analyse die praktischste Methode zum Ermitteln der Komplexität von Algorithmen. Dies liegt daran, dass wir nur die asymptotischen Variationen (wir werden später darauf zurückkommen) des Algorithmus betrachten, die die Komplexität eher basierend auf der Eingabegröße als auf Systemkonfigurationen angeben.

Nachdem wir ein grundlegendes Verständnis der Algorithmusanalyse haben, können wir zu unserem Hauptthema übergehen: der Komplexität von Algorithmen. Wir werden uns auf die Apriori-Analyse konzentrieren und den Umfang dieses Beitrags berücksichtigen. Beginnen wir also .

Tauchen Sie mit asymptotischer Analyse tief in die Komplexität ein

Die Analyse der Algorithmuskomplexität ist ein Werkzeug, mit dem wir erklären können, wie sich ein Algorithmus verhält, wenn die Eingabe größer wird.

Wenn Sie beispielsweise einen Algorithmus mit einem Datensatz der Größe n ausführen möchten , können Sie die Komplexität als numerische Funktion f (n) - Zeit gegenüber der Eingabegröße n definieren .

Nun müssen Sie sich fragen, ob es nicht möglich ist, dass ein Algorithmus an denselben Eingaben unterschiedlich viel Zeit benötigt, abhängig von Faktoren wie Prozessorgeschwindigkeit, Befehlssatz, Festplattengeschwindigkeit und Marke des Compilers. Wenn ja, dann klopfen Sie sich auf den Rücken, denn Sie haben absolut Recht!?

Hier kommt die asymptotische Analyse ins Spiel. Hier besteht das Konzept darin, die Leistung eines Algorithmus in Bezug auf die Eingabegröße zu bewerten (ohne die tatsächliche Ausführungszeit zu messen). Im Grunde genommen berechnen wir, wie sich die Zeit (oder der Raum) eines Algorithmus erhöht, wenn wir die Eingabegröße unendlich groß machen.

Die Komplexitätsanalyse wird an zwei Parametern durchgeführt:

  1. Zeit : Die zeitliche Komplexität gibt einen Hinweis darauf, wie lange ein Algorithmus in Bezug auf die Eingabegröße dauert. Die Ressource, um die wir uns in diesem Fall kümmern, ist die CPU (und die Wanduhrzeit).
  2. Raum : Raum Komplexität ist ähnlich, aber ist ein Hinweis darauf , wie viel Speicher „erforderlich“ , um den Algorithmus in Bezug auf die Eingangsgröße auszuführen. Hier beschäftigen wir uns mit System-RAM als Ressource.

Sind Sie noch da? Gut! Nun gibt es verschiedene Notationen, mit denen wir die Komplexität durch asymptotische Analyse analysieren. Wir werden sie alle einzeln durchgehen und die Grundlagen hinter jedem verstehen.

Das große Oh (Big O)

Die allererste und beliebteste Notation für die Komplexitätsanalyse ist die BigO-Notation. Der Grund dafür ist, dass es die Worst-Case-Analyse eines Algorithmus gibt. Das Nerd-Universum ist hauptsächlich besorgt darüber, wie schlecht sich ein Algorithmus verhalten kann und wie er zu einer besseren Leistung gebracht werden kann. BigO bietet uns genau das.

Kommen wir zur mathematischen Seite, um die Dinge in ihrem Kern zu verstehen.

Betrachten wir einen Algorithmus, der durch eine Funktion f (n) beschrieben werden kann. Um das BigO von f (n) zu definieren , müssen wir eine Funktion finden, sagen wir g (n) , die es begrenzt. Das heißt, nach einem bestimmten Wert n0 würde der Wert von g (n) immer f (n) überschreiten .

Wir können es schreiben als,

f (n) ≤ C g (n)

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

Wenn die obigen Bedingungen erfüllt sind, können wir sagen, dass g (n) das BigO von f (n) ist, oder

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

Können wir dasselbe anwenden, um einen Algorithmus zu analysieren? Dies bedeutet im Grunde, dass im schlimmsten Fall beim Ausführen eines Algorithmus der Wert nicht über einen bestimmten Punkt hinausgehen sollte, der in diesem Fall g (n) ist. Daher ist g (n) das BigO von f (n).

Lassen Sie uns einige häufig verwendete bigO-Notationen und ihre Komplexität durchgehen und sie ein wenig besser verstehen.

  • O (1): Beschreibt einen Algorithmus, der unabhängig von der Größe des Eingabedatensatzes immer zur gleichen Zeit (oder im gleichen Raum) ausgeführt wird.
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/
  • A good series on algorithm & data structures: //interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/WhatIsAlgorithmAnalysis.html