O(√n) — Корневая сложность

O(√n) — Сложность корень из n

Определение

Сложность O(√n) означает, что время выполнения алгоритма пропорционально квадратному корню от размера входных данных.

Формула

$O(\sqrt{n})$

где $n$ — размер входных данных

Характеристики

• Эффективнее чем O(n), но медленнее чем O(log n)
• Часто встречается в задачах с числами
• Типична для оптимизированных алгоритмов перебора
• Хороший компромисс между скоростью и простотой

Визуализация проверки делителей

Проверка делителей числа 100:

Полный перебор O(n):
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ..., 100
└─────────────────────────────────────┘
            100 операций

Оптимизированный O(√n):
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
└──────────────────────────┘
      10 операций = √100

Парные делители:
1 × 100 = 100
2 × 50 = 100
4 × 25 = 100
5 × 20 = 100
10 × 10 = 100  <- граница √100

Сравнение производительности

Размер (n)	√n	log₂ n	n
10	3	3	10
100	10	7	100
1,000	32	10	1,000
10,000	100	13	10,000
1,000,000	1,000	20	1,000,000

График сложности

Операции
     |
1000 |                                  ●     O(n)
     |                                ●
 750 |                              ●
     |                            ●
 500 |                          ●
     |                        ●
 250 |                      ●     O(√n)
     |                 ● ●
 100 |          ● ● ●
     |    ● ● ●  O(log n)
  10 | ●●●
     |
   0 +---------------------------------------------->
     10    100     1K     10K    100K    1M      n

Математическое обоснование

Для проверки делителей числа n:

Если d — делитель n, то n = d × k

Если d > √n, то k < √n

Значит, для каждого делителя > √n существует парный делитель < √n

Вывод: Достаточно проверить только числа до √n!

Практическое применение

• Проверка простоты чисел
• Факторизация
• Поиск делителей
• Jump Search (поиск прыжками)
• Алгоритмы работы с числами
• Оптимизация переборных алгоритмов

Сравнение с другими алгоритмами поиска

Алгоритм	Сложность	Требования
Линейный поиск	O(n)	Нет
Jump Search	O(√n)	Отсортированный массив
Бинарный поиск	O(log n)	Отсортированный массив

Важно помнить

✅ Эффективнее линейного поиска ✅ Часто оптимальна для задач с числами ✅ Простая реализация ✅ Хороший компромисс между O(log n) и O(n) ❌ Медленнее логарифмической сложности ❌ Не всегда применима

Примеры кода

1. Проверка простоты числа

function isPrime(n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 === 0 || n % 3 === 0) return false;
 
  // Проверяем делители только до √n
  for (let i = 5; i * i <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) {
      return false;
    }
  }
 
  return true;
}
 
console.log(isPrime(17)); // true
console.log(isPrime(100)); // false

2. Поиск делителей числа

function findDivisors(n) {
  const divisors = [];
 
  // Проверяем только до √n
  for (let i = 1; i * i <= n; i++) {
    if (n % i === 0) {
      divisors.push(i);
      // Добавляем парный делитель
      if (i !== n / i) {
        divisors.push(n / i);
      }
    }
  }
 
  return divisors.sort((a, b) => a - b);
}
 
console.log(findDivisors(36)); // [1, 2, 3, 4, 6, 9, 12, 18, 36]

3. Решето Эратосфена (оптимизированное)

function sieveOfEratosthenes(n) {
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
 
  // Проверяем только до √n
  for (let i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      // Вычеркиваем все кратные i
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
 
  return isPrime.map((prime, num) => prime ? num : null).filter(x => x !== null);
}
 
console.log(sieveOfEratosthenes(30));
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

4. Поиск в отсортированном массиве прыжками (Jump Search)

function jumpSearch(arr, target) {
  const n = arr.length;
  const step = Math.floor(Math.sqrt(n));
  let jump = step;
  let prev = 0;
 
  // Прыгаем блоками по √n
  while (arr[Math.min(jump, n) - 1] < target) {
    prev = jump;
    jump += step;
    if (prev >= n) return -1;
  }
 
  // Линейный поиск в найденном блоке
  while (arr[prev] < target) {
    prev++;
    if (prev === Math.min(jump, n)) return -1;
  }
 
  if (arr[prev] === target) return prev;
  return -1;
}
 
const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
console.log(jumpSearch(arr, 13)); // 6

5. Факторизация числа

function primeFactorization(n) {
  const factors = [];
 
  // Проверяем делители до √n
  for (let i = 2; i * i <= n; i++) {
    while (n % i === 0) {
      factors.push(i);
      n = Math.floor(n / i);
    }
  }
 
  // Если осталось число > 1, оно простое
  if (n > 1) {
    factors.push(n);
  }
 
  return factors;
}
 
console.log(primeFactorization(84)); // [2, 2, 3, 7]
console.log(primeFactorization(100)); // [2, 2, 5, 5]