자료구조, 알고리즘/개념

[알고리즘] 시간복잡도

wnstjd 2023. 11. 6. 10:58

개념

시간복잡도는 입력값에 따른 알고리즘의 대략적인 수행 시간을 나타내는 것이다. 

시간복잡도의 표기법은 세 가지가 있는데 보통은 최악의 경우를 고려하는 Big-O 표기법을 사용한다. 

Big-O 표기법은 O(n)의 형태로 표기하며 괄호안의 수가 알고리즘의 대략적인 수행 시간을 나타낸다.

 

 

점근적 표기법

위에서 시간복잡도는 알고리즘의 대략적인 수행 시간을 나타내는 것이라고 했다.

점근적 표기법은 쉽게 말해 대략적인의 기준을 잡고 수행 시간을 구하는 것이다. 

그 기준은 이미 정해져 있는데, 바로 수행 시간을 식으로 다항식으로 나타내었을 때의 최고차항이다.

최고차항인 이유는 다항식의 결과에 가장 많은 영향을 미치는 것이 최고차항이기 때문이다.

이 말이 잘 와닿지 않는다면 아래의 자료를 읽어보면 쉽게 이해할 수 있을 것이다.

https://ko.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation

 

점근적 표기법 (개념 이해하기) | 알고리즘 | Khan Academy

수학, 예술, 컴퓨터 프로그래밍, 경제, 물리학, 화학, 생물학, 의학, 금융, 역사 등을 무료로 학습해 보세요. 칸아카데미는 어디에서나 누구에게나 세계 최고의 무료 교육을 제공하는 미션을 가진

ko.khanacademy.org

 

 

Big-O

구현한 알고리즘에 따라 여러 종류의 Big-O표기가 나올 수 있겠지만 대략적으로 아래의 다섯가지가 있다.

  • O(1) : stack, queue등의 pop, push
  • O(n) : for 반복문
  • O(log n) : 이진트리
  • O(n log n) : 퀵 정렬, 병합 정렬
  • O(n^2) : 2중 for문, 삽입 정렬, 버블 정렬, 선택 정렬

각 시간복잡도의 수행 시간은 O(1) < O(log n) < O(n) < O(n log n) < O(n^2) 순으로 커진다.