알고리즘 시간복잡도, 공간복잡도

알고리즘 시간복잡도, 공간복잡도 개념

• 시간복잡도: 주어진 입력에 따라 알고리즘이 실행되는데 걸리는 시간의 양
• 공간복잡도: 주어진 입력에 따라 필요한 저장 공간의 양
• 성능 예측, 효율성 비교, 자원 최적화

알고리즘 복잡도 표기법, 빅오표기법

알고리즘 복잡도 표기법

구분	내용	비고
Big O	알고리즘이 최악의 성능일 때 평가	일반적 분석
Big Ω	알고리즘이 최상의 성능일 때 평가	최적 상황 분석
Big θ	알고리즘의 평균 성능 평가	전반적 성능 분석

• 주로 Big O 표기법으로 알고리즘의 복잡도 평가 및 측정

빅오표기법 유형

연산시간	유형	설명
매우빠름	$O(1)$	자료의 크기와 무관하게 항상 같은 속도로 작용
	$O(logn)$	일정한 크기로 잘라서 해결하는 유형
빠름	$O(n)$	입력순서대로 처리, 자료 크기와 수행시간 정비례
	$O(nlogn)$	분할과 합병, 정렬 알고리즘의 최소한의 복잡도
	$O(n^2)$	입력한 n 크기가 작을시 $nlogn$보다 빠르나, 데이터 크기가 증가시 급격하게 비효율
느림	$O(2^n)$	지수형으로 가능한 해결방법 모두 검사, 매우 비효율적
	$O(n!)$	입력 N에 따라 시간복잡도가 매우 빠르게 증가, 재고려 필요

알고리즘 시간복잡도, 공간복잡도

알고리즘 시간복잡도

구분	내용	사례
$O(1)$	상수 시간복잡도, 입력 크기와 관계 없이 실행	해시테이블
$O(logn)$	로그 시간복잡도, 입력에 따라 로그에 비례	이진 검색
$O(n)$	선형 시간복잡도, 입력에 따라 시간 증가	선형 검색
$O(nlogn)$	선형로그 시간복잡도, 효율적 정렬 알고리즘	병합정렬, 퀵정렬
$O(n^2)$	이차 시간복잡도, 중첩 루프 사용	버블정렬, 삽입정렬
$O(2^n)$	지수 시간복잡도, 피보나치 수열 계산	피보나치 재귀
$O(n!)$	팩토리얼 시간복잡도, 매우 비효율적	순열 생성

알고리즘 공간복잡도

구분	내용	사례
$O(1)$	상수 공간복잡도, 입력 상관없이 일정 공간 사용	스왑 알고리즘
$O(n)$	선형 공간복잡도, 입력 크기 비례 공간 사용	배열, 리스트
$O(n^2)$	이차 공간복잡도, 이차원 배열 사용 공간	행렬 곱셈

알고리즘 복잡도 측정방법

구분	시간복잡도	공간복잡도
실제 측정	실행시간 측정하여 복잡도 측정	메모리 프로파일러 통한 사용량 측정
이론적 측정	빅오 표기법 등 복잡도를 수학적 유도로 분석	알고리즘이 사용하는 변수, 자료구조 분석

• 데이터의 정렬 여부, 중복 여부에 다른 알고리즘의 성능 차이 고려