spicykong   4년 전

안녕하세요. 문제를 풀긴 풀었는데 제가 푼 알고리즘의 시간복잡도가 궁금해서 질문드립니다.

해당 코드의 시간복잡도는 O(N2)인가요?

제출한 소스 코드 링크를 첨부합니다.

https://www.acmicpc.net/source...

WeissBlume   4년 전

대략적으로 이렇게 살펴보면 될 것 같아요:

$$ T(k)=8T(k/3)=8^{\log_3k}=k^{\log_38}\approx k^{1.89} $$

WeissBlume   4년 전

(물론 전체 시간 복잡도는 출력이 $n^2$이라 말씀하신 대로 O(N2)입니다)

spicykong   4년 전

상세한 답변 감사드립니다 :)

시간복잡도를 분석하는 흐름이 이런 방식으로 이루어지는 거군요!

댓글을 작성하려면 로그인해야 합니다.