O(n)은 코드가 돌아가는 시간이 n에 비례해서 증가한다는 의미입니다. O(n)짜리 코드가 실제로 2n일 수도 있고, 3n일 수도 있고, 100n+10일 수도 있습니다. 똑같은 O(n)짜리 for문을 재귀함수로 구현하면 여전히 O(n)입니다.

http://kks227.blog.me/22076985...

그러면 혹시 피보나치로 예를들면 n=fibo(n-1)+fibo(n-2) 재귀함수를 두번 들어가는거랑

for문으로 n번째까지 구현한 

d3=d2+d1

코드랑 시간복잡도가 다르지 않나요?

재귀함수를 한번 호출하는게 for문 한번 쓰는거랑 똑같은건지 좀 헷갈립니다..

피보나치 수를 계산할 때 DP 메모이제이션을 안 했다면 O(n)이 아닙니다. for문으로는 첫 번째 피보나치 수부터 n번째까지 한 번씩 계산되지만, 메모이제이션이 없는 재귀로는 그렇지 않기 때문입니다. 반면, 메모이제이션을 했다면 fibo(1)부터 fibo(n)까지 한 번씩 계산되므로 시간복잡도는 O(n)입니다.

http://kks227.blog.me/22077710...

마찬가지로 팩토리얼이나 거듭제곱을 계산하는 경우 for문으로 구현한 것과 재귀로 구현한 것 모두 O(n)이 걸리겠죠.

죄송하지만.... 메모제이션 안했을 경우 피보나치 재귀함수 시간복잡도 계산은 어떻게 해야되나요?

재귀함수 n번째까지 돌린다치면 O(n) 인가요?  O(n)+O(n) 으로 봐야되나요? 아니면 O(n^2)으로 봐야되나요?

제가 링크한 글에서 설명되어 있습니다.

아하 지수 시간 복잡도가 발생하는군요.. 좋은 정보 감사드립니다!!

같은 시간 복잡도라도.. 재귀식으로 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 정도)