Algorytmy i struktury danych · Junior · Pytanie 64 z 75
Jaka jest złożoność czasowa sprawdzenia isPrime poniżej?
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)
- ✓Poprawna odpowiedź: O(√n)
Wyjaśnienie
Pętla kończy się, gdy i * i > n, więc wykonuje się najwyżej √n razy. Dzielnik większy niż √n miałby parę mniejszą niż √n, którą pętla już sprawdziła.