시간 복잡도와 공간 복잡도

시간 복잡도와 공간 복잡도 

접근적 표기법  : 
알고리즘의 실행 시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존한다. 이 속도는 알고리즘이 실행되는 소프트웨어와 하드웨어의 환경에 의존적이다. 이 속도는 알고리즘이 실행되는 소프트웨어와 하드웨어의 환경에 의존적입니다. 이렇게 환경에 의존적인 알고리즘을 속도로만 평가할 수 있는가?

알고리즘 실행 시간에 대해 두 부분으로 나누어 보자. 
1. 입력값의 크기에 따른 알고리즘의 실행 시간
2. 실행 시간의 성장률 

1번, 입력값 크기에 따른 알고리즘의 실행 시간은 직관적으로 이해가 가능, 배열의 크기가 커지면 선형 검색과 이진 검색의 최악으로 추측되는 연산 횟수가 커진다는 사실, 지도에서 길찾기를 할 때 탐색해야 할 길들이 골목길까지 포함하는게 아니라 오직 고속도로만 탐색한다는 조건을 걸면 더욱 길을 빠르게 찾을 수 있다는 사실로 알 수 있음. 

2번, 실행 시간의 성장률은 입력값의 크기에 따라 이 함수가 얼마나 빨리 커지는지 알아보는 것을 의미합니다. 이를 알기 위해선 알고리즘에서 중요하지 않은 부분은 버리고 가장 중요한 부분만 추려내어 함수를 간소화해야 한다. 

중요하지 않은 항목을 제거하여 어떠한 것을 표현하는 것은 점근적 표기법이라고 한다.
 
- 복잡도(Complexity)와 마주하기
복잡도란, 
1. 알고리즘의 성능, 효율성을 나타내는 척도
2. 크게 시간 복잡도(Time Complexity)와 공간 복잡도 (Space Complexity)로 나눌 수 있다.
3. 각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행 시간(연산) 혹은 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시한다.
4. 복잡도를 나타내는 방법으로는 점근 표기법으로  O(빅오), Ω(오메가), Θ (세타) 등이 있고, 주로 빅오와 세타 표기법이 많이 사용된다. 

시간 복잡도와 빅오 표기법  
시간 복잡도는 특정 크기의 입력(n)을 기준으로 실행하는 연산의 횟수이다. 
알고리즘에서 핵심이 되는 연산의 횟수만 세면 된다. 

복잡도(complexity)의 개념
알고리즘의 성능분석에 중요한 핵심은 복잡도(complexity)이다. 이를 결정하는 두가지 복잡도에 대해 알아보자.공간 복잡도(space complexity)와 시간복잡도(time complexit)가 있다. 

알고리즘은 유한한 횟수의 명렁어들을 정해진 순서에 의하여 수행한 다음 종료되어야함. 

시간 복잡도(time complexity): 알고리즘을 실행하여 종료할 때까지 필요한 시간
공간 복잡도(space complexity): 알고리즘을 실행하여 종료할 때까지 필요한 기억장치의 크기

공간 복잡도(Space complexity)

주어진 알고리즘을 실행시키기 위해 필요한 기억장치(space)는 다음과 같이 두 가지로 분류해 볼 수 있다.

1. 알고리즘과 무관한 부분 : 알고리즘의 특성과는 무관한 부분으로 프로그램 코드를 저장하기 위한 공간, 프로그램을 수행하기 위해 시스템이 필요로 하는 공간 등이 이에 포함된다.
2. 알고리즘과 밀접한 부분 : 알고리즘의 특성과 밀접한 관계가 있는 부분으로서 문제를 해결하기 위해 필요로 하는 공간을 의미한다. 즉, 변수를 저장하기 위한 공간이나 순환 프로그램일 경우 순환 스택(recursion stack)등이 이에 포함된다. 

일반적으로 알고리즘의 공간 복잡도를 분석할때는 위의 두가지 중 두 번째의 것을 계산하게 된다. 
즉, 알고리즘이 문제를 해결하기 위해서 반드시 필요한 부분만은 계산함으로써 주어진 알고리즘의 공간 복잡도를 계산한다. 


공간 복잡도의 계산 1
float abc(float a, float b, float c) {
return (a + b + b*c + (a + b -c)/ (a + b) + 4.0);
}

공간 복잡도 = 0


위의 프로그램에서 공간복잡도를 구하기 위해서 살펴볼 것은 변수 a, b, c이다. 따라서, float형의 변수가 한 워드(word)를 차지한다고 가정하면, 공간복잡도는 '3워드'라고 생각할 수 있다. 그러나  a, b, c는 전달되는 인자(parameter)로서 함수 abc내에서 해결하고자 하는 문제와는 무관하다고 볼 수 있으므로 공간 복잡도는 0이다. 

공간 복잡도 계산2
float sum(float a[], int n)
{
float s = 0.0;

for(int i = 1; i<=n; i++)
s += a[i];
return s;
}

