Komplexität von Array.includes()

dominik

Aktives Mitglied
Hi,

ich bin heute auf diese Stelle in einem Artikel gestoßen: https://www.aleksandrhovhannisyan.c...ptimize-later/#1-not-all-inputs-scale-in-size

Da drin heißt es:

Javascript:
// Version 2
const allowedValues = ['a', 'b', 'c', 'd'];

if (allowedValues.includes(value)) {
}

In this case, the array always has a fixed size of four elements. We're not passing in a dynamic array as a dependency to our algorithm—it's just a static, hard-coded array of items that we look up in an if statement.

Demzufolge sei die Komplexität hier O(1) anstatt O(n). Kann man das tatäschlich so argumentieren? :unsure:

Viele Grüße
Dominik
 

german

Aktives Mitglied
devCommunity-Experte
Big O ist die Komplexität. Das hat nicht notwendigerweise etwas mit Performance zu tun. Dass sich die beiden angeführten Beispiele in punkto Performance gleich verhalten, kann daher nicht als Begründung dafür herangezogen werden, dass aus O(n) plötzlich O(1) wird.
 

dominik

Aktives Mitglied
Big O ist die Komplexität. Das hat nicht notwendigerweise etwas mit Performance zu tun. Dass sich die beiden angeführten Beispiele in punkto Performance gleich verhalten, kann daher nicht als Begründung dafür herangezogen werden, dass aus O(n) plötzlich O(1) wird.

Der Meinung war ich auch - es geht ja nicht darum, wie schnell die Lösung konkret ist, sondern wie sie skaliert...
 

LimDul79

Neues Mitglied
Der Meinung war ich auch - es geht ja nicht darum, wie schnell die Lösung konkret ist, sondern wie sie skaliert...
Welche Lösung

Das ist die Gretchenfrage.

Arrays.includes hat O( n )

Wenn es aber um folgende Methode geht:

Code:
bool myMethod(char value) {
const allowedValues = ['a', 'b', 'c', 'd'];

if (allowedValues.includes(value)) {
return true;
}
}
Dann hat die Methode myMethod die Komplexität O(1) - da im Kontext der Komplexitätsanalyse von myMethod der Aufruf von allowedValues eben konstant ist.

Man muss aufpassen, das man nicht Äpfel & Birnen vergleicht. Man muss genau aufpassen, was das n, also die Eingabegröße wirklich ist.
 

Jan Krüger

Neues Mitglied
Die Komplexität ist genauer gesagt das asymptotische Verhalten eines Algorithmus bei steigender Länge der Eingabe. Da hier die einzige Eingabe variabler Länge value ist, kann das asymptotische Verhalten eigentlich nur davon abhängen. Das ist hier aber auch nicht der Fall, weil die Vergleichsstrings auch alle eine feste Länge haben und deshalb die maximale Dauer der Stringvergleiche auch durch eine Konstante limitiert ist (konkret die längste Zeichenfolge in allowedValues). Folglich ist der Algorithmus in O(1).
 
Oben Unten