복잡도

시간 복잡도

빅오 표기법

• 시간 복잡도란 ?
  • ‘문제를 해결하는 데 걸리는 시간과 입력의 함수 관계’
  • 보통 빅오 표기법으로 나타냄

• 예를 들어 ‘입력 크기 n’의 모든 입력에 대한 알고리즘에 필요한 시간이 10$n^2$+$n$이라고 할 때

  for (int i = 0; i < 10; i++) {
  		for (int j = 0; j < n; j++) {
  				for (int k = 0; k < n; k++) {
  						if (true) cout << k << '\n';
  				}
  		}
  }
  for (int i = 0; i < n; i++) {
  		if (true) ~
  }

  • 해당 코드의 시간 복잡도를 빅오 표기법으로 나타내면$O(n^2)$이 된다.
  • ‘가장 영향을 많이 끼치는’ 항의 상수 인자를 빼고 나머지 항을 없앤 것.
  • 입력 크기가 커질수록 연산량이 가장 많이 커지는 항은 n의 제곱항이고, 다른 것은 그에 비해 미미하기 때문에 이것만 신경 쓰면 됨.

시간 복잡도의 존재 이유

• 효율적인 코드로 개선하는 데 쓰이는 척도

 

• $O(n^2)$보다는$O(n)$,$O(n)$보다는$O(1)$을 지향해야 함.

공간 복잡도

• 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말함.

• 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함

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

• 자주 쓰는 자료 구조의 시간 복잡도
  • 자료 구조의 평균 시간 복잡도

    자료 구조	접근	탐색	삽입	삭제
    배열(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)$
    이중 연결 리스트(Doubly linked list)	$O(n)$	$O(n)$	$O(1)$	$O(1)$
    해시 테이블(Hash table)	$O(1)$	$O(1)$	$O(1)$	$O(1)$
    이진 탐색 트리(BST)	$O(logn)$	$O(logn)$	$O(logn)$	$O(logn)$
    AVL 트리	$O(logn)$	$O(logn)$	$O(logn)$	$O(logn)$
    레드 블랙 트리	$O(logn)$	$O(logn)$	$O(logn)$	$O(logn)$

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

    자료 구조	접근	탐색	삽입	삭제
    배열(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)$
    이중 연결 리스트(Doubly 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(logn)$	$O(logn)$	$O(logn)$	$O(logn)$
    레드 블랙 트리	$O(logn)$	$O(logn)$	$O(logn)$	$O(logn)$