시간복잡도
시간복잡도라는 것은 알고리즘이 데이터를 처리하는 시간과 데이터양과의 관계를 나타내는 한 방법입니다.
여러 가지 표현 방법이 있는데 많이 쓰이는 것은 O표기법입니다. 영어로 O-notation이라고 합니다. 다른 표기법으로는
o-notation(small O입니다), Ω-notation, Θ-notation 등이 있습니다. 이 중 우리가 주로 쓸 O는
조건에 만족하는 최악의 데이터가 들어왔을 때의 처리속도입니다.
즉, 데이터에 대해 '아무리 오래 걸려도 이 이상은 걸리지 않는다'입니다.
그렇다면 왜 다른 것을 놓아두고 이 것을 쓰느냐. 이 문제는 이렇게 생각할 수 있습니다.
데이터는 항상 같은 상태로 들어오지 않습니다. 어떤 알고리즘이 대부분의 데이터에 대해서는 1초만에 처리하다가
특정한 형태의 데이터에 대해서는 10초 걸린다면 이 알고리즘의 시간복잡도를 계산할 때 10초 걸릴 때 처리한 방법을
이용해야 합니다. 보통 3초 걸리더라도 최악의 데이터 때도 3초 걸린다면 그 알고리즘이 더 우수한 것입니다.
컴퓨터가 평소에 감당하기 어려울 만큼 빠르다가 간혹 사람을 환장하게 할 정도로 맛이 가는 것이랑, 언제나 어느 정도
속도가 나는 컴퓨터랑 어느 컴퓨터가 좋다고 할 수 있습니까. 그와 비교해보면 됩니다.
그러면 O표기법은 어떻게 나타낼까요? 데이터가 n개라면 특정 패턴 - 비교 등-이 n과 어떤 관계인가를 살펴봅니다
만약에 For i=1부터 n (처리) 를 한다면 O(n)이 됩니다. For문이 2개가 중첩된다면 O(n2)가 되는 것입니다. 이런 식으로
계산합니다. 그리고 log2n 같은 경우 그냥 밑이 10인 logn으로 계산합니다. 컴퓨터상으로 계산하는 데는 큰 차이가 나지
않아 무시하는 것입니다. 또한 이런 일환으로 For문 1개를 병렬로 3번 처리하였다면 그냥 O(n)이 됩니다. 요컨대,
전체 처리식 중 최고차 항만, 그중에서 계수를 무시하고 나타내면 됩니다. 즉, 데이터수와 상관없는 것은 무시하는 것입니다.
예를 들어 버블소트의 경우 {(n-1)*(n-1+1)}/2 = (n2 + n)/2와 같은 횟수만큼 비교하는 처리를 합니다. 이 때 최고차 항만
그리고 계수를 무시하면 O(n2)가 되는 것입니다.
가장 효과적인 시간복잡도는 어떤 것일까요?
순서대로 따지면 O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < ... < O(2n) < O(3n) < ... < O(n!)입니다.
하지만 항상 시간복잡도가 낮은 알고리즘만이 가장 우수하다고는 할 수 없습니다. 데이터가 100개 정도라면 n3까지도
10초정도(계수가 낮을 때) 내에 처리할 수도 있습니다. 작성하기도 이해하기도 쉽고, 작고, 간단하다면 시간복잡도가
낮은 알고리즘도 효용성이 있는 것입니다. 경우에 따라 잘 조율해야 합니다.
