복잡도 계산

덧셈, 뺄셈, 대입 연산은 상수시간이 걸리며 이를 O(1)라고 표현한다.

입력 데이터의 수 N에 대한 연산량을 계산한 수식의 최고차항만 취하여 표현한다.

O(1) < O(ln N) < O(N) < O(N ln N) < O(N²) < O(N³)
ln : 밑이 2인 log

실행환경에 따라 차이가 있지만 보수적으로 계산했을 때 1000만 건 정도의 연산이면 1초안에 결과가 나온다고 알려져 있다.

더 자세한 내용은 여기를 참조하세요.