시간복잡도 (Time Complexity)란?

1. 알고리즘 복잡도 계산 항목

1. 시간 복잡도: 알고리즘 실행 속도
2. 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈

 

 

2. 알고리즘 성능 표기법

Big O (빅-오) 표기법: O(N)

• 알고리즘 최악의 실행 시간을 표기
• 가장 많이/일반적으로 사용함
• 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이다.

 

 

3. 시간복잡도

가장 널리 사용되는 알고리즘의 수행시간 기준

알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현

<시간 복잡도와 입력 크기의 관계> 시간 복잡도가 높다는 것은 입력의 크기가 증가할 때 알고리즘의 수행 시간이 증가한다는 의미이다. 하지만 시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작하는 것은 아니다. 입력의 크기가 작을 때는 시간 복잡도가 높은 알고리즘이 더 빠르게 동작할 수도 있다.

 

 

4. 대문자 O 표기법

• 빅 오 표기법, Big-O 표기법 이라고도 부른다.

• O(입력)

  • 입력 n 에 따라 결정되는 시간 복잡도 함수
  • O(1), O(𝑙𝑜𝑔𝑛), O(n), O(n𝑙𝑜𝑔), O(𝑛^2), O(2^𝑛), O(n!)등으로 표기함
  • 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
    • O(1) < O(𝑙𝑜𝑔𝑛) < O(n) < O(n𝑙𝑜𝑔𝑛) < O(𝑛^2) < O(2^𝑛) < O(n!)

 

• 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 된다.

  • 표현식에 가장 큰 영향을 미치는 n 의 단위로 표기한다.

 

 

출처 : fastCampus Algorithm lecture 

빅 오 입력값 표기 방법

• 예:
  • 만약 시간 복잡도 함수가 2𝑛^2 + 3n 이라면
    • 가장 높은 차수는 2𝑛^2
    • 상수는 실제 큰 영향이 없음

 

 

시간복잡도를 구하는 주요 요소는 "반복문"이 지배한다.