시간 복잡도

오늘 특강에서 자료구조에 대한 설명을 시간복잡도라는 개념을 통해 설명을 해주셨는데 시간복잡도라는 개념에 대해 알지 못해 많이 당황하였던 것 같다. 대략적인 맥락으로 보았을 때 시간복잡도에 따라 효율이 달라지므로 리스트를 너무 과신하지 말자는 내용이었던 것 같은데 전체적인 내용을 이해하지 못하여 저녁을 먹고나서 튜터님께서 따로 시간을 내주셔서 추가 강의를 해주셨다.   

 

다시 듣고보니 시간복잡도라는 것은 자료구조를 통해 어떠한 값을 찾을 때에 복잡성에 관한 추정값으로  정확한 값이 아닌 평균적인 근사값인 것 같다. 지난 C# 강의 때 과제를 최우선으로 하여 강의 진도를 다 못 뺀 것이 이번 특강에 대해 이해가 부족했던 원인이었다. 그래서 지금이라도 조금이나마 강의를 보면서 알고리즘의 개념과 시간 복잡도에 대해 배워보는 중이다.

 

알고리즘?

 

알고리즘은 문제를 해결하기 위한 절차나 방법을 뜻하는 단어로 본다. 컴퓨터 프로그래밍 외에도 여러 분야에서 쓰인다고 하지만 일단 우리는 컴퓨터 프로그래밍에서의 알고리즘만 보도록하자.

 

알고리즘은 입력과 출력을 할 때의 과정에서 효율성을 따지는 단위로 보인다.  같은 입력과 결과를 출력하더라도 효율적인 알고리즘을 사용하는 것이 컴퓨팅 자원( 시간과 메모리 등) 을 절약할 수 있기에 우리는 이것을 따져 코딩을 하여야한다.

대략적인 개념은 얼마나 효율적으로 로직을 작성하느냐를 따지는 개념으로 생각하면 될 듯 하다.

 

Big O 표기법?

 

Big O 표기법은 알고리즘의 효율성을 따지기 위한 표기법이다.  입력에 따라 얼마나 많은 시간과 공간을 필요로 하는지를

평균적인 근사값을 따져 적어보는 것이다.   물론 어느정도 기준은 생각하고 이것을 구분한다.

 

O(1) : 상수 시간이라 부르며 입력의 크기에 상관없이 일정한 시간이 걸릴 때 표기한다.

 

O(n) : 선형 시간이라 부르며 입력의 크기에 비례하여 시간이 소요될 때 표기한다.

 

O(n^2) : 이차 시간이라 부르며 입력의 크기의 제곱에 비례하여 시간이 걸릴 때 표기한다.

 

O(log n) : 로그 시간이라 부르며 입력의 크기의 로그에 비례하여 시간을 표기한다.

 

일단 저것만 알고선 어디에 쓰이는지 모르겠다..

 

시간 복잡도?

 

시간 복잡도는 알고리즘이 문제를 해결하는데 걸리는 시간을 나타내는 척도로 Big O 표기법을 사용하여 표시한다.

 

복잡도에 따라 시간이 얼마나 걸릴까 예상해보고 예상한 결과를 도출한다고 생각하면 될 듯 하다. 이것을 나누는 이유는 의식하면서 코드를 짜라는 의미인것 같고..

 

O(1) 

List<int> list = new List<int> {1,2,3};

 

이런 식으로 리스트를 만들었을 때 이 리스트를 이용하여 2의 값을 받아오고 싶다면 우리는 몇번 째인지만 알면된다.

list[0]

1을 구하고 싶다면 0번째 값만 구하면 되므로 매우 적은 시간이 소요된다. 이런 것을 O(1) 으로 본다고 한다.

 

O(n) 부터는 얼마나 복잡한지를 따져서 그것을 판단하는데..

 

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

이런 경우엔  n번만큼 반복문을 실행하므로 그만큼 sum을 구하는 시간이 더뎌지게 된다.   0부터 n까지 n회의 연산을 하게 되므로   O(n) 이라하고 한다.

 

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

 

이번엔 이중 중첩문이다 sum을 구하려면  n번 연산을 하고 또 n번 연산을 하게 된다. 그만큼 또 시간을 n의n 만큼 소모하므로 이것을 O(n^2) 이라한다.

 

대략 이런 개념이다. 물론 n인지 아닌지는 중요하지는 않다. n이란건 추상적으로 보고 얼마나 반복할 것 같은지 또 그것에 따라 얼마나 시간이 소요될 것인지 그것을 구분하는 것이 시간복잡도다.

 

마찬가지로 공간 복잡도라는 개념이 있는데 이건 시간이 아닌 공간 즉 메모리크기를 얼마나 차지 할지를 구분 짓는다.

이것은 Big O 표기법을 사용하는 건 동일하지만 메모리 연산이 큰 메서드를 사용할 때 주의하여 사용하여야 한다는 ( 최적화의 문제)  개념같고..  아직 정확히 메서드들이 얼마나 값을 소모할 지는 모르기에 요런 개념으로만 알아두려한다.