Algorithmen und Datenstrukturen · Junior · Frage 64 von 75
Welche Zeitkomplexität hat die Prüfung isPrime unten?
function isPrime(n) {
if (n < 2) return false;
for (let i = 2; i * i <= n; i++) {
if (n % i === 0) return false;
}
return true;
}- 1O(n)
- 2O(log n)
- 3O(√n)
Antwort zeigen
Richtige Antwort: O(√n)
Erklärung
Die Schleife stoppt, wenn i * i > n, sie läuft also höchstens √n Mal. Ein Teiler größer als √n hätte einen Partner kleiner als √n, den die Schleife schon geprüft hat.