Tip:
Highlight text to annotate it
X
우리는 오늘 이진 검색 트리에 대해 이야기할 것입니다.
그것은 소위 랜덤하게 구축된 이진 검색 트리입니다.
그리고, 저는 수업 내내 이진 검색 트리를 BST로 줄여 쓸 것입니다.
그리고, 여러분은 모두 이진 검색 트리를 보았을 것입니다,
특히 금요일 수업에서요.
우리는 저기서 나타난 기본적인 아이디어를 구축할 것이고
그것들을 랜덤화하는 방법과 그것들을 좋게 만드는 방법에 대해 이야기할 것입니다.
여러분은 좋은 이진 검색 트리가 있다는 것을 압니다,
그것은 상대적으로 균형잡힌 것입니다,
이와 같이요. 높이는 log n 입니다.
우리는 균형 잡히지 않을 것을 불렀고, 그것은 좋습니다.
오더 log n은 좋을 것입니다.
검색의 관점에서, 그것은 오더 log n의 비용입니다.
그리고, 나쁜 이진 검색 트리가 있습니다 그것은 정말
큰 높이를 가집니다, 가능한 n만큼 큽니다.
이것은 좋습니다, 그리고 이것은 나쁩니다.
우리는 알고 싶습니다, 그리고 항상 좋은, 또는 적어도
대부분 시간에서 좋은 이진 검색 트리를 구축하고 싶습니다.
이것을 하는 많은 방법들이 있습니다,
그리고 몇 주 안에, 우리는 그것들 중 네 개를 보게 될 것입니다,
여러분이 문제 세트를 세어보면요.
오늘, 우리는 어떤 면에서 대부분의 시간에 균형 잡히게
하기 위해 랜덤화를 사용할 것입니다.
여러분의 문제 세트에서, 여러분은 넓은 면에서 할 것입니다.
이 주제를 동기 부여하는 하나의 방법은,
저는 약간 이진 검색 트리를
랜덤하게 구축하지 않을 것이라는
겁니다.
이진 검색 트리를 이용한 n 개의 수를 정렬하는 자연스러운 방법이 있습니다.
그래서, 제가 여러분에게 배열을 주면,
여러분은 어떻게 이진 검색 트리를 이용해서 정렬합니까?
이진 검색 트리를 구축하고,
순서대로 가로지르는 것입니다. 정확해요.
우리가 초기의 트리를 가지고 있다고 가정해 봅시다.
그것은 비어있습니다, 그리고 각 배열의 요소에 대해서
우리는 그것을 트리에 삽입합니다.
그것은 여러분이 검색 트리를 구축하는 것으로 의미한 것을 말합니다
그래서, 우리는 트리에 A[i]를 삽입합니다. 이것은 이진 검색 트리 삽입합니다,
표준 삽입입니다. 그리고, 우리는 가로지르는 순서로 합니다,
책에서 그것은 순서 트리입니다.
여러분은 이 알고리즘을 알아야 합니다,
그러나 매우 빠른 나머지를 위하여,
트리 삽입은 기본적으로 인자 A[i]를 찾습니다
그것이 있어야 하는 상조를 찾을 때까지요. 그것이 이미 트리에 있으면,
새 값을 더하기 위해 새 리프를 더합니다.
재귀적으로 왼쪽 서브 트리를 돌고, 루트를 출력합니다,
그리고 재귀적으로 오른쪽 서브 트리를 돕니다.
그리고 이진 검색 트리의 속성에 의하여,
그것은 정렬된 순서로 출력할 것입니다.
간단한 예를 해 봅시다 이것은 우리가 이미 보았던 다른 정렬 알고리즘과
관련된 것으로 드러났기 때문입니다.
예는 아마 아주 당연한 것인 반면에,
연결은 매우 놀라운 것입니다.
적어도, 그것은 제가 이 수업에서 처음 가르치는 것 같군요.
제 배열은 3 1 8 2 6 7 5 입니다.
그리고 저는 왼쪽에서 오른쪽의 순서로 이 인자들을 방문할 것입니다,
그리고 트리를 구축할 것입니다.
제가 보는 첫 번째 인자는 3입니다.
저는 3을 빈 트리에 넣습니다.
그것은 비교를 요구하지 않습니다. 그리고 저는 1을 삽입합니다.
1이 3 보다 큰가요 작은가요?
더 작습니다. 그래서 저는 그것을 여기에 넣습니다.
그리고 8을 삽입합니다. 그것은 3 보다 큽니다,
그것은 여기 새 리프를 얻습니다.
그리고 저는 2를 삽입합니다. 그것은 1과 3 사이에 있습니다.
그리고, 그것은 1의 오른쪽 자식으로 떨어집니다.
저는 2를 저기서 더합니다.
6은 3보다 큽니다, 그리고 8보다 작습니다.
그것은 여기로 갑니다. 7은 3보다 크고
8보다 작습니다, 그리고 6보다 큽니다.
그것은 여기로 가고, 5는 3과 5 사이에 맞습니다. 3과 6 사이 보다는요.
그것은 다시 이진 검색 트리입니다.
저는 가로지르는 순서로 갑니다,
그것은 1 2 3 4 5 6 7 8 을 출력합니다.
저는 제 머리에서 빠르게 돌릴 수 있습니다.
왜냐하면 저는 큰 스택을 갖기 때문입니다.
약간 주의해야 합니다.
물론, 여러분은 그것들이 정렬된 순서
1 2 3 4 5 6 7 8 로 나오도록 확인해야 합니다.
그리고, 여러분이 큰 스택을 가지지 않으면, 여러분은 가서 살 수 있습니다.
그것은 항상 유용합니다.
메모리는 요즘 가격이 약간 올라가고 내려갑니다.
그것은 정책 때문에 가격이 고정적이어야 합니다.
그래서 질문은,
알고리즘의 러닝 타임은 무엇입니까?
여기서, 이것은 그것이 의존하는 답들 중 하나입니다.
분석하기 쉬운 부분은 초기화입니다.
오더 트리 워크에서,
그것은 얼마나 걸리나요? n 입니다, 좋아요.
그래서, 그것은 워크를 위해 O(n)입니다, 그리고 초기화를 위해,
그것은 일정합니다.
제가 n 트리 삽입을 하기 위해 얼마나 시간이 걸리나요?
누가 답변해 볼 수 있나요?
저는 이미 알고 있습니다만.
네?
Ω(n log n)입니다, 좋아요.
그것은 적어도 n log n 입니다. 왜죠?
네. 그래서, 여러분은 두 이유를 주었습니다.
첫 번째는 결정 트리 하한 때문입니다.
그것은 사실 이것을 증명하지 않습니다.
여러분은 약간 신중해져야 합니다.
이것은 그것이 항상 Ω(n log n)이라는 주장입니다.
그것은 확실히 최악의 케이스에서 Ω(n log n) 입니다.
모든 비교 기반 정렬 알고리즘은 최악의 케이스에서 Ω(n log n)입니다.
그것은 또한 모든 단일 시간에 n log n 입니다,
Ω(n log n)입니다, 그것은 두 번째 이유 때문입니다,
그것은 일어날 수 있는 최고의 것이 우리가 완벽하게 균형 잡힌 트리를 가진다는 것입니다.
그래서, 이것은 제 삶에서
가장 많이 칠판을 쓰는 부분입니다,
15 노드의 완벽한 트리입니다.
우리가 운이 좋다면, 우리는 이것을 가집니다.
그리고 여러분이 여기서 모든 노드의 깊이를 더하면,
그것은 여러분에게 검색 트리 비용을 줍니다,
특히 아래에서 이 n 나누기 2 노드입니다, 각각은 깊이 log n을 가집니다.
그러므로, 여러분은 그것들을 위해 적어도 n log n을 지출해야 합니다.
여러분이 덜 균형 잡힌 걸 가졌다면, 그것은 더 나쁩니다.
그것은 어떤 증명을 수반하지만, 그것은 옳습니다.
그래서, 그것은 사실 항상 Ω(n log n)입니다.
어떤 케이스들이 있습니다,
여러분은 이미 거의 정렬된 인자들을 알고 있습니다,
여러분은 그것을 선형 수 비교에서 할 수 있습니다.
그러나 여기에서, 여러분은 할 수 없습니다.
이 질문의 답이 무엇인지 알겠나요? 네?
O(n^2) 인가요? 좋아요, 왜죠?
맞습니다. 우리는 n을 하고 있습니다,
각 노드는 깊이를 가집니다, 최대 n입니다.
우리가 인자 당 하는 비교는,
최대 n입니다.
그것은, 많아 봐야, n^2 입니다.
다른 답 있나요? 그것은 이 알고리즘이 n^2 시간을 가지도록 할 수 있나요?
θ(n^2) 이 걸리는 인스턴스가 있나요?
그것이 이미 정렬되어있으면, 그것은 매우 나쁩니다.
그래서, 그것이 이미 정렬되어 있거나 역으로 정렬되어 있다면,
여러분은 나쁜 모양에 있습니다.
왜냐하면 여러분은 이와 같은 트리를 얻기 때문입니다. 이것은 정렬된 케이스입니다.
그리고, 여러분은 계산합니다.
그래서, 총 비용, 일반적으로 시간은 트리에서 각 노드를 위한
노드들의 깊이의 합이 될 것입니다.
그리고 이 케이스에서, 그것은 1 더하기 2 더하기 3 더하기
4입니다, 이것은 등차 급수입니다.
그것들의 n이 있습니다, 그래서 이것은 θ(n^2)입니다.
그것은 n^2 나누기 2와 같습니다. 그것은 나쁜 소식입니다.
이 알고리즘의 최악의 케이스 러닝 타임은 n^2입니다.
최악의 케이스 러닝 타임이 n^2인,
특히 이미 정렬된 케이스에서, 이것이 친숙하게 들리나요?
그러나 우리가 운이 좋다면, 운이 좋은 케이스에 있다면,
그것은 균형 트리입니다.
훌륭하지 않나요?
Ω(log n) 높이는 우리에게 n log n에 돌아가는
정렬 알고리즘을 줍니다. 그래서, 운이 좋은 케이스에서, 우리는 n log n 입니다.
그러나 운이 나쁜 케이스에서,
우리는 n^2 이고 정렬을 사용합니다.
그것은 우리가 전에 보았던 알고리즘을 떠올리게 하나요?
퀵 정렬입니다. 이 알고리즘의 러닝타임은
매우 강력히 퀵 정렬의 러닝 타임과 같습니다.
그것은 이 알고리즘이 퀵 정렬이 하는
정확히 같은 비교를 한다는 것입니다.
그것은 다른 순서로 만듭니다,
그러나 그것은 정말 같은 알고리즘입니다.
여기서 놀라운 것입니다.
특히, 우리는 이미 퀵 정렬을 분석했습니다.
우리는 그 분석에서 공짜로 무엇을 얻어야 합니다.
BST 정렬과 퀵 정렬은 같은 비교를 하지만
다른 순서에 있습니다.
우리가 전에 했던 같은 예를 해 봅시다:
3 1 8 2 6 7 5.
배열이 있습니다.
우리는 특정한 버전의 퀵 정렬을 돌릴 것입니다.
저는 약간 여기서 신중해야 합니다.
그것은 퀵 정렬의 분명한 버전입니다.
기억하세요, 우리의 표준적인, 지루한 퀵 정렬은 여러분이
첫 번째 인자를 분할 인자로 취하는 것입니다.
저는 여기서 3을 가질 것입니다.
그리고, 저는 3 보다 적은 인자를 쪼갤 것입니다, 그것은 1과 2입니다.
그리고 3보다 큰 인자들이 있습니다, 8 6 7 5.
퀵 정렬의 이 버전에서,
저는 인자의 순서를 바꿀 수 없습니다,
8 6 7 5.
순서가 유지 됩니다 왜냐하면 그래야 이 동등성을 가질 수 있습니다.
이것은 안정적인 분할 알고리즘입니다.
하기 쉽습니다.
퀵 정렬의 특정 버전입니다.
그리고 곧, 우리는 그것을 랜덤화 할 것입니다.
그리고 나서, 이 차이는 중요하지 않습니다.
왼쪽 재귀에서, 우리는 분할 인자를 쪼갭니다.
1 보다 작은 것이 있는데, 그것은 아무 것도 없는 것이고,
1 보다 큰 것이 있는데, 그것은 2입니다.
그리고 그것은 우리의 분할 인자입니다.
우리는 다 했습니다.
여기서 우리는 8에서 분할합니다.
모든 것은 8 보다 작습니다.
우리는 6 7 5 를 얻습니다.
우리는 6에서 분할합니다. 우리는 6 보다 작은 것을 얻습니다,
주로 5 6 보다 작고, 주로 7 6 보다 큽니다.
그리고, 사소한 방법에서
분할 인자들이 있습니다.
이제, 우리가 분할 인자에서 얻는 트리는 이 트리와 같이 나쁩니다.
좋아요, 그것은 정확히 같은 트리여야 합니다.
그리고, 여러분은 걸을 수 있습니다.
퀵 정렬이 하는 비교는 무엇입니까?
자, 먼저, 그것은 모든 것을 3과 비교합니다.
3 자신을 제외하고요. 이제, 여러분이 여기서 보면,
우리가 인자를 삽입할 때 무슨 일이 일어나나요?
자, 우리가 인자를 삽입하는 매 시간, 우리가 하는 첫 번째 것은 3과 비교하는 것입니다.
그것이 작으면, 우리는 왼쪽 가지로 갑니다.
더 크면, 오른쪽 가지로 갑니다.
그래서, 우리는 양 케이스에서
3과 비교를 합니다.
우리가 3 보다 작은 인자를 가지고 있다면, 그것은 1 또는 2 입니다.
그것이 1이면, 우리는 다 했습니다.
여기서 1과 어떤 비교도 없습니다.
그러나, 우리는 1과 2를 비교합니다.
정말로, 우리가 그것을 3과 비교한 후에 2를 저기에 삽입할 때, 우리는 그것을 1과 비교합니다.
그리고 우리는 여기서 일어나는 것을 알아 냅니다.
같은 것이 퀵 정렬에서 일어납니다.
3 보다 큰 인자들을 위해, 우리는 여기서
8과 모든 비교를 합니다 왜냐하면 우리는 8에 대하여 분할하기 때문입니다
왜냐하면 그것이 3 이후의 옆 노드이기 때문입니다.
8이 삽입되자 마자,
우리는 8과 모든 것을 비교합니다:
모든 같은 비교 이지만,
다른 순서일 뿐입니다.
우리는 90° 돌립니다. 멋져요.
그래서, 이것은 분석에서 다양한 결과를 가집니다.
특히, 최악의 케이스 러닝 타임은
θ(n^2)입니다, 그것은 흥미로운 것이 아닙니다.
우리가 정말 신경 쓰는 것은 랜덤화된 버전입니다 왜냐하면 그것은 잘 수행하는 것이기 때문입니다.
그래서, 랜덤 BST 정렬은 랜덤 퀵 정렬과 같습니다.
여러분이 하는 첫 번째 것은 랜덤하게
배열을 변경하는 것입니다,
그리고 같은 확률로 모든 변경을 고릅니다.
우리는 BST 정렬이라고 부릅니다. 이것은
기본적으로 랜덤 퀵 정렬이 공식화되는 것입니다.
랜덤 BST 정렬은 랜덤 퀵 정렬과
정확히 같은 비교를 합니다.
여기서, 우리는 필수적으로 랜덤한 루트를 찾습니다
그리고 여기 퀵 정렬에서, 여러분은 랜덤하게 분할 인자들을 고릅니다.
그것은 같은 차이입니다.
그래서 이 알고리즘의 시간은 랜덤 퀵 정렬과 같습니다
왜냐하면 우리는 같은 비교를 하기 때문입니다.
그래서 비교의 수는 같습니다.
그리고 이것은 랜덤 변수에서 옳습니다.
랜덤 변수, 러닝 타임 이 알고리즘은
이 알고리즘의 랜덤 변수와 같습니다.
특히,
기대값도 같습니다.
좋아요, 그리고 우리는 랜덤 n 인자들에서
랜덤 퀵 정렬의 예상 러닝 타임이 무엇인지 알고 있습니까?
오, n log n 입니다.
좋아요. 저는 저기서 약간 걱정이 됩니다. 좋아요, 특히, BST 정렬의 예상 러닝 타임은 n log n 입니다.
명백히, 이것은 정렬의 견해로부터
매우 흥미로운 것이 아닙니다.
정렬은 이 연결을 보는 것입니다.
우리가 실제로 신경 쓰는 것은, 제가 BST 정렬을 소개하는 이유는
트리가 무엇과 같아 보이는지 입니다.
우리가 정말 원하는 것은 그 검색 트리입니다.
검색 트리는 정렬 보다 이상의 것을 할 수 잇습니다.
중위 순회(in-order traversal)는 검색 트리로 하기 매우 지루합니다.
여러분은 검색 트리에서 검색할 수 있습니다.
좋아요, 그것은 여전히 그리 흥미롭지 않습니다.
여러분은 인자들을 정렬할 수 있고
그것을 배열에 넣을 수 있고 이진 검색을 합니다.
그러나, 이진 검색 트리의 관점은, 이진 검색 배열 대신,
여러분이 그것들을 극적으로 업데이트 할 수 있다는 겁니다.
우리는 그것들을 이 강의에서 극적으로 업데이트 하지 않을 것입니다,
그리고 우리는 수요일에 그리고 여러분의 문제 세트에서 할 것입니다.
지금은, 그것은 일종의 준비 입니다.
그것을 변하지 않는 인자라고 합시다.
우리는 기초로부터 하나의 트리를 구축합니다.
우리는 시간에 앞서서 모든 n 개의 인자들을 가지고 있습니다.
우리는 그것을 무작위로 구축할 겁니다.
우리는 그 배열을 무작위로 변경합니다. 그리고 우리는 모든 인자를 이진 검색 트리로 던집니다.
그것이 BST 정렬이 하는 것입니다.
그리고 그것은 중위 순회(in-order traversal)를 호출합니다.
저는 정말로 중위 순회(in-order traversal)를 신경 쓰지 않습니다.
왜냐하면 우리가 그것을 분석했기 때문입니다.
제가 다 했으면 그것은 짧은 강의가 될 것입니다.
우리가 원하는 것은 이 랜덤하게 구축된 BST입니다,
그것은 우리가 이 알고리즘으로 도출하려는 것입니다.
이것은 BST 정렬로부터 결과를 얻는 트리입니다.
간단한 트리 삽입 정렬을 사용해서 이 인자들을 삽입하는 배열에서
변환하는 것으로부터 결과를 얻습니다.
그 트리는 무엇과 같습니까?
특히, 우리가 이 사실로부터 결론 지을 수 있는 것이 있습니까?
BST 정렬의 예상 러닝 타임은 n log n 입니다.
좋아요, BST 정렬의 러닝 타임이 무엇인지
저는 언급 했었습니다.
그것은 합이었습니다. 이것은 n 인자에서 BST 정렬의 시간입니다.
그것은 모든 노드의 합입니다.
깊이는 0에서 시작합니다 그리고 아래로 동작합니다
왜냐하면 루트 인자 때문입니다,
여러분은 그 이상에서 어떤 비교도 할 수 없습니다.
여러분은 깊이가 무엇이든 비교를 해야 합니다.
그래서 우리는 이것을 알아야 합니다. 기대값에서 우리는 이것이 n log n이라는 것을 압니다.
그것은 우리에게 트리에 대하여 무엇을 말해줍니까?
이것은 모든 노드를 위한 것입니다.
그것은 우리에게 예를 들어,
트리의 높이에 대해 말해줍니까? 네?
맞아요, 직관적으로, 그것은 트리의 높이가 n이 아니라,
θ( log n )이라는 것을 말합니다.
그러나 사실, 그것은 보여주지 않습니다.
그리고 그것은 여러분이 느끼면 그것이 직관인 이유입니다,
그러나 그것은 꽤 맞지 않을 수도 있습니다.
정말 아닙니다. 그것이 무엇을 말하는지 말해주겠습니다.
우리가 양 쪽의 기대값을 가지면, 여기서 우리는 n log n을 얻습니다.
그래서, 그것의 예상 값은 n log n 입니다.
여기서, 우리는 예상 총 깊이를 얻습니다,
그리고 그것은 그리 흥미롭지 않습니다.
예상 평균 깊이를 봅시다.
제가 1 나누기 n을 보면, X 깊이의 트리에서 모든 노드의 합은
평균 깊이 나누기 모든 노드입니다.
제가 얻어야 하는 것은 n log n 나누기 n 입니다
왜냐하면 저는 양쪽을 n으로 나누기 때문입니다.
그리고 저는 여기서 기대값의 선형성을 사용할 것입니다.
그리고 그것은 log n 입니다.
예상 러닝 타임이 저에게 알려주는 사실은
트리에서 평균 높이가 log n 이라는 겁니다,
그것은 log n인 트리의 높이가 아닙니다.
트리의 높이가 어던 노트의 최대 깊이라는 것을 기억하세요.
여기서, 우리는 평균 깊이를
바운드 합니다.
트리의 예를 봅시다.
저는 가장 좋아하는 그림을 그릴 겁니다.
그래서, 여기서 우리는 좋은 균형 트리를 같습니다. 절반의 노드 또는 약간 더 있습니다.
그리고 저는 특정 리프의
긴 경로를 가지고 있습니다.
그것이 무엇인지는 중요하지 않습니다.
저는 이 경로가 길이를 가진다는 것을 말합니다, 저는 루트 n을 원합니다,
그리고 그것은 log n 보다 많이 큽니다.
이것은 대략 log n 입니다.
그것은 n 의 로그 마이너스 루트 n 입니다.
대부분의 노드는 대수의 높이,
미안해요, 대수의 깊이를 가집니다.
여러분이 이 특정 트리에서 평균 깊이를 계산하면,
대부분의 노드를 위하여,
많아 봐야 n 노드는 높이 log n을 가집니다.
그리고 루트 n 노드들이 있습니다, 여기 아래에요,
그리고 그것은 깊이를 가지고, 많아 봐야 루트 n 입니다.
그래서 그것은 많아 봐야 루트 n 곱하기 루트 n 입니다.
사실, 그것은 1/2와 같지만, 그리 큰 것은 아닙니다.
그래서 이것은 n입니다. 그래서, 이것은 n log n 입니다,
미안해요, 평균 깊이 입니다. 모든 것을 n으로 나누어야 합니다.
n log n은 평균 높이, 평균 깊이를
위해 다소 커져야 합니다.
여기서 평균 깊이는 log n 입니다, 그러나 트리의 높이는 n의 제곱근입니다.
그래서 이것은 충분하지 않습니다.
평균 깊이가 log n이라는 것을 아는 것은 중요하지 않습니다,
그것은 높이가 log n이라는 것을 의미하지 않습니다.
그러나 주장은 오늘의 이 이론이 랜덤하게 구축된 이진 검색 트리의 예상 높이가 정말 log n이라는 것입니다.
정말 log n이라는 것입니다.
BST는 오더 log n입니다. 이것은 우리가 알고 싶은 겁니다
왜냐하면 우리가 이진 검색 트리를 랜덤하게 구축하면,
우리는 log n에서 검색할 수 있기 때문입니다.
정렬을 위해, 그것은 큰 문제가 아닙니다.
우리는 그것을 만드는 것의
예상 러닝 타임에 대하여 신경 쓰지 않습니다.
여기서 이제 우리는 우리가 이 정리를 증명한 것을 압니다
우리는 우리가 기대값에서 빠르게 검색할 수 있다는 것을 압니다,
사실 대부분의 시간에서요. 그래서 오늘 강의의 나머지는 이 정리를 증명하는 것입니다.
그것은 꽤 까다롭습니다,
여러분이 상상하는 대로요. 그것은 퀵 정렬 그리고 모든 것을 따라
큰 가능성의 분석입니다.
저는 증명의 아웃라인을 시작할 겁니다,
정리에 대하여 질문이 없다면요.
우리가 증명하려고 하는 것은 매우 분명해야 합니다.
이것은 우리가 전에 보았던 대부분의 분석들 보다 더 이상합니다.
그것은 훌륭한 트릭을 사용할 겁니다, 그것은 지수적인 랜덤 변수입니다.
그리고 그것을 하기 위해 우리는 Jenson's inequality 라는 툴이 필요합니다.
우리는 그 툴을 증명할 겁니다.
보통, 우리는 가능성 도구들을 증명하지 않습니다.
그러나 이것은 우리가 증명해야 할 것입니다. 그
것은 어렵지 않습니다.
그것은 또한 기본적인 분석입니다.
부명제 입니다, 우리가 볼록 함수 f를 가지면, 여러분은 그것이 무엇을 의미하는지 알아야 합니다,
그러나 저는 여러분이 잊어 버린 케이스에서 곧 그것을 증명할 것입니다.
여러분이 볼록 함수 f를 가지면,
여러분은 확률 변수 X를 가지고, 여러분은 기대값의 f를 취합니다.
즉, 많아 봐야,
그 랜덤 변수의 f의 기대값입니다.
그것에 대해 충분히 생각하고 꽤 직관적인 볼록 함수를 그려보세요.
그러나 우리는 그것을 증명할 겁니다.
그것이 우리에게 허락하는 것은 우리에게 트리의 높이를 알려주는
랜덤 변수 X_n 를 분석하는 대신에,
저는 랜덤 변수를 r.v.라고 부르겠습니다,
그것은 BST의 높이입니다, 우리는 n개의 노트에서 랜덤하게 구축된 BST를 분석할 것입니다.
이 요구되는 랜덤 변수를 분석하는 대신에,
미안해요, 이것은 대문자 X여야 했습니다.
우리는 X_n의 어떤 볼록 함수를 분석할 수 있습니다.
우리는 지수를 분석할 겁니다.
저는 Y_n을 2^(X_n)으로 정의할 겁니다.
여기서 큰 문제는 이것을 왜 괴롭힙니까?
답은 그것이 동작하기 때문이고 우리가 X_n을 분석하면
그것은 동작하지 않을 겁니다.
우리는 나중에 그것의 직관을 볼 것입니다,
그것은 매우 직관적이지는 않습니다. 이것은 여러분이 이 추가의 트릭을 필요로 하는 추가적인 분석입니다.
우리는 Y_n의 기대값을 바운드 할 것입니다,
그리고 Jensen's inequality를 사용할 것입니다,
우리는 X_n의 기대값에서 바운드를 얻습니다,
매우 타이트한 바운드입니다,
사실, 왜냐하면 우리가 정수로 바운드할 수 있으면
정수의 지수는, 우리는 X_n을 더 잘 바운드 할 수 있기 때문입니다
여러분은 X_n을 얻기 위해
로그를 취할 수 있습니다.
우리는 정수가 무엇인지도 알아낼 수 있습니다.
우리가 증명할 것은, 이것은 증명의 핵심입니다,
Y_n의 예상 값은 O(n^3)입니다.
여기서, 우리는 정수가 무엇인지 정말 알지 못합니다.
우리는 그럴 필요가 없습니다. 그리고, 우리는 이것들을 함께 할 수 있습니다.
그것을 해 봅시다.
우리가 정말 신경 쓰는 것은 X_n의 기대값입니다,
그것은 우리 트리의 높이입니다.
우리가 찾아야 하는 것은 이 사실입니다.
여기 어떤 수평의 공간을 남겨 둡시다.
우리는 X_n의 2의 기대값을 얻습니다.
그것은 Y_n의 기대값입니다. 우리는 그것이 O(n^3)이라는 것을 배웠습니다.
Jensen's inequality는
우리에게 다음을 알려줍니다
우리가 이 함수를 취하면, 우리는 그것을 여기에 꼽습니다,
왼쪽에서
우리는 2^(E[X_n])을 얻습니다.
2^(E[X_n])을 말이죠.
그래서 이제, 우리는 바운드를 가집니다.
그것은 많아 봐야 n^3입니다.
그래서, 우리가 양쪽에 로그를 취하면, 우리는 X_n의 E를 얻습니다,
그것은 많아 봐야 n^3의 로그입니다.
좋아요, 저는 그것을 재미 있는 방법으로 쓸 것입니다. lg(O(n^3))입니다.
그리고 그것은 사실 우리에게 정수를 알려줍니다.
이것은 3*lg(n)+O(1)입니다.
그래서, 우리는 랜덤하게 구축된 이진 검색 트리의 높이가
대략 3*lg(n)이라는 것을 증명할 것입니다.
저는 그것을 나중에 더 말할 겁니다.
여러분은 이제 증명의 마지막을 보았습니다.
그것은 전조입니다.
그리고 이제, 이것은 탑 다운 접근입니다.
여러분은 단계가 무엇인지 보게 됩니다.
이제, 우리는 단계들을 해야 합니다.
단계 1입니다: 약간의 일을 취하세요,
그러나 그것은 쉽습니다 왜냐하면 그것은 기본적인 것이기 때문입니다.
단계 2는 정의이고 그것은 우리가 했습니다.
단계 3은 아마 가장 어려운 부분일 겁니다.
단계 4는 이미 했습니다. 단계 1을 시작해 봅시다.
제가 필요한 첫 번째 것은 볼록 함수를 정의하는 겁니다.
왜냐하면 우리는 꽤 많은 정의를 조작해야 하기 때문입니다.
그래서 이것은 실제 분석의 개념입니다.
분석은 수학을 위한 훌륭한 단어입니다
여러분이 적절한 분석 수업을 듣지 않았다면요.
여러분은 어떤 수학 수업에서 볼록성을 들어야 했습니다.
볼록 함수는 이와 같아 보이는 하나 입니다.
좋아요. 이 개념을 공식화하는 방법은
이 곡선에서 두 점을 고려하는 겁니다.
저는 오직 실제의 함수에만 관심이 있습니다.
그것은 이와 같습니다. 이것은 어떤 것의 f입니다.
그리고, 이것은 어떤 것입니다.
저는 이 곡선에서 두 개의 점을 취합니다,
그리고 그것들을 연결하는 선을 그립니다. 선은 항상 곡선 위에 있습니다.
그것이 볼록성의 의미입니다.
그것은 기하학적 개념입니다, 그것은 기본적으로 같습니다.
그러나 함수를 위해, 이 라인은 고선 위해 존재해야 합니다.
선은 곡선 위에 있지 않습니다.
제가 그것을 더 연장하면,
그것은 곡선 아래에 있습니다.
저는 그것을 약간 공식화할 겁니다. 저는 이것을 x라고 부를 겁니다,
그리고 이것은 x의 f입니다.
그리고 저는 이것을 y라고 부를 것이고 이것은 y의 f입니다.
그래서 주장은 제가 x와 y 사이의 어떤 수를 취한다는 겁니다,
그리고 찾습니다,
여기 곡선의 점이 있습니다.
여기서 선의 점이 있습니다.
y 값에서 점의 값은 여기서
y 값 보다 크거나 같아야 합니다.
네? 점이 무엇인지 알아 내기 위해,
저는 기하학이 약간 필요합니다.
저는 그것이 분석 개념이라고 확신합니다.
그러나 저는 기하학자입니다, 그래서 저는 그것을 기하학이라고 부를 겁니다.
만약 여러분이 두 점 p와 q를 가지면,
여러분은 그들 사이의 선을 파라미터로 나타낼 수 있습니다.
저는 여기서 점을 파라미터로 나타내고 싶습니다.
그것을 하는 방법은 선형 결합을 취하는 겁니다.
여러분이 어떤 선형 대수를 취했으면, 선형 결합은 이와 같은 겁니다.
그리고 사실,
우리는 α 더하기 β가 1인
선형 결합을 가질 겁니다.
여러분이 모든 점,
수들을 가진다면요.
여러분이 모든 점을 가지면, 여러분은 여기서 전체의 선을 가집니다, 그것을 깔끔합니다.
그러나 우리는 전체 선을 원하지 않습니다.
여러분이 또한 α와 β를 음이 아니라고 제한하면,
여러분은 이 선을 얻습니다.
그래서, 이것은 α와 β가 0과 1 사이라고 강요합니다
왜냐하면 그것들을 합이 1이어야 하기 때문입니다, 그것은 또한 음이 아니어야 합니다.
우리가 여기서 하려고 하는 것은 α곱하기 x 더하기 β곱하기 y를 취하는 겁니다.
그것은 α+β가 1이라는
제약 사이의 점입니다.
α와 β는 0 보다 크거나 같습니다.
이 점은 그것의 f입니다. α_x 더하기 β_y의 f입니다.
그리고 이점은 fx와 fy의 선형 보간입니다.
그것은 α 곱하기 fx 더하기
β 곱하기 fy입니다.
좋아요, 그것은 직관입니다. 여러분이 그것을 따르지 않으면,
그것은 큰 문제가 아닙니다 왜냐하면 우리가 신경 쓰는 모든 것은
그것을 증명하기 위한 상징적인 답이기 때문입니다.
그러나 그것은 이것이 유래한 곳입니다.
그래서 여기에 정의가 있습니다.
그것의 함수는 볼록입니다. 모든 x와 y에 대하여, 모든 α와 β는 0 보다 크거나 같습니다,
그것의 합은 1입니다,
우리는 α_x와 β_y의 f를 갖고 그것은
α*f(x) + β*f(y) 보다 작거나 같습니다.
그것인 이 y를 여기에서 조정하는 것입니다.
그러나 그것은 이 그림 뒤의 상징성입니다.
좋아요, 그래서 이제 우리는 Jensen's inequality를 증명하길 원합니다.
우리는 아직 많이 하지 않았습니다.
우리는 Jensen's inequality에서 온 쉬운 간단한
부명제를 증명할 것입니다.
이것은 우리가 증명할 정리입니다.
여기 볼록 함수에 대한 부명제가 있습니다.
여러분은 그것을 전에 보았습니다. 그것은 Jensen's inequality에
중대한 것입니다.
이것은 2개 대신 n개의 선형 결합의 문장입니다.
이것은 볼록성이 n개를 취하기 위해
일반화 될 수 있다는 것을 말합니다.
우리가 n개의 실제 수를 가지고 있다고 가정해보세요,
그리고 우리는 n 개의 값 α_i를 가집니다.
그것들은 음이 아닙니다. 그것들의 합은 1입니다.
그래서, k가 0에서 n까지 일때, α_k의 합은 1입니다.
그것들은 가정입니다.
결론은 같습니다, 그러나 모든 합입니다.
k는 1에서 n까지일때 α_k*x_k의 합의 f값은
alpha_k * f(x_k) 입니다.
여기에서 k는 1에서 n까지입니다.
그래서, 볼록성의 정의는 정확히 그 문장과 같지만 n이 2인 곳에서입니다.
α1과 α2는 α 그리고 β입니다.
이것은 일반적인 n을 위한 문장입니다.
여러분은 이것을 재미 있는 방법으로 해석할 수 있습니다,
저는 들어가지 않을 겁니다.
물론이죠, 왜죠? 저는 기하학자입니다.
이것은 여러분이 이 곡선에서 어떤 점을 취하는 겁니다.
여러분은 그들이 정의한 다각형을 취합니다.
이것들은 직선입니다.
여러분은 인테리어를 가집니다.
여러분이 그와 같은 선형 결합을 가지면,
여러분은 그 다각형 안에 점을 얻을 수 있습니다 또는 경계에서요.
모든 점들은 곡선 위에 있습니다.
다시, 직관적으로 여러분이 좋은, 고전의 볼록선을 그리면 옳습니다,
그러나 사실,
그것은 대수적으로 옳습니다.
그것은 항상 좋은 것입니다.
우리가 이 정리, 이 부명제를 어떻게 증명하는지에 대한 제안 있나요?
그것은 매우 쉽습니다. 그것을 증명하기 이해 우리가 사용해야 하는 기술은 무엇입니까?
하나의 단어 입니다: 도입.
항상 좋은 답입니다.
도입은 여기서 큰 소리로 말해야 합니다
왜냐하면 우리는 이미 이것이 n이 2인 볼록성의 정의에 의해 옳다는 것을 알고 있기 때문입니다.
기본 케이스는 분명합니다. 사실, 더 간단한 기본 케이스가 있습니다,
그것은 n이 1인 케이스입니다.
n이 1이면, 여러분은 합이 1인 하나의 수를 가집니다.
α_1은 1입니다.
아무 것도 여기 없습니다.
이것은 1 곱하기 x_1의 f가 많아 봐야 1 곱하기 x_1의 f라는 것을 말합니다.
매우 흥미롭지는 않습니다
왜냐하면 그것은 질을 가지기 때문입니다.
그래서 우리는 n이 2인 기본 케이스가 필요하지 않습니다.
흥미로운 부분은, 매우 흥미롭지 않더라도,
도입 단계입니다.
이것은 도입에서 좋은 연습입니다.
우리가 신경 쓰는 부분은 이
선형 결합의 f입니다.
이제 제가 하고 싶은 것은 도입을 적용하는 겁니다.
제가 아는 것은 이 합의 f입니다.
모두 n까지 다 하는 대신
n-1까지 더했다면요.
제가 도입에 의해 다룰 수 있는 더 작은 수 입니다.
저는 n 번째 항을 제거하려고 합니다.
저는 그것을 분리하고 싶습니다. 그리고, 이것은 여러분이 전에
선형 결합을 해 보았으면 매우 자연스러운 것입니다.
그러나 그것은 약간의 대수입니다.
저는 α_n*x_n 항을 분리하고 싶습니다. 저는 또한 그것을 선형 결합으로 하고 싶습니다.
이것은 트릭입니다.
미안해요 여기 f가 없습니다. 제가 마지막 항을 제거하면,
1에서 n-1까지 α_k는 어떤 것도 더하지 않습니다.
그것들은 더 작은 것입니다.
그래서, 저는 이 항을 취하지 않을 것입니다.
저는 여기서 어떤 트릭을 해야 합니다.
좋아요. 여러분은 이것이 왜 옳은지 보아야 합니다
왜냐하면 1 마이너스 α_n은 소거되었기 때문입니다.
그리고 저는 α_k*x_k의 합을 얻습니다,
k는 1에서 n-1까지와 같습니다.
저는 여기서 아무 것도 하지 않았습니다.
이것은 같습니다. 그러나 지금, 저는 깔끔한 것을 가집니다,
그것은 한 편으로, 이 두 수입니다.
그리고 다른 한 편으로, 저는 그것을 옳게 했는데
이 수들은 1에서 n-1까지 더하는 것입니다.
그것들은 1까지 왜 더합니까?
자 이 수들은 1 마이너스 α_n까지 더했습니다.
그리고 저는 1 마이너스 α_n으로 모든 것을 나눌 겁니다.
그것들은 1로 더해집니다. 그래서 지금 저는 두 선형 결합을 가집니다.
저는 두 가지를 적용합니다.
저는 선형 결합이 동작한다는 것을 알고 있습니다
왜죠?
왜 제가 이것이 α_n*f(x_n)+ (1-α_n)*f(...)
의 합이라는 것을 말할 수 있나요?
크게 말해보세요. 두 가능한 답변이 있습니다.
하나는 정확하고 하나는 부정확합니다.
그것은 무엇이 되어야 하나요? 이것은 작거나 같아야 합니다.
그것은 중요합니다.
그것은 칠판에 있습니다. 그것은 너무 어려울 수 없습니다.
저는 그것을 큰 X값으로 다룰 겁니다.
저는 x_n을 가지고 있고 골치아픈 X를 가지고 있습니다.
저는 이 두 X 값의 선형 결합의 f를 원합니다, 그것은 많아 봐야,
이 X 값들의 f의 선형 결합입니다.
이것은 무엇입니까?
그것은 n이 2인 도입 가설입니다.
불행히도, 우리는 n이 2인 특별한 기본 케이스를 증명하지 않습니다.
우리는 여기서 제가 기본 케이스를 했던 대로
도입을 사용할 수 없습니다.
여러분이 n이 2인 기본 케이스를 했으면, 여러분은 그것을 할 수 있습니다.
여기서 우리는 할 수 없습니다. 다른 답은
볼록성에 의한 겁니다, 좋아요.
그것은 여기서 옳습니다. f는 볼록합니다. 우리는 이것이 어떤 X 값들에 대해 옳다는 것을 압니다,
그리고 이 두 합을 제공합니다.
우리는 이것이 옳다는 것을 압니다.
이제 우리가 도입을 적용할 때입니다.
그래서 이제 우리는 이 오른쪽 항을 조작할 겁니다.
우리가 n이 2 보다 더 크다는 것을 필수적으로 알기 전에, 보세요.
그러나, 우리는 n이 n-1 보다 크다는 것을 압니다.
저는 확신할 수 있습니다.
그래서 이것은 1 마이너스 α_n 곱하기 합입니다.
k는 1에서 α_k의 n-1 나누기 1 마이너스 α_n 곱하기 f of x_k 입니다,
제가 그것을 옳게 가진다면요.
이것은 도입, 도입 가설에 의한 것입니다,
왜냐하면 이 α_k 나누기 1 마이너스 α_n 합이기 때문입니다.
이제 이 1 마이너스 n은 취소되었습니다.
그리고 우리는 우리가 원하는 것을 얻습니다. 이것은 k가 1에서 n까지일때, α_k*f(x_k)와 같습니다.
그래서 우리는 합의 f를 얻습니다.
그것은 부명제를 증명합니다.
약간 지루하지만, 각 스텝은 매우 직관적입니다.
동의합니까?
이제, Jensen's inequality을 증명하는 것은 상대적으로 직관적입니다.
그것은 마법입니다.
우리는 기대값 분석을 합니다.
그래서, 우리는 우리의 좋은 친구들을 사용합니다. 그것은 지시자 랜덤 변수들입니다.
그러나 지금은, 우리는 이 문장을 증명하고 싶습니다.
우리가 볼록 함수를 가지면,
기대값의 f는, 많아 봐야, 그 랜덤 변수의 f의 기대값입니다.
이것은 랜덤 변수입니다, 그렇죠?
여러분이 이 랜덤 변수로부터 샘플을 원한다면,
여러분은 X로부터 얻을 수 있습니다, 그리고 여러분은 그것에 f를 적용합니다.
그것은 이 개념 f of X 의 의미입니다.
왜냐하면 X는 랜덤 변수이기 때문입니다.
우리는 f가 볼록하다는 것을 이용할 겁니다. 그것은 이것이 어렵지 않다고 드러났습니다.
여러분이 기대값의 정의를 기억하면,
저는 여기서 하나의 가정을 더 할 것입니다, 그것은 x가 필수적인 것이라는 겁니다.
그것은 정수의 랜덤 변수입니다,
그것은 정수 값을 의미합니다.
그것은 우리가 신경 쓰는 모든 것입니다 왜냐하면 우리는 러닝 타임을 보기 때문입니다.
이 문장은 연속적인 랜덤 변수들에게만 옳습니다,
그러나 저는 별개의 케이스를 하고 싶습니다
왜냐하면 저는 X의 U가 무엇인지 쓰기 때문입니다.
X의 E의 정의가 무엇입니까?
X는 정수 값만 취합니다. 이것은 쉽지만
여러분은 그것을 기억해야 합니다. 그것은 좋은 드릴입니다.
저는 x에 대하여 정말 모릅니다. 그것이 정수 값을 가진다는 것을 제외하고요.
제가 X의 기대값을 확장해야 한다는 것에 대한 어떤 제안 있나요?
얼마나 많은 사람들이 이것을 알고 있나요?
네, 그럼 많이 쉽지 않군요.
기대값은 확률과 연관이 있습니다, 그렇죠?
저는 X가 어떤 값 x와 같은 가능성과
같은 것을 보아야 합니다.
그것은 하기 좋은 것처럼 보입니다.
여기 무엇이 있습니까?
네, 합입니다.
여기 무엇이 있습니까? 네, 합입니다. X는 마이너스 무한대 그리고 무한대 사이 어딘가에 있을 수 있습니다.
그것은 확실히 옳습니다. 우리는 더 가지고 있습니다.
여기서 잃어 버린 것이 있습니다. 이 합이 무엇입니까?
어떤 랜덤 변수 X를 위해 정수 값을 취하는 것은
무엇입니까?
1 입니다, 좋아요. 저는 여기서 어떤 것에 더할 필요가 있습니다,
즉 X입니다. 그것은 기대값의 정의입니다.
이제, 어떤 것의 합의 f가 있는데,
그것은 우리가 증명했던 부명제와 같아 보입니다.
우리는 그것을 유한 케이스에서 증명했습니다.
그것은 드러났습니다.
그것은 여러분이 모든 정수를 가지면 유지됩니다.
저는 그것을 가정할 것입니다.
저는 이 가능성, α값을 가지고 있습니다.
그러므로, 저는 이 부등식을 사용할 수 있습니다,
이것을 가져보겠습니다. 저는 α를 가지고 합을 가집니다.
x는 마이너스 무한대와 같습니다,
그것은 확률입니다,
대문자 X는 값의 f 곱하기 작은 x와 같습니다.
저기 있습니다.
저는 부명제를 사용했습니다. 아마 이제 저는 부명제를 지울 겁니다.
저는 유한 케이스를 증명하는 동안 부명제의 셀 수 있는
버전을 사용함으로써 속였습니다.
그것은 제가 강의에서 할 수 있는 모든 것입니다.
이것은 부명제에 의한 겁니다.
이제, 제가 증명하고 싶은 것과 공백으로 남겨두고 싶은 것은 이것이
X의 f의 E라는 겁니다,
이 합은 X의 f의 E 입니다. 사실, 그것은 X의 f의 E와 같습니다.
그리고 그것은 정말 같아 보입니다, 그렇죠?
여러분은 어떤 확률 곱하기 fX의 합을 가집니다.
그것은 거의 E of f of X의 정의와 같아 보입니다,
그러나 그렇지 않습니다.
여러분은 약간 신중해져야 합니다 왜냐하면
E of f of X는 f of X가 특정 값과 같은 확률에 대해 이야기 하기 때문입니다.
우리는 이것을 다음처럼 연관 지을 수 있습니다.
그것은 너무 어렵지 않습니다.
여러분은 각 값을 볼 수 있고,
모든 값 k를 볼 수 있습니다.
모든 k는 fX가 x인 곳입니다.
좋아요, 이것은 fX가 x라고 쓰는
또 다른 방법입니다.
좋아요, 다시 말해, 저는 특정한 방법으로 항을
그룹 지을 수 있습니다.
fX는 다양한 값을 가집니다. 바꾸기 현명합니다.
저는 k의 알려지지 않은 것을 사용하곤 했습니다, 그래서 이것을 더 잘 부를 수 있습니다.
이것을 Y라고 부릅시다,
미안해요, 여기서 개념을 바꿔 봅시다. 그것은 말이 됩니다.
저는 X가 x인 가능성을 보아야 합니다.
제가 정말 신경 쓰는 것은 fX 값이 무엇을 가지는지 입니다.
그것을 Y라고 합시다. 모든 값들을 보세요.
그것은 f의 범위입니다.
그리고 나서, 저는 fX가 Y와 같은 x의 다른 값들을 볼 것입니다.
제가 이 확률들을 더하면,
그것들이 다른 값이기 때문입니다.
그것들은 일종의 의존적인 사건입니다.
이 합은 fX가 Y인 확률입니다.
이것은 대문자 X입니다.
이것은 소문자 y입니다.
제가 그것에 y를 곱하면, 저는 X의 f의 기대값을 얻을 수 있습니다.
이것에 대해 생각해 보세요,
이것은 여기서 약간 이상할 수 있습니다
왜냐하면 이 합은 잠재적으로 무한대이기 때문입니다.
그러나 그것은 옳습니다. 이것은 Jensen's inequality을 증명합니다.
매우 어렵지 않습니다.
우리가 이 강력한 볼록성 부명제를 한 번 가지면요.
그래서 우리는 볼록성을 사용했습니다.
우리는 X의 E의 정의를 사용했습니다.
우리는 볼록성을 사용했습니다. 그것은 우리가 f를 안으로 넣게 합니다.
그리고 우리는 이 항들을 재 그룹화하고,
그것이 E of f of X 라는 것을 알아 냅니다.
여기서 부등식은 볼록성으로부터 옵니다.
이제 알고리즘으로 갑니다.
이것은 기본적인 확률입니다, 그것은 연습하기 좋은 것입니다.
우리는 퀴즈에서 볼 것입니다,
그것은 놀라운 것이 아닙니다. 이것은 저를 위한 케이스입니다.
여러분은 알고리즘으로 많은 직관을 가지고 있습니다.
그것이 알고리즘적일 때 마다,
그것은 이치에 맞습니다 왜냐하면 여러분은 여러분이 아는 것의 기반이 되기 때문입니다
왜냐하면 여러분은 컴퓨터 과학자입니다.
그러나 기본적인 확률을 가지고,
여러분이 수학자가 아니면,
그것은 덜 직관적입니다, 그러므로 빨리 하기 더 어렵습니다.
퀴즈에서, 스피드는 매우 중요합니다.
기말고사에서 스피드는 또한 매우 중요합니다.
집에서 하는 것은 더 흥미롭습니다
왜냐하면 그것은 현명해지길 요구하기 때문입니다.
여러분은 사실 창의적이어야 합니다.
그것은 사실 알고리즘적인 설계입니다.
지금까지, 우리는 주로 테스트된 설계에 대해 보았습니다.
여러분은 확률을 할 수 있나요?
여러분은 여러분의 랜덤 퀵정렬의
러닝 타임이 무엇인지 기억하나요?
퀴즈 2는 사실 창의성을 테스트 입니다.
왜냐하면 여러분은 더 많은 시간을 가지기 때문입니다.
두 시간 안에 창의적이기 어렵습니다.
그래서 우리는 랜덤하게 구축된 이진 검색 트리의 예상 높이를 분석하길 원합니다.
우리는 이것을 전에 정의했습니다,
그러나 그것을 다시 해보겠습니다 왜냐하면 그것은 거의 강의 시작 부분이었으니까요.
저는 랜덤하게 구축된 이진 검색 트리의 높이의
랜덤 변수를 취할 겁니다.
그것은 랜덤화되었습니다.
랜덤 순열을 취합시다,
그것들을 트리의 왼쪽에서 오른쪽으로 하나씩 삽입하세요.
여러분이 얻는 트리의 높이는 무엇입니까?
어떤 노드의 최대 깊이는 무엇입니까?
저는 X_n을 많이 보지 않을 겁니다.
저는 X_n의 지수를 볼 것입니다.
여전히 우리는 직관이 없습니다.
그러나, X의 2는 볼록 함수입니다.
그것은 이와 같습니다. 그것은 매우 날카롭습니다.
그것은 제가 할 수 있는 최선입니다.
여러분은 제가 히스토그램을 그리는 방법을 보았습니다.
우리는 이 랜덤 변수를 쓰고 싶습니다.
어떤 대수에서요.
여기서 주요한 것은 케이스들을 나누는 겁니다.
그것은 우리가 보통 가는 방법입니다
왜냐하면 많은 다른 시나리오들이 있기 때문입니다.
그래서, 우리는 어떻게 시작으로부터 트리를 구축하나요?
우리가 하는 첫 번째 것은 첫 노드를 취하는 겁니다.
우리는 그것을 던지고, 루트로 만듭니다.
첫 번째 값이 배열에서 무엇이든,
우리는 그것을 루트에 넣습니다.
그것은 루트에 있습니다.
우리는 그것으로부터 루트를 바꾸지 않습니다.
이제, 모든 남은 인자들 중 몇은 이 값 보다 작습니다,
그리고 그것은 여기로 갑니다.
이것을 루트에서 r이라고 합시다.
그것들 중 몇은 r 보다 큽니다.
그것들은 여기로 갑니다. 아마 여기로 더 갈겁니다.
아마 여기로 더 갈 겁니다.
사실 임의 분할,
단일 랜덤 분할은 같습니다
왜냐하면
이것은 단일하게 선택되었습니다.
루트는 단일하게 선택되었습니다. 그것은 랜덤 순열에서 첫 번째 인자입니다.
그래서, 제가 하려고 하는 것은 그것에 의해 파라미터로 나타내는 겁니다.
얼마나 많은 인자가 여기 있고,
얼마나 많은 인자가 여기 있습니까?
이것이 랜덤하게 구축된 이진 검색 트리이기 때문입니다.
제가 r을 고르면, 그것은 누가 왼쪽으로 가고
누가 오른쪽으로 가는지 결정됩니다.
그리고, 저는 분할할 수 있습니다.
그것은 러닝 퀵정렬 같은 겁니다.
저는 r의 왼쪽, 오른쪽 인자를 분할합니다.
저는 재귀적으로 랜덤하게 이진 검색 트리를 구축합니다.
왜냐하면 서브 순열이 단일하기 때문입니다.
이것들은 필수적으로 재귀적인 문제입니다.
우리는 재귀 문제를 분석하는 방법을 압니다.
우리가 알아야 하는 모든 것은
여기 k 마이너스 1 인자들이 있다는 것이고, 여기 n 마이너스 k 인자들이 있다는 겁니다.
그것은 갖은 순서에서 r이 순위 k를
가진다는 것을 의미합니다.
제가 어디로 가야 합니까?
루트 r이 순위 k를 가지면,
이것은 이 사건의 건에 대한 문장입니다,
그것은 랜덤 사건이고,
우리가 가지는 것은 X_n 입니다 그것은 1 더하기 X_(k-1), X_(n-k)의 최대와 같습니다
왜냐하면 이 트리의 높이는 두 서브 트리의 높이의
최대 더하기 1이기 때문입니다.
그것은 자연스러운 겁니다.
우리가 분석하려고 하는 것은 Y_n 입니다.
우리는 이 제곱을 취해야 합니다.
그것은 2 곱하기
X_(k-1)의 2의 최대입니다.
그것은 Y_(k-1) 입니다.
이제 여러분은 왜 우리가 X 대신에
Y에 관심 있는지 보기 시작합니다. 그것은 우리가 하는 것입니다.
재귀를 풀 때,
우리는 기대값을 가지지 않습니다.
그러나 우리가 퀵정렬의 예상 러닝 타임을 계산할 때,
우리는 곱셈을 합니다,
우리는 재귀 서브 문제들을 가집니다,
그것은 같이 더하는 겁니다.
여기서 우리는 2의 인자를 갖습니다.
우리는 최대값을 갖습니다. 그러나 직관적으로,
우리는 정수와 랜덤 변수를 곱하는 방법을 압니다
왜냐하면 사이즈가 이 둘의 최대인 두 재귀
하위 문제들이 있기 때문입니다,
우리는 여기서 모릅니다.
그러나 우리는
잘 다루는 방법을 모릅니다.
정말로, 우리의 기술은 재귀를 푸는데 좋습니다,
정수 인자들을 제외하고요.
이것은 정말 정수 인자에
영향을 미치지 않습니다,
그러나 그것은 큰 문제입니다.
지수에서, 그것은 2의 인자입니다.
여기서 이것이 무엇을 하는지 보기 정말 어렵습니다.
우리의 분석은
그것을 하는 것이 좋은 생각이라는 겁니다
여러분이 제가 X_n으로 하려고 하는 것을 보면, 그것은 바운드 되지 않을 겁니다.
여러분은 어떤 것을 증명할 수 없습니다.
2의 인자로,
우리는 좋은 모양에 있습니다. 우리는 그것을 다루는 방법을 압니다.
우리가 X_n 대신 Y_n을
왜 사용하는지에 대한 증명을 할 때 더 말할 겁니다.
그러나 지금은, 우리는 Y_n을 사용합니다.
이것은 일종의 재귀입니다, 그것은 이 사건에서 조건이 있습니다.
제가 이것을 어떻게 항상 문장으로
바꿀 수 있나요?
네? 사건의 가능성으로 나누나요?
이 사건은 독립적입니다.
그것들을 모두 같습니다, 저는 말해야 합니다.
그것들은 독립적이지 않습니다. 사실, 하나는 모든 다른 것들을 결정합니다.
그래서, 제가 일반적으로 사건을 대수로 어떻게 나타냅니까?
지시자 랜덤 변수입니다, 좋아요.
여러분의 친구 지시자 랜덤 변수를 기억하세요.
이 모든 분석은 지시자 랜덤 변수를 사용합니다.
그것들은 이 사건을 나타냅니다,
우리는 그것을 Z_nk 라고 부릅니다.
루트가 순위 k를 가지면 그것은 1이 될 겁니다.
특히,
이것들을 모두 같습니다.
이것이 1과 같을 가능성은
또한 그 지시자
랜덤 변수의 기대값입니다,
그리고 여러분은 알아야 합니다,
그것은 1 또는 0의 값만 가집니다.
0은 기대값에서 중요하지 않습니다.
이것은 희망적으로 1 나누기 n이 될 것입니다
제가 맞다면요.
루트의 순위가 무엇인지에 대해 n개의 가능성이 있습니다.
각각은 같습니다
왜냐하면 단일 순열을 가지기 때문입니다.
이제 저는 이 조건문을 쓸 수 있습니다.
Z_nk는 제가 선택하도록 합니다. Y_n은 k가 1에서 n까지 일때,
Z_nk*(2*max{..., 미안해요,
Z_nk*(2*max{Y_(k-1),Y_(n-k)})의 합과 같습니다.
이제 우리는 좋은 친구 재귀를 가지고 있습니다.
우리는 그것을 풀 필요가 있습니다.
우리는 정말 그것을 풀 수 없습니다 왜냐하면 이것은 랜덤 변수이기 때문입니다
그리고 그것은 재귀 랜덤 변수에 대해 이야기하는 겁니다.
우리는 먼저 양 쪽의 기대값을 취합니다.
그것은 우리가 정말 바운드 하는 유일한 겁니다.
E[Y_n]은 n^2일 수 있습니다, 운이 나쁜 케이스에서요.
그것은 n^2일 수 있습니다.
여러분이 운이 나쁘다면 그것은 n의 2일 수 있습니다
왜냐하면 X_n은 트리의 높이 n만큼 클 수 있기 때문입니다.
Y_n은 그것의 2입니다. 그것은 n의 2일 수 있습니다.
우리가 증명하고 싶은 것은 그것이 n에서 다항적이라는 겁니다.
그것은 어떤 정수에 n입니다, 그리고 우리는 로그를 취합니다,
그것은 오더 로그 n일 겁니다. 그래서 우리는 기대값을 취합니다,
그리고 희망적으로 그것은 이 것을 보장합니다.
그래서 우리는 이 랜덤 변수의 합의 기대값
곱하기 재귀 랜덤 변수들을 가집니다.
저는 괄호를 잊었군요.
이 분석에서 우리가 하는 첫 번째 것은 무엇입니까?
이것은 기대값의 선형성이어야 합니다.
그것은 기억하기 쉽습니다. 우리는 합을 가집니다.
안에 E를 넣읍시다.
이제 우리는 우리 곱의 기대값을 가집니다.
우리가 사용해야 하는 것은 무엇입니까? 독립성입니다.
희망적으로, 그것은 독립적입니다.
그리고 우리는 이것을 쓸 수 있습니다.
그것은 곱의 기대값일 수 있습니다. 둘을 밖으로 합시다,
왜냐하면 그것이 아니기 때문입니다.
는 X와 같이 보이나요?
저는 그것들을 읽을 수 없습니다. 그것에 대해 미안합니다.
이것은 모든 Y의 것입니다. 좋아요, 매우 현명해요,
랜덤 변수입니다.
이것들은 왜 독립적인가요? 여기서 우리는 루트가 무엇인지의 선택,
루트 순위가 문제에서 무엇을 가지는지를 보고 있습니다.
여기서, 우리는 루트가 무엇인지 볼 것입니다.
루트 오른쪽 그리고 왼쪽에서와
같은 검색 트리의
양한 선택들이 있습니다.
모든 것이 여기서 단일이기 때문에 그것들은 독립적인 선택입니다.
이것의 선택은 단일이었습니다.
그것은 누가 왼쪽 그리고 오른쪽에서
분할하는지 결정합니다.
그것들은 완전히
독립적인 재귀 선택인가요?
왼쪽 또는 오른쪽서브 트리에서 누가 루트인가요?
이것은 보통 보다 더 까다롭습니다.
전에, 그것은 알고리즘에서 랜덤 선택이었습니다.
이제 그것은 우리가 시간에 앞서서
랜덤 수들을 선택하는 상황입니다.
그것은 약간 재미있지만 이것은 여전히 독립적입니다.
우리는 우리가 퀵 정렬 등에서 했던 것과 같은 것과 같이 이것을 얻습니다.
좋아요. 이제 우리는 계속합니다.
이제 그것은 엉성한 것입니다.
이것들 중 하나는 우리가 아는 겁니다.
우리는 여기서 E of Z_nk을 썼습니다.
그것은 1/n입니다.
좋아요. 우리는 밖에서 2 나누기 n을 얻습니다,
그리고 우리는 이 2 가지의 최대의 기대값의 합을 얻습니다.
보통, 우리는 쓰고,
저는 때때로 여러분이 최대값의 T 또는 여기 두 가지의
최대의 Y를 쓴다고 생각합니다.
여러분은 그것을 이 두 변수의 최대값으로 써야 합니다.
그것은 많은 트릭이 아닙니다,
최대 값은 많아 봐야 합입니다.
우리는 음이 아닌 것을 가지고 있습니다.
우리는 2 나누기 n...을 가지고 있습니다.
네,
어떤 면에서 이것은 우리가 우리가 무엇을 잃어 버리는 곳에서 중요한 단계입니다.
지금까지 우리는 정확했지만
이제 우리는 매우 엉성합니다.
우리가 2의 합의 합을 가지기 때문에,
저는 그것을 합으로 할 수 있습니다.
네?
여러분은 기대값의 선형성을 사용할 수 있습니다, 좋아요.
그것은 제가 해야 하는 첫 번째 것입니다.
기대값의 선형성은 제가 그것을 분리하도록 합니다.
이제 저는 2n의 합을 가집니다.
저는 그것을 이것들의 합으로 깰 수 있습니다.
여러분은 이 두 합에 대해 알고 있나요?
우리는 이 두 합에 대해 알고 있나요?
그것들은 같습니다. 사실, 여기 모든 항은 정확히 두 번 나타납니다.
하나는 n 마이너스 k입니다.
그것이 홀수이면 짝수는 동작합니다.
사실,
우리는 합들 중 하나를 취할 수 있고 그것에 2를 곱할 수 있습니다.
이것은 4 나누기 n 곱하기 합입니다,
그리고 그 합은 k가 0에서 n-1인 동안에 E[Y_k]까지 약간 더 쓸 수 있습니다.
Y_k이 0에서 n-1까지 나타나는 수는 정확히 2입니다.
이제 저는 재귀를 가집니다.
저는 E[Y_n]을 가집니다.
우리의 기억을 위해 그것을 써 봅시다.
그것은 무엇이죠? 좋아요.
이제 저는 재귀를 풀어야 합니다.
제가 어떻게 못생긴 이와 같은 재귀를 풀 수 있나요?
대입입니다!!!
마스터 메소드가 아닙니다. 그것은 매우 깔끔한 재귀입니다.
저는 알 수 있고 이미
여러분에게 그것이 n^3이라고 말해 주었습니다.
저는 n^3이 이 증명이 얻을 수 있는 곳에서
매우 정확하다고 생각합니다.
대입 메소드는 귀납법에 의한 증명입니다.
그리고 귀납법에 의한 모든 증명은
두 가지가 있습니다.
그것은 base 단계를 가져야 합니다,
그리고 여기서 기본 케이스는 n이 θ(1)입니다.
저는 그것을 쓰지 않았습니다, 물론,
여러분이 정수 크기의 트리를 가지면, 그것은 상수 높이를 가집니다.
그래서 이것은 여러분이 맞는 한 맞습니다 c가 충분히 크다면요.
좋아요, 그래서, 그것을 잊지 마세요.
많은 사람들은 퀴즈에서 그것을 잊어 버리거든요.
우리는 심지어 기본 케이스를 언급했었습니다.
보통, 우리는 기본 케이스를 언급하지 않습니다.
여러분은 저기 하나가 있다고 가정해야 합니다.
여러분인 어떤 증명에서 대입에 의해 이것을 말해야 합니다.
이제, induction step 단계를 합시다.
E[Y_n]이 많아 봐야 C of n^3 입니다,
그리고 그것이 더 작은 n을 위해 맞다고 가정합니다.
여러분은 여기서 (귀납법에서의) 가설을 써야 합니다,
그러나 저는 그것을 건너 뛸 것입니다 왜냐하면 시간이 없거든요.
이제 우리는 이 재귀를 할 것입니다.
E[Y_n]는 4 나누기 n
더하기 k 입니다.
이제, k가 항상 n 보다 작다는 것에 주목하세요.
우리는 도입을 적용할 수 있습니다.
이것은 4 나누기 n 입니다.
그것은 도입 가설입니다.
좋아요, 이제 저는 이 합에서 상계가 필요합니다.
여러분이 좋은 기억을 가지고 있다면, 여러분은 이 합을 위한 닫힌 형태를 압니다.
그러나, 저는 제가 사용했던 대로 좋은 메모리를 가지고 있지 않습니다.
저는 어렸을 때 이 합을 절대 외우지 않았습니다,
그래서 저 12살 이하일 때 아무 것도 외우지 않았습니다.
저는 여전히 pi 같은 모든 수를 기억합니다.
그러나, 제가 이제 기억하려고 하는 것은
같은 방법이지 않습니다.
그래서 저는 이 합을 알지 않습니다.
이 합의 근사치를 계산하는 좋은 방법은 무엇입니까?
적분입니다, 좋아요. 사실,
저는 c를 밖으로 꺼낼 것입니다.
그래서 이것은 4c 나누기 n입니다. 합은 적분입니다.
여러분이 범위를 가지면,
여러분은 더 크게 해야 합니다. N-1 대신에, 여러분은 n까지 해야합니다.
이것은 책에 있습니다.
그것은 직관적인 것입니다, 여러분이 단조 함수를 가지는 한이요.
그것이 핵심입니다.
여러분은 이과 같은 것을 가지고 있습니다.
그리고 합은 이것들 각각을 취해서
무게를 다는 것입니다.
적분은 이 곡선 아래를 계산하는 것입니다.
특히,
여러분이 이 적분의 근사치를 보면,
이것은 확실히 합입니다.
그것이 그림에 있는 증명입니다.
그러나 여러분은 이것을 책에서 볼 수 있습니다.
여러분은 042 수업에서 그것을 알아야 합니다.
이제 희망적으로, 여러분은 적분을 풀 수 있습니다.
x^3의 적분은 x^4 나누기 4 입니다.
저는 맞았습니다. 그리고 우리는 그것을 n에서 계산할 수 있습니다.
그것은 0입니다.
0을 빼는 것은 중요하지 않습니다 왜냐하면 0의 4제곱은 0이기 때문입니다.
그것은 단지 n^4 나누기 4입니다.
이것은 4c 나누기 n 곱하기 n^4 나누기 4 입니다.
편리하게, 이 4는 이 4를 취소합니다.
4는 이것 때문에 3으로 됩니다,
그리고 우리는 n^3을 얻습니다.
우리는 cn^3을 얻습니다. 편리하지요,
왜냐하면 그것이 우리가 증명하려고 하는 것입니다.
이 증명은 나머지 항이 없습니다.
우리는 모든 곳에서 엉성합니다,
그리고 우리는 정말 운이 좋습니다.
우리는 옳은 곳에서 엉성했습니다.
그래서 이것은 매우 까다로운 증명입니다.
여러분이 그것을 손으로 하려고 하면, 그것은 매우 쉽습니다,
그리고 꽤 옳은 답을 얻지 않습니다.
그러나 이것은 거의 작동하지 않습니다.
남아 있는 1분 동안 몇 가지를 말해주겠습니다.
그래서 우리는 결론을 말할 수 있습니다.
저는 시간이 없기 때문에 쓰지 않겠습니다, 그러나 여기 있습니다.
저는 Y_n에서 증명했습니다, 그것은 X_n 2제곱 이었습니다.
우리가 신경 쓴 것은 X_n 입니다.
우리는 Jensen's inequality를 사용했습니다.
우리는 E[2^(X_n)]을 얻습니다.
이것은 우리가 알고 있는 것입니다.
왜냐하면 그것은 Y_n이기 때문입니다. 우리는 E[Y_n]이 이제 O(n^3) 이라는 것을 압니다.
우리는 기본 케이스에 대하여 이것을
충분히 크게 설정했습니다.
우리는 여기 정수가 무엇인지 알아내지 못했습니다.
그것은 중요하지 않습니다
왜냐하면 이제 우리는 양쪽의 로그를 취하기 때문입니다.
우리는 로그를 취합니다.
그것은 추가적인 것입니다. 이 정수는 지수입니다.
그것은 로그를 취합니다. 그리고 곱합니다.
3 log n 더하기 오더 1입니다.
이것은 랜덤하게 구축된 이진 검색 트리의 높이에서
매우 타이트한 것입니다.
사실 X_n의 예상 높이는,
대략적으로,
저는 여기서 정확한 것을 원하지 않습니다, 2.9882 곱하기 log n 입니다.
이것은 제 친구 Luke Devroy에 의한 결과 입니다,
1986년에요.
그는 몬트리올의 McGill 대학의 교수입니다.
우리는 매우 가까운 3을 가집니다.
우리는 이것을 여기서 증명하지 않을 겁니다. 여기서 어려운 부분은 사실 하계입니다,
그러나 그것은 그리 많지 않습니다.
우리가 X_n 대신에 왜 Y_n을 사용하는지에 대해 좀 더 말해야 합니다.
그것은 경사에 대한 모든 것입니다.
특히,
우리가 랜덤 변수의 최대에 대해 말했을 때
이 단계는 합입니다.
그것이 Y일 때 더 맞습니다.
좋아요, 이것은 약간 이상합니다
왜냐하면 우리가 여기서 분석하는 것이 모든 k 값에 가능하기 때문입니다.
이것은 어떤 면에서, k가 무엇인지는 중요하지 않습니다.
우리는 모든 케이스를 동시적으로
바운드합니다.
그래서 여기서 우리는 k 마이너스 1 대 n 마이너스 k를 봅니다.
사실 여기서 그것은 다항식 버전입니다.
여러분이 두 값 a b를 가지면,
ab의 최대값은 많아 봐야 a 더하기 b 입니다.
다른 한편으로
a 제곱 더하기 b 제곱입니다.
이것이 더 낫게 느껴지지 않나요?
물론 그것들은 같습니다
여러분이 a 마이너스 b를 보면 이것은
이것 보다 더 타이트한 바운드가 됩니다
왜냐하면 여기서 우리는 a 마이너스 b의 절대 차이를 보기 때문입니다.
그것은 이것이 좋은 이유이고 이것이 나쁜 이유입니다.
우리는 a와 b가 거의 같기 때문에 정말 나쁩니다.
그러나 우리는 k-1 그리고 n-k의 분할을
위해 이것을 풀려고 노력합니다.
우리가 그것이 모두 분할하는 중간에서 나쁜 케이스를 약간 가지고 있다면 괜찮습니다.
그러나 우리가 기울자 마자 이것은 이것과 매우 가까워집니다,
반면에 이것은 여전히 이것과 멉니다.
여러분은 많은 것을 잃기 전에
가장자리와 가까워져야 합니다,
반면에 여러분은 빠르게 많은 것을 잃지 않습니다.
그것이 직관입니다. 시도해 보세요,
그리고 X_n으로 무엇이 일어나는지 보세요, 그것은 작동하지 않습니다. 수요일에 봅시다.