Time Complexity (시간 복잡도)

안녕하세요 BeePeach입니다 :)

오늘은 알고리즘이나 데이터 구조를 배울 때 한 번쯤 들어보는 Time Complexity(시간 복잡도)에 대해서 공부해보도록 하겠습니다.

 

 

---

시간 복잡도의 개념이 필요한 이유

 

어떤 한 가지 문제를 해결할 때 정해진 정답은 없습니다.

그 문제를 해결하는 방법은 매우매우 많겠죠.

어떤 해결방법(알고리즘)이 더 좋은 해결 방법인지 분석하기 위해서 시간 복잡도라는 것을 사용합니다.

 

시간 복잡도는 알고리즘의 실행 속도를 나타냅니다.

비슷한 예로 Space Complexity(공간 복잡도)가 있습니다.

공간복잡도는 알고리즘에 필요한 메모리 크기를 나타냅니다.

요즘 시대에는 메모리가 충분하기 때문에 공간복잡도의 중요성은 많이 낮아졌습니다.

 

그래서 대부분 시간 복잡도를 이용해 이 문제를 해결할때는 어떤 알고리즘이 더 효율적인지 판단하게 됩니다.

 

 

---

표기법

 

시간 복잡도를 나타낼때는 세 가지 표현방법을 사용합니다.

 

Big-O,  Big-Ω, Big-Θ

 

Big-O (빅 오)는 최악의 경우를 가정해서 그때 걸리는 실행시간을 나타낼 때 사용합니다.

최악의 상황이라도 이 정도의 성능은 보장한다라는 의미를 가지고 있기때문에 세 가지 중에 가장 많이 쓰는 표기 방법입니다.

시간 복잡도라고 하면 Big- O를 생각하시면 됩니다.

 

Big-Ω(빅 오메가)는 가장 최상의 경우를 가정하여 걸리는 실행시간을 나타낼때 사용합니다.

 

Big-Θ(빅 세타) - 평균적인 실행시간은 나타낼때 사용합니다.

 

이 두 가지는 잘 사용하지 않기때문에 이 정도로 설명하고 간단하게 넘어가겠습니다.

 

 

---

Big - O

 

빅 오 표기법에 대해서 조그만 더 자세히 알아보겠습니다.

 

표기 방법은 O(n)과 같이 표기를 합니다.

n은 데이터 입력을 나타냅니다.

상수는 무시하고 가장 영향을 많이 주는 부분만 표시하도록 합니다.

예를 들면 O(1), O(n), O(㏒n), O(n²) 등등...으로 표시할 수 있습니다.

 

n + 10, 3n, 100n + 100등은 모두 n으로 퉁쳐서 표기합니다.

10n² + 10n + 100도 마찬가지로 n²이 가장 많은 영향을 주므로 나머지는 생략하고 n²으로 표기합니다.

 

시간 복잡도에 가장 많은 영향을 끼치는 부분은 반복문입니다.

시간 복잡도를 낮추는 가장 효과적인 방법은 반복문의 사용을 줄이면 됩니다.

특히 반복문이 중첩이 된다면 n에서 n²으로 시간 복잡도가 급격히 증가하게 됩니다.

 

출처 : https://velog.io/@qmasem/TIL-Time-Complexity-Big-O-nataion

 

---

간단한 예제

 

가장 유명한 1부터 n까지 더하기 문제를 통해서 시간 복잡도를 보도록 하겠습니다.

첫 번째로는 반복문을 이용해서 1부터 n까지 더하는 알고리즘입니다.

 

 

입력 num에 따라서 반복 횟수가 num만큼 증가하게 됩니다.

100까지의 합을 구할 때 반복이 100번 된다고 해서 O(100)이 아닙니다.

이 알고리즘에서는 100까지의 합을 구한다면 100번을 반복하지만 1000까지의 합을 구하면 1000번을 반복하게 되므로 O(n)의 시간 복잡도를 가집니다.

 

그럼 다른 해결방법을 보도록 하겠습니다.

 

 

가우스가 초등학교때 사용했다는 1부터 n까지의 합을  구하는 수학 공식을 이용해서 문제를 해결했습니다.

이 알고리즘은 num에 1000이 들어와도 한 번만 계산한 후에 종료됩니다.

즉 어떤 수가 들어와도 1번의 계산으로 끝나게 되죠.

그러므로 O(1)의 시간 복잡도를 가집니다.

 

당연히 뒤에 알고리즘이 누가 봐도 더 좋아!라고 말하기보다 표기법을 사용해서 말하면 더 좋겠죠??

 

위의 알고리즘은 O(n) 시간 복잡도를 가지고 아래의 알고리즘은 O(1) 시간복잡도를 가지니까 아래의 알고리즘이 더 좋은 알고리즘이야!

라고 말이죠.

 

 

---