.gif&blockId=11b00c82-b138-8050-a58b-dcbceda2ef8f)
시간 복잡도(Time Complexity)
•
알고리즘의 수행 시간을 평가
•
실행 환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간 평가
•
기본 연산
◦
데이터 입출력 : copy, move
◦
산술 연산 : add, multiply
◦
제어 연산 : if, while
•
경우
◦
최선의 경우 (Best Case)
▪
빅 오메가 표기법
◦
최악의 경우 (Worst Case)
▪
빅 오 표기법
◦
평균적인 경우 (Average Case)
▪
평균 시간
빅 오 표기법
•
입력 크기가 n일 경우
◦
: 최고차항만 나타냄
◦
: 최고차항의 계수는 제외함.
int func (int n) {
int sum = 0; // 대입연산 1회
int i = 0; // 대입연산 1회
for(i=0; i < n; i++) { // 반복문 n+1회
sum += i; // 덧셈 연산 n회
}
for(i=0; i < n; i++) { // 반복문 n+1회
sum += i; // 덧셈 연산 n회
}
return sum; // 리턴 1회
}
# 해당 알고리즘의 시간 복잡도 : 𝑇(𝑛)=4𝑛+5=𝑂(𝑛)
Python
복사
𝑂(1) - 상수 시간 (Constant time) : 1회 실행
•
입력 크기(n)에 상관없이 일정한 연상을 수행할 때의 시간 복잡도
void func (int n) {
printf("%d\n", n);
}
Python
복사
𝑂(𝑙𝑜𝑔𝑁) - 로그 시간 (Logarithmic time) : 역지수
•
입력 크기(N)가 커질 때 연산 횟수가 logN에 비례해서 증가하면 시간 복잡도는 𝑂(𝑙𝑜𝑔𝑁)
for(i=1; i<=n; i*2) {
...
}
Python
복사
𝑙𝑜𝑔2(2𝑘)=𝑙𝑜𝑔2𝑁
𝑘=𝑙𝑜𝑔2𝑁
𝑂(𝑛) - 선형 시간 (Linear time) : 1차 방정식
•
입력 크기(n)가 커질 때 연산 횟수가 n에 비례해서 증가하면 시간 복잡도는 𝑂(𝑛)
•
연산횟수가 선형적으로 증가하는 형태
for(i=0; i < n; i++) {
...
}
Python
복사
𝑂(𝑛²) - 2차 시간 (Quadratic time) : 2차 방정식
•
입력 크기(n)가 커질 때 연산 횟수가𝑛²에 비례해서 증가하면 시간 복잡도는𝑂(𝑛²)
for(i=0; i < n; i++) {
for(j=0, j < n; j++) {
...
}
}
Python
복사
•
𝑛²에 비례해서 연산수가 증가
𝑂(2ⁿ) - 지수 시간 (Exponential time) : 2회 수행
•
입력 크기가 커질 때 연산수가 𝑛에 비례해서 증가하면 시간 복잡도는 𝑂(2ⁿ)
int func (int n) {
if (n <= 1)
return n;
return func(n-1) + fun(n-2);
}
Python
복사
시간 복잡도 구분
𝑂(1)<𝑂(𝑙𝑜𝑔𝑛)<𝑂(𝑛)<𝑂(𝑛𝑙𝑜𝑔𝑛)<𝑂(𝑛²)<𝑂(2ⁿ)<𝑂(𝑛!)
공간 복잡도(Space Complexity)
•
알고리즘 수행에 필요한 메모리 양을 평가
•
보조공간(Auxiliary Space)과 입력 공간(input size)을 합친 포괄적인 개념
•
보조 공간(Auxiliary Space)은 알고리즘이 실행되는 동안 사용하는 임시 공간
•
그렇기 때문에 입력 공간(input size)을 고려X
공간 복잡도 계산
int sum(int a[], int n)
{
int x = 0;
for(int i = 0; i < n; i++) {
x = x + a[i];
}
return(x);
}
Python
복사
•
int arr[n] : 4*n byte (입력 공간)
•
int n : 4 byte (입력 공간)
•
int x : 4 byte (보조 공간)
•
int i : 4 byte (보조 공간)
해당 알고리즘은 총 4n+12에 메모리를 요구
메모리가 입력 값에 따라 선형적으로 증가하기 때문에 공간 복잡도는 𝑂(𝑛)
배열 기준 크기
•
int arr[1000] :
•
int arr[1000000] :
•
int arr[1000][1000] :
•
int arr[2000][2000] :
•
일반적으로 100만개 이상의 배열을 선언하는 경우는 드물기 때문에 1000만개 이상의 배열을 선언했다면 알고리즘 설계를 제대로 하고 있는지 점검 필요
요구 사항에 따른 적절한 알고리즘 설계
•
N의 범위가 500인 경우: O(𝑛³ )인 알고리즘을 설계하면 풀 수 있음
•
N의 범위가 2,000인 경우: O(𝑛² ) - 일반적인 다중 중첩 반복문
•
N의 범위가 100,000인 경우: O(𝑛log𝑛) - 정렬
•
N의 범위가 10,000,000인 경우: O(𝑛)
시간/n | 1 | 2 | 3 | 4 | 8 | 16 | 32 | 64 | 1000 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
log n | 0 | 1 | 1.58 | 2 | 3 | 4 | 5 | 6 | 9.97 |
n | 1 | 2 | 3 | 4 | 8 | 16 | 32 | 64 | 1000 |
n log n | 0 | 2 | 4.75 | 8 | 24 | 64 | 120 | 384 | 9966 |
n² | 1 | 4 | 9 | 16 | 64 | 256 | 1024 | 4096 | 1000000 |
n³ | 1 | 8 | 27 | 64 | 512 | 4096 | 32768 | 262144 | 1000000000 |
2^n | 2 | 4 | 8 | 16 | 256 | 65536 | 4294967296 | 약 1844경 | 약 1.07 x 10^301 |
n! | 1 | 2 | 6 | 24 | 40320 | 20922789888000 | 약 2.63 x 10^35 | 약 1.27 x 10^89 | 약 4.02 x 10^2567 |
