[알고리즘] - 알고리즘의 정의

 

 

 

알고리즘은 컴퓨터에게 편한 관점이 아닌 사람에게 유용한 관점에서, 원하는 일을 처리하는 방법을 표현한 것을 의미합니다. 알고리즘을 결국은 프로그램으로 구현하여야 컴퓨터가 처리할 수 있기에 알고리즘과 프로그램은 서로 불가분의 관계에 있다고 볼 수 있습니다.

 

 

알고리즘

어떠한 문제를 해결하기 위한 여러 명령어들의 유한집합입니다. 언젠가는 끝나야 하는 속성을 지닙니다.

 

 

 

 

 

 

알고리즘의 조건

알고리즘은 다음 조건을들 만족해야 합니다.

• 입력 (Input) : 일방적으로 외부에서 주어지며, 0개 이상이어야 합니다.
• 출력 (Output) : 결과가 한 개 이상 있어야 합니다.
• 명확성 (Definiteness) : 명령은 명확하고 모호하지 않아야 하며, 결과를 예측 가능해야 합니다.
• 유한성 (Finiteness) : 명령을 유한번 실행하면 원하는 일이 달성되어야 합니다.
• 유효성 (Effectiveness) : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 합니다.

 

 

 

 

 

 

분석과 측정

성능 분석(Analysis)

사용할 컴퓨터와 무관하게 필요한 시간과 공간을 이론적으로 추정하는 것입니다.

 

 

성능 측정(Measurement)

특정 컴퓨터에서 시간과 공간을 실제로 측정하는 것입니다.

 

 

 

 

 

 

 

성능 분석과 프로그램의 복잡도

성능을 추정한 결과는 복잡도로 나타내어집니다. 복잡도에는 다음과 같은 두 가지 종류의 복잡도가 있습니다.

 

공간 복잡도 (Space Complexity)

프로그램이 실행을 마칠 때까지 필요한 메모리의 양을 의미합니다.

 

 

시간 복잡도 (Time Complexity)

프로그램 실행에 필요한 시간을 의미합니다.

 

 

 

 

 

 

 

 

 

 

공간 복잡도 (Space Complexity)

크기가 고정된 공간

프로그램의 입력과 출력의 수와 크기가 무관합니다. 

컴파일 할 때 변수나 상수등이 포함되어 크기가 정해지며, 이는 프로그램 종료 시까지 바뀌지 않습니다.

아래와 같은 코드는 컴파일 시에 크기가 고정되어 정해집니다.

public float average (float a, float b, float c){
	return (a+b+c) / 3.0 ;
}

 

 

 

 

크기가 가변적인 공간

프로그램 실행 시점에, 입출력의 개수나 값의 크기 등에 의해 달라지는 공간의 크기를 의미합니다.

공간 복잡도에서는 크기가 가변적인 공간을 중요시 여깁니다.

그러나 많은 경우, 공간 복잡도는 시간 복잡도에 비해 중요하게 여겨지지는 않습니다.

public void hi (){
	Scanner scanner = new Scanner() ;
	int numberOfStudents = scanner.nextInt() ;
	int[] scores = new int[numberOfStudents] ;
	......
}

프로그램에 필요한 배열의 공간 크기는, 프로그램이 실행되는 동안에 달라집니다.

 

 

 

 

 

 

 

 

 

 

 

 

시간 복잡도 (Time Complexity)

시간 복잡도는 프로그램의 실행 시간이 얼마나 걸리지는지를 따지는 것을 의미합니다.

시간 복잡도에는 입력과 출력의 크기와 개수가 영향을 미칠 수 있습니다.

또한 특정한 입력 데이터 자체가 시간 복잡도에 영향을 줄 수 있습니다. (예들 들어 퀵 정렬의 경우 입력 데이터가 이미 정렬되어 있으면 최악의 시간복잡도를 가집니다.)

 

추정을 할 때는 연산의 개수를 세는것을 통해 특정 컴퓨터에 의존적이지 않게 시간 복잡도를 추정할 수 있습니다.

그러나 이는 정확하지 않고 엄격하게 찾는 것은 매우 힘듭니다.

 

시간 복잡도 추정에 대한 예시는 다음과 같습니다.

pubic int f (int n){
	if ( n==0 ) { // 비교연산 1회
		return 0 ; // return 연산 1회
	}
	else {
	    return f (n/2) + f(n/2) + 1 ;// return, 함수call, 나누기, 더하기, 함수call, 나누기, 더하기 => 7회
	}
}

