Tip:
Highlight text to annotate it
X
좋은 아침입니다. 오늘 우리는 지난주에 말한 대로,
분석 보다는 설계를 조금 더 해야 합니다.
우리는 사실 분석을 할 것입니다,
그러나 그것은 흥미로운 설계 이슈로 이르는 분석의 타입입니다.
오늘 정말 흥미롭고
실용적인 문제를 배우는 방법의 응용을 가지고
수요일에 이어서 할 것입니다.
그래서 오늘 우리는 분할 상환 분석에 대해 이야기할 것입니다.
그리고 질문을 던지면서 이 주제에 대한 동기부여를 하고 싶습니다,
해시 테이블은 얼마나 커야 합니까?
해시 테이블은 얼마나 커야 합니까?
제안 있나요?
여러분은 해시 테이블을 만들어야 하고, 그것은 얼마나 커야 합니까?
그것을 간단한 해시 테이블이라고 합시다, 그것은 연쇄를 통해 충돌을 해결합니다.
그것은 얼마나 커야 합니까?
필요한 것 보다 두 배라구요? 그것은 얼마나 큽니까?
예를 들어, 인자의 두 배입니다.
제가 해시 테이블의 사이즈를 증가시킨 대로,
검색 시간은 어떻게 됩니까?
제가 해시 테이블의 사이즈를 증가시키면 검색 시간은 어떻게 됩니까?
네, 그러나 일반적으로는 어떻습니까?
그것은 감소합니다,
그렇죠? 그것을 더 크게 만들수록,
사실, 제가 그것을 충분히 크게 만들면,
저는 필수적으로 직접 접근 테이블을 얻습니다,
그리고 모든 것은 최악의 케이스, θ(1) 시간입니다.
어떤 면에서, 우리는 곧 여러분의 답으로 돌아갈 것입니다
우리는 그것을 가능한 크게 만들어야 합니다.
그래서 검색은 비용이 쌉니다.
그것의 이면은 무엇입니까?
그것은 많은 공간이 들어서 저는 공간을 낭비 하지 않기 위해 그것을 가능한 작게 만들고 싶습니다.
저는 큰 것을 원합니다,
우리가 분석에서 말했듯이,
중간은 그것을 n개의 인자를 위한 θ(n)으로 만듭니다.
그것을 θ(n)보다 크게 만들면,
여러분이 여분의 공간에 대해 지불한 비용은 검색시간 면에서 가치가 없다는 겁니다.
적어도 여러분은 그것을 그 방법으로 읽을 수 있습니다.
그러나,
이 질문이 있습니다.
제가 해시 테이블로 시작하면, 그것을 어떻게 만듭니까,
저는 그것으로 얼마나 많은 인자가 해시되는지 모릅니다.
저는 얼마나 크게 만들어야 하나요? 미리 우리가 모르면요? 우리가 n을 모르면요?
이 문제의 답은 꽤 괜찮습니다.
그것은 동적 테이블이라는 전략인데요.
아이디어는 이렇습니다.
테이블이 그것에 많은 인자를 넣을 때 마다,
그것은 꽉 차고,
우리는 테이블이 넘친다(overflows)고 말합니다.
우리는 그것을 키워서 더 큰 테이블을 만들 수 있습니다.
해시를 위하여, 그것이 넘친다고 말할 수 있는 점이 없더라도,
그것은 연쇄가 있다면
적어도 기능적입니다.
그런데 여러분이
그것을 개방 연쇄법으로 한다면 그럴 수 있습니다.
그러나 연쇄를 말해 봅시다,
그것이 너무 커질 때, 테이블의 수만큼 많은 인자가 있으면,
우리가 하는 것은 테이블을 키우는 것입니다.
우리가 C 같은 언어에서 할당할 때
하는 방법은 Malloc 입니다,
자바에서는 New 입니다.
우리는 더 큰 테이블을 만듭니다.
우리는 아이템들을 오래된 테이블에서 새로운 것으로 움직입니다. 우리는 오래된 테이블을 free 시킵니다.
예를 해 봅시다.
여기서 저는 사이즈가 1인 테이블을 가지고 있고, 그것은 처음에
비어있습니다. 저는 삽입을 합니다.
제가 하는 것은 테이블에 그것을 붙이는 것입니다.
그것은 들어 맞습니다.
여기서, 저는 그것을 해싱을 가지고 하지 않습니다.
저는 문제를 추상화하기 위해 문제들을 채우는
테이블을 가지고 있는 것처럼 할 것입니다.
그러나 그것은 해싱으로 동작하지 않습니다.
그것은 고정된 크기의 데이터 구조로 동작합니다. 저는 다시 삽입을 하고,
그것은 맞지 않는군요. 넘칩니다.
제가 하는 것은 새로운 것을 만드는 것입니다.
저는 그것보다 약간 더 공간이 필요합니다.
저는 사이즈 2의 테이블을 만듭니다, 크기를 두 배로 합니다.
저는 새로운 것에 오래된 값을 복사합니다.
저는 이것을 free 시키고, 두 아이템을 집어 넣습니다.
그것을 다시 합니다. 저는 또 넘칩니다.
이제 저는 사이즈 4의 테이블을 만듭니다.
저는 이것들을 복사했고, 제 수 3을 넣습니다.
저는 여기서 삽입합니다.
저는 5를 합니다. 저는 상동 기호(")를 사용해야 합니다.
그것은 더 똑똑합니다.
제가 무엇을 하고 있죠? 넘쳤습니다.
그리고 저는 사이즈 8을 가지고 있습니다. 이것들을 복사합니다,
이제 저는 5를 삽입할 수 있습니다. 그리고 6
7 등을 할 수 있습니다.
모두 이 기본 생각을 이해했나요?
제가 넘칠 때 마다 저는 두 배 크기의 테이블을 만들 것입니다.
이것의 빠른 분석을 해 봅시다.
우리는 n개의 삽입 연산 순서를 가지고 있습니다.
연산을 삽입하는 최악의 케이스는 무엇입니까?
이것의 어떤 것을 위한 최악의 케이스는 무엇입니까?
네, 그것은 θ(n)입니다,
오버헤드는 복사입니다. 제가 그것을 하나로 세면, 그것은 기본적으로 n 또는 n+1일 것입니다.
왜냐하면 우리는 모두 복사하기 때문입니다.
그것은 θ(n)입니다.
그러므로, 제가 이것들의 n을 가지고 있으면,
n 삽입의 최악의 케이스 비용은 n 곱하기
θ(n)이고, 그것은 θ(n^2)입니다.
질문 있나요? 이해 되나요?
손을 들어 보세요.
네, 모두 최악의 케이스가 아니군요,
좋아요. 사실, 이것은 완전히 틀린 분석입니다.
그것이 최악의 케이스에 θ(n)일 수 있는 것이 n이 필수적으로 θ(n)이라는 것을 의미하지 않기 때문입니다.
그래서 이것은 완전히 틀린 분석입니다.
사실, n 삽입은
최악의 케이스에서 θ(n)시간이 걸립니다.
그것은 θ(n^2) 시간이 걸리지 않습니다.
우리가 최악의 케이스 삽입을 θ(n)으로 두면 그것은 맞습니다.
그러므로, 잘못된 단계입니다.
여러분이 증명에서 버그를 볼 때 마다,
여러분은 어떤 단계에서 실패하는지 알길 원합니다,
그래서 여러분은 저기서 혼란을 가지지 않는다는 것을 확실히 할 수 있습니다.
적절한 분석을 해 봅시다.
c_i를 i번째 삽입의 비용으로 합시다.
그것은 i-1이
정확한 2제곱이면 i와 같습니다.
그것은 또 다른 것입니다.
제가 여기서 하면, 그것은
이전의 것이 정확한 2제곱인 곳에서 삽입할 때입니다.
왜냐하면 그것은 제 테이블 사이즈였기 때문입니다.
그것은 제가 오버플로우를 가지고 그것을 모두 복사해야 하는 때입니다.
예를 들어, 6을 삽입하기 위한 비용은 1입니다.
저는 단지 그것을 삽입합니다.
모두 그것을 이해했나요? 여기서 작은 테이블을 실제로 만들어서
더 분명하게 봅시다.
여기 i가 있습니다, 테이블의 사이즈에서, 그리고 단계 i에서 비용입니다.
자 봅시다, 단계 1에서
i의 크기는 1이었습니다.
단계 2에서,
그것은 2이었습니다. 그리고 단계 3에서,
테이블에서 3을 얻기 위해 우리는 여기서 크기를 두 배로 해야 합니다.
이것은 4이고,
4입니다, 그것은 들어 맞습니다.
그리고 5는 8로 커져야 합니다. 6은 8이었습니다.
7은 8이었습니다.
8은 8이었습니다. 9는 16 등으로 커져야 합니다.
그것이 크기입니다.
그리고 비용이 무엇이었는지 봅시다.
여기서 비용은 1이었습니다.
여기서 비용은, 저는 1을 복사했고, 1을 삽입합니다.
비용은 2이었습니다.
여기서 저는 2를 복사하고 1을 삽입합니다.
비용은 3이었습니다. 여기서 저는 1을 삽입합니다.
비용은 1이었습니다. 저는 4를 복사하고 1을 삽입합니다.
비용은 5였습니다.
네? 저는 그렇다고 생각해요.
그것은 i비용입니다. 5를 위한 비용은 i였습니다.
이것이 2제곱이면 5입니다.
1, 1, 이제 우리고 9를 지불하면 다시 반복됩니다.
그래서 그것은 우리가 지불하는 비용입니다.
제가 그것들을 부수면 비용이
무엇인지 알기 더 쉽습니다.
이것을 두 개의 값으로 다시 그려봅시다
왜냐하면 제가 삽입하고 싶은 것을 삽입하기 위한 비용이 항상 있기 때문입니다.
그리고 이제, 제가 지불해야 하는
나머지 양은 여기서 1입니다.
저는 2, 4, 8을 추가적으로 지불해야 합니다.
그것은 더 쉬운 패턴입니다.
이것은 복사를 하는 것과
실제 삽입하는 것의 비용입니다.
이제, 여러분이 필기를 하면,
여기 공간을 남겨 두세요 왜냐하면 저는 나중에 이 테이블로 돌아올 겁니다.
약간의 공간을 남겨 두세요
돌아 와서 나중에 몇 가지를 추가할 것입니다.
저는 n 삽입의 비용을 더할 수 있습니다.
그것은 합입니다,
i는 1의 c_i의 n과 같습니다.
이 분석에 의해서 그것은 필수적으로 n입니다
왜냐하면 그것은 더하는 것이기 때문입니다
2제곱을 더해야 하지만 제 n이 무엇이든 그것을 초과하지 않습니다.
제가 제 대수를 적절하게 하면,
그것은 lg (n -1) 입니다.
그래서 저는 모든 제곱을 저할 것이고 제 n 을 초과하지 않습니다.
이것은 무슨 수열인가요?
등비 수열입니다.
그것은 등비입니다, 그것은 큰 항에 의해 바운드됩니다.
가장 큰 항은 2의 ceiling값입니다.
그것은 가장 큰 항에 의해 지배됩니다.
그것은 최대 n 입니다.
그리고 모든 다른 항은 최대 n입니다.
그래서 이것은 사실 3n 보다 작거나 같습니다 그것은
우리가 보여주고 싶은 대로 θ(n)입니다.
그것은 대수입니다.
따라서 삽입 당 평균 비용은 θ(n)/n 입니다,
그러니까 θ(1)입니다. 삽입의 평균 비용은 θ(1)입니다,
그것은 우리가 해시 테이블을 구축하면
그것은 필수적이어야 하는 것입니다.
여러분이 큰 비용을 지불하더라도,
n 연산의 전반적인 비용은
θ(n)입니다.
그리고 그것은 분할 상환 분석의 개념입니다.
제가 연산의 순서를 보면,
저는 비용을 전체의 연산으로 퍼트릴 수 있습니다,
그래서 평균 비용은 θ(n)입니다.
우리가 그것을 요약하면,
우리는 연산 당 평균 비용이
작다는 것을 보여주기 위해
연산의 순서를 분석합니다.
확률이 없습니다.
우리가 그것을 평균으로 하더라도, 확률이 없습니다.
여러분은 중앙값을 볼 것이고,
평균이 있습니다.
여기 평균이 있지만, 계속 되는 확률은 없습니다.
그것은 최악의 케이스에서 평균입니다
왜냐하면 n 연산은 최악의 케이스에서 연산 당
정수의 시간이 들기 때문입니다.
n 연산은 θ(n)시간이 듭니다.
각 연산은 θ(1)시간이 듭니다,
그러나 그것은 n 연산에 대해 분할 상환입니다.
질문 있나요? 네. 네,
여러분은 섞을 수 있지만 굳이 할 필요는 없습니다.
그러나 핵심은 기본 분할 상환 분석이 사실 매우
강력한 것을 말하고 있다는 것입니다.
그것은 여러분에게 최악의 케이스 바운드를 줄 것이지만
순서의 각 인자를 보는 것과 반대로 순서에 대한 것입니다.
이제, 인쇄물에서 나타내는
분할 상환의 세 타입이 있습니다.
아마 더 있을 수도 있습니다. 하나의 점에서,
둘이 있습니다. 그리고 세 번째 것은 발전되었습니다.
아마 네 번째 것이 있을 수 있습니다.
첫 번째 것은 합계입니다, 그것은 합계 분석입니다.
이것은 우리가 본 것입니다,
여러분이 기본적으로 분석할 때, n 연산은 얼마나 걸리나요?
그리고 우리는 오늘 둘을 더 볼 것입니다.
하나는 회계 논의이고,
다른 것은 잠재 논의입니다.
이 둘은 더 정확합니다 왜냐하면 그것들은 각 연산에
특정한 분할 상환 비용을 할당하기 때문입니다.
합계 분석에 대한 것 중 하나는 여러분이 단일 연산의
분할 상환 비용이 무엇인지 쉽게 말할 수 없다는 것입니다.
여러분은 이 케이스에서 할 수 있습니다.
여러분은 그것이 θ(1)이라고 말할 수 있습니다.
그러나, 회계와 잠재 논의에서, 그
것은 여러분에게 특정 연산의 분할 상환 비용이
무엇인지 특징 짓는 더 정확한 방법을 줄 것입니다.
우리의 첫 번째 메소드로서 회계 메소드를 봅시다.
우리는 정확히 같은 예를 할 것입니다.
어떤 면에서,
가장 쉬운 것은 합계 분석입니다.
우리는 더 복잡한 것을 보는
논의로 들어갈 것입니다.
이 메소드들은
많은 환경에서 더 강력합니다.
그래서 저는 그것을 간단한 상황에서 하고 싶습니다
여러분이 특정 문제를 보고 그것에
접근하는 사실의 공감을 가지는 곳입니다.
그래서 회계 메소드는 여러분 스스로를 금융 회계사의 위치에 둡니다.
여러분이 하는 것은 우리가 i번째 연산에
허구의 분할 상환 비용을 부과하는 것입니다.
우리는 그것을 c hat sub i로 부를 것입니다,
거기서 우리는 하나의 단위를 위해 1 달러를 지불하는 추상화를 사용할 것입니다.
데이터 구조를 조작하는 시간이 있습니다.
여러분은 비용을 부과합니다.
이 연산은 5 달러가 듭니다.
Phi는 연산을 수행하는데 소비되지만
사용되지 않은 부분이 있을 수 있습니다.
사용되지 않은 양이 있으면,
그것은 나중의 연산에 의해 은행에 저장될 것입니다.
Phi가 지불되면, c_i hat phi는 연산을 수행하기 위해
지불하는데 충분하지 않습니다,
그리고 여러분은 지불하기 위해 은행에서 돈을 꺼냅니다.
그리고 여러분은 체포되지 않습니다,
여러분이 가져야 하는 속성은 무엇입니까?
여러분은 은행 잔고를 가져야 합니다.
은행 균형은 무엇입니까? 은행 잔고를 유지해야 하는 수학적인 사실은 무엇입니까?
네 그것은 0 보다 크거나
같은 것이 좋습니다.
대부분의 사람들은 그것에 친숙합니다.
은행 잔고는 음으로 가서는 안됩니다.
다시 말해, 분할 상환 비용 마이너스 연산의
비용은 항상 여러분이 하는
모든 연산을 지불하는데 충분해야 합니다.
다시 말해, 여러분은 미래에서 빌립니다.
분할 상환 분석에서, 우리는 미래에서 빌리지 않습니다,
적어도 간단한 것에서는 아닙니다.
그래서 그것은 우리가 합을 가져야
하는 것을 의미합니다,
그러므로 잔고가 음으로 가지 않으면,
모든 n을 위하여 분할 상환 비용에 의해 바운드 되어야 합니다.
은행 잔고가 음으로 가지 않는 것에 대하여, 제가 옳은 비용을 더하면,
그것은 제가 항상 지불할 수 있는 케이스가 되어야 합니다.
이것은 제가 지불하는 것입니다.
이것은 사실 제게 비용이 드는 것입니다.
그것은 데이터 구조에서 연산하기 위해
지불해야 하는 케이스인 것이 더 낫습니다.
그것은 그 점까지의 데이터 구조의 사용을 위해야
부과하는 양에 의해 다뤄지는 것이 낫습니다.
그리고 그것은 모든 n을 위해 옳아야 합니다.
그러나 이것이 제게 특정한 연산을 부과하는
방법을 준다는 것을 주목하세요.
총 분할 상환 비용은 총 비용에서 상계를 제공합니다.
총 분할 상환 비용은 옳은 비용에서 상계입니다.
이것에 대해 질문 있나요?
우리는 이 방법론을 사용하는 동적 테이블의 예를 할 것입니다.
동적 테이블로 돌아 갑시다.
우리가 이 케이스에서 할 것은 모든 i에 대하여
i번째 삽입을 위해 3달러를 부과하는 것입니다.
그리고 1달러는 즉시 삽입을 위해 지불되고,
2달러는 테이블을 두 배로 하기 위해 저장될 것입니다.
그것은 확장될 필요가 있습니다.
테이블이 두 배 될 때,
우리는 최근 아이템을 움직이기 위해 1달러를 사용할 것입니다,
우리는 오래된 아이템을 움직입니다.
예를 해 봅시다. 제가 크기 8의 테이블을 가지는 상황에 있다고 상상해 보세요,
저는 제 테이블을 두 배 합니다.
저는 테이블의 네 아이템을 가집니다.
제가 하려는 것은 테이블에 달러를 가지지 않는 것입니다.
아이템 수 5의 삽입을 따라서요.
저는 그것에 3달러를 부과합니다.
1달러는 테이블에서 아이템을 넣게 하고, 저는 2달러를 남깁니다.
저는 아이템이 있는 곳과 일치하는 슬롯에서 2달러를 저장합니다.
이제 아이템 6이 들어옵니다.
다시 1달러이고, 3달러를 부과합니다, 1달러를 삽입을 위해 부과되고,
2달러는 남겨집니다, 저는 2달러로 할 것입니다.
이것을 아래로 두겠습니다.
2달러가 남아 있습니다,
그리고 이제 9번째 아이템이 들어옵니다.
그래서 저는 테이블의 크기를 두 배로 합니다.
그리고 이제 저는 이 모든 것들을 여기로 복사합니다.
그리고 무엇이 일어납니까? 그것을 보세요,
저는 8달러를 가집니다, 그리고 복사되어야 하는
8 아이템을 가집니다. 완벽해요.
이 달러들 중 하나는 마지막 라운드에 삽입되었습니다,
그리고 그것들 중 하나는 오래된 것을 위해 지불합니다.
그리고 저는 그것들을 복사하고
그것들 중 아무도 돈을 가지지 않습니다.
그리고 9번째 사람이 들어옵니다, 그는 2달러를 남겨 둡니다.
우리는 계속 합니다. 여러분은 그것을 봅니다,
제가 모두에게 3달러를 부과하면, 저는 항상 모든 테이블을 다룰 수 있고,
테이블을 위해 부과할 수 있습니다
왜냐하면 제가 유지했던 초기의 불변이 그것이 두 배 된 후에,
계좌에 아무 것도 없기 때문입니다.
그리고 이제 저는 2달러를 넣습니다.
저는 지불할 수 있고 같은 상황에 남겨집니다.
그것은 절대 음이 되지 않는
은행 잔고 케이스입니다.
그것은 증명해야 하는 중요한 불변입니다.
그러므로, 옳은 비용의 합 또는 분할 상환 비용,
상계입니다.
I가 1의 n과 같으면,
이것은 3n 입니다.
핵심은, 이제
제가 이제 3n에 의한 비용의 합을 바운드했다는 것입니다.
이 테이블로 돌아 갑시다,
그리고 제가 c_i hat과 은행 잔고를 넣는지 봅시다.
사실, 제가 하는 첫 번째 것은 삽입입니다.
insert; I charge $3, right, and I do an insert.
저는 3달러를 부과합니다, 그리고 저는 삽입합니다. 얼마나 많이 남았나요? 저는 2달러를 가집니다.
저는 사실 2달러를 부과할 것이고 1달러만 남습니다.
그래서 저는 첫 번째 것을 할 것입니다.
저는 여러분에게 제가 모두에게 3달러를 부과하면 동작한다는 것을 보여줄 것입니다.
첫 번째 것을 제외하고요, 저는 2달러를 부과합니다.
저는 사실 숫자 1에서 약간 저장할 수 있습니다.
이것을 위해서 저는 3달러를 부과할 것입니다.
제가 다 했을 때 은행 잔고의 크기는 무엇입니까?
저는 한 사람을 복사해야 합니다.
그는 모두 지불했고, 저는 2달러가 남습니다.
모두 알겠나요? 다음 사람입니다,
저는 3달러를 부과합니다. 사실 저는 이것들에게 3달러를 부과할 것입니다.
여기서 이제 저는 기본적으로
크기 4의 테이블을 가집니다.
저는 복사해야 하고,
세 번째 것을 삽입할 때, 둘을 복사해야 합니다.
그것을 다 사용할 것이고,
저는 삽입한 후에 테이블에 2달러가 남겨집니다.
이제 저는 네 번째 것을 삽입합니다.
그리고 그것은 좋은 것입니다 왜냐하면 이제 저는 4의 잔고를 구축하기 때문입니다 저는 아무 것도 복사하지 않아야 합니다.
이제 저는 다섯 번째 것을 삽입합니다.
저는 네 아이템을 복사해야 합니다. 그것은 잔고를 늘립니다.
저는 두 남겨진 것을 가집니다.
그리고 여기서 기본적으로 둘을 더합니다.
이 점에서, 저는 그것을 모두 다 써 버리고 둘로 돌아 갑니다.
그래서 여러분은 그것들 중 하나를 볼 수 있습니다
여러분이 보길 바라는 것은 여기서 3을 부과하는 것입니다.
그리고 저는 추가적인 달러를 가지지 않습니다.
그것은 중요하지 않습니다.
그것은 여전히 상계입니다.
분할 상환을 부과하는 다른 스키마는 동작할 수 있습니다.
그것들은 모두 같아야 하지 않습니다.
여러분이 분할 상환 분석을 할 때
동작하는 하나의 스키마가 있습니다.
저는 모두에게 4달러를 부과할 수 있습니다.
그것은 동작했습니다.
그러나 저는 모두에게 2달러를 부과하지 않았습니다.
제가 모두에게 2달러를 부과하면, 제 잔고는 음이 됩니다.
제 잔고는 음이 되지만,
저는 3 달러를 부과할 것이고 그것은 동작합니다.
4 5 6 저는 그것을 부과합니다.
그것은 간단히 낮은 바운드입니다.
그것이 3n 보다 작거나 같은 대신에,
그것은 4n 또는 5n 보다 작거나 같습니다.
그러나 제가 2n을 하려고 하면 그것은 동작하지 않습니다
왜냐하면 저는 모든 것을 복사할 충분한 돈이 남아있지 않기 때문입니다.
저는 여기서 1 달러만 가집니다,
그것이 테이블을 두 배할 시간이 될 때
저는 8개를 복사할 필요가 있습니다.
저는 4달러를 위한 계좌를 구축해야 합니다,
미안해요, 제가 3달러를 부과하고 1달러가 남으면요.
이것이 실제로 동작하도록 하기 위해,
무엇이 동작하고, 동작하지 않는지 보세요.
알고리즘 설계를 위한 알고리즘적 공식이 없습니다.
좋아요.
책에서, 여러분은 테이블 축소에 대해 읽을 수 있습니다.
여러분이 인자를 삭제하기 시작할 때 무슨 일이 일어나나요?
이제 여러분은 테이블을 더 작게 만들고 싶습니다.
이제 여러분은 조심스러워져야 합니다
왜냐하면 여러분이 넣기 않으면, 누가 물리학에서,
이력 현상을 기억하나요?
몇 명 있나요? 여러분은 이력 현상에 대해 걱정해야 합니다.
여러분이 조심하지 않으면,
그것이 2제곱 보다 작지 않으면,
여러분은 2분의 1로 갑니다, 여러분은 참패하는 것을 알 수 있습니다.
여러분은 그것을 만들 필요가 있고
시스템에서 메모리가 있습니다 그래서
여러분은 충분한 수의 삭제를 한 후에 충돌을 합니다.
그리고 책은 더 일반적인 케이스의 분석을 가집니다.
회계 메소드에 대한 질문 있나요?
회계 메소드는 정말 귀엽습니다.
정말 귀여워요.
And, it's the one most students prefer to do,
그들은 배울 때까지 다음 것을 보통 싫어합니다.
한번 배우면,
좋다고 말합니다.
그러나 시작하기 위해서, 그것은
용기가 필요합니다.
그러나 그것은 놀랍습니다.
좋은 잠재 인자는 매우 좋습니다. 그리고 우리는 다음 것을 보아야 합니다,
그래서 여러분은 분명히 복습해야 하고 수요일 강의 전에
이해해야 합니다 왜냐하면 수요일에,
우리는 잠재 메소드를 이해하고 있다고 가정할 것이기 때문입니다.
해 봅시다.
잠재 메소드는
알고리즘 분석에서
아름다운 결과 중 하나입니다.
여러분은 무엇을 염원하나요?
경리인가요 물리학자인가요?
우리는 은행원이 되길 원하지 않습니다.
우리는 물리학자이고 싶습니다.
우리는 분석하는 동적 잠재 에너지에
대해 이야기할 것입니다.
왜죠?
그것은 봄이 하는 것과 같은 일을 전달합니다. 예를 들어,
여러분이 에너지를 연구할 때 또는
무엇을 높이 올릴 때 등입니다.
우리는 동적인 것을 잠재적인 것으로 변환하고
그것은 정확히 우리가 하는 것입니다.
그것은 비슷한 수학입니다.
우리의 케이스에서 그것은 별개의 수학입니다.
여기 잠재 메소드를 위한 프레임워크가 있습니다.
우리는 어떤 데이터 구조 D_0에서 시작합니다.
그리고 연산 i는 D_(i - 1)를 D_i로 변환합니다.
우리는 데이터 구조에서 매핑함으로써 연산을 봅니다,
하나의 데이터 구조를 다른 데이터
구조로 매핑합니다.
이미 그것은 수학적입니다.
그리고 물론 연산 i의 비용은
c_i에 남아 있습니다.
이제 우리가 하려고 하는 것은 잠재 함수 phi를 정의하는 것입니다,
그것은 데이터 구조 집합을 실제로 매핑합니다.
모든 데이터 구조와 연관된 것은 잠재적입니다.
그래서 초기 잠재는
0이고 D_i의
phi는 0 보다 크거나 같습니다.
잠재 함수는 음이 아닐 수 없습니다
은행 계좌처럼요.
잠재 함수는 필수적으로
잠재 함수를 나타냅니다.
그래서 우리는 항상 잠재 함수가 음이 아니길 원합니다.
사실, 잠재 함수를 이용하는 곳이 있습니다.
거기서 여러분은 이 속성들을 위반합니다.
이것들을 위반하지 않는
흥미로운 잠재 논의들이 있지만,
우리는 간단한 것을 할 것이고,
이것들이 옳다고 가정할 것입니다.
그러나 우리는 D_0의 phi가 0이 아닌 것을 볼 것입니다,
그것은 중요하지 않습니다.
일반적으로 이것은 우리가 잠재 함수에서
가정하는 것입니다.
저는 여러분이 더 큰 것이 있다는
것을 알길 바랍니다.
저는 여러분에게 여기서 보여줄 것입니다.
이 상황 아래서
우리는 분할 상환 비용을 정의합니다.
그리고 이것은 여러분이 기억할 수 없으면,
그것을 놓아야 합니다.
그래서 c_i hat은 c_i hat
더하기 D_i의 phi 마이너스 D_i의 phi 마이너스 1과 같습니다.
그래서 이것은 잠재 차이에서 변화입니다.
그것을 줄여서 델타 phi i라고 부르겠습니다.
그리고 그것이
다른 상황에서 의미하는 것을 봅시다.
델타 phi i가 0보다
크거나 같으면 c_i hat과
c_i 사이의 관계는 무엇입니까?
이것은 0 보다 큽니다. c_i hat은 c_i 보다 큽니다.
c_i hat은 c_i 보다 큽니다.
그것은 무엇을 의미합니까?
제가 연산을 할 때, 저는 더 많이 부과합니다.
남은 것은
은행에 넣어져서
잠재 에너지가 됩니다.
저는 나중을 위해 데이터 구조에서 저장합니다.
비슷하게 델타 phi i가 0 보다 작으면,
c_i hat은 c_i 보다 작습니다. 그리고 데이터 구조는
전달합니다.
그것이 0보다 작으면, 그것은 잠재 함수에서 변화를 의미합니다.
은행 계좌는 결과로 내려갑니다,
그러므로 데이터 구조에서 일어난 것은
순서로 된 것을 제공했습니다.
왜냐하면 옳은 비용은 분할 비용 보다 크기 때문입니다.
그것에 대해 생각해 보면,
분할 함수 견해와
회계 견해의 차이점은
제 분할 비용일 것입니다.
이제 제 은행 계좌를 분석하겠습니다,
그것이 절대 음이 아니라고 확신하세요.
어떤 면에서,
제 은행 계좌는 항상 있습니다.
분할 비용이 하는 것을 분석해 보겠습니다.
그것은 접근법의 차이 입니다.
하나는 은행 계좌를 구체화하는 것입니다.
다른 것은, 여러분이 분할 비용을
구체화하는 것입니다.
이것은 왜 합리적인 방법입니까?
자, n 연산의 총 비용을 봅시다.
그것은 합입니다.
그것은 총 분할 상환 비용입니다.
이 공식을 위해
c_i hat을 치환합니다.
그것은 c_i + Φ(D_i) - Φ(D_i) - 1 입니다.
그것은 c_i와 같습니다. 그리고 이제 제가 이 항들을 더하면 무슨 일이 일어납니까?
무슨 일이 일어나죠?
우리가 사용하는 수학적인 항은 무엇입니까?
항을 줄어듭니다.
왼쪽의 모든 항은 더해집니다,
그것이 i-1일 때 빼집니다, 첫 번째와 마지막 항을 제외하고요.
n을 위한 항은 더해집니다.
0을 위한 항은 빼집니다.
그러니까 항이 줄어드는 거죠.
이 항은 무엇입니까? 우리가 이것이 대해 아는 속성은 무엇입니까?
그것은 0 보다 크거나 같습니다.
이것은 0과 같습니다.
그러므로 이것은 c_i 보다 크거나 같습니다.
따라서 분할 상환 비용은 옳은 비용에서 상계입니다,
그것은 우리가 원하는 것입니다.
분할 비용은 옳은 비용의 합에서 상계입니다.
그러나 여기서
우리가 정의하는 방법은 잠재함수를
정의하는 것에 의한 것입니다. 그래서
잠재 함수는 회계와
잠재 메소드 간의 차이입니다.
여러분은 은행 계좌를 구체화합니까 또는 비용을 구체화합니까?
여러분은 잠재 에너지를 구체화하나요
또는 비용을 구체화하나요?
그러나 어떤 케이스에서, 이 바운드를 얻고,
수학은 더 좋습니다. 저는 망원경을 좋아합니다.
그래서 분할 상환은 상계 비용이 듭니다.
여기서 테이블을 두 배해 봅시다.
이것을 분석하기 위해, 우리는 우리의 잠재 함수를 정의해야 합니다.
이것을 알면,
저보다 낫습니다.
저는 가까스로 몇시간 동안 했습니다
저는 똑똑하지 않으니까요.
그것은 제가 사용할 잠재 함수입니다.
2i 마이너스 2의 lg I 입니다.
그리고 우리는 0과 같은 것을 가정할 것입니다
그것은 제한에 있는 것이기 때문입니다.
로그 0을 위해
이것은 마이너스 무한대가 됩니다. 2의 마이너스 무한대는 0입니다.
그것은 수학적인 편리함입니다.
그것을 가정해보세요.
어디서부터 저는 이것을 얻었나요?
저는 가지고 놀았습니다.
저는 지운 순서를 보았습니다 왜냐하면
잠재 함수가 쉽다고 정의하는 곳의 문제가 있기 때문입니다.
그러나 분할 상환 비용을 정의하는 것은 어렵습니다.
회계를 정의하기 위해서요.
이것을 위해,
회계 메소드는 사용하기 더 쉽습니다.
그러나 저는 여러분에게
잠재 함수로 할 수 있다는 것을 보여줄 것입니다.
직관적으로, 이것은 i번째 연산에서
계좌의 왼쪽에 있는 것입니다 왜냐하면 저는 은행에 2i를 넣었기
때문입니다 저는
이것을 필수적으로 뺐습니다.
이 점까지요.
그래서 먼저 관찰해 봅시다, phi of D_0는 무엇인가요?
0입니다. 그것은 좋습니다.
그리고 Φ(D_i)는 0 보다 크거나 같습니다.
왜 그런가요?
왜죠?
가장 큰 것은 무엇인가요?
lg i의 ceiling값은 lg i 또는 lg i 더하기 1입니다.
가장 큰 것은 lg i 더하기 1입니다.
lg I 더하기 1이면, 그것은 2i 입니다.
그것은 가장 큰 것입니다.
다른 방법으로 해 봅시다.
이 부분에서 i이고, 이 부분에서 2 입니다.
그래서 그것은 가장 큰 것일 수 있습니다.
그것은 단지 i의 로그입니다. 이것은 2i 마이너스 I 또는 2i 마이너스 2i일 것입니다.
양쪽 케이스에서,
그것은 0 보다 큽니다.
이것이 잘 정의된 잠재 함수이기 위한
두 속성이 있습니다.
분할 상환 비용은
만족되지 않습니다.
저는 분석을 할 수 있고 원하는 바운드를 얻을 수 있습니다.
저는 적절한 잠재 함수를 가지는
구문을 만족시킵니다.
이것을 알기 위해
여기서 간단한 예를 해 봅시다.
제가 8을 가지는
상황에 있다고 가정해 보세요.
6개는 꽉 찼습니다.
이것에 의한 phi는 2i일 겁니다. 그것은 2 곱하기 6 마이너스 2의 2i입니다.
무엇이죠?
미안해요, 마이너스 2의 lg i입니다.
I는 6입니다,
그래서 lg i는 lg 6입니다. 그것의 ceiling값은 3입니다.
그것은 마이너스 2^3 즉 8입니다.
그것은 12 마이너스 8입니다. 4입니다.
여러분이 이것에 대해 생각해보면,
이것은 0입니다,
그리고 이것들은 2입니다.
왜냐하면 이것이 절반이고
우리는 2를 더하기 때문입니다.
함수는 저에게
실제 비용이 무엇인지 말해줍니다.
모두 알겠나요?
그래서 그것은 이 특정 잠재 함수가 의미하는 것입니다.
그래서 이제 i 번째 삽입의 분할 비용을
더합시다.
그것은 i 번째 삽입의 분할 비용입니다,
정의에 의해서요. 그리고 이제 그것은 같습니다.
c_i는 무엇입니까?
우리는 여전히 가지고 있나요 또는 그것을 이점에서 지웠나요?
저는 우리가 지웠다고 생각합니다.
우리는 그것을 다시 쓸 수 있습니다.
i-1이 정확히 2제곱이면 그것은 i입니다. 그것은 2입니다.
그것은 c_i 입니다.
그것은 이 항이고, phi of D_i 입니다. 그것은 무엇이죠?
phi of D_i 는 이것입니다.
phi of D_i 는 이것입니다.
그래서 그것은 분할 비용입니다.
좋은 공식입니다,
그렇죠?
그것이 단순화되길 바랍시다.
우리는 i와
1을 여기서 가집니다.
우리는 소거할 수 있는 것이 있습니다.
여기서 2i 마이너스 2i가 있습니다.
그것은 소거됩니다. 그리고 왼쪽에 있는 것은 마이너스 2 입니다.
그것은 플러스 2입니다.
이제 저는 마이너스 이 항 더하기 이 항을 가집니다.
그것은 더 예쁩니다. 그것은 여전히 엉망입니다.
우리는 케이스 분석을 해야 합니다. 왜 그것은 케이스 분석을 연상 시키나요?
우리는 케이스를 가집니다.
케이스 분석을 합시다.
I-1은 정확히 2제곱입니다.
c_i는 이제 i입니다.
그것은 그 케이스입니다.
그리고 우리는 남은 것들을 가집니다.
그것은 I 더하기 2와 같습니다.
자 봅시다.
I 마이너스 1은 정확히 2제곱입니다,
이 항은 무엇입니까? I 마이너스 1은 정확히 2제곱입니다.
고마워요,
그것에 대해 미안해요.
학생들이 있는 것은 좋습니다. 제 수학은 나쁘거든요.
이것은 사실
제가 좋은 이론가로 끝나는 이유입니다 왜냐하면 저는 쓴 것을 믿지 않습니다.
저는 그것을 입증할 수 있는 방법으로 씁니다
왜냐하면 저는
5개의 식을 가질 만큼
똑똑하지 않기 때문입니다.
그것을 쓰세요. 저는 항상 씁니다 그래서 증명할 수 있습니다.
그것은 다른 사람이
제가 한 것을 이해할 수 있는 부수 이익을 가집니다.
이것은 무엇인가요?
이것은 2의 lg i -1 입니다
이것이 2제곱이면 lg i -1의 ceiling값은
lg i -1 입니다.
이것은 2의 lg i -1입니다.
그렇죠?
네. 그것이 정확한 2제곱이면,
로그는 정수입니다, 그렇죠?
ceiling값을 가지는 것은 중요하지 않습니다,
제거하세요.
이것은 정확히 2제곱이 아닙니다.
그러나 그것은 무엇인가요? 그것은 1 입니다.
우리는 i-1이 정확히 2제곱이 아니라는 것을 알고 있습니다,
그래서 그것은 다음의 더 큰 것일 겁니다.
그래서 이것은 무엇인가요?
이 둘은 어떻게 비교하나요?
이것은 이것 보다 얼마나 큰가요?
그것은 크기를 두 배 합니다. 우리는 그것이 무엇인지 압니다.
그것은 첫 번째 원칙의 이유입니다.
이것은 lg i -1 +1 입니다.
그래서 여러분은 그것을 이것으로 줄일 수 있습니다. .
여러분은 floor값과 ceiling값에 대해 생각해 보아야 합니다.
여기서 무엇이 일어나나요?
그래서 이제 우리는 이것을 단순화할 수 있습니다.
우리는 여기서 무엇을 가지나요?
제가 이것을 곱하면,
저는 I 더하기 2 마이너스 2i 더하기 2 더하기 I 마이너스 1을 가집니다.
아마 여러분의 90%가 이 단계를 할 것입니다.
여러분은 이 단계에서
마지막 단계로 직접적으로 갈 것입니다.
그것은 틀립니다.
여러분이 그것을 하도록 격려하겠습니다.
여러분이 천천히 하면 버그를 찾는 것은 더 쉽습니다.
사실 천천히 하는 것은 장기적으로 더 빠릅니다.
가르치는 것은 어렵습니다.
쉽게 하세요. 연습하세요,
그리고 천천히 하세요.
그것은 사실 더 빠릅니다.
모두 거북과 토끼 이야기를 알고 있겠죠.
그러나 아무도 그것을 믿지 않습니다.
이제 우리는 2i와 i와 i를 가집니다.
우리에게 2 더하기 2 마이너스 1을 남깁니다,
그것은 3입니다. 놀랍습니다.
분할 상환 비용은 3입니다 i-1이 2제곱일 때요.
케이스 2입니다.
i-1은 정확히 2제곱이 아닙니다.
그래서 우리는 c_i hat을 가집니다.
이제 i-1은 정확히
2제곱이 아닌
케이스에서 이 두 항에 대해
제게 말할 수 있나요?
무엇입니까? 같습니다.
왜죠? ceiling값은 같고,
같은 정수를 가집니다.
이 둘은 같고, 이것이
3과 같다는 것을 의미합니다.
그러므로, n 삽입입니다.
분할 비용은 모든 연산에 대해
모든 삽입에 대해 3입니다.
그러므로 n 삽입 비용은 3입니다.
각 분할 상환 비용은 3입니다.
분할 비용은 3n 입니다.
그것은 최악의 케이스에서 상계입니다.
N 삽입은 최악의 케이스에서 θ(n)의 비용이 듭니다.
이 분석에서 버그가 있습니다.
그것은 사소한 버그입니다.
그것은 첫 번째 삽입 전에 지적하는 것입니다.
저는 충분히 신중하게
다루지 않았습니다.
그래서 그것은 연습이고
그것이 일어나는지 여러분이 어떻게
보여주는지 보는 것입니다.
요약하겠습니다.
분할 상환 분석에 대한 결론입니다.
분할 상환 비용은 데이터 구조 수행을 위한 명확한 추상화를 제공합니다.
예를 들어, 제가
동적 테이블을 구축한다고 가정해보세요.
여러분의 수행 모델링 관점에서
그것은 더 쉽습니다,
그것은 각 삽입 당 정수 시간이 듭니다.
여러분이 실제 행동을
신경 쓰지 않으면,
그것은 복잡한 것이라고 말하는 것 보다 수행을 위한
좋은 추상화입니다
모든 연산은 θ(1)의 비용이 들고,
그것은 정말 간단합니다.
그것들은 이해해야 합니다. 그것은 분할 측면에서 θ(1)입니다.
그것들이 실제 제약을 가지면 분할은
그것을 분할하지 않습니다.
그러나 많은 문제들을 위해, 그것은 완벽하게 좋습니다.
그것을 다소 간단하게 설명해보겠습니다.
우리는 다른 연산이 다른 분할 비용을 가지는
데이터 구조를 볼 것입니다.
그리고 그것에 대해 좋은 것은 저는 더할 것입니다,
제 다른 연산의 비용은 무엇인가요,
각 연산을 위한 다른 비용은 어디인가요?
그것들은 lg n일 겁니다. 어떤 것은 θ(1)입니다.
그것들을 더하세요.
그것은 상계입니다.
추상화에서 엄청난 단순화이고
이 복잡한 데이터 구조에 대한 이유입니다.
이것은 매우 큽니다.
추상화는
여러분이 학부 4년간 배우는 것이고,
박사 학위를 받으면
15년이 걸립니다.
여러분이 가르치는 모든 것은
추상화입니다.
이것은 강력한 추상화입니다. 좋습니다.
이제, 우리는 세 메소드를 배웠습니다.
일반적으로 어떤 메소드는 사용될 수 있습니다.
여러분은 하나를 다른 하나로 전환할 수 있습니다.
그러나 각각은 가장 간단한 또는 가장 정확한 상황을 가집니다.
메소드들은 사용될 수 있습니다.
그러나 여러분은
모든 것을 배워야 합니다.
왜냐하면 여러분이 그것이 필요한 상황이 있기 때문입니다.
여러분이 읽어보면,
여러분은 그것을 하는 다른 방법을 알 수 있습니다.
여러분이
시험에서 정말 편리하더라도,
저는 이것을 잠재 함수 논의를 가지고 풀 것입니다.
여러분은 편리하고 싶습니다.
네.
마지막은 다른 잠재 함수 또는
회계 비용이 다른 바운드를 산출한다는 것입니다.
여러분이 분할 분석을 할 때, 비용의 하나가
다른 것 보다 나은 것은 아무 것도 없습니다.
예를 들어 데이터 구조에서 일반적으로 그것은 삭제를 지원합니다.
저는 모든 삭제를 분할 상환할 수 있습니다.
일반적으로
제가 할 수 있는 것은 삭제를 자유롭게 하는 것이고,
각 삽입에 대해 두 배를 부과하는 것입니다.
제가 삽입을 할 때 충분합니다.
여러분은 회계 메소드를 가지고 할 수 있습니다.
여러분은 잠재 메소드를
가지고도 할 수 있습니다.
저는 사실 데이터 구조에서 각 아이템에 대해
삭제의 비용을 가집니다.
그래서 핵심은 제가 비용을 다른 방법으로 할당할 수 있다는 것입니다.
또는 저는 옳은 값과 같은 분할 상환 비용을
가질 수 있습니다.
제가 분할 상환 비용을 할당할 수 있는 다른 방법들이 있습니다.
하나의 방법이 있지 않고
다른 바운드를 산출하는 다른 것들을 선택할 수 있습니다.
그렇지 않을 수도 있으나, 그것은 다른 바운드들을 산출합니다.
일반적으로 그것은 다른 것들을 산출합니다.
다음 시간에, 잠재 함수의 놀라운 사용을 볼 것입니다.
매우 좋은 것입니다.
수요일 강의는 놀랍습니다.
우리는 놀라운 분석 타입을
할 수 있습니다.