정의
O(√n)은 데이터(N)의 제곱근만큼만 확인하면 되는 알고리즘입니다.
핵심 특성
- ✓면적(N) 대신 한 변(√N)만 확인
- ✓약수는 항상 짝이 있음
- ✓소수 판별에 매우 효율적
활용 사례
이런 상황에서 사용됩니다:
🛡️
소수 판별
√n까지만 나눠보면 소수인지 알 수 있음
🔢
약수 찾기
36의 약수: 1~6까지만 확인하면 짝 자동 발견
📦
제곱근 분할법
배열을 √n 블록으로 나눠 구간 쿼리 최적화
🔄
Mo's Algorithm
오프라인 쿼리 처리에 √n 활용
복잡도
시간 복잡도
최선
O(1)
평균
O(√n)
최악
O(√n)
공간 복잡도
O(1)
시각화로 더 깊이 이해하기
단계별 애니메이션과 코드 실행을 통해 알고리즘이 어떻게 동작하는지 직접 확인하세요.
시각화 시작하기