내가 알기 위해 정리하는.. 알고리즘 그 심오한 세계.. 너무 어렵댜 🤯
0. 알고리즘
프로그래밍에서의 알고리즘은 입력 값을 통해 출력(결과) 값을 얻는 계산 과정으로, 문제를 해결하기 위한 동작이다.
알고리즘 의 조건
- 입력 : 외부의 제공되는 자료, 0개 이상 존재
- 출력 : 최소 1개 이상의 결과
- 명확성 : 모호하지 않은 명령어로 구성되어, 각 수행 과정이 명확해야 함 (정밀/유일성)
- 유한성(종결성) : 유한한 횟수의 명령어 수행 후, 유한 시간 내에 문제 해결(종료)
- 효율성(효과성) : 모든 연산은 유한한 시간 내에 정확하게 수행할 수 있을 정도로 효과적이어야 함
좋은 알고리즘이란?
"문제를 효과적으로 해결하는가"
이해하기 쉽고, 정확하며 빠른 명령을 수행하여 결과를 낼 수 있어야 한다.
1. 복잡도 Complexity
알고리즘에서의 복잡도는 성능을 나타내는 지표로 쓰인다. 동일한 기능을 수행하는 알고리즘이 있다면, 복잡도가 낮은 알고리즘이 좋은 알고리즘이다.
- 시간 복잡도 Time Complexity : 알고리즘의 수행 시간 분석 결과
- 공간 복잡도 Space Complexity : 알고리즘의 메모리 사용량 분석 결과
복잡도는 시간과 메모리에 따라 분석할 수 있는데, 이 분석 결과를 점근적 표기법으로 나타낸다.
점근적 분석 & 점근적 표기법
알고리즘을 진행하며 "N 이 계속 커질 때, 어떤 함수 T(N)이 어떤 형태의 함수로 근사하게 되는지"를 분석하는 것을 점근적 분석이라고 한다.
예시) N → ∞일 때 T(N)의 최고차항을 제외하고는 다 제거점근저 표기법은 점근적 분석을 통해 근사된 함수를 표기하는 방법으로, O(빅오), Ω(오메가), Θ(세타) 등이 있고, 빅오와 세타표기가 많이 사용된다.
2. 시간 복잡도 Time complexity
특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간, "연산의 횟수(시행 횟수)" 로 계산된다.
알고리즘 분석에는 최악과 평균의 경우를 가장 많이 활용하나 알고리즘이 복잡해질 수록 평균을 구하기 어려워져 최악의 경우(Big-O 표기법)로 성능 파악을 진행한다.
- 최선의 경우(Best Case) : 최적의 입력으로 가장 빠른 시간이 걸리는 것 (Big-Ω 빅 오메가)
- 최악의 경우(Worst Case) : 최악의 입력으로 가장 오랜 시간이 걸리는 것 (Big-O 빅 오)
- 평균의 경우(Average Case) : 여러 경우를 대입하여 총 실행 시간을 계산하고 시행 횟수로 나눈 것 (Big-Θ 빅 세타)
2.1. BigO 표기법
-
점근적 상한성
-
계수와 낮은 차수의 항을 제외시키고, 상수는 과감하게 삭제(모두 1로 처리)
-
O(1) (Constant)
- 입력 크기(n)에 상관없이 일정한 시간이 걸림
- 데이터의 크기가 성능에 영향을 미치지 않음
- ex)
배열에서 특정 인덱스 찾기, 해시테이블 추가
-
O(log n) (Logarithmic)
- 입력 크기(n)이 커지면 연산 횟수이 log₂ n 에 비례해서 증가
- 초반에는 빠르지만, 뒤로 갈수록 시간이 증가함
- ex)
이진트리
-
O(n) (Linear)
- 입력 크기(n)에 비례해서 연산 횟수(n)이 증가
- ex)
연결 리스트 순회, 최대값찾기
-
O(n log n) (Linear - Logarithmic)
- 입력 크기(n)가 커질수록 처리 시간이 log 배(n * log₂ n)만큼 증가
- ex)
퀵 정렬, 병합정렬
-
O(n²) (quadratic)
- 입력크기(n)이 커지면 연산 횟수가 n²에 비례
- 데이터가 10배가 되면, 처리시간은 100배가 됨
- ex)
이중 반복문, 버블정렬, 삽입정렬
-
O(2ⁿ) (Exponential)
- 입력 크기(n)가 커지면 연산 횟수가 2ⁿ에 비례
- 데이터의 크기가 커질수록 처리시간이 기하급수적으로 증가
- ex)
피보나치수열
-
빅O 표기법에 사용되는 그래프에서 곡선이 가파를수록 효율성이 떨어진다.
- O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) (faster - slower 순)
시간복잡도를 줄이려면?
- 반복문의 수를 줄이자
- 적절한 자료구조를 활용
- 적절한 알고리즘 사용
3. 공간복잡도 Space Complexity
특정 알고리즘이 어떤 문제를 해결하는데 "얼마나 많은 메모리를 사용" 하는지를 계산한다.
컴퓨터 성능의 발전으로 이전보다는 중요성이 떨어졌지만, 데이터를 많이 다루는 빅데이터 분야에서는 여전히 중요한 지표이다.
알고리즘 실행에 필요한 저장공간 = 고정 + 가변
- 고정공간 :
- 처리 데이터의 양과 무관하게 요구됨(알고리즘과 무관)
- 성능에 영향 없음
- 코드 저장공간 등
- 가변공간 :
- 처리 데이터의 양에 따라 다르게 요구됨(알고리즘 실행과 관련)
- 명령 실행 중 동적으로 필요한 공간
- 성능에 큰 영향
- 순환 스택 등
공간 복잡도에서 이슈가 생긴다면, 보통은 변수 설정이 문제일 수 있다. (변수 설정할 때 쓸데없이 공간을 많이 차지하도록 설정했다던지)
4. 시간복잡도 vs 공간복잡도
시간과 공간은 반비례하는 경향이 있다. 시간을 절약하기 위해 더 많은 메모리를 사용하거나, 메모리를 절약하기 위해 시간을 더 소비하는 것
대체로 시간복잡도를 우선으로 판단된다. (시간복잡도가 맞다면 공간복잡도도 통과됨)
참고 자료
알고리즘(Algorithm)
[Algorithm] 알고리즘이란?
시간복잡도 개념, Big-O(빅 오) 표기법, 점근적 표기법 설명
알고리즘 복잡도
시간복잡도(Time Complexity) 와 공간 복잡도(Space Complexity)
[알고리즘] Time Complexity (시간 복잡도) - 더 자세한 예시가 많이 있다
