프로젝트/2차
시간복잡도(Time Complexity)
8기_이지정
2024. 6. 17. 21:32
알고리즘의 효율성
- 시간 복잡도(time complexity) : 알고리즘 수행 시간 ( 즉, 실행에 필요한 CPU 시간 )
- 공간 복잡도(space complexity) : 알고리즘이 수행하는 동안 사용되는 메모리 공간의 크기 ( 즉, 알고리즘 수행에 필요한 변수나 자료의 크기 )
- 여러가지의 변수 ( 하드웨어, 운영체제, 컴파일러, 사용언어 등 )로 인해 알고리즘의 효울성을 객관적으로 평가하기 어려우기 때문에 시간복잡도와, 공간복잡도 등을 사용
알고리즘의 복잡도 분석 방법
- 최악 경우 분석 (Worst-case analysis): 최악의 상황에서 알고리즘의 성능이나 동작 방식을 분석하는 것
- 평균 경우 분석 (Average-case analysis): 일반적인 상황에서 알고리즘의 성능이나 동작 방식을 분석하는 것
- 최선 경우 분석 (Best-case analysis): 가장 이상적인 상황에서 알고리즘의 성능이나 동작 방식을 분석하는 것
복잡도의 점근적 표기
- 시간(공간) 복잡도는 입력 크기에 대한 함수로 표기, 이 함수는 주로 여러개의 항을 가지는 다항식
- 함수를 단순한 함수로 표기하기 위해 점근적 표기(anymptotic notation)을 사용
- 오메가 표기법 (Big - Ω notation) : 최선 경우의 분석, 하한 점근
- 정의 : 두 개의 함수 이 주어졌을 때 모든 0에 대해 을 만족하는 상수 c'와 n0가 존재하면 이다.
- 설명 : 알고리즘이 가장 효율적으로 동작하는 경우를 고려하여 성능을 평가, 이는 알고리즘이 이상적인 상황에서 얼마나 빠르게 동작하는지를 파악 가능
- 세타 표기법 ( θ notation) : 평균 경우 분석, Big - Ω과 Big - θ의 평균
- 정의 : 두 개의 함수 이 주어졌을 때 모든 0에 대해 을 만족하는 상수 c와 c', n0가 존재하면 이다.
- 설명 : 모든 가능한 입력에 대해 알고리즘이 평균적으로 어느 정도의 자원을 소비하는지를 평가, 이는 알고리즘이 실제 사용 환경에서 어느 정도의 성능을 보일지를 파악 가능
- 빅오 표기법 (Big - O notation) : 최악 경우의 분석, 상한 점근
- 정의 : 두 개의 함수 이 주어졌을 때 모든 0에 대해 을 만족하는 상수 c와 n0가 존재하면
- 설명 : 모든 가능한 입력 중에서 가장 비효율적이고 가장 긴 시간이 걸리는 경우를 고려하여 알고리즘의 성능을 평가, 이는 알고리즘이 가장 나쁜 상황에서도 얼마나 잘 동작하는지를 파악하기 위해 중요
Big - O 표기법 (Big - O notation)
1. O(1) : 상수 시간 복잡도(constant time complexity)
// 입력값의 크기에 상관없이 실행시간이 일정한 경우 O(1), 상수는 무시
F(arr[]){
print(a[0]);
}2. O(n) : 선형 시간 복잡도(linear time Complexity)
// O(n)은 입력 데이터의 크기에 비례해서 처리 시간이 걸리는 알고리즘
// n이 1번 늘어날 때마다 처리시간이 1 증가하여 선형적으로 증가
// i의 출력을 n번 반복하기 때문에 O(n)
F(int[] n){
for (int i = 0; i < n; i++){
print(i);
}더보기
* Big - O 표기법 (Big - O notation)은 상한 점근적이기 때문에 앞의 상수는 무시
// 아래의 코드는 i와 j가 n씩 반복하므로 O(2n)이지만,
// Big - O 표기법은 상한 점근적 표현법이므로 앞의 상수의 크기는 무의미
// 때문에 O(n)으로 표기하는 것이 올바름
F(n){
for i to n{
print(i);
}
for j to n{
print(j);
}
}3. O(n^2) : 제곱 시간 복잡도(quardratic time complexity)
// (O^2)의 대표적 예시는 2중 for문
// i 기준의 for문 반복이 j 기준의 for문을 또 돌리기 때문에 두 for문의 반복 수를 곱한 것과
// 같은 시간 복잡도가 나옴
F(int[] n){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
print (i + j);
}
}
}더보기
* O(n*m)
// 아래의 코드는 i가 n번 반복, j가 m번 반복 하므로 O(n*m)으로 표기
F(n, m){
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++)
print0 (i * j);
}
}
}4. O(n^3) : 세제곱 시간 복잡도 (cubic time complexity)
// 삼중 for문의 경우 O(n^3)
// 이중 for문으로 n^2번 반복하면서, 크기가 n인 배열에서 n/2개를 뽑으면서 이들 중 최대값을
// 구하는 것은 n/2에 비례하는 시간이 소요되므로 n에 비례하는 시간 따라서 총 O(n^3)
F(A[], n){
sum = 0;
for(int i = 0; i < n; i++){
for(j = 0; j < n; j++){
k = A[1...n]에서 임의로 n/2개로 뽑을 대 이들 중 최댓값;
sum = sum + k;
}
return sum;
}
}5. O(2^n) : 지수 시간 복잡도(exponential time complexity)
// O(n^2)은 n번 반복할 수록 2의 n제곱만큼 시간이 증가함을 의미
// 재귀함수를 이용하여 피보나치를 구현하면 함수를 두번 호출하는 중복호출이 생겨 O(n^2)
F(n, r){
if (n <= 0) return 0;
else if (n == 1) return r[n] = 1;
return r[n] = F(n-1, r) + F(n-2, r);
}6. O(log n) : 로그(대수) 시간 복잡도(logarithmic time complexity)
// O(log n)은 밑이 2인 log2 n을 일반적으로 나타냄
// 그러나, Big-O는 상한 점근적 표기이기 때문에 log 밑의 의미에 크게 영향을 주지 않음
// 아래의 코드 while(i<n)만 보면 n번 반복할 것 같지만, i = i * 2로 인해 숫자는
// 1 > 2 > 4 > 8 > 16 ... 16인 2의 거듭제곱으로 커지기 때문에 log2n만큼 반복
F(c){
i = 1;
while(i >= 1){
print(i);
i = i * 2;
}
}7. O(n log n) : 로그-선형 시간 복잡도 (log-linear time complexity )
// for문과 while문이 중첩되어 while문은 logn에 곱하기 n번 한 만큼의 반복이 될 것
// for문이 while 내에 중첩되든, while문이 for문 내에 중첩되든 상관없이 반복횟수는
// 각각 반복문의 곱셈
F(n){
for(int i=1;i<n;i++){
j=1;
while(j<n){
print(i,j);
j = j * 2;
}
}
}효율적인 알고리즘이 필요한 이유
- O(n^2)과 O(n log n) 비교
| O(n^2) | 1,000 | 1 백만 | 10 억 |
| PC | < 1초 | 2시간 | 300년 |
| 슈퍼컴 | < 1초 | < 1초 |
| O(n log n) | 1,000 | 1 백만 | 10 억 |
| PC | < 1초 | < 1초 | 5분 |
| 슈퍼컴 | < 1초 | < 1초 | < 1초 |
- 입력의 크기가 작으면 어느 알고리즘을 사용해도 비슷한 수행시간이 걸리나, 입력이 커지면 커질수록 그 차이는 커짐
- 효율적인 알고리즘은 슈퍼 컴퓨터보다 더 큰 차이가 있다고 말할 수 있음 (즉, 값 비싼 하드웨어의 기술 개발보다 효율적인 알고리즘 개발이 훨씬 더 경제적)