Feb 13th(Thu) DSA

📌 T(n) = T(1) + log n * C = C1 + C * log n → Θ(log n) 설명!

이 수식은 BST(Binary Search Tree)에서 탐색(검색, 삽입, 삭제) 연산의 시간 복잡도를 구하는 과정을 나타낸 거야.
아래 단계별로 분석해볼게. 🚀

---

1️⃣ 점화식 다시 보기

BST에서 탐색을 할 때, 각 단계마다 문제 크기가 절반으로 줄어듦.
이걸 점화식으로 표현하면:

T(n)=T(n/2)+CT(n)=T(n/2)+C

여기서:

• T(n/2): 절반 크기의 트리에서 다시 탐색
• C: 현재 노드에서 비교하는 비용 (상수 시간, O(1))

---

2️⃣ 점화식 확장하기 (반복 적용)

점화식을 한 단계 더 확장해보자.

T(n)=T(n/2)+CT(n)=T(n/2)+CT(n/2)=T(n/4)+CT(n/2)=T(n/4)+CT(n/4)=T(n/8)+CT(n/4)=T(n/8)+C

...

이걸 계속 확장하면:

T(n/2k)=T(1)+kCT(n/2k)=T(1)+kC

---

3️⃣ k 구하기

점화식이 종료되는 조건은 탐색할 노드가 1개 남았을 때 (T(1)).
즉, n/2^k = 1을 만족하는 k 값을 찾자.

n2k=12kn​=1

양변에 2^k를 곱하면:

n=2kn=2k

양변에 log_2를 취하면:

log⁡2n=klog2​n=k

즉, BST의 탐색 깊이(최대 비교 횟수)는 k = log_2 n.

---

4️⃣ 점화식에 k 대입하기

위 결과를 점화식에 넣으면:

T(n)=T(1)+kCT(n)=T(1)+kCT(n)=T(1)+log⁡2n⋅CT(n)=T(1)+log2​n⋅C

여기서:

• T(1) = C1 (Base Case, 즉 1개의 노드를 탐색하는 시간)
• C는 각 단계에서 비교하는 비용 (상수)

따라서:

T(n)=C1+C⋅log⁡2nT(n)=C1+C⋅log2​n

---

5️⃣ Θ(log n)이 나오는 이유

Big-Theta(Θ) 표기법에서 가장 큰 항만 고려하고, 상수 계수를 무시한다.

T(n)=C1+Clog⁡2nT(n)=C1+Clog2​n

• C1은 상수이므로 무시 가능
• C \log_2 n에서 C는 상수이므로 무시 가능
• 최종적으로 Θ(log n)

즉, BST 탐색(검색, 삽입, 삭제)의 시간 복잡도는 Θ(log n)이다! 🚀

---

📌 6️⃣ 실제 코드에서 확인해보기

java

CopyEdit

