알고리즘 심화 특강 (2024.04.26)

알고리즘

알고리즘 수행내용을 의사코드(Pseudo-code)로 작성하기도 하며,
알고리즘이 문제를 얼마나 빠르게 해결하는지 평가하는 공간 복잡도와 시간 복잡도가 있다.

여기서 잠깐!

의사코드(Pseudo-code)는 무엇일까?

• 컴퓨터 프로그램이나 알고리즘이 수행해야할 내용을 논리적으로 서술한 것

특정한 프로그래밍 언어의 문법이 아니라 인간의 언어로 코드를 흉내 내어 작성하는 것을 뜻한다.

알고리즘 분석기준

위에 말한대로 공간복잡도와 시간복잡도를 통해 알고리즘의 성능분석을 하는데 그에 대한 분석기준을 간단하게 작성해보려한다. (특강X)

• 정확성
• 명확성
• 수행량
• 최적성
  이렇게 4가지의 분석기준을 가지고 분석을 하게 되며,
  일반적으로는 실행에 필요한 공간 측면에서 분석하는 공간 복잡도와 실행에 소요되는 시간 측면에서 분석하는 시간복잡도를 추정하여 일반적인 평가를 한다고 한다.
  그중 우리는 시간복잡도에 대하여 알아볼 것이다.

시간 복잡도

시간 복잡도란 소요 시간과 입력값의 상관 관계를 표현하기 위한 개념이라고 생각하면 된다.

만약 아래와 같은 코드를 짰다고 생각해보자

maxScore(x[])
{
	max <- 0;
	
	for (i <- 0; i < x.length; i <- i+1) do {
		if (x[i] >= max) then {
			max <- x[i];
		}
	}
	
	return max;
}

이 코드에서는 for문을 통해 배열 x의 모든 원소를 방문해서 if문을 통해 max와 비교해 만약 배열 x의 원소가 크면 max로 바꾸는 알고리즘을 가지고있다.

만약 배열 x의 길이를 n이라고 봤을 때, for문은 배열의 길이만큼 반복되기 때문에 해당 알고리즘은 n에 비례하여 소요 시간이 걸리게 된다.

만약 for문안에 for문이 있다면?

multiplyAllElements(a[])
{
	sum <- 0;
	
	for (i <- 0; i < a.length-1; i <- i+1) do { 
		for (j <- 0; j < a.length-1; j <- j+1) do {
			sum <- sum + a[i] * a[j];
    }
	}
	
	return sum;
}

n안에 n이 있으므로 n²이 된다.
여기에서 시간복잡도의 표기법인 Big-O표기법이 등장한다!

Big-O 표기법

위에서 말했던 n과 n²을 O( )괄호안에 넣으면 된다! (쉽게말하자면)
괄호안에 들어가는 건 최고차항으로, 수치를 단순화한다고 보면된다.

위 그래프를 보면 알 수 있지만 시간 복잡도를 비교하자면 아래와 같다.
O(1) < O( 𝑙𝑜𝑔𝑛 ) < O(n) < O(n 𝑙𝑜𝑔𝑛 ) < O( 𝑛2 ) < O( 2𝑛 ) < O(n!)

O(1)이 가장 빠르지만, 현실적으로 불가능한 수치이므로 로그 함수인 O( 𝑙𝑜𝑔𝑛 )과 O(n 𝑙𝑜𝑔𝑛 )의 복잡도를 가지면 효율적인 알고리즘이라고 말할 수 있다. (이상적인 알고리즘..)

Big-O 표기법은 수치를 단순화해서 경향성을 보기 위한 표기법 즉, O(n)은 n과 비례하거나 더 작은 함수들의 모임이라고 보면된다.

계속해서 수치를 단순화 한다고 했는데 만약 실행시간 함수가 4n + 2 이라면 Big-O표기법으로는 어떻게 표시할까? 바로 O(n) 이다.
함수값에 가장 큰 영향이 주는 최고차항은 4n이고, 계수 4는 생략하고 표기하기 때문이다.

ex)
5n² = O(n²)
5n² + 4n = O(n²) (최고차항이 n²이기 때문)