02. 알고리즘 시간 복잡도 함수(1)

(해당 내용은 "C++로 쉽게 플어쓴 자료구조(천인국, 최영규 저, 2016)"을 기반으로 작성되었습니다.)

(해당 내용은 자료구조/알고리즘을 공부하기 위해 작성된 것이므로, 내용에 오류가 있을 수 있습니다.)

 

좋은 알고리즘이란 아무래도 실행 시간이 빠르고 기억공간을 적게 사용하는 알고리즘일 것입니다.

여기서, 실행 시간을 분석하는 것을 시간 복잡도(time complexity)라 하고,

사용되는 기억 공간을 분석하는 것을 공간 복잡도(space complexity)라고 합니다.

일반적으로 알고리즘의 복잡도를 평가할 때는 주로 시간 복잡도를 사용하는데,

사용자들은 프로그램이 차지하는 기억 공간보다는 프로그램의 처리속도에 더 관심을 가지기 때문입니다.

 

시간 복잡도 함수란 알고리즘이 완료될 때까지 거치게 되는 연산의 수를 입력값 n의 함수로 표현한 것입니다.

 

그럼 간단한 알고리즘을 통해 시간 복잡도 함수를 표현해 보겠습니다.

	a = (n + 2) / 4;

이 알고리즘은 n 대입에서 한번, n+2 연산에서 한번, 이를 4로 나누는 것에서 한번 해서 총 3번의 연산 과정을 거칩니다.

그렇다면 복잡도 함수는 T(n) = 3으로 표현됩니다.

 

for (int i = 0; i < n; i++)
		a++;

다음 알고리즘은 for 문이 포함되어 있으며, n에 따라 for 문 내의 연산을 반복하게 됩니다.

i와 n 대입에서 각각 한번씩, 그리고 i++와 a++는 n번 반복되므로, 해당 알고리즘은 T(n) = 2n + 2로 표현이 되겠네요.

 

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			a++;

이 알고리즘은 for문이 2개 중첩되어 있는 형태입니다.

아까와 마찬가지로 i와 n에서 각각 한번씩, 그리고 i++는 n번 반복됩니다.

for 문 안의 또다른 for문에서는 j 대입에서 한번, 그리고 j++와 a++는 n번 반복되므로 2n + 1이 표현됩니다.

그리고 2n+1을 n번 반복하게 되므로 최종적으로는 T(n) = 2 + n + n(2n + 1) = 2n² + 2n + 2로 표현됩니다.

 

시간 복잡도 함수를 작성하다 보니 글이 길어져서 나머지 부분은 다음에 작성하겠습니다.

제가 이해한 대로 작성했는데, 제대로 표현되었는지 모르겠네요 ^^;;

더 자세한 부분은 아래 참고할 만한 블로그를 첨부하겠습니다.

 

참고

1. 휴먼스케이프 인턴 Jason님의 블로그(https://medium.com/humanscape-tech/%EC%BD%94%EB%93%9C%EC%9D%98-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%84%EC%82%B0%ED%95%98%EA%B8%B0-b67dd8625966)

코드의 시간 복잡도 계산하기

2. 성실하게 준비한 하루이야기(https://thenicesj.tistory.com/284)

3. Knowledgy Framework(https://chanos.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%84%B1%EB%8A%A5%ED%8F%89%EA%B0%80%EB%A5%BC-%EC%9C%84%ED%95%9C-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EC%99%84%EB%B2%BD%ED%9E%88-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-2)