[코드트리] 시간복잡도

문제 링크

아 시간복잡도 너무 어렵다.

function solution1(n)
  for i = 0 ... i < n * n
    for k = 0 ... k <= i
      print("Hi")
    for j = n ... j >= 0
      print("Bye")

위 코드의 시간 복잡도?
O(N^2)까지는 이해 (맨 바깥의 for문)

k for문의 시간 복잡도를 알아보자

0 ~ i까지 진행 => i + 1번 진행 O(i)
i가 0 ~ n * n이기 때문에 k for문의 시간 복잡도는 O(n * n)

j for문의 시간 복잡도를 알아보자

n ~ 0까지 진행 => n번 진행 O(n)

전체의 시간 복잡도!

k for문의 시간 복잡도는 O(n * n)
j for문의 시간 복잡도는 O(n)
이 두 for문들이 n * n번 반복되기 때문에 전체 시간 복잡도는

O(n * n * n * n) + O(n * n * n) => O(n^4)