자료구조

[자료구조] 복잡도

soowitty 2023. 10. 22. 15:55

💡 본 글은 면접을 위한 CS 전공지식 노트 도서를 참고하여 정리하였습니다.

intro - 자료구조와 알고리즘

사전적 의미의 자료구조는 대량의 데이터를 효율적으로 접근 · 관리할 수 있는 데이터의 구조를 뜻한다.
쉽게 말해, 데이터를 담는 그릇(Data Container) 이라고 할 수 있다.

대부분의 자료구조는 특정 상황의 문제를 해결하는 데에 특화되어 있다. 따라서, 많은 자료구조를 알아두면 문제를 빠르고 정확하게 해결할 수 있다.

알고리즘이란 어떤 문제를 풀거나 계산하기 위한 일련의 유한한 절차이다.

📌 입력한 값이 자료구조에 저장되고, 자료구조에 저장된 값에
연산을 적용하여 원하는 출력을 계산하는 절차가 알고리즘이다.

알고리즘의 성능을 분석할 때 복잡도를 사용한다.
복잡도는 시간 복잡도와 공간 복잡도로 나뉜다. 시간 복잡도는 알고리즘의 시간 효율성을,
공간 복잡도는 알고리즘의 공간(메모리) 효율성을 의미한다.

알고리즘이 어떤 문제를 해결하는데 걸리는 시간과 입력 크기의 관계를 나타낸 것이다.

복잡도를 표기하는 대표적인 방법으로, 알고리즘의 최악의 실행시간을 표기한다.
최악일 경우를 판단하면 평균과 가까운 성능으로 예측하기 쉽다.

최고차항만을 표기한다. 상수항, 계수, 영향력 없는 항은 무시한다.

- 알고리즘의 실행시간 보다는 데이터나 사용자 증가율에 따른 알고리즘 성능을 예측하는 것이 목표이기 때문
- 입력 값이 충분히 크다고 가정했을 때, 증가 속도 측면에서 나머지 항이 차지하는 비중이 상대적으로 미미하다. 따라서 크게 의미가 없음

즉, Big-O는 불필요한 연산을 제거하여 알고리즘 분석을 쉽게하는 것이 목적이다.

1) 상수항 무시
O(N+5) -> O(N)

2) 계수 무시
O(3N) -> O(N)

3) 영향력 없는 항 무시
O(2N^2+N+5) -> O(N^2)

표기법	설명	예
O(1)	입력 데이터 크기와 상관 없이 실행시간이 언제나 일정한 알고리즘	스택에서 push, pop
O(logn)	연산이 한 번 실행될 때 마다 데이터의 크기가 절반 감소하는 알고리즘	이진 탐색 알고리즘, tree 형태 자료구조 탐색
O(n)	입력값이 증가함에 따라 실행시간도 선형적으로 증가하는 알고리즘	for문
O(nlogn)	대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다.	퀵 정렬, 병합정렬, 힙 정렬
O(n^2)	입력 데이터를 n만큼 반복하는데, 그 안에서 또 n만큼 반복하는 알고리즘	이중 for문, 삽입정렬, 거품정렬, 선택정렬
O(2^n)	주로 재귀적으로 수행하는 알고리즘이 이에 해당한다.	피보나치 수