[자료 구조] - 복잡도

자료 구조란,

효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합

ex) 배열, 스택, 큐, 이중 연결 리스트 등이 있다.

복잡도

복잡도는 시간 복잡도와 공간 복잡도로 나뉜다.

 

시간 복잡도

시간 복잡도란 '입력 크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간'

 

주요 로직의 반복 횟수를 중점으로 측정되며, 보통 빅오표기법으로 나타낸다.

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

빅오표기법

입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는 지 나타내는 것.
가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항을 없앤 것이다.

 

=> O(n^2) 보단 O(n), O(n) 보단 O(1)를 지향해야 함. 

 

공간 복잡도

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

 

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

 

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

자료구조	접근	탐색	삽입	삭제
배열	O(1)	O(n)	O(n)	O(n)
스택	O(n)	O(n)	O(1)	O(1)
큐	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트	O(n)	O(n)	O(1)	O(1)
해시 테이블	O(1)	O(1)	O(1)	O(1)
이진 탐색 트리	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)

 

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

자료구조	접근	탐색	삽입	삭제
배열	O(1)	O(n)	O(n)	O(n)
스택	O(n)	O(n)	O(1)	O(1)
큐	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트	O(n)	O(n)	O(1)	O(1)
해시 테이블	O(n)	O(n)	O(n)	O(n)
이진 탐색 트리	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)