7장 Theory of computational complexity : Sorting problem

Ch:7: Theory of computational complexity: Sorting problem

as a case study

computational complexity theory = 계산 복잡도 이론

• 특정 문제를 해결하기 위해 필요한 시간복잡도를 계산하는 것이 아니라 동일한 문제를 해결하는데 사용될 수 있는 모든 알고리즘에 대해 시간 효율성에 대한 하한을 결정하는 이론
• 그렇기 위해서 주어진 제한된 자원으로 해결할 수 있거나 해결할 수 없는 문제를 분류함.
• 최대 T(n)으로 문제의 시간복잡도를 보이는 상한(upper bound)의 증명은 쉽지만(T(n)인 특정 알고리즘이 있다는 것만 보여주면 되기 때문) 하한을 증명하는 것은 어렵다(lower bound) 왜냐하면 lower bound는 주어진 문제를 해결하는 모든 알고리즘에 대해 설명하기 때문이다.
• 가능한 모든 알고리즘이란 미래에 발견될 수 있는 모든 알고리즘도 포함한다. = 즉, 어떤 알고리즘도 T(n)보다 낮은 시간 복잡도를 가질 수 없음을 보여야 하기에 어렵다.
• 아래적힌 값이 worst case인 경우는 lower bound는 worst case와 비교하기 때문임.

문제가 주어졌을 때 두가지 중 하나를 수행할 수 있다.

1. 문제에 대해 보다 효율적인 알고리즘을 개발하기 위해 노력한다.
2. 보다 효율적인 알고리즘 개발이 불가능하다는 것을 증명하려고 한다.

• 정렬 문제의 경우 키 비교 연산으로 하여 병합 정렬보다 우수한 새로운 정렬 알고리즘을 개발하는 것은 불가능함이 증명된 사례다.
• 즉 1번방식의 새로운 알고리즘 개발을 위해서는 문제 자체의 이론적 lower bound를 알아야한다. 그렇게 해서 존재하는 기존 알고리즘의 worst case 시간 복잡도가 lower bound보다 커야지만 더 효율적인 알고리즘 개발을 시작할 수 있을 것이다.

→ 주어진 계산 문제의 하한은 worst case의 시간복잡도에 대한 하한이다.

• 문제의 lower bound와 동일한 효율성을 갖는 알고리즘을 가지는 문제를 tight lower bound를 갖는다고 이야기한다.

• sorting에는 merge sort가 있으니 sorting은 tight lower bound를 갖는다.(sorting은 nlogn이 최선이다.)

  

• 요약 = comparison based decison은 tree형태로 모델링이 가능하다.
• 모든 sorting 알고리즘은 comparison기반이기에 sorting 문제도 binary tree형태로 만들 수 있다. leaf의 개수는 n! 개 (n = number of input data)이다.