[자료구조] Time Complexity (시간 복잡도)

Time Complexity (시간 복잡도)

• 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도
• 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계
• 알고리즘의 로직이 얼마나 오랜 시간이 걸리는지 나타내는 데 사용
• 알고리즘의 로직을 코드로 구현할 때, 효율적으로 구현하기위해 고려해야 함
  • 효율적인 알고리즘 구현: 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성
• 주로 빅-오 표기법을 사용해 나타냄

시간 복잡도를 표기하는 방법

• Big-O(Big-Oh, 빅-오) ⇒ 상한 점근, 최악의 경우에 대해 나타내는 방법
• Big-Ω(Big-Omega, 빅-오메가) ⇒ 하한 점근, 최선의 경우에 대해 나타내는 방법
• Big-θ(Big-Theta, 빅-세타) ⇒ 빅 오와 빅 오메가의 공통부분, 최소와 최악의 중간인 평균적인 복잡도

 

Big-O 표기법

• 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 표기법
•  ‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’를 표기하는 방법

Big-O 표기법의 종류

1. O(1)
   • 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않음
   • 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있음
2. O(n)
   • 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미
   • 입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미가 점점 없어지기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기
3. O(log n)
   • 로그 복잡도(logarithmic complexity)라고 부르며, Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도
4. O(n2)
   • 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미
   • n3과 n5 도 모두 O(n2)로 표기
5. O(2n)
   • 기하급수적 복잡도(exponential complexity)라고 부르며, Big-O 표기법 중 가장 느린 시간 복잡도

 

자료구조에서의 시간 복잡도

자료 구조의 평균 시간 복잡도

자료 구조	접근	탐색	삽입	삭제
배열 (Array)	O(1)	O(n)	O(n)	O(n)
스택 (Stack)	O(n)	O(n)	O(1)	O(1)
큐 (Queue)	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트 (Double Linked List)	O(n)	O(n)	O(1)	O(1)
해시 테이블 (Hash Table)	O(1)	O(1)	O(1)	O(1)
이진 탐색 트리 (BST)	O(log n)	O(log n)	O(log n)	O(log n)
AVL 트리	O(log n)	O(log n)	O(log n)	O(log n)
레드 블랙 트리	O(log n)	O(log n)	O(log n)	O(log n)

 

자료 구조의 최악의 시간 복잡도

자료 구조	접근	탐색	삽입	삭제
배열 (Array)	O(1)	O(n)	O(n)	O(n)
스택 (Stack)	O(n)	O(n)	O(1)	O(1)
큐 (Queue)	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트 (Double Linked List)	O(n)	O(n)	O(1)	O(1)
해시 테이블 (Hash Table)	O(n)	O(n)	O(n)	O(n)
이진 탐색 트리 (BST)	O(n)	O(n)	O(n)	O(n)
AVL 트리	O(log n)	O(log n)	O(log n)	O(log n)
레드 블랙 트리	O(log n)	O(log n)	O(log n)	O(log n)