시간복잡도

• 문제를 효율적으로 해결했는지 판단하는 척도 (입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구현했는가)
• 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?
• 종류
  • Big-O(빅-오) : 최악의 경우, 가장 많이 사용한다.
  • Big-Ω(빅-오메가) : 최선의 경우
  • Big-θ(빅-세타) : 평균

입력값으로 들어올 수 있는 데이터의 최대값을 참고하여 알고리즘이 수용할 수 있는 Big-O를 판단할 수 있다.

대부분의 문제는 실행시간 1초(1억번의 연산)에 가깝게 디자인된다.

• O(N) : 100,000,000
• O(NlogN) : 5,000,000
• O(N^2) : 10,000
• O(N^3) : 500
• O(2^N) : 26
• O(N!) : 11

예를 들어, 입력값의 크기가 100이라면 굳이 O(n)이나 O(logn)까지 최적화를 시키지 않더라도 O(n2)나 O(n3)으로 충분히 알고리즘을 구현할 수 있다.

Quiz

아래 코드의 시간복잡도는?

for (let i = 0; i < n; i++) {
	i *= k;
}

O(logn) 또는 O(logk(n)

k배수만큼 i가 커지며 n에 도달하고 있기 때문에 logk(n)이지만 log base는 big O notation에서 중요하지 않으므로 logn으로 표현 가능하다.