inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

파이썬으로 배우는 알고리즘 기초

최적 이진검색트리 관계식

해결된 질문

420

hyb9579

작성한 질문수 7

0

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

위 식에서

이 부분이

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

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

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

algorithm

답변 1

1

주니온

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

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

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

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

0

hyb9579

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

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

0

276

1

self

2

645

1

Two sum

2

342

1

Test_queue 출력 오류

1

557

2

int 범위

2

331

1

시간복잡도

1

1381

1

심화 과정 커리큘럼 질문

1

534

1

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

0

283

0

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

1

243

1

쉽지 않네요 ㅠ

0

346

1

분기 한정법과 배낭 문제

0

399

1

배낭문제와 동적계획법

0

520

1

플로이드 알고리즘

0

433

2

n-Queens

0

226

1

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

0

237

1

퀵정렬

0

215

1

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

0

309

1

마지막 matrixmult 파라미터 값

0

270

2

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

0

662

2

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

0

290

3

이진탐색 vs 합병정렬

1

457

2

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

1

327

1

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

2

347

1

리스트의 합

0

186

1