inflearn logo
강의

Course
Instructor

Learning Algorithm Basics with Python

최적 이진검색트리 관계식

Resolved

412

hyb9579

7 asked

0

안녕하세요! 최적 이진검색트리에서 궁금한점이 있어서 질문 남깁니다.

위 식에서

이 부분이

위에서 를 탐색하는 비용이라고 하셨는데,

제 생각에는 를 탐색하는 비용은 P_k가 되야 될거 같은데 왜 가 되는지 궁금합니다.

여기에서 어떤 임의의 K_i를 탐색하게 되더라도 탐색 깊이가 1인 (비교횟수가 1인) 를 무조건 지나가게 되니 비교횟수 1 * (모든 K_i의 확률)이 되서 가 된것인가요??

algorithm

Answer 1

1

joonion

꼼꼼하게 강의를 듣고 계시는 군요!

질문 속에 이미 답이 나와 있습니다.

어떤 K1... Kn의 키를 검색하려면 Kk는 반드시 지나가야 하므로,

sigma(Pk)가 Kk 노드에서의 Kk키에 대한 탐색 비용이 되는 것이지요.

0

hyb9579

그렇군요! 답변 감사합니다! 강의 잘듣고 있습니다 :)

문제 생각 몇분정도가 좋을까요

0

257

1

self

2

640

1

Two sum

2

338

1

Test_queue 출력 오류

1

548

2

int 범위

2

326

1

시간복잡도

1

1375

1

심화 과정 커리큘럼 질문

1

527

1

Algorithm 3.5 : Print Shortest Path 관련 질문 (플로이드 알고리즘)

0

274

0

코드 중간에 오류 보고 합니다!

1

236

1

쉽지 않네요 ㅠ

0

336

1

분기 한정법과 배낭 문제

0

392

1

배낭문제와 동적계획법

0

511

1

플로이드 알고리즘

0

426

2

n-Queens

0

223

1

큰정수의 계산법 강의에서 몫과 나머지

0

228

1

퀵정렬

0

208

1

1.1알고리즘 이란 에서 교환정렬 파이썬으로 바꿀때

0

303

1

마지막 matrixmult 파라미터 값

0

259

2

내장함수에 언더스코프의 의미

0

648

2

def mergesort(S) 부분이 이해가 가지 않습니다.

0

282

3

이진탐색 vs 합병정렬

1

450

2

분할정복에서 큰 정수 곱셈 다른 계산법?

1

319

1

0번째 왜 자꾸 버리시는건가요?

2

341

1

리스트의 합

0

181

1