위의 경우 스텝의 수는 다음과 같이 나타낼 수 있습니다.

$$\left\{\begin{matrix}
2 & if\; n=0 \\
 2 \times T(\frac{n}{2}) + 8 &  if\; n>0\\
\end{matrix}\right.$$

 

 

 

시간 복잡도는 측정이 아닌 추정을 하려는 것입니다.

따라서 n의 값이 매우 큰 상황을 고려하여 추정합니다.

 

예를 들어 스탭의 총 횟수가 5n + 4인 경우, n이 매우 큰 상황에서는 4가 무시되어 5n으로 표기할 수 있습니다.

그리고 측정이 아닌 추정을 하는 것이므로 크기에 따른 현상을 이해하는 것이 주 목적이며, 이는 비례한다는 정도를 나타내는 것으로 충분하고 따라서 n에 비례한다고 나타낼 수 있습니다.

 

 

시간 복잡도를 나타낼 때에는, 최선의 경우, 최악의 경우, 평균적인 경우에 대해서 고려해야 합니다.

 

 

 

 

 

 

 

점근 표기(Asymptotic Notation)

대부분의 경우 스텝의 수로 표현하는 것에서 스텝의 수를 정확히 세는 일이 매우 어려우며, 세는 행위 자체가 부정확합니다.

엄격한 표현을 사용하는 것이 오히려 유용하지 않을 수 있으며 따라서 스텝의 수로 표기하는 대신 점근 표기법을 사용합니다. 그리고 이러한 점근 표기의 대표적인 예시가 빅오(Big-Oh) 표기법입니다.

 

 

 

 

 

 

 

 

빅오 표기법(Big-Oh)

빅오 표기법은 상한(Upper Bound)를 나타냅니다.

쉽게 얘기하면 n이 충분히 클 때 ~~ 이상은 아니다를 의미합니다.

예를 들어 f(n) = 5n+4 인 경우, f(n) = O(n)으로 나타낼 수 있으며, 이 경우
n이 상당이 클 때, f(n)은 어떤 상수 c에 대해 c * n 이상은 아니다라는 의미로 사용합니다.

 

 

명확한 정의는 다음과 같습니다.

두개의 함수 f(n)과 g(n)이 주어졌을 때 충분히 큰 모든 n에 대하여 다음의 부등식을 만족하는 양의 상수 c가 존재하면

$$f(n) \leq  c|g(n)|$$

f의 순위가 g의 순위보다 높지 않다고 하며, 이를 다음과 같이 표기합니다.

$$f(n) = O(g(n))$$

 

사용 예시는 다음과 같습니다.

f(n) = 2n^2 + 6n + 8 은 O(n^2)을 증명하라.


g(n) = n^2 이라 하면, 
3g(n) - f(n) = n^2 - 6n + 8 = (n-3)^2 -1

4보다 크거나 같은 모든 n에 대해 다음이 성립한다.
3g(n) - f(n) >= 0

그러므로 
c * g(n)  >= f(n) 을 만족하는 c와 n이 존재하므로, 
Big Oh의 정의에 따라
f(n) = O(n^2)

 

 

빅오 표기법은 작을수록 의미를 갖습니다.

예를 들어 위의 경우 f(n) = O(n^10000000)이라 하여도 문제는 없습니다.

그러나 해당 수치는 전혀 의미 없는 수치이므로 상한은 최대한 작을수록 좋습니다.

 

 

 

 

빅오 표기법의 오해

빅오 표기법은 상한을 나타낸다 하였는데,이는 최악의 경우를 나타내는 것이 아닙니다.

상한이 의미하는 것은 주어진 입력의 개수 n이 매우 큰 경우를 의미하는 것입니다.

 

입력의 개수가 매우 클 때에도 최선의 경우와 최악의 경우, 평균적인 경우가 있을 수 있습니다.

모든 경우를 빅오 표기법으로 나타낼 수 있으며 이해를 돕기 위해 퀵 정렬의 시간 복잡도를 빅오로 나타내면 다음과 같습니다.

최선의 경우	평균적인 경우	최악의 경우
O(n log n)	O(n log n)	O(n^2)

 

 

 

 

복잡도 함수의 그래프

자주 사용되는 복잡도 함수에 대한 그래프입니다.

https://gompangs.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84Time-Complexity