Algorithmen und Datenstrukturen · Senior · Frage 75 von 75
Warum ist Array.prototype.indexOf innerhalb von filter in Code-Reviews ein häufiges verstecktes O(n²)?
const unique = items.filter((x, i) => items.indexOf(x) === i);- 1
indexOfsortiert das Array vor der Suche - 2
indexOfdurchsucht das Array für jedes Element vonfilter - 3
filterkopiert für jedes Element das ganze Array
Antwort zeigen
Richtige Antwort: indexOf durchsucht das Array für jedes Element von filter
Erklärung
Jeder der n Callbacks macht eine lineare Suche, 10.000 Elemente bedeuten also bis zu 100 Millionen Vergleiche. [...new Set(items)] erledigt dasselbe in O(n). Solche verschachtelten Suchen zu erkennen ist eine typische Senior-Fähigkeit im Review.