Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 다시보기
- JPA
- 코드트리
- 기본유형
- 싸피
- DP
- 그리디
- JUnit
- 트러블슈팅
- 다익스트라
- 코테
- Union Find
- 완전탐색
- 알고리즘기본개념
- 자바
- SWEA
- 코딩테스트실력진단
- SSAFY
- 완탐
- 코딩테스트
- 부분수열의합2
- database
- 알고리즘
- Java
- DFS
- 백준
- BFS
- 유니온파인드
- 그래프
- Spring
Archives
- Today
- Total
HwangHub
BST의 시간복잡도 O(log N) 증명하기 본문
BST를 탐색하는 시간복잡도가 O(logN)이라고 한다.
이를 어떻게 유도할 수 있나?
유도 과정
기본적으로 크기가 N인 ordered array가 있다고 해 보자.
Binary search tree의 매커니즘과 동일하게 생각해보면, 우리는 숫자의 범위를 절반씩 잘라가는 행위를 결국에는 남은 숫자의 개수가 1이 될 때 까지 반복할 것이다. 이렇게 반복한 횟수를 k번이라 해 보자. (즉, 여기서 k가 의미하는 것은 결국 해당 연산을 몇 번 수행하냐를 의미하게 되며, 이는 BST의 탐색 연산 횟수와 같다.)
이를 수식화하면 N * (1/2)^k = 1 라고 표현할 수 있다. 이는 N = 2^k와 같다. 따라서 양 변에 밑이 2인 log를 취하면 log N = k 라는 결과가 나온다. 이는 N개의 숫자를 갖는 BST에서의 탐색 알고리즘은 log N이라는 시간복잡도를 갖는다는 것에 대한 증명이 된다.
'CS-STUDY > 자료구조 & 알고리즘' 카테고리의 다른 글
자바로 알고리즘 시작하기 2 - List, Queue 컬렉션 (1) | 2024.01.14 |
---|---|
자바로 알고리즘 시작하기 1 - 알고리즘 왜 하나요? (0) | 2024.01.07 |
[가벼운 고민] linked list에서 순서에 관계없이 노드를 추가할라면 어디에 추가하는게 가장 효율적인가? (0) | 2023.11.07 |
다이나믹 프로그래밍 (0) | 2023.10.18 |
그리디 알고리즘 (1) | 2023.10.09 |
Comments