반응형
컴퓨터 프로그램은 Data structure + Algorithm이다.
알고리즘은 Input을 받아서 Output을 내는 잘 정의된 Computational Procedure라고 할수 있다.
알고리즘에서 자주 보이는 표기는 빅O 표기이다. (big-O notation) 이는 어떤 함수의 복잡도를 정의하는데 일반적으로 사용하는 기호로 자료 집합의 크기가 성장함에 따라 알고리즘의 효율이 어떻게 변화하는지를 대략적으로 추정하는 함수라고 볼수 있다.
가장 좋은 알고리즘은 O(c)로 자료집합의 크기에 상관 없이 수행에 걸리는 시간이 동일한 경우이다.
다음으로 자료의 크기에 의존적인 알고리즘 중에서 가장 효율적인 것은 O(log_2 n) 으로 기수가 2인 로그 함수이다. 자료의 크기가 커질 수록 더욱더 효율적인 경우라고 볼수 있다.
다음은 O(n)으로 자료 크기에 선형적으로 증가하는 알고리즘이다.
다음은 O(n log_2 n)으로 일반적으로 정렬(sorting) 알고리즘이 가져야 할 최소한의 복잡도로 간주된다. 대충 이정도면 효율적이라고 한다.
다음은 O(n^2) 로 for 문안에 for문이 들어 있는 경우라고 볼수 있는데, n에 따라서 기울기가 급하게 올라가기 때문에 효율적인 알고리즘은 아니다. O(n^3)은 더욱 말할 것도 없이 나쁘다
O(2^n)은 매우 비효율적인 알고리즘이다.
참고로 자료 집합이 작은 경우 O(2^n)이 O(n^2)보다 빠르다. 하지만 자료 집합이 증가하면 차이는 확인히 나타나게 된다.
반응형
