O(n)은 코드가 돌아가는 시간이 n에 비례해서 증가한다는 의미입니다. O(n)짜리 코드가 실제로 2n일 수도 있고, 3n일 수도 있고, 100n+10일 수도 있습니다. 똑같은 O(n)짜리 for문을 재귀함수로 구현하면 여전히 O(n)입니다.
O(n)은 코드가 돌아가는 시간이 n에 비례해서 증가한다는 의미입니다. O(n)짜리 코드가 실제로 2n일 수도 있고, 3n일 수도 있고, 100n+10일 수도 있습니다. 똑같은 O(n)짜리 for문을 재귀함수로 구현하면 여전히 O(n)입니다.
피보나치 수를 계산할 때 DP 메모이제이션을 안 했다면 O(n)이 아닙니다. for문으로는 첫 번째 피보나치 수부터 n번째까지 한 번씩 계산되지만, 메모이제이션이 없는 재귀로는 그렇지 않기 때문입니다. 반면, 메모이제이션을 했다면 fibo(1)부터 fibo(n)까지 한 번씩 계산되므로 시간복잡도는 O(n)입니다.
http://kks227.blog.me/22077710...
마찬가지로 팩토리얼이나 거듭제곱을 계산하는 경우 for문으로 구현한 것과 재귀로 구현한 것 모두 O(n)이 걸리겠죠.
같은 시간 복잡도라도.. 재귀식으로 dp를 풀어버리는 거랑
그냥 깡 dp로 풀어버리는 거하고 차이가 좀 있습니다.
함수를 호출하려면... 스택에 뭔가도 쌓아야 하고.. (복귀주소라던지.. 파라미터라던지..)
또 제거도 해야 하니.. 이 연산이 생각보다 가볍진 않아유..
그렇다고 깡 dp로 해야 하느냐. 그건 또 아닌게.. 재귀식으로 짜면.. 더 직관적이잖아유.
같은 시간 복잡도를 가지더라도 앞에 붙는 상수 때문에
시간 초과냐 Accept냐가 갈리는 경우가 있는데..
팬윅트리 vs 세그먼트 트리 vs lazy 기법을 적용한 seg 트리 정도가 있지 않나 싶군요.
제가 최근에 경험한 것 중에서는 multiset을 사용하면 시간 초과인데.. 세그 트리를 사용하면 Accept 받는 경우도 있었어유.
근데 사실 앞에 붙는 상수 때문에
시간 초과냐. 억셉이냐 갈리는 건.. 왠만큼 문제를 풀어보시면 접할 문제이구요.
아직은 아닌 거 같아유..^^;; 그러니까 초반에는 걍 마음놓으시고 걍 시간 복잡도를 낮추는 방향으로만..
아. 그렇다고.. 막 for문 1000만번 호출해서 더하는 걸 재귀식으로 구현하면 어케 될 지 몰라유..
예를 들어서
ll zaegui(ll x)
{
if(x==0)
return x;
return x+zaegui(x-1);
}
...
int main(void)
{
ll r;
r=zaegui(10000000);
...
}
아니면 kks님에게 하나 하나 물어보시는 것도..??
요새 메이플을 하시는 거 같긴 했는데.. ㅎㅎ;;
하나 팁.
호출 깊이 하나당 파라미터들의 형 크기 + 8byte ~ 32byte 정도 잡으면 될 거 같아요.
더 잡아야 할 수도 있긴 하지만 보통 전 그리 잡습니다.
일단 그 중 하나는 복귀주소가 되겠네요.
main에서 foo라는 함수를 호출했습니다.
foo라는 함수를 끝내면 어디로 돌아가야 하는지를 저장하신다 보면 됩니다.
이걸 변조해서 자기가 원하는 루틴으로 가게 만들기도 합니당.
자세한 건 어셈블리 뜯어보시면 좋을 거 같아요..
vs는 되게 크게 크게 잡아놓는 걸로 알고 있어요. (대충 몇 백 byte 정도)
댓글을 작성하려면 로그인해야 합니다.
jokerkwu 2년 전
for문은 시간복잡도가 빅오 n 으로 알고 있습니다.
재귀함수로 구현할경우 시간복잡도가 어떻게 되는지 궁금합니다.
구현하다보니 재귀함수가 더 오래 걸리는거 같은데 정확하게 어느정도 걸리는지 모르닌까
문제 풀 때 사용해야될지 말아야될지 감을 못잡겠네요.