1. 복잡도
알고리즘의 성능, 효율성을 나타내는 척도로 시간 복잡도와 공간 복잡도가 있다.
1-1. 복잡도의 종류
- 시간 복잡도(수행 시간)와 공간 복잡도(메모리 사용량)가 있다.
- 주어진 특정 크기의 입력(n)을 기준으로 수행시간 (시간 복잡도)와 사용공간(공간 복잡도)이 얼마나 되는지 비교할 수 있는 기준을 제시한다.
1-2. 빅오(Big-O) 표기법을 주로 사용하는 이유?!
시간 복잡도에는 빅오 표기법 외에도 3가지 표기법이 존재한다.
: 오메가(가장 빠른 수행시간 분석), 세타(평균 시간 분석), 빅오(가장 최악의 수행시간 분석)
- 이 중에서 세타와 빅오 표기법을 주로 사용하는데, 사실상 빅오 표기법을 더 많이 사용한다. (세타 표기법도 사용되지만, 알고리즘이 복잡해질수록 평균 시간을 분석하기 어렵기 때문에 빅오를 더 많이 사용한다.)
최악의 상황을 보장할 수 있기 때문에 빅오 표기법을 이용한다.
2. 빅오 (Big - O) 표기법
2-1. 빅오 표기법의 정의
n ≥ n0인 모든 n에 대해 f(n) ≤ c · g(n)를 만족하는 양의 상수 c와 n0가 존재하면 f(n) = O(g(n))이다.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) O(1)로 갈 수록 더 좋은 효율을 가진 것이다.
2-2. 빅오 표기법 특징
-
상수항 무시
- 빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정한다.
- 결과적으로 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 상수항은 무시하고 작성한다.
O(3N) → O(N)처럼 상수항을 무시하고 표시
-
최고차항만 표시
- 빅오 표기법은 데이터 입력값에 영향을 받기 때문에, 최고차항을 제외한 다른 항들은 무시해도 된다.
O(N^2 + N + 1) → O(N^2)처럼 최고차항을 제외하고선 다 무시한다.
✅ 위의 규칙을 적용해 최종적으로 표현하면 O(N^2 + N + 1) → O(N^2)
3. 시간 복잡도
입력 크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간으로, 주요 로직의 반복 횟수(연산의 횟수)를 중점적으로 측정된다. 주로 빅오 (Big - O) 표기법으로 나타낸다.
3-1. 왜 반복 횟수?!
- 왜 하필 반복 횟수를 중점적으로 측정하는 것일까? 코드가 실행될 때의 시간을 측정하면 되는 것 아닐까?!
- 실행 시간은 하드웨어나 프로그래밍 언어에 따라서 편차가 있다. 그렇기 때문에 반복 횟수를 측정해 사용하는 것이다.
- 같은 기기라도 실행할 때 마다 약간의 오차가 발생하게 된다.
❗ 그렇다면 반복 횟수를 측정하면 된다.
어떠한 컴퓨터를 사용해도 반복 횟수는 변하지 않는다. 그래서 이러한 기준을 바탕으로 시간 복잡도를 측정하는 것이다.
4. 공간 복잡도
프로그램을 실행시켰을 때, 필요로 하는 자원 공간의 양을 의미한다.
총 공간 = 고정 공간 + 가변 공간
- 고정 공간 : 알고리즘과 무관하게 요구되는 공간
- 가변 공간 : 알고리즘과 밀접한 공간
5. 알고리즘 판단
❓그렇다면 알고리즘 성능을 파악할 때 뭐가 더 중요할까?
보통 알고리즘 성능을 판단할 때는 시간 복잡도를 기준으로 판단한다. 그리고, 공간 복잡도는 메모리의 발전으로 인해 중요도가 감소하고 있다.
