#5 [C 자료구조] 지옥의 알고리즘 성능분석

알고리즘 성능 분석 왜 하는가!!!

"알고리즘 성능 분석을 왜 하는가!! 그냥 데이터 분석하게 해딸라!!"

라는 생각을 가지고 계속 살아왔는데 잘못된 것을 깨닫기까지 오래 걸렸다ㅎㅎ

데이터가 커지면 커질수록, 자신이 다루는 툴이나 공식들이 복잡해질수록 성능 분석은 필수다ㅎㅎ 아니면 나중에 슈퍼컴 가지고 못 돌릴 수 있는 알고리즘을 짜고 있는 자신을 발견하게 될 것이다ㅎㅎㅎㅎㅎㅎㅎ

내가 웃는 이유는 되지도 않는 알고리즘 짜고 프로그램 강종을 한 게 꽤 되기 때문이다ㅎㅎ

그렇다!!! 우리는 알고리즘을 효율적으로 짜는 연습을 해야 한다.컴퓨터를 단순 노동용으로 쓰지 말자.

 

예를 들자면 이런 것이다.

 

오른 쪽을 이용하면 훨씬 더 빠르게 답이 나온다.

코딩을 짜는 우리가 멍청하면 컴퓨터도 멍청하게 반응할 수밖에 없다. 따라서 좋은 알고리즘을 짤 수 있는 것도 프로그래머 능력의 척도라고 볼 수 있다.

 

알고리즘 성능 분석 기준

알고리즘은 성능 측정(Machine Dependent)과 성능 분석(Machine Independent)의 단계로 이루어진다.

성능 측정은 말 그대로 기계가 슈퍼컴이라면 아주 좋은 결괏값을 낼 수 있다. 즉 알고리즘의 퍼포먼스만 독립적으로 측정하지 못한다.

성능 분석은 다시 1) 공간 복잡도와 2) 시간 복잡도로 나뉜다.

 

*1) 공간 복잡도: 프로그램을 실행시켜 완료하는데 필요한 공간 = 고정 공간 + 가변 공간

*2) 시간 복잡도: 프로그램을 실행시켜 완료하는데 필요한 컴퓨터 시간의 양 = 컴파일 시간 + 실행 시간

 

1) 공간 복잡도(Space Complexity) -> S(P) = C + SP(I)

고정 공간(Fixed Space Reequirement) -> C

- 인풋과 아웃풋에 상관없이 고정됨

- 단순 구조, 변수, 상수들을 위한 공간임

 

가변 공간(Variable Space Requirement) -> SP(I)

- 경우의 수(Instance Characteristic, I)의 영향을 받음

-  숫자, 사이즈, 인풋 사이즈, 아웃풋 사이즈, 회귀 공간, 지역 변수 등이 있음

 

예시 1)

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

S_abc(I) = 0

 

예시 2)

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

S_rsum(I) = S_rsum(n) = 12n

- list [] = 4n, integer = 4n, return address = 4n

- rsum함수는 계속해서 자기의 이전 함수(rsum(list, n-1)를 호출해야 한다. 따라서 답을 도출해낼 때까지 메모리 공간을 지속적으로 확장할 수밖에 없다.

 

2) 시간 복잡도 -> T(P) = C + Tp(I)

컴파일 시간(Compile Time) -> C

- 인풋과 아웃풋에 상관없이 고정됨

- 한번 컴파일되면 이후 계속 실행

 

실행 시간(Run Time) -> Tp(I)

- 자세한 실행 시간 계산

• System Clock 함수 사용(clock_t)
• 프로그램의 연산 횟수를 직접 계산(직접 구현하지 않아도 됨)
• 프로그램 단계: 의미 있는 프로그램 단위를 뜻함
  - 단순 산술, 대입, 비교, 이동 연산에 따라 수행 시간은 변하지 않음
  - 실행 명령문이 필요로 하는 프로그램 단계 수만큼 더함
  - Tabular method(표 방식): 실행 단계 * 빈도 수로 계산

예시)

n장의 카드 중 최댓값 찾기: n-1

 

 

다음 시간엔 성능 분석 중 가장 중요한 시간 복잡도에 대해서 조금 더 자세하게 알아보도록 하자! 후 어렵다