Algorithmen und Datenstrukturen · Middle · Frage 67 von 75
Welche Komplexität hat die Prüfung, ob zwei Strings der Länge n gleich sind?
- 1Immer O(1), Strings werden interniert
- 2Im schlimmsten Fall O(n)
- 3O(n²), weil Zeichen kopiert werden
Antwort zeigen
Richtige Antwort: Im schlimmsten Fall O(n)
Erklärung
Zeichen werden verglichen, bis ein Unterschied auftaucht, gleiche oder fast gleiche Strings kosten also O(n). Das zählt, wenn Strings als Schlüssel dienen: auch das Hashen eines Schlüssels liest den ganzen String.