[DS] 알고리즘 분석

# 알고리즘의 성능 분석

- 설계된 프로그램의 구현이 완료될 때 프로그램 성능 평가 과정이 수행됨

- 프로그램은 여러 개의 알고리즘으로 구성될 수 있으므로 알고리즘의 성능 평가라고 부를 수 있음

- 일반적인 성능 평가 질문의 예: 기준이 모호하고 구체적이지 않으므로

객관적인 평가 방법으로 사용하기에 적합하지 않음

· 프로그램이 본래의 요구 사항들을 만족하고 있는가?

· 오류 없이 올바르게 동작하는가?

· 효율적으로 구현되었는가?

- 실행 가능한 성능 분석 기준: 공간 복잡도(space complexity), 시간 복잡도(time complexity)

- 실행 가능한 성능 분석 기준은 알고리즘 간의 성능 비교가 가능함

  → 측정 가능한 구체적인 수치를 제공하기 때문

 

 

# 공간 복잡도(Space Complexity)

- 프로그램이 수행을 완료하는데 필요로 하는 메모리의 양

- 알고리즘 실행에 필요한 메모리 공간의 양

- 메모리 공간: 고정 메모리 공간 or 가변 메모리 공간

- 고정 메모리 공간: Sc

  > 프로그램이 실행되기 전에 결정되는 요소

  ex) 프로그램 명령어, 고정 크기 변수, 상수 등

  > 한번 할당하면 추가적인 공간 필요하지 않으며 예측 가능

  > 안전함

- 가변 메모리 공간: Sv

  > 프로그램 실행 중에 요구되는 요소들

  ex) 배열 전달(array passing), 재귀 호출 등이 프로그램에 포함되는 경우

  > 실행 중에 요구하는 메모리 공간은 양이 가변적이고 예측이 어렵기 때문에 공간 복잡도 평가에서 더 중요함

  > 실행시에만 알 수 있기 때문에 예측 불가

  > 안전하지 않음

- Total Space Complexity: S = Sc + Sv

 

- example 1: Simple variables

float abc(float a, float b, float c){
  return a + b + c + (a + b -c) / (a + b) + 4.00;
}

 

> input: 세 개의 변수

> output: 단순 변수(float 형)

> Sv(abc) = 0 → 가변 요구 공간: 0

 

- example 2: Sum

float Sum(float list[], int n){
  int i;
  float total = 0;
  
  for(i=0;i<n;i++){
    total = total + list[i]
  
  return total;
}

 

> input: 배열과 정수

> output: 단순 변수(float 형)

> Sv(sum): 배열 전달 방식에 따라 가변 요구 공간이 있을 수도 있고 없을 수도 있음

 

 

- call by value & call by reference

> 환경 또는 언어에 따라 다름

 

- example 3: rsum

float rsum(float list[], int n){
  if(n) return rsum(list, n-1) +  list[n-1] ;
  else return 0;
}

 

> 저장되어야 할 context: return address(4byte), float list[](4byte), int n(4byte)

> n번의 function calls: rsum(n-1) .... rsum(0)

> 공간 복잡도: 12n (context들이 필요한 메모리 공간 * n)

 

 

# 시간 복잡도

- 프로그램이 수행을 완료하는데 걸리는 시간

- T: 컴파일 시간(Tc) + 실행 시간(Te)

  > 컴파일은 완료되고 나면 더 이상 수행되지 않으므로 시간 복잡도 평가에는 실행 시간이 더 중요한 요소

  > 물리적인 프로그램 실행시간을 측정할 수도 있지만 이는 하드웨어 환경에 따라 달라질 수 있음

  → 실행해야 할 명령문의 수를 시간 복잡도로 간주하여 사용

 

실행 명렁문 표 작성법

1. 한 문장에 포함된 명령문의 수를 결정 2. 이 문장이 반복 실행되는 빈도(frequency)를 결정 3. (명령문 수 * 빈도)로 이 문장의 총 실행 횟수를 계산 * 함수의 헤더, 변수 선언문, 블록의 시작과 끝은 명령문으로 간주하지 않음

 

- example1: Iterative Sum

> n: 배열에 저장된 원소의 개수

> ②: 참일 때(i가 0 ~ n-1일 때) + 거짓이 됨을 판별(i가 n과 같아질 때) → n+1

> ③: for의 명령문으로 조건이 참일 때(i가 0 ~ n-1일 때) 실행 → n

 

- example2: Recursive Sum

 

> ①: 참(재귀 호출의 종료조건으로 n이 0이 아닐 때) + 거짓(n이 0이 되면 거짓임을 판별) → n+1

> ②: if문이 참일 때 실행 → n

 

- example3: Matrix Addition

  > (a) + (b) = (c)

> ①: 참(i가 0 ~ rows-1일 때) + 거짓(i가 rows와 같아질 때) → rows + 1

> ②: {참(j가 0 ~ cols-1일 때) + 거짓(j가 cols와 같아질 때)} && ①이 참일 때 → rows*(cols+1)

> ③: ①가 참일 때 && ②가 참일 때 → rows*cols

 

 

 

# 점근적 표기법

- 입력의 수(n)가 매우 커질 때(무한대로 커질 때)

알고리즘의 복잡도(실행 명령문의 수)가 증가하는 패턴을 근사적으로 표현하는 것

- 알고리즘의 성능을 표기하는데 사용

- 상한선(upper bound), 하한선(lower bound), 상한-하한선(upper and lower bound) 존재 유무에 따라

   Ο, Ω, Θ 기호를 사용하여 근사적인 복잡도를 표현

- 분기점: 두 개의 시간 복잡도 함수의 실행 명령문의 수가 바뀌는 시점

- 일반적으로 n이 매우 큰 경우 프로그램의 수행 성능이 더 중요함

> 분기점: 98

 

(1) Big-Oh Notation

- n0 이상인 모든 n에 대해서 f(n) ≤ c·g(n)을 만족하는 양의 상수 c와 n0가 존재한다면

시간 복잡도 함수 f(n) = Ο(g(n))이라고 표기할 수 있음. 그리고 이 반대의 경우도 성립

- 시간 복잡도 함수 f(n) = Ο(g(n))이라고 표기할 수 있다면,

  이 알고리즘의 수행 시간은 상한선 c·g(n)을 넘지 않는다는 의미

  > c·g(n): upper bound → 아무리 시간이 걸려도 이 이상 걸리지 않음

  > tip) c는 최고차항의 계수와 항의 개수를 고려해 적절하게 선택한다

  → g(n)이 f(n)의 각 항들보다 빨리 증가하므로 항의 수와 최고차 항의 계수의 합보다 큰 수로 지정하면

      이 관계는 항상 성립하게 됨

