Loading...

O(√n) - 제곱근 시간

쉬움

O(√n) - Square Root Time

전체를 다 볼 필요 없다! 정사각형의 한 변만 확인하는 O(√n)의 원리를 배웁니다.

📊 복잡도

구분	복잡도
최선	O(1)
평균	O(√n)
최악	O(√n)
공간	O(1)

🏷️ 태그

기초복잡도

📖 개념 소개

O(√n)은 데이터(N)의 제곱근만큼만 확인하면 되는 알고리즘입니다.

1/20

Loading...

🤔36의 약수는 몇 개?

36을 나누어 떨어지게 하는 수를 모두 찾아봅시다. 1부터 36까지 다 확인해야 할까요?

기초 학습

O(√n) - 제곱근 시간

정의

O(√n)은 데이터(N)의 제곱근만큼만 확인하면 되는 알고리즘입니다.

핵심 특성

✓면적(N) 대신 한 변(√N)만 확인
✓약수는 항상 짝이 있음
✓소수 판별에 매우 효율적

시간 복잡도

최선

O(1)

평균

O(√n)

최악

O(√n)

공간 복잡도

O(1)

O(√n) - 제곱근 시간 | AlgoNote