지수 탐색 알고리즘

반복문의 수행 횟수를 입력크기의 다항식으로 표현할 수 있는 알고리즘을 다항 시간 알고리즘이라고 한다.

이동 평균 알고리즘에서도 N^2과 N으로 표현되었으니 다항 시간 알고리즘이라고 할 수 있겠다.

 

지수 탐색 알고리즘의 경우는 재귀함수를 사용해서 입력으로 주어지는 숫자의 개수에 따라 수행시간이 달라진다. 

하지만 소인수 분해 알고리즘은 크기에 따라 수행시간이 달라진다. 

 

소인수 분해 알고리즘은 입력 값(n)이 1이 될 때까지 가능한 모든 숫자로 n을 나눈다. n의 크기에 따라 반복문의 수행횟수가 달라진다.

n이 소수일 경우, n은 div가 n-1이 될 때까지 어떤 수로도 나누어지지 않는다. 따라서 반복문의 횟수는 n-1이 된다.

n이 아무리 커도 입력은 n 1개 뿐인데 수행시간이 달라진다는 건 어떤 의미인가.

 

소인수 분해 문제에서는 입력 값(n)으로 어떤 값이 들어오냐에 따라 수행시간이 달라지므로, 숫자가 특정범위 안에 있다고 가정할 수 없다.

입력 값이 커질수록 숫자를 저장하는데 필요한 메모리 공간도 커질 것이다. 입력 값이 차지하는 비트의 수에 따라 수행 시간이 증가한다고 생각해보자.  비트의 수가 하나 증가할 때마다 표현할 수 있는 수의 범위와 알고리즘의 최대 수행 시간은 두 배로 증가한다. 그렇기 때문에 지수 시간이 걸린다고 할 수 있다.