자료구조 -시간복잡도와 공간복잡도

[ 시간 복잡도와 공간 복잡도 ]

시간 복잡도(Time Complexity)는 n개의 입력 데이터에 대하여 알고리즘이 문제를 해결하는데 얼만큼 시간이 걸리는지를 나타낸 것으로 일반적으로 시간 복잡도를 표기하기 위해 점근 표기법이 사용된다.

공간 복잡도(Space Complexity)는 알고리즘이 실행될 때 사용되는 메모리 양을 말한다.

점근 표기법(Asymptotic notation)은 중요하지 않은 상수와 계수를 제거하여 알고리즘의 실행시간에서 중요한 성장률에 집중하는 방법을 의미한다 (항만 계산한다는 뜻).점근 표기법에는 세가지 종류가 존재하는데,

 Big O(빅-오) 표기법 : O(N) - 알고리즘 최악의 실행 시간을 표기
 Ω (오메가) 표기법 : Ω(N) - 알고리즘 최상의 실행 시간을 표기
 Θ(세타) 표기법 : Θ(N) - 알고리즘 평균 실행 시간을 표기

이 중에서 아무리 최악의 상황에도 이 정도 성능을 보장한다는 빅오 표기법이 일반적으로 사용된다.

O(1) : 상수 시간

• 알고리즘이 문제를 해결하는 데에 필요한 단계의 수가 오직 한 단계인 경우
• 즉, 입력 데이터의 개수와 관계없이 처리 시간 혹은 메모리 사용량이 일정
• 스택에서 Push, Pop

O(log n): 로그 시간

• 알고리즘이 문제를 해결하는 데에 필요한 단계의 수가 연산마다 특정 요인에 의해 감소하는 경우
  이진트리

O(n): 직선적 시간

• 알고리즘이 문제를 해결하는 데에 필요한 단계의 수가 입력 데이터의 개수 n에 비례하는 경우
• 즉, 입력 데이터의 개수에 따라 처리 시간 혹은 메모리 사용량이 선형적으로 증가
• for 문

O(n log n) - 선형 로그 시간

• 알고리즘이 문제를 해결하기 위한 단계의 수가 n번에 그 하나의 n번당 필요한 단계들이 연산마다 특정 요인에 의해 줄어드는 경우
• 퀵 정렬(quick sort), 병합 정렬(merge sort), 힙 정렬(heap sort)

O(n^2) - 2차 시간

• 알고리즘이 문제를 해결하기 위해 필요한 단계의 수가 입력 데이터의 개수 n의 제곱인 경우
• 삽입 정렬(insertion sort), 거품 정렬(bubble sort), 선택 정렬(selection sort)

O(C^n) : 지수 시간

• 알고리즘이 문제를 해결하는 데에 필요한 단계의 수가 주어진 상수값 C의 n제곱인 경우
• 피보나치수열

 

자료구조 별 Big-O 표기법

 

정렬 알고리즘 별 Big-O 표기법