[코드트리 조별과제] - 조금 복잡한 시간복잡도

https://www.codetree.ai/missions/6/problems/time-complexity-3?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제

 

풀이과정

첫번째 문제

• k for문 -> 내부구문은 시간복잡도가 O(1), 0부터 i까지 i+1번 반복되기 때문에 시간복잡도가 O(i). 이떄 i는 최댓값이 n^2이므로 시간복잡도는 O(N^2)
• j for문 -> 내부구문은 시간복잡도가 O(1), j가 0부터 n까지 n+1번 반복되기 때문에 시간복잡도가 O(N)
• 바깥 for문 -> n^2만큼 반복.
• 따라서 O(N^2 * N^2) + O(N^2 * N) 이므로 O(n*4)

두번째 문제

• while문에서 i가 1일때 반복횟수는 0, i가 2일때 반복횟수는 1, i가 4일때 반복횟수는 2, i가 8일때 반복횟수는 3....
• i가 2배늘어날때마다 while문의 반복횟수가 1씩 늘어남
• i에 대해 log i 반복이 필요 -> while문의 시간복잡도는 O(log i) -> O(log N)
• while문을 for문에서 N번 반복
• 따라서 O(log N * N) = O(N log N)

 

답

O(n*4), O(N log N)