데이터구조 2차시: 시간복잡도 Big-oh notation

알고리즘이 우수한가?

같은 문제에 대해 이를 해결할 수 있는 알고리즘은 여러 개가 있을 수 있다.

어느 것이 더 우수한지 비교할 수 있는 기준은 무엇인가?

기준은 크게 두 가지가 있다.

하나는 시간이고, 다른 하나는 공간이다.

시간은 알고리즘을 이용해서 문제를 풀 때 시간이 얼마나 소요되느냐 하는 것이다.

공간은 알고리즘이 수행되기 위해서 얼마만큼의 메모리가 필요하느냐 하는 것이다.

시간복잡도,  

알고리즘의 우수성을 사용하는 시간측면에서의 기준을 말한다.

영어로는 time complexity.

예를 들어,

1부터 정수 숫자 n까지 모든 숫자를 더해서 합을 구하는 문제를 생각해보자.

이 문제를 푸는 방법에는 두 가지가 있다.

즉, 두 가지 알고리즘이 있다.

첫 번째 알고리즘은 누구나 생각할 수 있는 간단한 방법이다.

1부터 n까지 숫자를 하나씩 더하면 된다.

C언어로 프로그래밍하면 다음과 같다.

 

두 번째 알고리즘은 파스칼이 생각해낸 방법이다.

어린 시절 파스칼은 1부터 10까지의 합이 55라는 것을 

아래와 같은 천재적인 방식으로 알아냈다.

어느 것이 시간복잡도면에서 더 우수한가?

첫 번째 알고리즘은 n이 커질수록 계산하는 데 시간이 더 오래 걸린다.

for-loop 반복횟수가 많아지기 때문이다.

두 번째 알고리즘은 n의 크기와 상관없이 아래와 같은 공식으로 계산이 가능하다

따라서 두 번째 알고리즘이 첫 번째보다 시간 복잡도면에서 우수하다고 할 수 있다.

Big-O notation

시간 복잡도를 나타내기 위해서 사용하는 표현식이다.

읽을 때는 '빅 오 노테이션'이라고 읽는다.

첫 번째 알고리즘의 시간복잡도를 big-O notation으로 쓰면

O(n)이 된다. 

즉, n에 비례하여 걸리는 시간도 그만큼 증가한다는 것이다.

두 번째 알고리즘의 시간복잡도는 O(1)이다.

즉, n에 상관없이 항상 일정(1)하다는 것이다.

특히 어떤 문제에 대해 O(1) 알고리즘을 만들어 낼 수 있다면 

최상의 해결책을 찾아낸 것이다. 

다양한 시간복잡도

O(n) 시간복잡도의 알고리즘과 시간복잡도를 보자면

당연히 후자 알고리즘이 시간이 더 많이 걸린다는 것이다.

이 외에도 같은 것도 있다.

이것은 보다는 우수하지만, O(n)보다는 시간이 오래 걸리니 좋지 않다.

알고리즘의 시간복잡도를 나타내는 Big-O notation에 대해서 설명합니다.