2447번 - 별 찍기 - 10
안녕하세요. 문제를 풀긴 풀었는데 제가 푼 알고리즘의 시간복잡도가 궁금해서 질문드립니다.
해당 코드의 시간복잡도는 O(N2)인가요?
제출한 소스 코드 링크를 첨부합니다.
https://www.acmicpc.net/source...
대략적으로 이렇게 살펴보면 될 것 같아요:
$$ T(k)=8T(k/3)=8^{\log_3k}=k^{\log_38}\approx k^{1.89} $$
(물론 전체 시간 복잡도는 출력이 $n^2$이라 말씀하신 대로 O(N2)입니다)
상세한 답변 감사드립니다 :)
시간복잡도를 분석하는 흐름이 이런 방식으로 이루어지는 거군요!
댓글을 작성하려면 로그인해야 합니다.
spicykong 4년 전
안녕하세요. 문제를 풀긴 풀었는데 제가 푼 알고리즘의 시간복잡도가 궁금해서 질문드립니다.
해당 코드의 시간복잡도는 O(N2)인가요?
제출한 소스 코드 링크를 첨부합니다.
https://www.acmicpc.net/source...