알고리즘 복잡도 뽀개기: 2. 재귀 함수와 마스터 정리

#알고리즘 #복잡도 #뽀개기
알고리즘의 시간 복잡도 분석 관련
문제 풀이 위주의 해설 강의입니다. (총 3강)
1. 복잡도 분석 문제와 해설
2. 재귀 함수와 마스터 정리
3. 복잡한 복잡도 문제 풀이
전체 재생목록 바로가기:
• 알고리즘 복잡도 뽀개기
강의자료 다운로드:
drive.google.c...
주니온TV@UA-cam - 자세히 보면 유익한 코딩 채널
/ 주니온tv

[@kgwgo1]

7:58초
3번째 연습문제를 보면
a = b^k 이므로
마스터 정리에 의해
O(N^3 * logN)이 되어야하는거 아닌가요???
if (a > b^k) 로 보시고 시간 복잡도를 계산하신 게 아닌가 싶습니다 !

[@joonion]

맞네요! 오류 지적해 주셔서 고맙습니다. ^^;

[@TW-l4x]

좋은 강의 정말 감사합니다!!

[@ililillliilillilllliliilii4724]

14:45 여기서, k가 1인 이유가 무엇인가요? 반복문이 없으니 0이 되는 것이 아닌가요?

[@joonion]

div rem 연산이 n번 실행되니까 0이 아니라 1이라고 봐야겠네요.

[@Amolang991]

9:52에서 mergesort가 return을 안하는데 pseudocode인건가요?

[@joonion]

전체 코드는 in-place sort로 구현되어서 그렇습니다. 슈도 코드로 보시면 됩니다 ^^;

[@조성욱-i5d]

7:20초
두번째 T(n)의 경우
logb(a) 값 > k니깐
문제의 답이 n^2 아닌지요?

[@joonion]

네. 오류를 정확히 보셨네요. ^^;