5.1 복잡도

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다.

 

• 빅오 표기법
  
  • 시간 복잡도
    • 입력 크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간
    • 주요 로직의 반복 횟수에 중점을 둠
    • 보통 빅오 표기법으로 나타낸다.

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) cout << i << '\n';
}

=> 10n^2 + n => O(n^2)

가장 영향을 많이 끼치는 상수 인자를 빼고 나머지 항을 없앤 것.

 

 

• 시간 복잡도가 필요한 이유 
  
  • 효율적인 코드로 개선하는데 쓰이는 척도가 된다. 

 

• 공간 복잡도
  
  • 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
  • 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함한다. 
  • int a[1004];이면 int의 크기는 4byte이므로 1004 * 4 btye만큼의 공간이 필요하다. 

 

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

 

평균 시간 복잡도

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(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)

 

최악의 시간 복잡도

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)ㅊ