인프런 커뮤니티 질문&답변
작성한 질문수
재귀함수의 시간 복잡도
해결된 질문
작성
·
50
0
안녕하세요 큰돌님, 강의 잘 듣고 있습니다!
커뮤니티에서 나온 질문 중에 n이 이전에는 더하는 것의 개수까지 포함했었는데 이번 강의에서는 그냥 n으로 둬도 되냐는 질문이 있었습니다. 저도 같은 의문인 것 같아서 더 자세히 질문하고자 합니다!
5-2. 문제로 연습하는 시간복잡도 -> 점화식 설명에서,
등비수열의 합을 구하시면서
a(r^n-1)/r-1 => 1(2^log_2(n)+1 -1)/1 이런식으로 계산하여 등비수열의 합에서 n부분도 log로 표현하여 계산하셨었는데,
이번 강의인 7. 문제로 연습하는 시간복잡도 Q5의 경우
똑같이 등비수열의 합을 구하시면서
a(r^n-1)/r-1 => 1(3^n-1)/3-1=>1/2 * (3^n-1) 로 n 부분은 그대로 n으로 두고 계산하신 것을 보고,
약간의 혼동이 온 것 같습니다. 언제는 트리의 높이로 구해야 하고, 언제는 n을 그대로 둬도 되는 건지 이런 부분에서 혼동이 오는 것 같아요.ㅠㅠ
n의 의미가 다른 것인지,제가 어디서 놓친 부분이 있는 것인지 짚어주시면 감사하겠습니다!!
항상 강의 잘 보고 있습니다! 감사합니다!
답변 2
0
안녕하세요 채연님 ㅎㅎ
Q3과 Q5 모두 트리의 높이를 기반으로 생각하시면 됩니다.
Q3의 경우 정확히 반을 쪼개지면서 재귀함수가 호출이 됩니다.
재귀함수를 보시면 mid를 기준으로 반으로 쪼개어서 호출이 되는 것을 볼 수 있습니다.
각 호출에서 구간 [l, r]을 절반으로 나누고, 두 하위 구간을 재귀적으로 처리하기 때문에 -> 트리의 높이는 log_2N 꼴을 가지게 됩니다.
Q5의 경우 n - 1을 하면서 각 단계에서 3배로 증가하는 호출구조를 가지고 -> 트리의 높이는 N을 가지게 됩니다.
ex)
깊이 0:
solve(N)1번 호출깊이 1:
solve(N-1)3번 호출깊이 2:
solve(N-2)3^2 = 9번 호출…
깊이 N:
solve(0)3^N번 호출
여기서 트리의 높이를 기준으로 등비수열의 합 공식을 사용해서 시간복잡도를 측정하면 됩니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다.
박채연님, 질문 주셔서 감사합니다! 님의 질문과 유사한 기존의 답변 몇 가지를 추천해 드리겠습니다. 이 답변들은 재귀 함수와 시간복잡도에 대해 상세히 설명하고, 혼란스러운 부분을 명확히 이해하는 데 도움이 될 것입니다. 아래 링크들을 통해 상세한 내용을 확인해보세요:
-
이 답변에서 이중 for문과 백트래킹의 시간복잡도 계산에 대한 논의가 있습니다. 등차수열, 등비수열 배경 설명이 매우 유용합니다.
-
이 링크는 로그 함수의 유도와 트리 노드의 계산에 대해 설명합니다. 시간이 충분할 때 꼭 참고해보세요.
-
이 토론에서는 시간 복잡도와 재귀 함수의 관계, 그리고 왜 log가 사용되는지에 대한 추가 설명이 제공됩니다.
1주차 개념 #7. 문제로 연습하는 시간복잡도 Q5 강의 질문있습니다.
이 게시물은 동일한 강의와 관련한 다른 수강생의 질문과 자세한 답변을 포함하고 있습니다.
포인트 요약:
- 트리 구조에서의 높이는 로그 함수로 표현됩니다. 이는 트리의 각 레벨에서 자식 노드의 개수가 지수적으로 증가하기 때문입니다. 예를 들어, 높이가 n인 트리에서 노드의 개수는 대략적으로 O(2^n)입니다.
- 반면, 단순히 n^k 형태의 복잡도를 갖는 경우는 반복문 등이 있을 때로, 하나의 단위 작업이 여러번 수행되는 경우를 의미합니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
답글이 늦었습니다!
4번쯤 써보니까 큰돌님의 설명과 함께 이해가 됩니다!!
감사합니다!!