시간복잡도와 공간복잡도란?

복잡도

시스템이나 시스템 구성 요소 또는 소프트웨어의 복잡한 정도를 나타내는 말

 

시간 복잡도

알고리즘을 수행하기 위해서 프로세스가 수행하는 연산 횟수를 수치화한 것

시간이 얼마나 오래 걸리냐를 나타내는 것이 아니라 연산의 횟수(=실행 횟수)를 수치화한 것이다.

시간 복잡도가 낮을수록 알고리즘의 실행시간이 짧고, 높을수록 실행시간이 길어짐

 

 

 

점근 표기법의 종류

빅오 표기법 : 실행시간이 최악일 때 표기하는 방법

세타 표기법 :                 평균

오메가 표기법 :              최상

 

 

빅오 표기법

알고리즘의 성능을 수학적으로 표기해주는 것

알고리즘의 시간과 공간 복잡도를 표현할 수 있음

 

O(1)

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

데이터가 증가함에 따라 성능의 변화가 없다

예) 스택의 삽입, 삭제

 

O(n)

입력데이터의 크기에 비례해서 처리 시간이 걸리는 알고리즘

n의 크기만큼 처리 시간이 증가한다.

데이터가 시간이 같은 비율로 증가한다. 

예) for문

 

O(2n)

문제 해결에 필요한 단계가 2의 입력값(n) 제곱만큼 수행됨

피보나치수열을 생각하면 된다.

1부터 시작해서 

1,1,2,3,5,8.... 

출처 : 엔지니어대한민국

O(n2)

문제 해결에 필요한 단계가 입력값(n)의 제곱만큼 수행된다.

예) 삽입 정렬, 쉘 정렬, 선택 정렬, 버블 정렬, 퀵 정렬

 

O(log n)

이진검색이라고 생각하면 된다.

예) 이진트리(Binary Tree), 이진 검색(Binary Search)

 

O(nlogn)

문제 해결에 필요한 단계가 n(log2) 번만큼 수행된다.

예) 힙정렬, 2-way 합병 정렬

 

 

빅오에서 상수는 과감하게 버린다.

빅오 표기법에서는 O(2n)이라고 하지 않고 O(n)이라고 표현한다.

O(n2+n2) => O(n2)이라고 표현한다.

 

 

공간 복잡도

공간 복잡도란 프로그램을 실행시킨 후 완료하는데 필요로 하는 자원 공간의 양을 말한다.

고정 공간과 가변 공간이 있으며, 고정 공간은 입력과 출력의 횟수나 크기와 관계없는 공간의 요구를 말한다.

가변 공간은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 동적으로 필요한 공간을 의미한다.

 

필요한 변수만 사용하는 게 좋은 공간 복잡도를 갖는다.

 

정리

시간 복잡도는 얼마나 빠르게 실행되는가?

공간 복잡도는 얼마나 많은 자원이 필요한가?