ex. f(n) = n2 + n ≤ n2 + n2 = 2n2 ≤ 2g(n) = Ο(n2)

- Ο(1): k개의 명령어를 수행 → 입력과 무관하므로 상한선이 될 수 없음

  > 상한선은 원래 그래프에 가까울수록 더 정확함

 

- 예제: 시간 복잡도(1-1)

 

> c와 n0을 각각 3과 1로 선택하면, f(n) ≤ 3n3이 항상 만족이 됨

> g(n)에 곱하는 상수 c는 f(n)의 각 항의 수와 최고차 항의 계수를 고려하여 구하면 좋음

> f(n) = n3 + n2 + n ≤ n3 + n3 + n3 = 3n3 = 3g(n)

 

 

- 예제: 시간 복잡도(1-2)

Q. 다음 시간 복잡도를 점근적 표기법으로 쓰시오.

① 2n + 3 = Ο(n) 이유: 모든 n ≥ 3에 대해서, 2n + 3 ≤ 3n

② 10n2 +4n + 2 = Ο(n2) 이유: 모든 n ≥ 5에 대해서, 10n2 +4n + 2 ≤ 11n2

③ 2n + n2 = Ο(2n) 이유: 모든 n ≥ 4에 대해서, 2n + n2 ≤ 2·2n

④ n2 + 2n + 3 ≠ Ο(n) 이유: 이 식을 만족하는 c와 n0가 존재하지 않음

⑤ logn + n + 3 ≠ Ο(logn) 이유: 이 식을 만족하는 c와 n0가 존재하지 않음

 

(2) Big-Omega Notation

- n0 이상인 모든 n에 대해서 f(n) ≥ c·g(n)을 만족하는 양의 상수 c와 n0가 존재한다면

시간 복잡도 함수 f(n) = Ω(g(n))이라고 표기할 수 있음. 그리고 이 반대의 경우도 성립

- n0 이상 모든 n에 대해서 f(n)의 수행 시간은 하한선인 c·g(n)보다 항상 많이 걸림

  → 이 알고리즘의 수행 시간은 최소한 하한선 이상으로 걸림

 

- 예제: 시간 복잡도(2)

Q. 다음 시간 복잡도 함수의 점근적 표기법이 성립함과 식과 그래프로 증명하시오

 

> c와 n0를 양의 상수 2와 1로 각각 선택하면, n ≥ 1인 모든 n에 대하여 2n + 3 ≥ 2n이므로

3n + 2 = Ω(n)으로 표기할 수 있음

 

 

 

 

 

 

 

(3) Big-Theta Notation

- n0 이상인 모든 n에 대해서 c1·g(n) ≤ f(n) ≤ c2·g(n) 을 만족하는 양의 상수 c1, c2, n0가 존재한다면,

시간 복잡도 함수 f(n) = Θ(g(n))이라고 표기할 수 있음. 그리고 이 반대의 경우도 성립

- n0 이상 큰 모든 n에 대해서 f(n)의 수행 시간은 하한선(c1·g(n))과 상한선(c2·g(n)) 사이에 존재

 

- 예제: 시간 복잡도(3)

Q. 3n + 2 = Θ(n)이 성립함을 식과 그래프로 증명하시오

> 모든 n ≥ 3에 대하여, 2n ≤ 2n+3 ≤ 3n

 

(4) 시간 복잡도 함수의 종류

- 시간 복잡도 함수의 종류

점근적 표기	이름	n이 충분히 클 때 수행 속도
Ο(1)	constant	fast
Ο(logn)	logarithm
Ο(n·logn)	log linear
Ο(n)	linear
Ο(n^2)	quadratic
Ο(n^3)	cubic
Ο(2^n)	exponential
Ο(n!)	factorial	slow

- n이 충분히 큰 경우, 수행 속도는 명령문의 수에 반비례하므로 다음과 같음

  > Ο(logn) ≥ Ο(n) ≥ Ο(n·logn) ≥ Ο(n2) ≥ Ο(n3) ≥ Ο(2n)

  > tractable: 풀어볼만한 문제 ex) n, n2

  > intractable: n이 커질 때 사용하기 어려움 ex) 2n, n!

 

https://hellbo2.tistory.com/12