알고리즘 성능과 증가율 : 실험적 분석과 이론적 분석

msung99·2022년 3월 14일

자료구조

성능이란?

자료구조와 알고리즘은 뗄랴야 뗄 수 없다.
알고리즘은 자료구조 + 성능 에 대한 것이기 때문이다.

알고리즘에서의 성능은 아래와 같이 정의된다.

1) 실행시간 (= 러닝타임) 2) 사용된 데이터

실행시간(Running Time)

실행시간의 종류

Average case : 정확히 정의내리기 힘듦
- input의 크기에 따라 Average case의 결과가 달라진다.

Worst case : 모든 케이스 중 가장 오래걸니는 케이스
- 구하기 쉬운 case. 기능과 직접적으로 연관되어있음
Best case : 최선의 경우. 구해도 쓸모없어서 생각자체를 잘 안함

실험적 분석 - Experimental studies

경험적으로 수행시간을 측정하는 방법 : best case time, average case time, worst case time 가 있다.

3가지 방법중에 의미있는 방법은 average case, worst case 이다.

1) average case time (평균시간)

100개의 케이스를 다 책정한다음 모두 합해 100으로 나누는 방법이다.
이는 잘 조정하면 의미있는 데이터가 되겠지만, 일반적인 정의를 내리긴 힘들다.

2) worst case time (최악의 경우)

모든 케이스중 가장 오래걸리는 시간을 책정한다.
이는 구하기 쉽고, 기능과 직접적으로 연관되어있다.
이러한 측정은 clock() 같은 함수를 사용하여 정확한 시간을 측정한다.

cf. 많은 경우에 메모리를 많이 쓰면 시간이 짧게 걸린다.

실험적 분석의 한계 - average case의 한계

1) 알고리즘을 실행하기 위해 오류가 없어야 한다.

2) 모든 인풋 사이즈 케이스에 대한 수행시간이 아니므로 일반화의 오류가 생김 (정확성이 떨어진다)

3) 컴퓨터의 성능(hw, sw환경)에 의해 실행시간이 달라진다

이론적 분석(Theoretical Analysis)

실행시간을 직접 측정해 구해내는 것이 아닌, 인풋크기 n에 관한 함수로 나타내는 것
( 수행시간을 0.01초, 0.5초 이렇게 구하는 것이 아니라, 6n+1 과 같이 표현 )

수도 코드를 분석하는 방법
- 알고리즘을 쓰는 방법(high-level 설명방법 종류) : 1) flow chart(순서도), 2) pseudo code(수도코드)

실행시간을 함수로 표현
- 인풋크기 n 정도면 수행시간이 이 정도 걸릴 것이라는 것을 함수로 표현
함수를 비교하므로 hw, sw 환경에 영향을 받지 않고 수행시간 측정 가능

수도코드(pseudocode) - 이론적 분석법 방법1

정확한 형태없이 쓰지만, 일관성있게 쓰고 모호하지 않게 작성할 것
알고리즘에 대해 high-level에서 서술하는 방법 중 하나

수도코드 키워드 종류 및 형태

Control flow
- if .. then .. [else .. ]
- while .. do ..
- repeat .. until ..
- for .. do ..
Method declaration (함수 선언)

Algorithm 함수명 (인자 값)
Input..
Output..
Method call(함수 호출)
- num.함수명(인자 값)
Return value (리턴 값)
- return ~~
Expression (표현식)
- <- : = (c++의 = 과 동일)
- = : == (c++의 == 과 동일)
- n^2 : 이렇게 수학적 표현도 가능

예시 - 배열의 최댓값찾기 수도코드

Algorithm arrayMax(A, n)
  Input array A of n integers   => n개의 정수로 구성된 배열 A
  Output maximum element of A 
  
  currentMax <- A[0]
  for i<-1 to n-1 do
    if A[i] > currentMax then
      currentMax <- A[i]
  return currentMax

RAM (Random Access Machine) 모델

수도코드에서 사용되는 기본연산(primitive operation)들이 실제로 동작하는 가상의 컴퓨터
가상의 컴퓨터 환경
- CPU 하나(단일 CPU)
- 메모리 제한 없음(메모리는 충분한 모델)
- 메모리의 어느 부분을 접근해도 동일한 단위 시간이 걸린다. (빠름)
메모리에 구애를 받고 프로그래밍을 하는 경우는 거의 없기 때문에, 메모리 제한이 없다고 가정한 것임

