알고리즘 복잡도 편집하기

알고리즘 복잡도(Algorithm Complexity)는 알고리즘이 수행하는 연산의 수와 사용되는 자원의 양을 분석하여 성능을 평가하는 개념이다. 복잡도는 일반적으로 실행 시간(Time Complexity)과 공간 사용량(Space Complexity)으로 나뉜다.
==개요==
알고리즘 복잡도는 입력 크기(n)에 따라 알고리즘이 얼마나 효율적으로 실행되는지를 평가하는 척도이다. 주요 분석 요소는 다음과 같다.
*'''시간 복잡도(Time Complexity)''' - 입력 크기에 따른 연산 횟수를 측정.
*'''공간 복잡도(Space Complexity)''' - 입력 크기에 따른 메모리 사용량을 측정.
*'''최선/평균/최악의 경우 분석''' - 특정 입력 조건에서의 성능을 평가.
==시간 복잡도(Time Complexity)==
시간 복잡도는 알고리즘이 실행되기까지 수행해야 하는 기본 연산의 횟수를 나타낸다. 일반적으로 빅-오 표기법(Big-O Notation)을 사용하여 표현한다.
===시간 복잡도의 표기법===
시간 복잡도는 입력 크기 n에 대한 함수로 표현되며, 가장 큰 차수의 항만 남겨서 분석한다.
*'''O(1)''' - 상수 시간(Constant Time)
**특정 입력 크기에 관계없이 일정한 시간이 걸림 (예: 배열의 첫 번째 원소 접근).
*'''O(log n)''' - 로그 시간(Logarithmic Time)
**입력 크기가 증가할수록 실행 시간이 느리게 증가 (예: 이진 탐색).
*'''O(n)''' - 선형 시간(Linear Time)
**입력 크기에 비례하여 실행 시간이 증가 (예: 배열 탐색).
*'''O(n log n)''' - 선형 로그 시간(Linearithmic Time)
**입력 크기에 log n을 곱한 시간 복잡도 (예: 병합 정렬, 퀵 정렬 평균 경우).
*'''O(n²)''' - 이차 시간(Quadratic Time)
**입력 크기의 제곱에 비례하여 실행 시간이 증가 (예: 버블 정렬, 삽입 정렬).
*'''O(2ⁿ)''' - 지수 시간(Exponential Time)
**입력 크기가 커질수록 실행 시간이 급격히 증가 (예: 피보나치 수열 재귀).
*'''O(n!)''' - 계승 시간(Factorial Time)
**입력 크기 n! 만큼 연산이 필요 (예: 브루트 포스 순열 생성).
===알고리즘별 시간 복잡도 예시===
*'''탐색'''
**선형 탐색(Linear Search) - O(n)
**이진 탐색(Binary Search) - O(log n)
*'''정렬'''
**버블 정렬(Bubble Sort) - O(n²)
**퀵 정렬(Quick Sort) - O(n log n) (평균)
**병합 정렬(Merge Sort) - O(n log n)
*'''그래프 알고리즘'''
**다익스트라 알고리즘(Dijkstra's Algorithm) - O(V²) 또는 O((V+E) log V) (우선순위 큐 사용 시)
**플로이드-워셜 알고리즘(Floyd-Warshall) - O(V³)
==공간 복잡도(Space Complexity)==
공간 복잡도는 알고리즘이 실행될 때 사용하는 추가 메모리 공간을 측정하는 개념이다.
*'''O(1)''' - 추가 메모리 없이 실행 가능 (예: 변수 하나만 사용하는 알고리즘).
*'''O(n)''' - 입력 크기에 비례하여 메모리 사용 (예: 리스트 저장).
*'''O(n²)''' - 행렬을 저장하는 경우 발생 (예: 그래프의 인접 행렬).
===재귀 호출의 공간 복잡도===
재귀 알고리즘에서는 추가적으로 '''호출 스택(Stack Space)'''이 필요하다.  예를 들어, 피보나치 재귀 호출은 O(n) 만큼의 추가 메모리를 소비한다.
==최선, 평균, 최악의 경우 분석==
알고리즘의 성능을 평가할 때는 다양한 입력에 대해 다음과 같은 경우를 분석한다.
*'''최선의 경우(Best Case)''' - 알고리즘이 가장 빠르게 수행되는 경우.
*'''평균적인 경우(Average Case)''' - 일반적인 입력을 고려한 실행 시간.
*'''최악의 경우(Worst Case)''' - 실행 시간이 가장 오래 걸리는 경우.
예를 들어, 퀵 정렬(Quick Sort)의 시간 복잡도는 다음과 같다.
*최선: O(n log n) (균등한 피벗 분할)
*평균: O(n log n)
*최악: O(n²) (이미 정렬된 경우, 최악의 피벗 선택)
==빅-오 표기법(Big-O Notation)의 특징==
*'''상수 계수 무시''' - O(2n) → O(n), O(3n²) → O(n²)
*'''낮은 차수 무시''' - O(n² + n) → O(n²)
*'''곱셈 연산 유지''' - O(n log n) 유지
==복잡도 비교==
다음은 주요 시간 복잡도 비교표이다.
{| class="wikitable"
|+알고리즘 복잡도 비교
|-
!복잡도!!입력 크기 10!!입력 크기 100!!입력 크기 1000
|-
|O(1)||1||1||1
|-
|O(log n)||3.3||6.6||10
|-
|O(n)||10||100||1000
|-
|O(n log n)||33||660||10000
|-
|O(n²)||100||10000||1000000
|-
|O(2ⁿ)||1024||1.26×10³⁰||1.07×10³⁰⁰
|}
==알고리즘 복잡도 최적화 방법==
*'''데이터 구조 최적화''' - 배열 대신 해시 테이블 사용 등.
*'''동적 프로그래밍 적용''' - 중복 연산을 줄여서 시간 단축.
*'''분할 정복 기법 활용''' - 문제를 작은 부분으로 나누어 해결.
==같이 보기==
*[[시간 복잡도]]
*[[공간 복잡도]]
*[[빅오 표기법]]
*[[정렬 알고리즘]]
*[[검색 알고리즘]]
설명	입력하는 내용	문서에 나오는 결과
기울임꼴	''기울인 글씨''	기울인 글씨
굵게	'''굵은 글씨'''	굵은 글씨
굵고 기울인 글씨	'''''굵고 기울인 글씨'''''	*굵고 기울인 글씨*