시간복잡도(Time Complexity) 1분 요약 정리

<Big O 시간 복잡도 그래프>

• 코드를 짤 때 시간 복잡도를 고려한다는 것은 연산 횟수에 비해 시간이 얼마나 걸리는가를 계산하여 가장 효율적인 알고리즘을 만드는 것을 말한다.
• 항상 입력값으로 0 이상의 수를 입력받는다. 음의 입력값은 시간복잡도를 고려할 때 말이 되지 않는다. 따라서 시간복잡도는 항상 0보다 크다고 가정한다.
• 함수는 더 많은 입력값이 있을 때 더 많은 작업을 필요로 한다.
• 시간 복잡도에서는 모든 상수를 삭제한다.
  • ex) 3n, 5n, 50n 복잡도란 존재하지 않는다. 오로지 n만이 존재한다.
• 알고리즘에서 1보다 작은 지점은 고려하지 않는다.
  • n이 아주 클 때의  경우를 고려한다.
• 다양한 차수 항을 가지고 있는 함수가 있을 때 낮은 차수의 항과 상수는 고려하지 않는다.
  • 오직 제일 큰 차수의 항만이 알고리즘의 시간 복잡도에 영향을 미치기 때문이다.
    • n^3 + n^2 + n + 5의 시간복잡도를 가진 알고리즘이다(X)
    • n^3의 복잡도를 가진 알고리즘이다(O)
• 모든 로그는 서로 배수 관계이기 때문에  로그의 밑에 대해 고려하지 않고, 그냥 log n의 복잡도를 가진다고 표현한다. 
  • 자바에서 math.log(2)가 의미하는 것은 자연로그에 2를 넣는 것을 의미한다. -> ln(2)
  • 자바에서 밑이 10인 로그 2를 구할 때 자연로그 2의 값을 알고 있다면 밑에 대한 로그로 나누면 된다.
    • 자연로그를 분자에 넣고, 바꾸고자 하는 로그로 나눈다. -> ln(2)/ln(10)
  • 여러 알고리즘을 비교하게 되면 계산하기 쉬운 밑을 사용하면 된다.
• 일반적으로 알고리즘 문제의 제한시간은 1초이다. 1초 안에 수행 가능한 연산 횟수는 약 1억 회이다.
  • 즉 테스트 개수가 1만 개일 때 O(n^2)의 알고리즘을 가진다면 100,000,000(1억)이므로 풀이 코드가 O(n^2)이하의 시간복잡도를 가져야만 테스트를 시간 초과없이 통과할 수 있다.

 

<시간복잡도 정리>

시간 복잡도의 종류

• Big-O(빅-오) : same or faster / 최악의 경우를 고려할 수 있다. 
• Little-o(리틀-오) : faster
• Ω(빅-오메가) : same or slower / 최선의 경우를 고려할 수 있다. 
• ω(리틀-오메가) : slower
• θ(세타) : same rate / 평균을 고려할 수 있다.

이 중에서 빅오 표기법이 최악의 경우를 고려하므로 가장 많이 사용한다.

 

빅오 표기법 정리 

O(1)

 constant complexity라고 하며, 입력값의 크기와 관계없이 바로 출력 값을 얻어낼 수 있다.

 

O(log n)

 logarithmic complexity라고 부르며, 빅오 표기법 중에서 O(1) 다음으로 빠른 시간 복잡도를 가진다.

 

O(n)

 linear complexity라고 부르며, 입력값이 증가함에 따라 시간이 같은 비율로 증가하는 것을 의미한다.

 

O(n^2)

 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

 

O(2^n)

 exponential complexity라고 부르며, 빅오 표기법 중에서 가장 느린 시간 복잡도를 가진다. 대표적으로는 재귀로 구현하는 피보나치 수열이 있다.