4.2 Performance Evaluation

        1) Main Function

   레코드의 수를 n이라고 했을 때, 파일의 레코드를 읽기 위한 loop는 레코드의 수인 n번을 호출하게 되므로, O(n)의 시간복잡도를 가진다.

2) Save recoard to CData object

   하나의 레코드의 필드의 수를 m이라고 하자.

 이 레코드를 읽어들여서 해당 Command에 따른 함수를 호출하게 된다. 각각의 함수들은 나머지 레코드의 필드를 잘라서 각각 데이터 객체에 저장하게 되는데, SaveInsertRecord는 loop를 m번만큼 수행하여 모든 필드를 데이터에 저장하고(m), SaveDeleteRecord는 if-else 내의 loop를 m-c1만큼 수행하여 필드를 데이터에 저장하며, SaveUpdateRecord는 m-c2만큼 필드를 저장하고 if-else내에서 나머지 필드를 m-c3만큼 저장한다. SavePrintRecord는 m만큼의 필드를 저장한다.

 즉, SaveInsertRecord는 m = O(m), SaveDeleteRecord는 m-c1 = O(m), SaveUpdateRecord는 (m-c2) + (m-c3) = O(m), SavePrintRecord는 m = O(m)이다.

 어떠한 Command를 수행하더라고 시간복잡도는 O(m)이므로 이 함수의 전체적인 시간복잡도 역시 O(m)이 된다.

3) Insert Node to BST

   트리의 노드 수를 n이라고 하자.

  삽입될 노드는 loop 내에서 현재 위치한 트리의 노드의 크기와 작은지 큰지를 비교하며 한쪽 트리로만 이동하게 된다. 즉, 트리의 균형이 최악의 경우가 아니라면 트리의 높이는 log₂c1(n+c2)을 가지게 되는데(완전 이진트리의 높이는 log₂(n+1)이다) 중간에 같은 값의 노드가 있다면 비교 loop를 빠져나오게 되므로 전체적으로 log₂c1(n+c2-c3)의 시간복잡도를 가진다. 그런데 삽입시 이름트리와 전화번호트리 두 곳에서 삽입을 하므로 log₂c1(n+c2-c3) * 2 = 2log₂c1(n+c2-c3) = 2log₂n = O(log₂n)의 시간복잡도를 가진다.

   하지만 트리의 균형이 최악이라면 트리는 선형리스트와 같은 구조를 지니게 되므로 삽입시 n-c1 = O(n)의 시간복잡도를 가지게 된다.

4) Delete Node from BST(by name and phone)

   트리의 노드 수를 n이라고 하자.

  삭제될 노드는 loop 내에 같은 값을 가진 노드가 있는지를 비교하며 한쪽 트리로 이동하게 된다. 즉 삽입에서와 같은 시간복잡도인 O(log₂n)을 가지게 된다. 만약 삭제될 노드를 찾았다면 삭제될 노드의 자식트리에서 교체될 노드를 찾아야 하는데 노드는 아직 트리의 끝에 다다르지 않았으므로 교체될 노드를 찾아서 다시 loop를 돈다고 해도 전체적으로 log₂n만큼의 수행을 하는 것과 같다.(전체 트리 검색 = 삭제될 노드 검색 + 교체될 노드 검색)

   따라서, 삭제될 노드와 교체될 노드를 찾은 시간복잡도는 O(log₂n)이며, 노드의 교체는 상수시간만큼 일어나므로 최종적인 시간복잡도는 O(log₂n)을 가지게 된다.

   하지만 삽입과 마찬가지로 트리의 균형이 최악이라면 시간복잡도는 O(n)이다.

5) Update Node to BST

   업데이트는 노드를 삭제한 후 다시 새로운 데이터값을 가진 노드를 삽입하는 방식이다. 노드의 삽입시 시간복잡도는 log2n이고 삭제 역시 log2n이므로 업데이트의 시간복잡도는 2log2n = O(log2n)을 가지게 된다.

   하지만 업데이트 역시 트리의 균형이 최악이라면 삽입(n) + 삭제(n) = O(n)의 시간복잡도를 가지게 된다.

6) Print BST

   트리의 노드 수를 n이라고 하자.

            이름이 같은 노드, 전화번호가 같은 노드, 모든 노드를 출력시 트리의 모든 노드들은
            스택에 꼭 한번씩 삽입이 된다. 즉, loop내에서 n번만큼 수행하므로 O(n)의 시간복잡도를 가진다.