primitive operation(기본 연산)
RAM 에서 할수있는 가장 기본적인 연산들
컴퓨터가 할수있는 기본연산들 (예시)
- 사칙연산
- 변수(메모리)에 값 할당하기
- 배열 주소값으로 찾아가기
- 함수 호출
- 함수 끝나고 return 하기

이 기본연산들을 조합해서 프로그램을 만들고, 수도코드로 표현될 수 있다
수도코드에서 이 기본연산들이 몇번이나 사용되었는지 카운팅된다
=> 카운팅 결과가 인풋 크기 n에 대한 함수로 표현됨
RAM 모델에서 모든 기본연산은 수행시간이 상수 1, 즉 단위라고 생각하면 된다.
=> 이 기본연산들이 전체적으로 총 몇번이 실행됐는지 생각해보면 프로그램의 실행시간이 나온다.

기본 연산 횟수 카운팅하기

기본연산(primitive operation) 들의 사용 최대횟수 세기( = 최악의 경우)
카운팅한 결과는 인풋 크기 n에 대한 함수로 나온다.
=> 이것이 이론적 분석임

(즉, 이론적 분석은 기본연산들의 최대횟수를 카운팅한 결과로, 인풋 크기 n에 관한 함수로 표현된다)

Algorithm arrayMax(A, n)
  currentMax <- A[0] // 2 
  for i <- 1 to n-1 do // 2n 
    if A[i] > currentMax then // 2(n-1) 
      currentMax <- A[i] // 1
  return currentMax // 1

currentMax <- A[0]

=> 할당연산(<-)1번 + 인덱싱연산(A[0]) 1번 = 2
for i <- 1 to n-1 do

=> 기본연산횟수 : 2 (더하기 연산i++ 을하고, 비교연산 n-1과 비교함)
반복문이 (n-1) 번 반복되므로 총 2(n-1) 번 실행됨

그리고 반복문 마지막 실행시 i = n-1 일때 1을 더해서(더하기연산) i=n 이 된후 그 값을 n-1 과 비교 연산을 한번한다.
따라서 마지막에 1+1 = 2번 연산을 진행한다. ( 결론 : 2(n-1) + 2 = 2n )
if A[i] > currentMax then

=> 기본연산횟수 : 2 (인덱싱 연산"A[0]" + 비교 연산">")
반복문이 (n-1)번 반복되므로 총 2(n-1) 번 실행됨
currentMax <- A[i]

=> 기본연산횟수 : 2(인덱싱 연산"A[0]" + 할당연산"<-")
반복문이 (n-1)번 반복되므로 총 2(n-1) 번 실행됨
return currentMax

=> 리턴하기 1번
총 연산이 6n-1 번 진행된다.

시간복잡도

입력 데이터의 크기가 커지면 연산의 실행횟수도 커지므로

연산의 실행횟수를 입력 데이터의 크기에 관한 함수로 표현한 것이다.

실행 횟수 계산은 수도코드를 참조한다.

ex) n^2, 2n+3

이때 평균시간 복잡도는 알고리즘이 복잡해질수록 구하기가 굉장히 어렵기 때문에,

비교적 구하기 쉬운 최악의 경우 시간복잡도를 주로 사용한다.

실행시간 추정법

실제 컴퓨터에서는 primitive operation도 수행시간이 다름
때문에 같은 6n-1 번의 primitive operation을 한다고 하더라도,
해당 primitive operation이 무엇인지에 따라 알고리즘 수행시간이 달라짐

가정

arrayMax 알고리즘은 최악의 경우 (6n-1) 의 기본 연산을 했었다.
T(n) : arrayMax의 최악의 경우 실행시간
a : 기본연산중 수행시간이 가장 빠른 것
b : 기본연산중 수행시간이 가장 느린 것

( 예를들어 + 연산이 * 보다 느림. 기본연산들간에 속도 차이가 있음)

결론

a(6n-1) : 가장 빠른 연산 a를 (6n-1)번 진행한 실행시간
b(6n-1) : 가장 느린 연산 b를 (6n-1)번 진행한 실행시간

T(n) 은 가장 빠른 연산들로만 실행한 시간보다는 느릴것이고,
가장 느린 연산들로만 실행한 시간보다는 빠를 것이다.