공간 복잡도 = n + 3
위의 프로그램에서 사용되는 변수는 a[], n, s, i이다. 이번 예에서도 a[]와 n은 인자로 전달됨을 볼 수 있다. 그러나 [예제 4.1] 과는 다르게 변수 a[]는 합을 구하기 위하여 반복문 내에서 n개의 원소가 모두 참조되고 있음을 볼 수 있다. 또한, n은 for-문을 벗어나기 위한 한계값으로 사용된다. 따라서 a[]와 n은 알고리즘이 해결하고자 하는 문제와 밀접한 관련이 있다고 볼 수 있다. 그러므로 프로그램의 복잡도는 (a[]를 저장하기 위한 공간) + (변수 n, s, I를 위한 공간) = n + 3이 된다. 

[예제 4.3] 공간 복잡도 계산 3
float RSum(float a[], int n)
{
if(n <= 0)
return (0.0);
else
return (RSum(a, n-1) + a[n]);
}

공간 복잡도 : 3(n+1)

위의 프로그램은 순환기법(resursion)으로 작성된 것이다. 위의 경우 살펴볼 변수는 a[], n이다. 우선 변수는 n은 if문 내에서 순환의 한계값으로 사용되고 있음을 볼 수 있다. 또한 변수 a[] 는 합을 구하기 위하여 사용되고 있으며 a[]의 원소 중에서 n번째의 원소만 필요로 한다. 따라서 변수 a[]와 n이 모두 알고리즘과 밀접한 관계가 있으므로, 프로그램이 필요로 하는 공간은 (a[]의 n번째 원소를 위한 공간) + (n을 위한 공간) = 1 + 1으로 볼 수 있다.
그러나 위의 프로그램은 순환기법에 의해 작성되었음을 고려해야 한다. 
즉, 프로그램이 순환적으로 실행될 것을 고려해서 몇번의 순환 후에 실행이 종료되는지 (the depth of recursion)를 계산해야 하며, 또한 순환을 위해서 필요한 복귀 주소(return address)를 저장할 공간도 계산해야 한다. 

 

시간 복잡도 

시간 복잡도란 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수를 나타낸다.

이름은 시간 복잡도이지만 실행 시간이 아닌 연산 횟수를 세는 이유는 다음과 같다. 

• 모든 OS, IDE, 플랫폼에서 동일한 결과가 나오지 않는다.
• 실행 시간 측정을 위한 또다른 방법이 필요하다.

 

알고리즘의 성능 평가 Case

• 최선의 경우 (Bests Case)
  
  • 최적의 입력을 한 상태에서, 작업을 완료하는 데 가장 연산 횟수가 적은 경우
• 최악의 경우 (Worst Case)
  • 최악의 입력을 한 상태에서 작업을 완료하는 데 가장 연산 횟수가 많은 경우 
• 평균의 경우 (Average Case)
  • 여러 경우의 수를 고려하여, 총 연산 횟수를 계산하고 시행 횟수로 나눈 경우

알고리즘 분석 시 평균의 경우와 최악의 경우가 가장 많이 활용되며, 알고리즘이 복잡해질수록 평균을 구하기 어려워져 최악의 경우로 알고리즘 성능을 파악한다. 

 

시간 복잡도 예시

양의 정수 n을 n번 더하는 계산을 진행한다고 가정해보자. 

n X n 을 계산하는 것과 n을 n번 더한 것을 계산하는 등 여러 방법이 있습니다. 

 

/** Case 1 */

sum <- n * n;

 

/** Case 2 */

sum <- 0

for i <- 1 to n do

     sum <- sum + n;

 

/** Case 3 */

sum <- 0

for i <- 1 to n do

    for j <- 1 to n do 

          sum <- sum + 1;

연산 종류	Case 1	Casae 2	Case 3
대입 연산	1	n + 1	n * n + 1
덧셈 연산		n	n * n
곱셈 연산	1
나눗셈 연산
전체 연산 횟수	2	2n + 1	2n^2 + 1

 

곱셈 연산은 덧셈 연산보다 시간이 더 소요되지만 동일하다고 가정할 경우라도 위 3개의 알고리즘을 비교할 수 있다. 

하나의 연산이 t만큼의 시간이 필요하다고 가정한다면 Case 1의 경우는 2t만큼의 시간이 필요하고 Case 2의 경우

(2n + 1)t 만큼의 시간, 마지막으로 Case 3의 경우에는 (2n^2 + 1)t 만큼의 시간이 필요합니다. 

 

 

참고 문헌 : )

https://yoosioff.oopy.io/4441ae46-8edb-44c2-8752-4f0931875866

시간복잡도, 공간복잡도

https://madplay.github.io/post/time-complexity-space-complexity

시간복잡도와 공간복잡도(Time Complexity Space Complexity)

https://servertrix.com/880