[자료구조] 시간 복잡도, 공간 복잡도

자료구조

자료구조는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 방법을 의미한다.

적절한 자료구조를 선택함으로써 특정 작업을 더 빠르고 효율적으로 수행할 수 있다.

• 예) 배열, 연결 리스트, 스택, 큐, 해시 테이블, 트리, 그래프 등

 

알고리즘

알고리즘은 문제를 해결하기 위한 절차나 방법을 의미한다.

알고리즘의 효율성은 주로 시간 복잡도와 공간 복잡도로 평가한다.

• 예) 정렬 알고리즘, 검색 알고리즘, 그래프 알고리즘, 동적 프로그래밍, 분할 정복 등

 

시간 복잡도

시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다.

동일한 기능을 수행하는 알고리즘이 있다면 시간이 적게 걸리는 것이 좋은 소스다.

 

시간 복잡도를 표현할 때는 빅오(Big O) 표기법을 사용하는데, 가장 빠르게 증가하는 항만을 고려하는 표기법이다.

예를 들어, 동전을 튕겨 뒷면이 나올 확률을 이야기할 때 운이 좋으면 1번에 뒷면이 나오지만 운이 안 좋다면 n번만큼 동전을 튕겨야 하는 경우가 발생한다. 이 최악의 경우를 계산하는 방식을 빅오 표기법이라 한다.

시간 복잡도 그래프

O(1)  <  O(log n)  <  O(n) < O(n log n)  <  O(n²) < O(2ⁿ)

빅오 표기법	명칭	예제
O(1)	상수 시간	스택의 push, pop
O(log n)	로그 시간	이진 탐색
O(n)	선형 시간	for 문
O(n log n)	로그 선형 시간	퀵 정렬, 병합 정렬, 힙 정렬
O(n²)	이차 시간	이중 for 문, 삽입 정렬, 버블 정렬, 선택 정렬
O(n³)	삼차 시간	삼중 for 문
O(2ⁿ)	지수 시간	피보나치 수열

 

O(1) (Constant)

입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘.

데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않음.

 

O(log n) (Logarithmic)

입력 데이터의 크기가 커질수록 처리 시간이 로그만큼 짧아지는 알고리즘.

이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당됨.

 

O(n) (Linear)

입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘.

대표적으로 1차원 for문이 있음.

 

O(n log n) (Log-Linear)

입력 데이터의 크기가 커질수록 처리 시간이 로그 배만큼 늘어나는 알고리즘.

정렬 알고리즘 중 병합 정렬, 퀵 정렬, 힙 정렬이 대표적.

 

O(n²) (Quadratic)

입력 데이터의 크기가 n일 때, n의 제곱에 비례하여 처리 시간이 급수적으로 늘어나는 알고리즘.

이중 루프가 대표적인 구조. 단, m이 n보다 작을 때는 O(nm)로 표시하는 것이 바람직함.

O(2ⁿ) (Exponential)

입력 데이터의 크기가 커질수록 처리 시간이 2의 제곱수 형태로 기하급수적으로 늘어나는 알고리즘.

대표적으로 피보나치 수열이 있음.

 

공간 복잡도

공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.

지금은 예전에 비해 컴퓨터 성능의 발달로 메모리 공간이 넘쳐나 중요도가 떨어졌다고 한다.

 

시간 복잡도의 경우 알고리즘을 잘못 구성하면 결괏값이 나오지 않거나 느린 속도로 나오기 때문에 공간 복잡도보다 시간 복잡도를 더 우선시한다.

 

✨👩‍💻 ✨

시간 복잡도와 공간 복잡도는 반비례적인 경향이 있는데, 최근 대용량 시스템이 보편화되면서 공간 복잡도보다는 시간 복잡도가 우선시되어 프로그래밍하면 좋다.

결론적으로 알고리즘은 시간 복잡도가 중요하다..!

 

 

 

출처

https://velog.io/@cha-suyeon/Algorithm-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%B5%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

이것이 취업을 위한 코딩 테스트다, 나동빈