미국유학/Data Structure and Algorithm (14) 썸네일형 리스트형 2.25 dsa수업 Easy 2.20 목요일 DSA 2.14 FRI DSA 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.. 2.11 DSA 이거랑(BinarySearchTree)... 그다음 배운거는 재귀. T(n) = T(n-k) + k*c 관련해서 지피티의 설명. Got it! Your professor is likely explaining how to analyze the time complexity of recursive linear search using recurrence relations. Let’s go through this step by step. 🚀Step 1: Understanding Recursive Linear SearchThe recursive linear search function looks something like this:javaCopyEditboolean linearSearch(int[] arr,.. linkedlist - reverse Iterable, Linkedlist, Queues, Stack, Trees public class LibraryCatalog implements Iterable { private ArrayList books; LibraryCatalog() { books = new ArrayList(); } public void addBook(String name, String author) { Book book = new Book(name, author); books.add(book); } public String toString() { StringBuilder sb = new StringBuilder(); for (int i = 0; i iterator() { return books... QueueWithTwoStacks package queue;import stack.ArrayStack;import stack.Stack;/** The class that implements the functionality of the queue * (enqueue, dequeue, empty) with two stacks. */public class QueueWithTwoStacks { private Stack s1 = new ArrayStack(); private Stack s2 = new ArrayStack(); // You may NOT use any other memory, no array and no linked list, // only the two stacks, s1, s2. You may call me.. 이전 1 2 다음
