Written by JS970
on
on
컴퓨터 알고리즘 2023-04-05 수업정리
Flow
- Dynamic Programming - Optimal Binary Search Trees(2)
Dynamic Programming - Optimal Binary Search Trees(2)
컴퓨터 알고리즘 4.3 수업정리에서 이어짐
How to find Optimal BST?
- 앞서 살펴본 알고리즘에 의하면, Optimal BST의 Average Search Time은 구할 수 있지만 Optimal BST가 무엇인지는 알 수 없다.
- Optimal BST를 구하기 위해서는 Optimal BST의 Average Search Time을 구하는 알고리즘에서 가장 작은 평균 탐색 시간을 갖도록 하는 루트 노드 k를 찾을 때, 이 노드(노드 k)를 따로 저장하여 Optimal BST를 구할 수 있다.
- 이렇게 Dynamic Programming을 사용하여 N개의 노드를 가지는 Binary Search Tree 중 Optimal BST의 root node 및 해당 노드의 subtree들이 optimal BST가 되도록 하는 root node들을 구할 수 있다.
- 아래는 Optimal BST의 Average Search Time을 구하는 코드를 수정하여 작성한 Optimal BST를 구하는 C++코드이다.
// 구현하여 채워 넣을 것 2023-04-09
Optimal Binary Search Tree를 구하는 알고리즘의 시간복잡도
- 코드에서 확인 가능하듯이 3중 for문이 사용된다. 따라서 아래와 같은 시간복잡도를 가지게 된다.
- i번째 노드부터 j번째 노드로 이루어지는 subtree에 대한 탐색$$T(n^2)$$
- i이상 j이하의 값을 가지는 모든 k에 대해, Average Search Time이 가장 작은 경우에 대한 조사.$$T(n)$$
- 따라서 본 알고리즘의 시간복잡도는 다음과 같다.$$T(n^2)\times T(n) = T(n^3) = \Theta(n^3)$$