Алгоритми та структури даних · Junior · Запитання 64 з 75
Яка часова складність перевірки isPrime нижче?
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)
- ✓Правильна відповідь: O(√n)
Пояснення
Цикл зупиняється, коли i * i > n, тож виконується не більше √n разів. Дільник, більший за √n, мав би пару, меншу за √n, яку цикл уже перевірив.