class BSTNode { int data; BSTNode left, right; public BSTNode(int data) { this.data = data; this.left = this.right = null; } } class BST { BSTNode root; public BST() { root = null; } public void insert(int key) { root = insertRec(root, key); } private BSTNode insertRec(BSTNode root, int key) { if (root == null) return new BSTNode(key); if (key < root.data) root.left = insertRec(root.left, key); else root.right = insertRec(root.right, key); return root; } // BST 탐색 연산 (재귀적) public boolean search(int key) { return searchRec(root, key); } private boolean searchRec(BSTNode root, int key) { if (root == null) return false; // Base Case if (root.data == key) return true; return key < root.data ? searchRec(root.left, key) : searchRec(root.right, key); } public static void main(String[] args) { BST tree = new BST(); int[] values = {50, 30, 70, 20, 40, 60, 80}; for (int v : values) tree.insert(v); System.out.println("Search 40: " + tree.search(40)); // true System.out.println("Search 100: " + tree.search(100)); // false } }

✅ BST에서 탐색을 수행하면 최대 log_2 n 번 비교하므로 Θ(log n) 시간
✅ 탐색할 때마다 절반씩 줄어드는 것을 확인 가능!

---

📌 최종 정리

1️⃣ 점화식 풀이

1. BST에서 탐색하는 과정은 문제를 절반씩 줄임 → T(n) = T(n/2) + C
2. 반복 적용하면 T(n/2^k) = T(1) + kC
3. n/2^k = 1이 되는 k 찾기 → k = log_2 n
4. 점화식 대입 → T(n) = C1 + C log_2 n
5. Big-Theta 표기법으로 표현 → Θ(log n)

2️⃣ BST 탐색의 시간 복잡도

• 최선의 경우: O(1) (탐색할 값이 루트에 있을 때)
• 평균적인 경우: O(log n)
• 최악의 경우: O(n) (편향 트리에서 탐색할 때)
• **균형 BST (AVL, Red-Black Tree 등)**에서는 항상 Θ(log n)

😆 이제 점화식과 Θ(log n)이 나오는 원리 완벽하게 이해됐지? 🚀🔥

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

📌 효율적인 거듭제곱 계산 (A Better Power Function)

주어진 함수는 거듭제곱(power) 계산을 효율적으로 수행하는 재귀 함수입니다.
일반적인 거듭제곱 계산보다 훨씬 빠르게 계산할 수 있어요. 🚀

---

1️⃣ 기본적인 power(x, n) 계산 방법

일반적으로 거듭제곱을 계산하는 가장 직관적인 방법은 x를 n번 곱하는 것:

java

CopyEdit

int power(int x, int n) { int result = 1; for (int i = 0; i < n; i++) { result *= x; } return result; }

하지만 이 방식의 시간 복잡도는 O(n) 이므로, n이 커지면 매우 비효율적!

---

2️⃣ 효율적인 방법: 분할 정복 (Divide & Conquer)

주어진 코드는 분할 정복(Divide & Conquer)을 활용한 거듭제곱 계산이에요.

java

CopyEdit

int power(int x, int n) { if (n == 0) return 1; // Base Case: x^0 = 1 if (n == 1) return x; // Base Case: x^1 = x if (n % 2 == 0) return power(x * x, n / 2); // 짝수일 때 else return power(x * x, n / 2) * x; // 홀수일 때 }

✅ 짝수 지수(n이 짝수일 때):

xn=(x2)n/2xn=(x2)n/2

즉, 한 번 제곱해서 지수를 반으로 줄여서 계산!

✅ 홀수 지수(n이 홀수일 때):

xn=(x2)n/2×xxn=(x2)n/2×x

짝수의 경우처럼 줄이지만, 마지막에 x를 한 번 더 곱해줌.

---

3️⃣ 코드 실행 과정 분석

📌 예제 1: power(2, 10)

우리는 2^10을 계산하고 싶음.

1. n = 10 (짝수) → power(2 * 2, 10 / 2) 호출 → power(4, 5)
2. n = 5 (홀수) → power(4 * 4, 5 / 2) * 4 호출 → power(16, 2) * 4
3. n = 2 (짝수) → power(16 * 16, 2 / 2) 호출 → power(256, 1)
4. n = 1 (Base Case) → return 256
5. 값 반환:
   • power(256, 1) = 256
   • power(16, 2) = 256
   • power(4, 5) = 256 * 4 = 1024
   • power(2, 10) = 1024

✅ 결과: 2^10 = 1024
✅ 연산 횟수: O(log n) 번만 재귀 호출됨!

---

4️⃣ 시간 복잡도 분석

이 방법은 매 단계에서 지수를 절반씩 줄이므로 시간 복잡도가 O(log n) 이다.

📌 비교

• 일반적인 방법: O(n)
• 분할 정복 방법: O(log n)

예시: power(2, 1024)

• 일반적인 방법 → 1024번 곱하기 수행
• 분할 정복 방법 → log_2(1024) = 10번 곱하기 수행 (훨씬 빠름!)

 

 

 

 

 

 

 

 

public void deleteIterative(int elem) {
    if (root == null) { // nothing to delete
        return;
    }
    BSTNode prev = null;
    BSTNode current = root;

    // Find current that contains the elem value
    // Keep track of prev (parent)
    while (current != null) {
        if (elem == current.data)
            break;
        else if (elem > current.data) {
            prev = current;
            current = current.right;
        }
        else {
            prev = current;
            current = current.left;
        }
    }
    //System.out.println(current.data);
    if (current == null)
        return; // element not in the tree, nothing to delete

    // Removing a node with one child
    // The root also needs to change if we delete the root
    if (current.left == null) { // no left child
        if (prev == null) {
            // removing the root with one right child
            root = root.right;
            return;
        }
        // Removing a node without the left child, but it is not a root
        if (prev.left == current)
            prev.left = current.right; // since current has not left child
        else { //current is the right child of prev
            prev.right = current.right;
        }
    }
    else if (current.right == null){ // removing a node that does not have the right child
        if (prev == null) {
            // removing the root with one left child
            root = root.left;
            return;
        }
        // Removing a node without the right child, but it is not a root
        if (prev.left == current)
            prev.left = current.left;
        else { //current is the right child of prev
            prev.right = current.left;
        }
    }
    else { // has both children
        // Find the smallest value in the right subtree
        BSTNode rightRoot = current.right;
        BSTNode prevBeforeRightRoot = current;
        while (rightRoot.left != null ) {
            prevBeforeRightRoot = rightRoot;
            rightRoot = rightRoot.left;
        }
        System.out.println("smallest in the right subtree " + rightRoot.data);

        int smallest = rightRoot.data;
        current.data = smallest;
        // Remove smallest
        if (prevBeforeRightRoot.right == rightRoot) {
            prevBeforeRightRoot.right  = rightRoot.right;
        }
        else
            prevBeforeRightRoot.left = rightRoot.right;
    }
}