복잡도

 알고리즘은 쉽게 말해 어떠한 문제를 해결하기 위한 절차나 방법이라고 할 수 있다.

 

이런 알고리즘을 사용하는데에는 해당 알고리즘의 효율성을 따질 수 밖에 없다.

 

예를 들어 어떤 문제를 해결하는 데 있어서 어떤 알고리즘은 최적인 상황임에도 불구하고 100시간이 걸리고

 

또 어떤 알고리즘은 최악의 상황임에도 10시간이 걸린다면 당연히 후자의 알고리즘을 선택하는 것이 맞는 것이다.

 

반대로 전자의 알고리즘은 1kb의 메모리를 요구하고, 후자의 알고리즘은 100mb의 메모리를 요구한다면 

 

메모리를 사용하는 데에 있어서는 전자의 알고리즘이 효율적인 것이다.

 

이를 따지기 위해서 사람들은 알고리즘의 효율성을 공간적, 그리고 시간적 효율성으로 나누어 판단했다.

 

우선 공간적 효율성은 연산량에 대비하여 얼마나 적은 메모리 공간을 요하는 가를 따진다.

 

예를 들어 여러 정점과 정점 사이의 연결된 간선을 행렬의 모양으로 입력받는다고 생각해보자. 

 

간단하게 생각하면 행렬 그 자체를 그대로 받는 2차원 배열을 구성해 입력받을 수 있다. 

 

하지만 정점이 무수히 많고 간선은 상대적으로 현저히 적을 경우를 생각해 본다면,

 

위는 단순한 예시다.

 

7개의 정점을 2차원 배열로 만든다면 49개의 공간이 필요하다.

 

7개의 정점 사이에 연결된 간선이 4개 밖에 안 된다면, 자기 자신을 향한 공간을 제외한 곳은 낭비되고 있는 것이다.

 

만약 정점이 100,000개에 간선은 겨우 4개라면?

 

정점을 표현하기 위해 100,000*100,000 크기의 2차원 배열을 만들고, 그 배열에 입력하는 값의 개수는 

 

자기 자신을 향한 공간을 제외하고는 겨우 8개 정도이다. 

 

이러한 경우 공간적 효율성이 떨어진다고 볼 수 있다.

 

 이와 비슷하게 시간적 효율성은 연산량 대비 얼마나 적은 시간을 요구하는 가를 따진다.

 

위에서 말했듯 얼마나 오래 걸리느냐에 따라 효율성을 판단할 수 있다.

 

알고리즘에서 이러한 효율성을 '복잡도'라는 단어를 통해 표현한다.

 

복잡도가 높을수록 효율성은 저하된다.

 

흔히들 말하는 '시간 복잡도'가 결국 알고리즘의 시간적 효율성을 의미하는 것이다.

 

 

라고 이해했다.