알고리즘의 성능 분석

알고리즘의 성능 분석은 내가 작성한 코드가 얼마나 효율적인지 판단하기 위해 꼭 필요한 절차

작성한 알고리즘의 성능을 분석하기 위해서는 2가지 측면인 실행 시간 메모리 사용량 을 고려해야한다. 하지만 실행 시간 은 컴퓨터의 성능에 따라 달라질 수 있으므로, 객관적인 지표인 시간 복잡도 로 프로그램의 대략적인 실행 시간을 계산한다.

📝 용어 정리

---

  알고리즘  
문제를 해결하기 위한 일련의 절차나 방법   코드로 문제 해결 방법을 작성

  시간 복잡도  
알고리즘을 위해 필요한 연산의 횟수

  공간 복잡도  
알고리즘을 위해 필요한 메모리의 크기

  점근적 표기법  
중요하지 않은 값을 제거하고 표기하는 방법 실행시간 성장률 확인 가능

  시간 복잡도 함수  
T(n) 연산의 개수를 입력의 개수 n 으로 나타낸 함수

  빅오 표기법  
O(n) 입력에 따라 프로그램의 실행 시간을 대략적으로 나타내는 방법  

---

시간 복잡도

알고리즘 풀이를 구글링하다보면 "최악의 경우 X만큼의 실행 시간이 걸리므로 비효율적이다" 라는 맥락의 글을 자주 볼 수 있다. 사실 문제를 풀면서 반복문을 많이 사용하면 안된다 최소한의 비교 연산만 수행할 수 있도록 작성해야한다 정도로만 알고 있었지, 내 코드를 뜯어보며 최악의 경우 처리해야할 연산의 횟수 를 지표로 나타내지는 못했다.

시간 복잡도 는 알고리즘이 수행하는 연산의 횟수 를 바탕으로 계산할 수 있다. 그렇다면 연산의 횟수 는 어떻게 카운팅 해야할까? 양의 정수 n을 n번 더하는 알고리즘을 통해 생각해보자.

// [알고리즘 A] T(n) = 1

int sum = n * n;

// [알고리즘 B] T(n) = n + 1

int sum = 0;

for(int i = 0; i < n; i++) {
    sum += n;
}

// [알고리즘 C] T(n) = 2n^2 + 1

int sum = 0; // 삽입 연산 (+1)

for(int i = 0; i < n; i++) { 
	for(int j = 0; j < n; j++) {
    	    sum += 1; // 덧셈 연산 (+ n^2) 대입 연산(+ n^2)
    }
}

3가지 알고리즘 모두 동일한 문제를 해결하기 위한 방법이지만 시간 복잡도 는 제각각이다. 연산의 종류는 대입 연산 사칙 연산 비교 연산 이 있고, 이 연산들이 몇번 수행되는지 시간 복잡도 함수 로 나타낼 수 있다. int sum = 0; 과 같이 단순히 값을 대입하는 경우에는 입력되는 데이터의 양 과 상관없이 어떤 경우에도 동일한 실행 횟수를 갖기 때문에 상수 로 나타내고, 반복문 안의 덧셈 연산 과 대입 연산 은 입력되는 데이터의 양 에 따라 실행 횟수가 달라지기 때문에 n 에 대한 값으로 나타낸다.

사실상 상수 는 장기적으로 봤을때 프로그램의 실행시간에 큰 영향을 주지 않는다. 뿐만아니라 n 의 계수가 실행 시간에 주는 영향도 미비하다. 이렇게 시간 복잡도 함수 에서 중요하지 않은 부분들을 제거해서 표현한 식이 빅오 표기법 이다.

참고 자료

📘   C언어로 쉽게 풀어쓴 자료구조

📌   점근적 표기법 (개념 이해하기) | 알고리즘 | Khan Academy

📌   Understanding time complexity with Python examples