=> a(6n-1) <= T(n) <= b(6n-1)

따라서 실행시간 T(n)은 두 일차식에 의해 수렴함

실행시간의 증가율(Growth Rate)

하드웨어나 소프트웨어의 환경에 따라 실제 실행시간이 달라질 순 있으나,
cf. primitive operation도 실제 컴퓨터에서의 실행시간은 조금씩 다르므로
입력 크기에 따른 실행시간 증가율은 고정됨.
⇒ 증가율은 알고리즘의 수행능력을 가름짓는 본질이다.

hw, sw 환경을 바꾸면 상수배만큼 실행시간에 영향을 끼치긴한다.
하지만 본질적으로 영향을 미치지 않음. (즉, 함수의 증가율에는 영향x)

ex) T(n) = n^2 인 알고리즘을 성능이 차이나는 컴퓨터 A,B 에서 실행

=> A,B둘다 인풋을 100개를 주고 계산해보고, 인풋을 2배로 200개로 늘리면 A,B에서 걸린시간 모두 기존 실행시간에 비해 4배가 된다. (인풋을 3배로 늘리면 둘다 실행시간이 9배가 됨)
인풋이 100개일때 A,B에서 실행시간이 각각 1초, 10초였다면,
인풋을 200개를 넣었을때의 실행시간은 각각 4초, 40초가 된다.
인풋을 300개로 넣었을떄의 실행시간은 각각 9초, 90초가 된다.

(실제 측정시간은 다를지 몰라도, 100개에서 작동시켰던 시간과 200개에 대해서 작동시켰던 시간은 인풋이 2배가 되면 4배가 된다.)

두 컴퓨터에서 실행시간(측정값)은 다를지 몰라도, 동일한 알고리즘이면 증가율이 어디서 수행하든 동일하다.

증가율이 빨라야(작아야) 엄청큰 인풋이 들어와도 실행시간이 빠른것!!

그냥 인풋 크기 n에 관한 함수로 나타내고 끝내도 되지만, 그 함수를 더 단순화 하기 위해 증가율을 고려한다.

알고리즘의 본질적 특성은 1차함수(선형함수)이다.

빅오 표기법

증가율을 간단하게 나타낸 것

f(n) = O(g(n)) : f(n) <= cg(n) for n >= n0

g(n) 에다 상수를 곱하면 특정지점(n0) 이후부터 항상 f(n) 보다 크다.
즉, g의 증가율이 f의 증가율보다 크다는 것.

ex) g(n) = n, f(n) = 2n+10 일때 g(n) 에다 상수 3으로 곱하면 특정 지점인 n=10 이후로 부터 3g(n) 이 항상 값이 더 크다.
즉, f(n) = O(n) 이다.

O(g(n)) : 상한 함수의 집합. g(n)보다 증가율이 느리거나 같은 함수들을 O(g(n))으로 표현

O(g(n)) 의미, 상한(upper bound)

함수의 집합 => O(g(n)) 이란 g(n) 보다 함수의 증가율이 같거나 더 느린 함수들의 집합이다.

f(n) = O(g(n)) 인 f(n)과 g(n) 이 있다면,

g(n) 이 말하기를 "야! f(n) !! 니가 아무리 커봤자 나보다 더 증가율이 크지 않아. 내가 이 구역에선 증가율이 최고야!" 이런 느낌
ex) f(n) = n^2+1000n + 3 , g(n) = n^2 인 경우, 지금 당장으로는 n=1 과 같이 인풋이 작아도 상수를 100을 곱하면 g(n) = 100n^2 이 되어서 어떤 특정지점(n=n0) 이상부터는 무조건 g(n) 이 더 값이 크게 된다.

ex) O(n^2) 의 집합 : 모든 2차함수(증가율 같은 함수들) + 모든 1차함수 + 모든 nlgn + 모든 ...

=> 이 집합의 모든 함수들은 cn^2 보다 특정지점 기준으로 다 아래에 있다.

O(g(n)) 이 함수 집합의 함수들에게 자신보다 더 위로 올라오게 못하게 막음. 그래서 이를 Big-O 를 upper bound(상한) 이라고도 부름

msung99

블로그 이전했습니다 🙂 : https://haon.blog

이전 포스트

링크드 리스트

다음 포스트