Tip:
Highlight text to annotate it
X
이 강의의 한국어자막은 www.snow.or.kr 자원활동가들에 의해 작성되었습니다.
제 이름은 에릭 드메인이고, 에릭이라고 불러주시면 됩니다.
6.046에 오신 것을 환영합니다. 두 번째 강의 시간입니다.
오늘은 첫 번째 강의시간에 배웠던 수학적 기초 개념에 대해서
더 자세히 배워보도록 하겠습니다.
첫 번째 강의 시간에 우리가 삽입 정렬이나 합병 정렬을 통해서
알고리즘 분석에 대해 약간의 맛을 봤습니다.
약간의 도구들이 필요했고,
점근적이라는 개념에 대해
보았습니다.
오늘은
오늘은 그것을 수학적으로 알 수 있도록
점근적 표기법을 발전시켜보도록 하겠습니다.
또한 합병 정렬을 가지고 recurrence에 대해 알아보겠습니다.
recurrence를 어떻게 구하는지를 잘 보아야 합니다.
오늘 이 두 가지를 하도록 할 것입니다.
예, 목소리를 좀 더 크게 하도록 하겠습니다.
좋습니다.
마이크가 있어도 소리가 크게 나오지 않는군요.
점근적 표기법부터 시작해보도록 하겠습니다.
우리는 몇몇 기본적인 점근적 표기법을 보아왔습니다.
아마도 다른 수업에서 이미 봤을 것입니다.
빅오 표기법 같은 것 말이죠.
오늘 수업에서는 이것들을 좀 더 엄밀하게 정의해보도록 할 것입니다.
그래서 무엇이 진실이고 아닌지, 무엇이 유효하고 그렇지 않은지 알게 될 것입니다.
오늘은 정의에 대해서 공부하게 될 것입니다.
안타깝게도 오늘은 정말 수학적으로 가고, 알고리즘은 하지 않을 것이에요.
약간 실망스런 소식이죠. 그렇지만, 다음 수업에서는
진짜 알고리즘들에 대해서 이야기하고, 오늘 배운 것들을 진짜 알고리즘들에
적용해 보는 시간을 갖게 될 것입니다. 이것이 빅오 표기법입니다.
대문자 'O' 표기법이죠. f(n)=O[g(n)]이 있습니다.
이 식은 충분히 큰 n에 대해서
f(n)이 cg(n)보다 작거나 같은 것을 만족하는
적절한 상수 c와 n_o가 있다는 것을 의미합니다. 매우 직관적인 표기법이지요.
우리는 전에 이것을 본적이 있습니다.
여기서 f(n)이 음수가 아니라고 가정합시다.
그리고 f(n)은 위쪽으로는 g(n)보다 작거나 같게 됩니다.
우리는 많은 예들을 봤었습니다.
2n^2은 O(n^3)로 정의됩니다. 그리고 이것은 대략적으로
앞쪽의 계수와 낮은 차수의 항들을 제거하면,
이것보다 더 적거나 같다는 것을 의미합니다. 그래서 빅오는 대략
그 보다 작거나 같다는 것을 뜻합니다. 그러나 이것은 공식화된 것이고,
그것에 대해 생각하는 다른 방식을 보면, 이 표기법이 사실은 비대칭이라는
재미있는 사실을 알게 됩니다.
일반적으로 =는 뜻에 대해서 대칭이라고 생각할 것입니다.
A=B이고 B=A인 것처럼 말이죠. 그러나 여기서는 그렇지 않습니다.
n^3이 O(n^2)이 되지 않고,
심지어 O(n^3)도 n^2와 같아지지 않습니다.
그래서 그것이 어떤 의미인지 정확하게 알아야 합니다.
그렇지만, 그것을 하기 전에, 이 표기법이 약간 특이한 표기법이고,
항상 그것이 무엇을 의미하는지 생각해봐야 합니다.
그것이 의미하는 바를 생각해보는 다른 방법으로는
f(n)이 g와 같은 함수들의 집합이라는 것입니다.
여러분은 O[g(n)]이 함수들 중 하나의 집합이 될 수 있도록 정의해야 합니다.
상수들이 존재하는 것을 만족하는 함수를 f(n)이라고 부르도록 하죠.
그것들은 정의가 같습니다.
c와 n_o가 있고, 0보다 크거나 같고,
cg(n)보다 작거나 같은 f(n)이 있습니다.
약간 길죠.
그래서 이것을 반복적으로 쓰는 것을 피하기 위해 이 표기법을 사용하는 것입니다.
n^2대신에 O(n^3)와 같다는 것을 생각 할 수 있습니다.
우리가 의미하는 것은
2n^2이 O(n^3)에 포함된다는 것입니다.
그리고 이렇게 포함되는 것을 나타낼 때, ‘=’ 표시를 사용하는 것이지요.
우리는 앞으로도 ‘=’ 을 사용하게 될 것입니다.
이렇게 써도 괜찮고, 때때로 이렇게 쓰여져 있는 것을 보게 될 테지만,
‘=’ 이 앞으로 우리가 계속 사용할 표기법이 될 것입니다.
‘=’은 대칭적이고 이런 연산자와 같다는 결론을 얻을 수 있습니다.
사실 빅오 표기법을 사용하는 몇몇 실용적인
방법들이 있습니다.
그리고 매크로로써 사용합니다. 그런데, 오늘 다뤄야 할 양이 많습니다.
그래서 수업이 좀 빠르게 진행될 거예요.
잘 모르는 것이 있으면 멈추고, 질문하셔도 됩니다.
그러면 좀 천천히 진행하도록 하겠습니다. 그렇지 않으면
모두 다 이해하시는 줄 알고, 빠르게 진행하도록 하겠습니다.
관습상, 이것은 직관적입니다.
여러분이 매크로 프로그래밍 같은 것을 한다면 말이죠.
그렇지만, 조금은 더 수학적입니다.
우리는 빅오 표기법을 정의 내렸고, 그것은 어떤 것의 빅오와 같습니다.
그리고 우리는 우리가 어떤 함수의 빅오를 = 표시에서 가지고 있을 때만,
빅오의 정의를 내렸었죠.
그러나 빅오를 포함하는 우변에서
일반적인 수식을 가지는 것은 유용합니다.
예를 들어보겠습니다. f(n) = n^3 + O(n^2)라는 식이 있다고 합시다.
error bound를 얻으려고 합니다.
f(n)은 기본적으로 n^3이고
여기에 O(n^2)도 있습니다.
이것은 하나의 함수를 의미하고
f(n) = n^3 + h(n)을 만족하면서 O(n^2)에 속하거나 같은,
h(n)이 있다는 것을 의미합니다.
이것은 충분히 큰 n에 대하여 c*n^2에 포함되어 있는
낮은 차수 항들이 있다는 것을 말합니다.
그것이 바로 O(n^2)을 말하고, f(n) = n^3 + O(n^2) 식에서
‘=’은 진짜 ‘=’이 되는 것이지요.
이것이 여기서 매우 유용한데,
기본적으로 leading constant가 무엇 인지를 표현하고 있고,
뒤쪽에 이것들은 기껏해야 n^2가 된다는 것을 잘 말해주고 있죠.
그러므로 f(n)은 또한 order n^3도 되죠.
그렇지만 약간 부족한 표현이라고 할 수 있습니다.
자주 사용할 일은 없을 것입니다.
그러나 유용하기는 하죠. 지난 시간에 봤던 것처럼,
때때로 보게 될 경우가 있을 것입니다.
앞으로 어느 곳에서든 볼 수 있죠.
요점은 이것들이 집합 안에서 몇몇 함수들을 대표한다는 것입니다.
이것은 덜 직관적이지만, 좀 미묘합니다.
좌변의 이 식이 의미하는 것은 무엇일까요?
같은 것을 의미하죠. 그러나 ‘=’이 의미하는 것에는 약간의 관습이 있습니다.
그리고 이것이 ‘=’ 표시가 비대칭인 이유이죠.
‘=’을 “is"라고 읽어주면 됩니다.
우변에 있는 모든 것들이
좌변에 있는
몇몇의 것들과
‘=’을 의미할까요?
n^2 + O(n)의 몇몇은 O(n^2)입니다. 그러나 그 역은 성립하지 않아요.
그래서 약간 비대칭적이라고 하는 것입니다.
이것에 대해 생각하면, 매우 직관적이라고 생각하지만,
그래도 약간 복잡한 생각을 필요로 하기 때문에 조심해야 합니다.
이것은 좌변에서의 매크로의 확장을 이야기 하고 있습니다.
여기는 f(n)이 되어야 하고요.
우변에는 ‘=’을 만족하는 매크로의 확장이 있습니다.
만약 ‘=’표시의 관계를 가진 체인이 있다면,
“is"의 체인들이요,
그러면 그 제일 첫 번째 것은 가장 마지막 것과 같거나 작게 될 것입니다.
그래서 일반적으로 하는 방식으로
‘=’로 연결해 갈 수 있을 것입니다.
좋습니다.
이것이 바로 빅 오 표기법입니다. 질문 있으신가요?
빅오 표기법은 upper bound를 표현하기에 좋습니다.
이제부터는 lower bound에 대해서도 이야기 해보도록 하지요.
알고리즘에서 우리는 보통 러닝 타임에서의 upper bound에 관심을 가집니다.
빅오 에서는 러닝 타임이 많아 봐야 n^2, n log n 같은 것들을 봤습니다.
그러나 때때로 적어도 어느 정도의 러닝타임을
가지는 함수들을 표현할 필요가 있습니다.
예를 들면 정렬은 어떤 모델에서
적어도 n log n 만큼의 시간은 요구하는 것을 볼 수 있습니다.
그래서 이것을 표현할 다른 표기법이 필요한 것입니다.
그리고 그 표기법이 바로 빅 오메가 표기법입니다.
빅 오메가 표기법은 매우 대칭적입니다.
여기에 집합의 정의를 적도록 하겠습니다.
적어도 c g(n)보다 크거나 같은 것을 의미하는 f(n)이 있는
f(n)= big Omega[g(n)]을 쓰도록 합니다.
단지 f와 g사이의 불평등한 관계를 반대로 바꾸는 작업을 하고 있습니다.
놀라울 것은 하나도 없지요.
그냥 그 부분만 바꿔 써주기만 하면 됩니다. 예를 한번 보겠습니다.
이제 좀 더 어려워 질 거예요,
root n = big Omega(log n).
그리고 여러분은 n이 충분히 클 때, root n은 적어도
log n 만큼은 된다 라고 읽어주시면 됩니다. 오메가는
크거나 같은 것이라고 볼 수 있죠. 표기법들을 비교하여 설명 드리도록 하겠습니다.
여기 빅 오가 있고, 빅 오메가가 있습니다.
이것은 작거나 같고, 이것은 크거나 같습니다.
조금 후에 여기에
더 추가해서 설명해 드리겠습니다.
우리가 가지고 있는 일반적인 연산자들을 사용하는 것은 좋습니다.
우리는 보통 엄밀하게 작고, 크고, 같은 표시들을 사용합니다.
그리고 상수와 낮은 차수의 항들을 무시하는
점근적 세계에서 우리는 이러한
약간의 아날로그들을 원합니다. 예를 들면, big Theta[g(n)],
쭉 통과해서 그리는 것이 아니라
중간에 수평 선(bar)를 그려줘야 합니다.
제가 그리스어를 지어낸 것이 아니고, 원래 그렇게 씁니다.
Theta는 작거나 같고,
크거나 같은 것을 의미하고,
그래서 두 집합, 빅 오와 빅 오메가의
교집합 부분이 됩니다.
이것은 일종의 등호(=) 같지만, 사실 매우 다릅니다.
여러분은 n^2와 같은 것을 가지고 있습니다.
그것은 2(n^2)의 빅 theta 입니다.
왜냐하면 여러분은 정수 항들을 무시할 수 있기 때문입니다.
그렇지만 이 다른 모든 관계들은, 네, n^2 + O(n) = Theta(n^2) 입니다. 그러나 이것은 theta에
동의하지 않습니다. 왜냐하면 n의 제곱근이 정말로 log n 보다 점진적으로 크기 때문입니다.
그리고 n^2 대 n^3와 같은 몇 가지 다른 예들을 볼 수 있는데,
이것들은 T에 동의하지 않습니다.
그리고 우리는 작은 오 표기법과 작은 오메가 표기법이라는
엄격한 표기법을 가지고 있습니다.
여기에는 작은 theta가 없습니다. 왜냐하면
엄격한 동일성 대 엄격하지 않은 동일성의 표기법이 없기 때문입니다.
작은 오는 대략적으로 보다 작은 것에 부합하고,
작은 오메가는 보다 큰 것에 부합할 것입니다.
이것은 여러분이 앞으로 익숙해져야 하는 표기법입니다.
그리고 저는 여기서 이것을 정확히 정의하지 않을 것입니다.
왜냐하면 그것은 거의 정확하게 같은 것이기 때문입니다.
차이점은 정수 c와 n_o가 존재한다고 말하는 것 대신에,
여러분은 모든 정수 c에 대해서 정수 n_o가 존재한다고 말해야 합니다.
F와 g 사이의 관계, 즉 이 부등식은 단지 1을 위해서가 아니라
모든 c를 위해 있어야 합니다. 그리고 n_o는 이제 c에 의존합니다.
여러분은 정말로 n이 충분히 크다고 가정할 수 있습니다,
그러나 이것은 여러분에게 엄격한 부등식을 줍니다.
여러분이 여기에, g 앞에 어떤 정수를 집어넣든,
우리가 작은 오를 하고 있다고 말해봅시다, f는 충분히 큰 n에 대하여
c 곱하기 g 보다 여전히 작을 것입니다.
우리는 몇 가지 랜덤한 예들을 가지고 있습니다.
우리는 다시 정수들을 무시할 것입니다.
충분히 큰 n에 대하여 n^2는 항상 n^3 보다 작습니다.
그리고 그것은 여기서 약간 미묘합니다. 제가 말하려고 하는 것은
이와 같은 것을 증명하기 위해, 그것은 여러분이 그것을 약간 조작한 후에
직관적이 될 것 입니다. 여러분은 c의 관점에서
n_o가 무엇인지 알아내야 합니다. 저는 그것이 2/c 같은 것이라고 생각합니다.
만약 우리가 작거나 같은 것을 가지고 있다면, 그것은 맞을 것입니다.
Long n이 적어도 이렇게 크다면, c가 얼마나 작든,
여러분은 여기서 c에 대해 생각해야 합니다,
여기서는 입실론 입니다. 보통의 입실론과 델타에서요.
C가 얼마나 작아지든, 여전히 저는 n^3의 관점에서 n^2를 묶을 수 있습니다,
upper bound 이지요 그러나 여러분이 theta를 가지고 있을 때면 언제든,
여러분은 이 관계들을 다 가지지 않을 것입니다.
예를 들어, ½n^2 = Theta(n^2) 이고,
그것은 작은 o(n^2)가 아닙니다. 그리고 그것은 작은 omega(n^2)도 아닙니다.
왜냐하면 그것은 엄격히 정확히 n^2이기 때문입니다.
여러분이 여러분의 문제 세트에서 보게 될 바대로 몇 가지 지저분한 행동들이 있음에도 불구하고,
여러분은 이것 밖에서 오더 관계를 알 수 있을 것입니다.
점근 표기법에 대하여 질문 있나요?
빨리 설명한 것 같군요. 이제 우리는 몇 가지 recurrence들을 풀기 위해
그것을 사용할 것 입니다. 비록 우리가 오늘 그것을 그리 많이 사용하지 않았을지라도,
우리는 수요일에 그것을 많이 사용할 것 입니다.
좋아요.
우리는 오늘의 두 번째 주제로 넘어갈 것입니다,
그것은 recurrence를 푸는 것 입니다. 여러분은 아마 전에
6.042 또는 여러분이 들었던 별개의 어떤 수학 수업에서든 recurrence를 풀었을 겁니다.
우리는 좀 더 해볼 것입니다
여기에 몇 가지 기술들이 있습니다.
그것은 재귀 알고리즘을 위해 부분적으로 유용한 것입니다,
그리고 우리는 수요일에 그것들을 대부분 보게 될 것입니다.
Recurrence를 풀기 위해 우리는 여기서 세 가지 주요한 메소드들을 사용할 것입니다.
첫 번째는 대입 메소드입니다.
Recurrence를 풀기 위한 일반적인 과정은 없습니다.
Recurrence를 풀기 위한 좋은 알고리즘도 없습니다,
불행히도. 우리는 단지 몇 가지 기술들을 가지고 있습니다.
그것들 중 몇 가지는 일부 시간에 작동합니다,
그리고 만약 여러분이 운이 좋다면 여러분의 것이 여러분의 recurrence에 작동할 것입니다,
그러나 그것은 적분을 푸는 것과 같은 것입니다.
여러분은 그것들 중 몇 가지를 알아야 합니다,
여러분은 그것들을 풀기 위해 다양한 메소드들을 알아야 합니다. 여러분이 옳은 답을 가지고 있는지
확인하는 것은 보통 쉽습니다. 적분과 달리,
여러분은 차별화합니다, 그리고 '오, 내가 옳은 답을 가졌군.' 이라고 말합니다.
그리고 그것은 대입 메소드에 필수적인 생각입니다.
대입 메소드는 항상 작동합니다, 그러나 불행히도 스텝 1에서 답을 추측해 보세요.
그리고 여러분은 그것을 올바르게 추측해야 합니다.
그것은 그 문제를 더 어렵게 만듭니다.
여러분은 그것을 완벽하게 추측할 필요는 없습니다.
여러분은 정수 항을 알지 못한 채 보통 벗어날 수 있습니다,
그것은 좋은 것입니다. 왜냐하면 우리는 정수 항들에 대해
정말로 신경 쓰지 않기 때문입니다. 여러분은 형식을 추측합니다.
여러분은 오, 그것은 대략 n^2 일거야 라고 말합니다, 그리고 그것은
아마 어떤 정수 곱하기 n^2일 겁니다. 그래서, 여러분은 그것을 추측합니다.
우리는 정수들을 알아낼 것입니다.
여러분은 recurrence가 이 bound를 도입에서 만족시키는지
입증하도록 노력합니다, 그리고 그것이 핵심입니다.
대입은 도입을 사용합니다. 그리고 그것으로부터
여러분은 보통 공짜로 정수들을 얻습니다. 여러분은 이것이 작동하도록 하기 위해
어떤 정수가 있어야 하는지 알아 냅니다.
그래서, 이것이 일반적인 생각입니다. 여러분은 이것의 몇 가지 예들을 볼 것입니다.
사실, 몇 번 같은 예들이 있습니다.
불행히도,
이것은 여러분이 뭐라고 부를지 모르겠네요.
이것은 알고리즘입니다, 그러나 그것은 옳은 답을 알고 있는
신탁을 사용합니다. 그러나 때때로 그것은
답을 추측하기 너무 어렵습니다.
만약 여러분이 이 recurrence를 보게 되면, T(n) = 4T(n/2) + n 입니다,
우리는 함축적으로 어떤 정수의 T의 기본적인 몇 가지 경우들을 항상 가지고 있습니다.
보통 1은 정수입니다, 그래서 우리는
기본적인 경우에 대하여 정말 신경 쓰지 않아도 됩니다.
항상 그런 알고리즘에 대해서요. 그리고 우리는 이것들을 풀길 원합니다.
답이 무엇인지 아는 학생 있나요?
이 recurrence를 푸는 방법을 이미 알고
있지 않는 사람이 이상적입니다.
좋아요. 이 recurrence를 푸는 방법을
얼마나 많은 학생들이 알고 있죠? 몇 명 있군요, 네.
그리고, 남은 학생들 중에, 추측할 수 있나요?
만약 여러분이 여기서 무엇이 진행되는지 본다면, 여기서 여러분은 T(n/2)를 가집니다.
크거나 같은 이라는 용어를 무시합시다.
우리는 여기서 n/2를 가집니다. 만약 우리가 double n 과 T(n) 을 가지면
우리는 그 값과 4를 곱합니다. 그리고 나서 이 추가적인 것이 있습니다,
그러나 그것은 그리 많이 중요하지 않습니다.
여러분이 4의 인자로 결과를 구할 때
여러분은 어떤 함수를 알고 있나요? 네?
n/2 입니다. 여러분은 n/2를 생각해야 합니다
그러면 여러분은 맞을 겁니다. 그러나 우리는 아직 n/2라는 것을 증명하지 않을 겁니다.
더 간단한 것을 증명해 봅시다. 왜냐하면 그것이 기껏해야
n/2라는 것을 증명하는 것은 약간의 고통이라는 것이 드러났기 때문입니다.
우리는 몇 분 안에 알게 될 것입니다.
그러나 먼저 T(n) = O(n^3) 를 추측해 보세요.
왜냐하면 그것은 도입에 의해 증명하기 더 쉬울 것이기 때문입니다.
여러분은 쉬운 경우에, 그것이 어떻게 되는지 알게 될 것입니다, 그리고 나서 우리는 실제로
옳은 답을 얻게 될 겁니다, 나중에요, 그 답은 n^2 입니다.
저는 증명할 필요가 있군요. 제가 하려고 하는 것은
T(n)이 어떤 정수 곱하기 n^3라는 것입니다,
그래서 저는 약간 더 정확해질 것입니다. 저는 대입 메소드에서 빅오 표기법을 사용할 수 없습니다
그래서 저는 그것은 정수를 사용하는 것으로 확장해야 합니다.
저는 여러분에게 왜 그런지 약간 보여줄 것입니다,
그러나 제가 여러분에게 빅오 표기법을 사용하지 않는 것에서
무엇이 중요한지 높은 수준에서 말해줄 겁니다. 빅오 표기법은 여러분이 빅오 관계의
한정된 체인을 가지고 있다면 훌륭합니다.
n^2 는 big O(n^3) 이고 big O(n^4) 이고 big O(n^4) 입니다.
그것은 항상 옳습니다. 그래서 여러분은 n^2 가 big O(n^4) 라는 것을 알게 됩니다.
그러나 만약 여러분이 이 관계들의 무한정한 체인을 가지고 있다면,
첫 번째 것은 마지막 것의 빅오가 아닙니다.
여러분은 매우 신중해야 합니다.
예를 들어, 이것은 강의 노트와 별개로 전반적인 것입니다.
여러분이 n = O(1) 라는 것을 증명하길 원한다고 가정해보세요.
이것은 훌륭한 관계입니다.
만약 그것이 옳다면, 모든 알고리즘은 정수의 러닝 타임을 가질 것입니다.
이것은 옳지 않습니다.
Wayne's World 표기법에서가 아니라요. 여러분은 기본적인 경우가 1 = O(1) 이라고 말함으로써
“도입에 의해 이것을 증명하는 것”을 할 수 있습니다.
네, 이것은 맞습니다. 그리고 나서 또한 도입 단계입니다,
만약 제가 그 n-1을 알고 있다면요, 그래서 n-1 = O(1) 이라는 것을 가정해 봅시다,
자, 그것은 n이 (n-1) +1 인 것을 함축하고 있습니다.
만약 이것이 O(1) 이고 1 = O(1) 이면, 전체적인 것은 O(1) 입니다.
그리고 그것은 맞습니다. 만약 여러분이 (n-1) = O(1) 이고 1 = O(1) 이라는 것을 안다면,
그것들의 합은 또한 O(1) 입니다, 그러나 이것은 틀린 증명 입니다.
여러분은 빅 오들로 인도할 수 없습니다.
여기서 일어나고 있는 것은 여기 안에 함축된 정수들이 변하고 있다는 것 입니다.
여기서 여러분은 1의 빅오를 가집니다,
여기서 여러분은 1의 어떤 빅오를 가집니다. 여러분은 아마
여러분이 이 관계를 할 때마다 항상 거기서 정수를 두 배로 해야 할 것입니다.
만약 여러분이 정수를 두 배로 하는 한정된 수를 가진다면,
큰 문제는 아닙니다,
그것은 단지 정수입니다.
그러나 여기서 여러분은 n을 두 배로 하고 그것은 좋지 않습니다.
정수는 이제 n에 의존하고 있습니다.
그래서, 우리는 정수를 씀으로써 이런 문제를 푸는 것을 피할 것입니다.
우리는 정수가 변하지 않는다는 것을 확실히 해야 합니다.
좋아요.
이제 저는 정수를 썼습니다.
저는 안전해야 할 것입니다. 그래서 모든 k에 대해 n 보다 작은 그것을 가정할 것입니다,
이제 저는 그것이 모든 k에 대해 n과 같다는 것을 증명해야 합니다.
저는 T(n)을 가지고 그것을 확장할 것입니다.
저는 분명한 일을 할 겁니다.
저는 이 T(n)을 확장하는 recurrence를 가지고 있습니다.
그리고 나서 그것은 T(n/2)를 포함합니다. 그리고 저는 T(n/2)에 대한 어떤 사실을 알고 있습니다.
왜냐하면 n/2는 n 보다 작기 때문입니다.
그래서, 확장해 봅시다. T(n) = 4T(n/2) + n 입니다.
그리고 이제 저는 도입 가설로부터 이것에 대한 upper bound를 가집니다.
이것은 많아 봐야 4 곱하기 c 곱하기 세제곱한 인수
더하기 n 입니다.
여기서 계속해 봅시다. 이것을 약간 확장해 봅시다.
우리는 2의 세제곱 분의 n 세제곱을 갖습니다. 2의 세제곱은 8입니다,
그래서 8분의 4는 2분의 1입니다. 그래서, 우리는 ½cn^3 + n 을 가집니다.
그리고 제가 이것이 되었으면 하는 것은, 제가 가려고 하는 아래에서,
이것이 기껏해야 cn3 이라는 것입니다.
그것은 제가 n을 위한 도입 가설을 재정립하기 위해
증명하려고 하는 것입니다. 그것이 어떤 경우에서인지 보기 위해,
제가 하려고 하는 것은 이것을 단지 제가 원하는 대로 쓰는 것입니다,
그래서 이것은 일종의 바라는 값, cn3,
제가 무엇을 원하지 않든 마이너스 입니다.
이것은 오차라고 불립니다. 이제 저는 실제로 이것을 알아 내야 합니다.
자 봅시다.
우리는 cn^3을 가집니다, 그러나 여기 단지 ½cn^3 이 있습니다,
그래서 저는 그것을 구하기 위해 ½cn^3을 빼야 할 필요가 있습니다.
그리고 나서 저는 플러스 n을 가지고 여기에 마이너스가 있습니다,
그래서 이것은 마이너스 n 입니다. 그리고 이것은 오차 입니다.
이것이 많아 봐야 이것이 되기 위해, 저는 오차가 음이 아니라는 것이 필요합니다.
이것은 만약 오차 부분이 0 보다 크거나 같으면,
매우 하기가 쉬운 것입니다.
왜냐하면 여기서 저는 c에 대해 컨트롤 할 수 있기 때문입니다.
저는 제가 무엇을 원하든 c를 고를 겁니다.
그리고, c가, 오, 모르겠네요, c가 적어도 2인한,
그리고 이것은 적어도 1 입니다. 그리고 나서 n^3 이
n 보다 크거나 같아야 합니다. 그리고 그것은 항상 그 경우 입니다.
예를 들어, 이것은 c가 적어도 1이면 맞습니다.
그리고 저는 n이 무엇인지가 중요하다고 생각하지 않습니다,
그러나 재미 삼아 n이 적어도 1이라고 해 봅시다.
그래서, 우리가 한 것은 T(n)이 많아 봐야 어떤 정수 곱하기 n^3 이라는 것이
증명됩니다. 그리고 그 정수는 1과 같은 것 입니다.
그래서, 그것은 upper bound 입니다. 그것은 타이트한 upper bound는 아닙니다.
우리는 사실 그것이 n^2 라는 것을 믿었습니다, 그리고 사실 그렇습니다,
그러나 여러분은 조금 신중해져야 합니다.
이것은 답이 n^3 라는 것을 의미하지는 않습니다.
그것은 단지 많아 봐야 n^3이 big O(n^3) 하는 것을 의미합니다.
그리고 이것은 도입에 의한 증명입니다.
이제, 기술적으로 저는 이 도입에 기본적인 경우를 놓아야 합니다.
그래서 약간 놓친 것이 있습니다.
기본적인 경우는 매우 쉽습니다. 왜냐하면 T(1)이 어떤 정수이기 때문 입니다,
그러나 그것은 일종의 영향을 미치는 것일 겁니다.
기본적인 경우에 T(1)은 어떤 정수입니다.
그리고 우리가 필요한 것은 그것이 많아야 c 곱하기 1의 세제곱,
즉 c라는 것입니다. 그리고 그것은 여러분이
c를 충분히 큰 것으로 선택하는 한 맞을 겁니다.
그래서, 이것은 만약 c가 충분히 큰 것으로 선택되었다면 맞습니다.
이제, 우리는 정수들에 대해 신경 쓰지 않습니다. 그러나, 핵심은
단지 약간 신중해져야 한다는 것입니다. 여기서 우리가 필요한 모든 것이
c가 많아 봐야 1이라는 것일 지라도 T(n)이 많아 봐야 1 곱하기 n^2 라는 것은 맞지 않습니다.
기본적인 경우가 작동하기 위하여,
c는 사실 100 또는 T(1)이 무엇이든 그 값이어야 할 수도 있습니다.
그래서, 저기서 약간 신중해져야 합니다.
그것은 값에 정말로 영향을 미치지 않습니다, 보통 그것은 영향을 미치지 않을 겁니다,
왜냐하면 우리가 여기서 매우 간단한 기본적인 경우를 가지고 있기 때문입니다.
좋아요, 그래서 O(n^2)의 타이트한 바운드를 증명해 봅시다.
저는 오메가 바운드를 증명하지 않을 겁니다, 그러나 여러분은
대입 메소드를 이용하여 오메가 n 제곱을 증명할 수 있습니다.
저는 지금 n 제곱의 upper bound를 증명하는 것에 만족할 것입니다.
증명해 봅시다. T(n)은,
이것은 같은 recurrence 입니다, 저는 그것이 O(n^2) 라는 것을
증명하고 싶습니다. 저는 같은 일을 할 것입니다.
그리고 저는 좀 더 빠르게 쓸 것입니다.
왜냐하면 이것은 기본적으로 복사하는 것이기 때문입니다.
지금을 제외하고, 3 대신에 저는 2를 가집니다.
그리고 T(n) = 4T(n/2) + n 입니다. 저는 이 T(n/2) 를 확장합니다.
이것은 많아 봐야 4c(n/2)^2 + n 입니다. 그리고 이제, 2의 제곱 대신에,
저는 2의 제곱을 가집니다, 그것은 4 입니다.
4는 약분 됩니다. 저는 cn^2 + n 를 얻습니다.
그리고 만약 여러분이 이것을 바라는 대로 마이너스 오차라고 쓰길 선호한다면,
저는 cn^2 - (-n) 라고 합니다. 그리고 저는 이것이 음이 아니길 원합니다.
그리고 마이너스 n이 음이 아니라는 것은 어렵습니다.
만약 n이 0이라면 우리는 행복합니다,
그러나 불행히도 이것은 n에 있어서 도입입니다.
그것은 모든 n에 대하여 1 보다 같거나 클 것입니다.
이것은 cn^2 보다 작거나 같지 않습니다.
이것을 O(n^2) 과 같다고 쓰려는 유혹에 주의하세요.
cn^2 - (-n), 자, 이것들은 모두 오더 n 입니다,
또는 이것은 오더 n 입니다,
이것은 오더 n 제곱입니다.
확실히 이것은 O(n^2) 입니다, 맞습니다,
그러나 이것은 도입을 완벽하게 하지 않습니다.
도입을 완벽하게 하기 위해, 여러분은 이 정수 c를 가지고
n을 위한 도입 가설을 증명해야 합니다.
여기서 여러분은 c + 1 과 같은 정수 c를 가질 겁니다,
그것은 좋지 않습니다. 이것은 옳지만 쓸모가 없습니다.
이것은 도입을 끝내지 못합니다, 그래서 여러분은 그것을 무시할 수 있습니다.
이 증명은 효과가 없습니다.
이것은 일종의 짜증나는 것입니다, 왜냐하면
우리가 진심으로 T(n) = n^2 라고 느끼거든요.
이것을 고쳐야 하는데 여러분은 T(n)을 약간 다른 형태로 표현할 필요가 있습니다.
이것은, 다시, 신의 영감 입니다.
그리고, 만약 여러분이 신성과의 좋은 연결을 가지고 있다면,
여러분은 모두 된 것입니다.
그러나 그것은 단순한 인간인 나머지 우리들에게는 약간 더 어렵습니다.
그것은 판명되었지요,
그리고 아마 여러분은 이것을 추측할 수 있습니다,
그 생각은 우리가 도입 가설을 강화하길 원한다는 것 입니다.
우리는 이것을 상대적으로 약간 것으로 가정했습니다,
T(k)는 어떤 정수 곱하기 k^2 보다 작거나 같습니다.
우리는 정수가 무엇이었는지 알지 못합니다, 그것은 괜찮아요,
그러나 우리는 더 낮은 오더 항이 없었다는 것을 가정했습니다.
저는 더 낮은 오더 항에서 보길 원합니다.
아마 그것들은 역할을 할 겁니다.
그리고 만약 여러분이 이 진행을 보게 된다면,
여러분은 오, 내가 n^2와 같은 것을 가지고 정수들은 매우 타이트하군 이라고 말할 겁니다.
제가 말하려고 하는 것은 4는 약분되고,
c는 그냥 유지 된다는 것입니다. 제가 어떻게
더 낮은 오더 항 더하기 n을 제거할까요? 자, 아마 저는 여기서
일차항을 뺄 수 있습니다 그리고, 만약 제가 운이 좋다면,
그것은 이것과 함께 약분될 겁니다. 그것은 우리가 이 점에서 가지고 있는
모든 직관입니다. 그것은 작동하는 것으로 드러났습니다.
우리는 T(n)을 봅니다 그리고 이것은 늘 그렇듯이 4T(n/2) + n 입니다.
이제 우리는 약간 더 지주분한 형태로 확장할 겁니다.
우리는 4[c_1*(n/2)^2 - c_2*(n/2)] + n 을 가집니다.
이 부분은 같습니다 왜냐하면 4는 다시 약분되기 때문입니다.
그래서, 우리는 c_1*n^2 를 갖는데, 이것은 좋습니다.
제가 말하고자 하는 것은 그것이 일종의 우리가 원하는 형태라는 겁니다.
그리고 나서 우리는 어떤 것 곱하기 n을 가집니다, 그래서 그것을 알아내 봅시다.
우리는 플러스 1 곱하기 n을 가집니다, 그래서 그것을 2 곱하기 n 분의 1
빼기 c_2 라고 씁시다. 웁스, 잘못 됐군요.
4 곱하기 2가 있습니다, 사실 2는 올라갑니다.
제가 확인을 해 보겠습니다. 맞습니다.
좋아요. 이제 우리는 이것을 바라는 대로
마이너스 오차라고 쓸 수 있습니다. 그리고 우리는 여기서 약간 신중해져야 합니다
왜냐하면 이제 우리는 더 강한 증명할 도입 가설을 가지고 있기 때문입니다.
우리는 그것이 많아 봐야 c_1*n^2 라는 것이 필요하지 않습니다,
그것은 여기서 괜찮습니다
왜냐하면 우리는 큰 c_2를 고를 수 있기 때문입니다,
그러나 우리가 정말 필요로 하는 것은 c_1*n^2 - c_2*n 입니다, 그리고 나서 어떤 다른 것을
뺍니다. 이것은, 다시
바라는 마이너스 오차 입니다. 그리고 마이너스 오차는,
봅시다, 우리는 마이너스 1을 가지고 있습니다 그리고 우리는 마이너스 c_2를 가지고 있습니다.
그것은 행복해 보이지 않습니다. 플러스 c_2, 고마워요,
왜냐하면 그것은 다시 정말 음으로 보이기 때문입니다.
그것은 플러스 c_2 입니다. 저는 제 표시를 할 것입니다,
여기 마이너스가 있고 여기 마이너스가 있습니다
그래서 해 봅시다. 다시, 저는 제 오차가 0 보다 크거나 같아지길 원합니다.
그리고 만약 제가 그것을 가진다면
저는 이 귀납적인 인자를 만드는 것에서 다 될 것입니다.
오피스 시간은 이번 주부터 시작되었어요, 여러분이 오고 싶다면요.
24 건물의 어떤 방에서 진행됩니다,
그것은 대략 여기와 Stata 사이의 중간 지점 정도 입니다,
특별한 이유는 없어요.
그리고 여러분은 오피스 시간에 대한 자세한 내용을 웹 페이지에서 볼 수 있습니다.
계속해 봅시다,
언제 c_2 – 1 가 0 보다 크거나 같아 질까요?
자, 그것은 c_2 가 최대 1일 때 옳습니다, 그것은 큰 문제가 아닙니다.
다시, 우리는 우리가 무엇을 원하든, 정수를 고를 것입니다.
그것은 어떤 정수의 선택을 가져야 합니다.
그래서, 우리는 c_2 가 1 보다 크거나 같다고 해둘 수 있습니다.
그러면 우리는 행복합니다.
그것은 이 모든 것이 c_1*n^2 - c_2*n 보다 작거나 같다는 것을 의미합니다.
만약 c_2가 1보다 크거나 같다면요. 그것은 여기서 재미있군요.
이것은 도입을 끝냅니다, 적어도 도입 단계에서요.
우리는 이제 c_1의 어떤 값에 대해서도,
제공된 c_2가 적어도 1 이라는 것을 증명했습니다.
우리는 c_1이 사실 충분히 커져야 한다는 것에
더 신중해 져야 합니다. 어떤 특별한 이유가 있나요?
c_1 은 정말로 음이 아닌 것이 낫습니다, 정말로요.
c_1은 이 것이 작동하기 위해서는 양이어야 합니다,
그러나 그것은 심지어 양의 것 보다 커져야 합니다. 미안해요.
제가 좀 빨리 했던 거 같군요, 여러분에게 질문을 하지 않았어요.
이제 여러분은 잡혔습니다. 네?
기본적인 경우 때문에요, 정확해요.
그래서, 기본적인 경우는 다음과 같습니다. T(1)은 c_1 곱하기 1 나누기 마이너스 c_2 입니다,
우리는 그것이 많아 봐야 이것이라는 것을 증명하길 원합니다,
그리고 T(1)은 우리가 가정했던 어떤 정수입니다.
우리는 c_2 보다 충분히 큰 c_1을 고를 필요가 있습니다,
사실, 그래서 c_2는 적어도 1이어야 합니다.
c_1은 이것이 100이라면 적어도 101이어야 할 것입니다.
이것은 c_1이 충분히 크다면 옳을 것입니다.
그리고 c_2에 관하여 충분히 크다는 것을 의미합니다.
여러분은 좀 더 신중해져야 합니다,
그러나 이 경우에 그것은 중요하지 않습니다.
대입 메소드에 대하여 질문 있나요?
그것은 세 번 같은 예였습니다.
마지막에, 그것은 우리가 옳은 답을 가졌다는 것으로 드러났습니다.
그러나 우리는 그것을 찾기 위해, 답을 알아야 했었습니다,
그것은 약간 고통스러웠지요. 그것은 어떤 절차에 의해
답을 알아내는 것보다 더 좋을 것입니다,
그리고 그것은 우리가 이야기할 다음 두 기술일 겁니다. 네?
여러분은 어떻게 lower bound를 증명하나요?
저는 그것을 이 recurrence에 대해 시도하지 않았습니다,
그러나 여러분은 정확히 같은 형태로 할 수 있어야 합니다.
T(n)이 c_1*n^2 - c_2*n 보다 크거나 같다고 해 보세요.
저는 특정한 형태가 작동할 것이라는 것을 검사하지 않았습니다,
그러나 저는 그것이 작동한다고 생각합니다.
이 다른 메소드들은, 어떤 면에서,
여러분에게 upper와 lower bound를 줄 것입니다.
만약 여러분이 조금 신중해진다면요. 그러나, 정말로 검사하기 위해서,
여러분은 꽤 많이 대입 메소드를 해야 할 것입니다.
그리고 여러분은 그것으로 연습을 하게 될 것입니다.
보통 우리는 upper bound에 대해서만 신경 씁니다.
이와 같은 upper bound를 증명하는 것은 우리가 집중하게 될 것입니다,
그러나 때때로 우리는 lower bound가 필요합니다.
매칭하는 lower bound를 증명하는 것에 의에 여러분이 옳은 답을
가지고 있다는 것을 아는 것은 항상 좋습니다.
우리가 이야기 해 볼 다음 메소드는 재귀 트리 메소드 입니다.
그리고 그것은 recurrence를 더하는 특정한 방법입니다,
그리고 그것은 제가 가장 좋아하는 방법입니다.
그것은 보통 작동합니다. 그것은 그에 대한 훌륭한 것이에요.
그것은 여러분에게 직관을 공짜로 제공합니다.
그것은 답이 무엇인지 여러분에게 매우 많이 알려 줍니다.
그것은 약간 엄격하지 않습니다,
이것은 약간 고통스러워요, 그래서 여러분은 그것을 적용할 때 정말로 신중해야 합니다.
그렇지 않으면, 여러분은 틀린 답을 얻게 될 것입니다.
왜냐하면 그것이 점, 점, 점들을 포함하기 때문에,
우리가 가장 좋아하는 세 문자들인데,
그러나 점, 점, 점들은 항상 엄격하지 않습니다. 그러니 신중하세요.
기술적으로, 여러분이 해야 하는 것은
재귀 트리 메소드를 이용하여 답이 무엇인지 알아내는 것입니다.
그리고 그것이 실제로 맞는지 대입 메소드로 증명하세요.
보통 그것은 필수적이지는 않지만,
여러분은 적어도 여러분의 마음속에 그것이 엄격하게 요구된다는 것을 새기고 있어야 합니다.
그리고 아마 여러분이 풀 첫 번째 recurrence는,
여러분이 그것을 그 방법으로 해야 합니다.
여러분이 정말 재귀 트리 메소드를 이해할 때,
여러분은 약간 더 대충할 수 있습니다 만약 여러분이 옳은 답을
가지고 있다는 것을 정말 확신한다면요. 예를 들어 봅시다.
우리는 지난 시간에 그것이 왜 n log n이었는지 직관 대로 합병 정렬로
매우 간단히 재귀 트리를 보았습니다.
그리고, 만약 여러분이 재귀 트리 메소드로 했던 것과 같은 예를 든다면,
그것은 매우 간단합니다.
우리 삶을 힘들게 하기 위해, 복잡한 재귀를 해 봅시다.
여기서 우리는 우리가 어떤 알고리즘을 가지고 있다고 상상해 봅시다.
그것은 문제 사이즈 n으로 시작합니다,
그것은 재귀적으로 n/4 사이즈의 문제를 풉니다.
그것은 그리고 n/2 사이즈의 문제를 풉니다.
그리고 그것은 재귀적이지 않은 일 없이 n^2의 일을 합니다.
그것이 무엇이죠? 제가 말하는 것은 그것이 조금 덜 명확하다는 것입니다.
우리가 하려고 하는 것은 그림을 그리는 것입니다,
그리고 우리는 트리 형태에서 그 재귀를 확장해갈 겁니다,
그리고 나서 모든 것을 더합니다.
우리는 일반적인 그림을 원합니다, 그리고 재귀 트리 메소드에서 일반적인 원칙은
우리가 이것을 그림으로 그리는 것입니다.
T(n)은 n^2, T(n/4), T(n/2)의 합입니다.
이것은 합을 쓰는 이상한 방법이지만
그것을 이렇게 쓰면 안되나요?
이것은 트리가 될 것입니다.
그리고 그것은 이 두 개의 각각을 재귀적으로 확장함으로써 트리가 될 것입니다.
저는 T(n)을 이것으로 확장함으로써 시작합니다,
그리고 나서 저는 모든 것을 확장하고, 확장하고, 확장해 나갈 것입니다.
한 단계 더 해봅시다. 우리는 n^2, T(n/4), T(n/2) 를 가집니다.
만약 우리가 한 번 더 확장한다면,
이것은 n^2 더하기 두 가지가 될 것입니다.
첫 번째 것은 (n/4)^2가 될 것이고, 두 번째 것은
(n/2)^2가 될 것입니다. 그것들의 재귀 가지를 더하세요.
우리는 T(n/16)과 T(n/8)를 가집니다. 여기서 제 연산은 약합니다.
이것은 같을 겁니다, 그리고 이것은 T(n/4)이 되어야 합니다.
여러분은 영원히 계속합니다,
여러분이 T가 정수인 기본적인 경우로 내려갈 때까지 말입니다.
그래서, 저는 지금 어떤 단계를 뛰어 넘을 것입니다,
그리고 점, 점, 점을 말합니다.
이것은 여러분이 신중해야 하는 부분 입니다.
우리는 n^2, (n/4)^2, (n/2)^2 를 가집니다.
이제 이것은 매우 쉽습니다 왜냐하면 제가 이미 그것들을 다 했기 때문입니다.
(n/16)^2, (n/8)^2, 다시 (n/8)^2, (n/4)^2,
그리고 기타, 점, 점, 점,
여기 재귀의 많은 단계들이 있습니다.
아래에, 우리는 정수들의 가지를 얻을 겁니다.
이것들은 잎들입니다.
저는 얼마나 많은 잎들이 있는지 알고 싶습니다.
한 가지 도전은, 트리에 얼마나 많은 잎들이 있을 수 있습니까?
이것은 약간 미묘합니다,
합병 정렬 또는 우리가 풀었던 이전의 recurrence들과는 다릅니다.
여기 잎들의 수는 약간 재미있습니다 왜냐하면
우리는 다른 속도로 순환할 것입니다. 이 트리는 이 트리 보다 매우 작아질 겁니다.
그것은 더 작은 깊이를 가질 겁니다
왜냐하면 그것은 이미 (n/16) 아래로 했기 때문입니다.
여기서 그것은 (n/4) 아래로만 갑니다.
그러나 이 재귀 트리에 얼마나 많은 잎들이 있습니까?
제가 필요한 모든 것은 upper bound입니다, 어떤 합리적인 upper bound가 필요합니다.
저는 여러분에게 그것이 기껏해야 T(n^10) 이라고 말할 수 있습니다, 그러나 그것은 약간 합리적이지 않습니다.
그것은 n 보다 작아야 합니다.
왜 그것은 n 보다 작습니까?
정확해요. 저는 n 크기의 문제로 시작했습니다.
그리고 저는 n/4와 n/2 문제로 재귀합니다.
재귀합니다.
제가 멈춘 곳으로 내려갈 때입니다. 그래서, n/4 + n/2 = ¾n 입니다,
이것은 n 보다 엄격하게 작습니다. 그래서, 분명히 모든 잎들의 수는
많아 봐야 n 입니다. 만약 제가 n과 같은 것으로 시작해서
그것의 4분의 1을 제거하고 재귀하면,
그것은 분명히 아래에서 n 보다 작을 겁니다.
그래서, 엄격히 n 잎들보다 작을 겁니다.
이 점에서, 저는 아무 흥미로운 것도 하지 않았습니다.
그리고 재귀 트리에서 두 번째 좋은 생각은
여러분이 이 트리를 단지 확장하지 않는다는 것입니다.
이것이 무엇과 같은지 보세요, 그리고, 하느님, 제가 어떻게 이것을 더하나요?
라고 말합니다. 여러분은 그것을 레벨 별로 더합니다.
그것이 유일한 다른 생각입니다. 그것은 보통 정말로 작동합니다,
정말로 잘 작동해요. 여기서 그것은 약간 복잡합니다
그리고 저는 n^2가 n^2인 것을 알아 내는 것을 생각해야 합니다.
그것이 첫 번째 레벨 입니다. 쉽습니다.
두 번째 레벨은, 제가 더 어렵게 생각해야 합니다.
세 부류의 수학자가 있습니다,
그들 중 누구는 더할 수 있고 누구는 그렇지 않습니다,
그리고 저는 여러분의 도움이 필요한 후자 입니다. 여러분은 이것들을 함께 더할 수 있나요?
그것은 어떤 것 분의 n^2 입니다.
네? (5/16)n^2 입니다.
이제 저는 여러분의 도움이 정말 필요합니다.
저는 제가 할 수 있었던 모든 것을 생각합니다, 그러나 이것은 약간 더 어렵습니다.
저는 여러분이 그것을 계산하는 동안 제 노트를 볼 것입니다.
답이 나왔나요? 73/256.
그것을 확신할 수 있는 학생 있나요? 그것은 저에게 좀 높아 보이는군요.
73은 저에게 옳게 들리지 않아요. 64?
더 가까워졌네요. 우리가 이것을 옳게 얻는다는 것은 사실 중요합니다.
256은 맞습니다. 제가 말할 수 있어요.
여러분 모두 16^2 = 256 라는 것을 알아야 합니다.
우리는 컴퓨터 과학자들입니다.
25, 좋아요. 우리는 25라고 말하는 두 명의 학생이 있네요,
그러므로 민주주의에 의해 그것은 맞습니다.
25는 또한 제 노트에서 말하고 있는 것 입니다,
저는 그것을 집에서 계산했었거든요. (25/256)n^2 는 옳은 답입니다.
이제, 여러분은 이 진해에 대하여
마술과 같은 것을 주목했었나요?
그것은 매번 제곱합니다.
그리고, 만약 우리가 이것을 더하면, 여러분은 그것을 무엇이라고 부르죠?
등비 급수, 매우 좋아요.
그래서, 그것은 이것이 등비라는 것으로 드러났습니다.
그리고 우리는 등비 급수를 계산하는 방법을 알고 있습니다,
여러분은 해야 하고요.
우리는 n^2를 시작했습니다. 우리는 아래에서 그것을 알고 있습니다,
자, 이것은 단계가 아닙니다, 우리는 n과 같은 것을 얻습니다,
그러나 우리는 기하학적으로 감소할 것입니다.
그래서, 합은, 즉 recurrence의 답은
이 트리에서 모든 수들의 합입니다.
만약 우리가 그것을 레벨 별로 다 다하고 모든 레벨을 더하면
그것은 우리에게 답을 줄 것입니다.
이것은 단계 별로 계산 된 합입니다.
그것은 그것을 계산하는 귀여운 방법입니다.
그것은 보통 여러분에게 기하학적인 답 같은 좋은 답들을 줍니다.
우리는 n^2(1 + 5/16 + 25/256 + ...) 를 가집니다.
그리고, 만약 우리가 운명을 믿는다면 그리고 우리가 이 세 수의 recurrence를 본다면,
우리는 우리가 옳은 답을 가지고 있다는 것을 알 수 있습니다.
일반적으로, 그것은 recurrence가 될 것입니다.
그리고 그것은 계속 될 것입니다.
그것은 무한대로 계속 가지는 않습니다, 그러나 그것이 무한하게 간다고 가정해봅시다.
그것은 영원히 가는 upper bound가 될 겁니다.
이것은 항상 n^2 입니다
이제, 만약 여러분이 등비 급수에 대한 것을 한 가지 안다면,
여러분은 1 + ½ + ¼ 라는 것을 알아야 합니다. 만약 여러분이
2의 모든 제곱을 더하면 여러분은 2를 얻습니다. 우리는 컴퓨터 과학자들입니다.
우리는 적어도 2진 케이스를 알아야 합니다.
이것은 이진법으로 0.1111111를 쓰는 것과 같습니다,
사실 1.11111 입니다. 그리고 계속 11111은 1과 같습니다,
그래서 이것은 2입니다. 이것은 심지어 더 작습니다.
우리는 5/16을 가집니다, 그것은 2 분의 1 보다 작고
우리는 매번 제곱합니다, 그래서 이것은 2 보다도 작습니다.
여러분이 원한다면, 일반적인 등비 급수를 푸는 훌륭한 공식이 있습니다,
그러나 우리가 필요한 모든 것은 그것이 정수라는 것 입니다.
이것은 O(n^2) 입니다.
그것은 또한 O(n^2) 입니다. 그것이 O(n^2) 라는 것은 매우 분명합니다
왜냐하면 위에 있는 것이 n^2 이기 때문입니다.
그래서, n^2의 lower bound가 있습니다.
그리고 우리는 그것을 2의 인자 안에서 그것을 가집니다, 그것은 매우 좋은 것이에요.
여러분은 사실 더 좋은 인자를 여기서 얻습니다.
그래서, 그것은 재귀 트리 메소드 입니다.
그것은 여기서 좀 불안합니다 왜냐하면 우리가 이 점, 점, 점들을 가지고 있거든요,
그리고 우리는 그것이 기하학적이라고 믿습니다.
그것은 그것이 대부분 기하학적이라고 판명되었습니다.
여기서 문제는 없습니다. 저는 대입 메소드로 그것을 검사할 것입니다
왜냐하면 이것이 기하학적일 거라는 것이
저에게 분명하지 않거든요.
우리가 곧 보게 될 경우들에서, 그것은 더 명확해질 겁니다,
그래서 우리는 모든 것이 잘 작동하는 정리를 쓸 수 있습니다.
그리고 여전히, 좋습니다.
그래서, 그것은 재귀 트리였습니다.
우리가 이야기 할 하나의 메소드가 더 있습니다,
그리고 여러분은 필수적으로 그것을 재귀 트리 메소드의 응용으로 생각할 수 있습니다
그러나 그것은 더 정확하게 만들어졌습니다.
그리고 그것은 실제의 정리입니다, 반면에 재귀 트리는,
만약 점, 점, 점들이 분명하지 않으면, 여러분은 그것들을 검사하는 것이 좋습니다.
마스터 메소드에 대해 슬픈 부분은
그것이 매우 제한적이라는 겁니다.
그것은 recurrence의 특정 집합에만 적용됩니다.
그것은 T(n) = aT(n/b) + f(n) 이 되어야 합니다.
제가 그것을 f라고 부를까요? 네, 저는 그것을 f라고 부를 겁니다.
특별히, 그것은 제가 풀었던 모든 recurrence를 커버하지는 않을 겁니다
왜냐하면 저는 다른 사이즈의 두 다른 문재에서 재귀 했었기 때문입니다.
여기서, 여러분이 재귀 하는 모든 문제는 같은 사이즈여야 합니다.
하위 문제들이 있습니다.
이것을 생각하는 방법은 재귀 알고리즘입니다.
여러분은 하위 문제들을 가지고 있습니다. 그것들 각각은 n/b 사이즈이고,
그래서 총 비용은 이것입니다.
그리고 나서 여러분은 재귀적이지 않은 일 f(n)을 할 것입니다.
몇 가지 제약 조건이 있습니다. A는 적어도 1 이어야 하고,
적어도 1 재귀를 해야 합니다.
B는 엄격하게 1 보다 커야 합니다.
여러분은 문제를 더 작게 만드는 게 좋을 겁니다 그렇지 않으면
그것은 무한할 것입니다. 그리고 f는 좋은 특성을 가져야 합니다.
f(n)은 점진적으로 양이어야 합니다.
점진적으로 양이라는 것의 의미를 얼마나 많은 학생들이 알고 있죠?
아무도 없군요. 좋아요, 여러분은 교재를 읽지 않았군요.
좋습니다.
저도 그것을 읽지 않았습니다, 그러나 찰스에게 말하지 마세요.
그리고 그는 알 것입니다. 그리고 여러분은 점진적으로
양이라는 것이 무엇이라고 생각합니까? 우리가 할 수 있는 것은 더 좋습니다.
뭐라구요?
네, 그것은 충분히 큰 n에 대해 f(n)이 양인 것을 의미합니다.
이것은 f(n)이 n에 대해 0 보다 크다는 것을 의미합니다,
적어도 어떤 n_o에 대해세요, 어떤 정수 n_o에 대해서 그렇습니다.
결국 그것은 양이어야 합니다. 제가 말하는 것은, 우리는 그것이 n=1 일 때 마이너스 1인지 아닌지에 대해
신경 쓰지 않아도 됩니다, 그건 큰 문제가 아닙니다.
그것은 답에 영향을 미치지 않습니다.
왜냐하면 우리는 그 안의 점진적인 것에 대해서만 신경을 쓰거든요.
여러분이 그것을 이 형태의 recurrence에 주었던,
마스터 메소드는 여러분에게 답을 알려줍니다.
그것은 마스터 메소드에 대해 훌륭한 것입니다.
마스터 메소드에 대해 화나는 것은 그것이 세 경우를 가지고 있다는 것 입니다.
그것은 큽니다.
그것은 모든 다른 것들 보다 외우기 약간 더 깁니다
왜냐하면 다른 것들은 그냥 생각이거든요.
여기서 우리는 몇 가지 것들을 사실 기억할 필요가 있습니다.
제가 정리를 써 보겠습니다. 자, 아직 아니군요.
매우 간단한 생각이 하나 있습니다, 그것은 우리가
이 재귀적이지 않은 일 f(n)을 매우 특정한 함수 n^(log_b(a))과 비교하려는 것입니다.
왜 n^(log_b(a)) 인가요?
여러분은 나중에 알게 될 것입니다. 그것은 재귀 트리에서 잎의 수라는 것이 드러났습니다.
그러나 그것은 전조입니다.
그래서, 그것은 작거나 같거나 큽니다.
그리고 여기서 우리는 점진적이라는 것에 대해 신경 써야 합니다.
그리고 우리는 작거나 같거나 큰 것에 대하여 약간 더 소중히 해야 합니다.
여러분은 그것이 작은 오, 큰 Theta, 도는 작은 오메가를
의미한다고 생각할 지도 모릅니다.
그것은 정리가 모든 경우에 대해 유지 된다면 좋습니다,
그러나 그것은 약간의 차이가 있습니다. 케이스 1부터 시작해 봅시다.
케이스 1은 f가 더 작을 때 입니다. 그리고 그것이 작은 o가 아니라,
사실 더 작은 것 입니다. 그것은
n^(log_b(a)) 보다 다항적으로 더 작은 것이어야 합니다.
어떤 양의 입실론에 대하여,
러닝 타임은 다음과 같아야 합니다.
이것은 n^(log_b(a)) 보다 정말로 다항적으로 작습니다.
우리는 작은 오 케이스를 다룰 수 없습니다, 그것은 약간 너무 강합니다.
이것은 그것이 정말로 더 작다고 말하는 것 입니다.
그러나 답은 정말 간단합니다,
T(n) = Theta(n^(log_b(a))) 입니다.
좋아요. 그것은 케이스 1 입니다.
케이스 2는 f(n)이 n^(log_b(a)) 과 매우 같을 때 입니다.
그리고 매우 같다는 것은 다항의 로그 인자를 의미합니다.
이것은 로그 2의 n의 k 제곱입니다.
여러분은 이 표기법을 알아야 합니다.
예를 들어, k는 0이 될 수도 있습니다.
그리고 그것들은 정수 인자들과 같습니다, 어떤 k에 대하여
0 보다 크거나 같습니다. 보다 작은 것은 동작하지 않습니다,
그래서 k가 음이 아니라는 것은 정말 중요합니다.
그것은 아마 정수여야 합니다.
그것은 정수인지 아닌지는 사실 중요하지 않습니다,
그러나 여기서는 중요해요. 그것은 n^(log_b(a)) 곱하기 log n
또는 아무 것도 곱하지 않는 것 입니다, 무엇이든요.
다시, 해답은 여기서 쉽습니다. T(n) = Theta(n^(log_b(a))* lg^(k+1)(n)) 입니다.
아마 그것은 적어도 곱하기 log k 여야 합니다.
그것이 log k 더하기 1 이라는 것이 드러났습니다.
이것은 케이스 2입니다.
우리는 약간 더 복잡한 한 가지 케이스를 더 가지고 있습니다.
우리는 케이스 3을 위해 약간 더 가정할 필요가 있습니다.
그러나 케이스 3은 대략적으로 f(n)이 n^(log_b(a)) 보다 클 때 입니다.
그래서, 그것은 대문자 오메가여야 합니다,
여기 우리가 오메가를 사용하는 한 곳이 있습니다,
어떤 양의 입실론에 대하여 (n^(log_b(a)) + epsilon) 입니다. 그것은 단순히 큰 것이 아니라
다항적으로 큰 것이어야 합니다. 여기서 그것은 로그 인자를 키웁니다,
그리고 여기서 그것은 다항의 인자 입니다.
이 케이스에서,
우리는 f에 대하여 또 하나의 가정을 해야 합니다
왜냐하면 우리는 f가 얼마나 빠르게 커지는지에 대해 걱정하기 때문입니다.
우리는 여러분이 재귀로 내려가면서 f가 작아 진다는 것을 확실히 하길 원합니다.
그것은 여러분이 내려가면서 f가 작아지면
좋은 것입니다, 여러분이 그렇지 않으면,
다시, 무한대 또는 무엇이든 더하려고 노력해 보세요.
저는 왜 이것이 어떤 입실론에 대해서 0 보다 가장 큰지 압니다.
제가 하고 싶은 것은 만약 제가 recurrence,
이 T(n)을 가진다면,
f(n)은 af(n/b)와 다소 관련이 있어야 한다는 것 입니다.
제가 하고 싶은 것은, 재귀 트리의 위에 있는 그 f(n)이
다음 아래 레벨의 것 보다 커야 한다는 것 입니다.
다음 아래 레벨에서 모든 값들의 합은
어떤 정수 인자에 의해 더 커야 한다는 것입니다.
여기서 다음 아래 레벨은 커 봐야 1 – e 입니다,
그것은 1 보다 엄격하게 작은 것입니다,
윗 레벨에서 어떤 1보다 엄격히 작은 정수 곱하기 어떤 것 입니다.
저는 이것들이 제가 아래로 내려갈수록 점점 작아진다는 것을 확실히 해야 할 필요가 있습니다.
그리고 나서 T(n) = Theta[f(n)] 입니다.
그리고 이것은 정리입니다. 이것은 마스터 정리이고
또는 여러분이 부르고 싶은 대로 불러도 됩니다. 이것은 마스터라는 어떤 사람에 의해 이름 붙여진 것이 아닙니다.
이것은 단지 모든 메소드들의 마스터 입니다
왜냐하면 이것은 적용하기 매우 쉽기 때문입니다.
그것을 몇 번 적용해 봅시다. 그것은 모든 것에서 즉시 가집니다.
그리고 저는 여러분에게 여러분이 재귀 트리를 본다면
이것이 옳은 것이라는게 정말 놀라운게
아니라는 것을 알기 위한 증명의 스케치를 줄 것입니다.
그러나 첫 번째로 그것을 사용하려고 시도해 봅시다.
예를 들어, 우리는 T(n) = 4T(n/2) + n 을 가질 수 있습니다.
이것은 a이고, 이것은 b이고
이것은 f(n) 입니다. 우리가 계산해야 하는 첫 번째 것은
n^(log_b(a)) 입니다. 이것은 제가 할 수 있는 것 입니다.
로그 2의 4 입니다. 제가 할 수 있어요.
이것은 n^2 입니다. 좋아요, 그래서 f(n)은 n^2 보다 작거나 큽니까?
자, f(n) = n 입니다.
n^2는 다항의 인자에 의해 명백히 큽니다.
그래서, 우리는 케이스 1에 있습니다. 답이 무엇이죠?
네, n^2 입니다. 그것은 T(n^(log_b(a))) 인데,
여기서 n^2 입니다. 약간 다른 것을 해 봅시다.
저는 a와 b는 같게 두고 f를 바꿀 것입니다.
T(n) = 4T(n/2) + n^2 라고 해 봅시다.
n^2가 정수가 되면서 n^2는 점진적으로 같습니다.
답이 무엇이죠? 이것은 케이스 2 입니다.
이것은 약간 더 어렵습니다.
이 예에서 k는 무엇입니까? 0 입니다. 답은 무엇이죠?
n^2 log n 입니다.
좋아요. 그리고 몇 가지가 더 있습니다.
T(n) = 4T(n/2) + n^3. 답이 무엇이죠?
n^3 입니다. 이것은 케이스 3 입니다.
저는 이것이 매우 지루하다는 것을 압니다. 이 점에서 우리는
이것을 어리석은 정리에 적용할 것입니다. n^2/lg n 은 어떻죠?
답은 무엇이죠? 좋아요.
이 케이스에서 아무도 답을 해서는 안 됩니다.
그것은 까다롭습니다. 저는 정확히 답을 잊어버립니다.
저는 그것이 log n 분의 n^2 log log n 와 같은 것이라고 생각합니다,
아닌가요? 오, 아니네요.
n^2 log log n, 맞습니다.
네. 그러나 여러분은 그것을 알지 못합니다,
그리고 이것은 마스터 메소드로부터 온 것이 아닙니다.
이것은 여러분이 풀어야 하는 것입니다,
아마 재귀 트리로 하는 것이 이것을 하는 좋은 방법이 될 겁니다,
그리고 여러분은 그것이 어떻게 가는지 알아야 할 로그들의
어떤 속성들을 알아야 합니다.
그러나 여기서 마스터 메소드는 적용하지 않습니다.
그리고 여러분은 다른 메소드를 사용해야 합니다.
좋아요. 제가 하고 싶은 마지막 것은
여러분에게 왜 마스터 메소드가 맞는지 알려주는 것입니다, 그리고 그것은
훨씬 더 직관적으로 만들어 줍니다, 특히 재귀 트리를 사용할 때,
왜 모든 것이 작동하는 지를요.
이것은 증명의 스케치입니다, 온전한 것이 아니에요.
여러분은 교재에서 증명을 읽어야 합니다.
제가 보여줄 것 보다 많이 어렵지 않습니다,
그러나 공식을 자세하게 아는 것은 여러분에게 좋습니다.
저는 여기 모든 자세한 것을 쓸 시간이 없습니다.
저는 여러분에게 핵심적인 부분을 말해줄 겁니다.
이것은 증명 스케치 또는 마스터 메소드 뒤의 직관 입니다.
우리가 하려고 하는 것은
이 recurrence에 대해 재귀 트리를 가지고 각 단계를 더하고
그리고 나서 모든 단계들을 더하고 우리가 무엇을 얻는지 봅니다.
우리는 한 레벨 확장한 후에 위에서 f(n)으로 시작합니다.
그리고 우리는 다른 문제들을 얻습니다,
n/b의 각각을요. 그리고 우리가 그것들을 확장한 후에
그것은 각각을 위한 f(n/b)이 될 것입니다. 그것들은 모두 같은 사이즈입니다.
그리고 나서 우리는 모든 것들을 확장합니다,
그리고 우리는 거기로부터 또 다른 하위 문제들을 얻습니다. 우리는
우리는 f((n/b)^2)와 같은 얻을 겁니다. 그것은
일종의 기하학적으로 감소하는 사이즈입니다,
우리가 아래에서 정수 사이즈 문제를 얻을 때까지요.
이것은 기본적인 경우이기 때문에 약간 특별합니다,
그러나 우리는 아래에서 다른 정수를 가집니다.
우리는 얼마나 많은 잎들이 있는지 알고 싶습니다,
그러나 그것은 지금 약간 까다롭습니다.
이 트리의 높이를 먼저 계산해 봅시다.
그것을 제가 여기 그려보겠습니다. 이 트리의 높이는 얼마죠?
저는 n 사이즈의 문제부터 시작하겠습니다.
저는 사이즈 1의 문제까지 내려 가고 싶습니다.
얼마나 오래 걸릴까요?
얼마나 많은 레벨들이 있나요?
이것은 아마 어떤 학생들에게는 매우 쉬울 것이고, 다른 학생들에게는 그렇지 않을 겁니다.
로그 b의 n 입니다,
좋아요. 이 트리의 키는 n^(log_b(a)) 입니다.
왜냐하면 그것은 단지 제가 1로 내려갈 때까지
제가 얼마나 많이 b로 나누었나 이기 때문입니다.
좋습니다. 이제 저는 잎들의 수를 계산할 수 있어야 합니다
왜냐하면 저는 가지 인자 a, 키 h를 가지고 있습니다.
잎의 수는 a^h, a^log_b(n) 입니다.
제가 그것을 약간 확장해 보겠습니다.
a^log_b(n), 로그 속성에 의해,
우리는 n을 아래로 가지고 a를 위로 둘 수 있습니다.
그리고 우리는 n^(log_b(a))를 얻습니다. 우리의 좋은 친구 n^(log_b(a)) 입니다.
그래서, 이것은 우리의 좋은 친구 n^(log_b(a))가 마스터 메소드에서 중요한 이유입니다.
우리가 하고 있는 것은
윗 레벨의 f를, 아래 레벨인
n^(log_b(a))와 비교하는 것입니다.
이제 잎들은 모두 같은 단계에 있습니다
왜냐하면 모든 가지에서 우리가 같은 비율로 감소시키고 있으니까요.
만약 제가 아래 레벨에서 비용을 더하면,
그것은 Theta(n^(log_b(a))) 입니다. 저는 그것을 윗 레벨에서 더합니다
그것은 f(n) 입니다, 그렇게 흥미로운 것은 아니죠.
그러나 다음 레벨에서, 이것은 약간 더 흥미롭습니다,
그것은 여러분이 이미 마스터 메소드를 암기했다면
친숙하게 보일 af(n/b) 입니다.
그래서, 우리는 af(n/b)이 어떤 정수 인자 1-입실론에 의해
감소된다는 것을 압니다.
우리는 아래로 갔습니다. 이것은 이것 보다 더 작은 정수 인자 입니다.
그리고 나서 여러분은 다음 단계를 더합니다.
그것은 a^2f(n/b^2) 이 될 겁니다.
저는 사실 이것, 괄호를 잘못 썼습니다.
미안해요.
그것은 (n/b)^2이 아니라 (n/b^2) 입니다.
그래서, 적어도 케이스 3에서, 이 순서는 기하학적으로 감소할 것입니다.
만약 그것이 정수 인자까지 기하학적으로 감소한다면,
그것은 f(n) 이라는 큰 항에 의해 제거됩니다.
우리는 Theta[f(n)]를 얻습니다.
다른 케이스를 봅시다, 그리고 제가 이것들을 우리가 시간이 얼마 남았는지에 따라
맞춰보겠습니다. 와우, 시간이 많이 남았네요.
5분 남았습니다. 매우 많은 시간 이지요.
무엇을 할까요? 그것을 써보겠습니다.
케이스 3에서, 비용은 감소합니다. 이제, 이것은 점, 점, 점이
매우 분명하다고 제가 말하는 곳 입니다.
여기서, 이것은 매우 간단 합니다. 그것은 a^kf(n/b^k) 입니다.
그리고, 케이스 3에서, 우리는 우리가 트리를 내려갈수록
비용이 기하학적으로 감소한다고 가정합니다.
그것은 케이스 3으로 시작한 것을 뒤로 가는 것이었습니다.
케이스 1을 해 봅시다, 그것은 다른 직관적으로 쉬운 케이스입니다.
케이스 1에서, 우리는 f(n)이
이것보다 다항적으로 더 작다는 것을 압니다.
그리고 우리는 중간에서 이 매우 간단한 절차에 의해 바꿀 것입니다.
저는 이것이 여러분이 더 공식적인 논의가 필요하다면,
손을 흔들겠습니다.
저는 이것이 기하학적으로 증가할 것이라고 주장합니다.
그것은 이 f(n)이 이것 보다 다항적으로 작기 때문에
기하학적으로 증가해야 합니다,
여러분은 작은 것에서부터 큰 것까지
중간에서 기하학적으로 해석하는 다양한 다항식을 얻을 것입니다.
그러므로 큰 것은 제거합니다 왜냐하면, 그것은,
다시, 등비 급수니까요. 제가 말했던 대로, 이것은 직관입니다,
공식적인 논의가 아닙니다. 이것은 매우 공식적입니다,
왜냐하면 우리가 그것을 가정했으니까요, 그러나 여기서 여러분은 더 논의가 필요합니다.
그것들은 기하학적으로 증가하지 않지만
더 빠르게 증가할 수 있습니다,
그리고 그것은 또한 괜찮습니다. 그래서, 케이스 3에서,
여러분은 제거됩니다, 여러분은
등비 급수에서 가장 큰 항에 의해 항상 제거될 것입니다.
여기서 f(n)이 있고 여기서 여러분은 아래 항과 함께
n^(log_b(a))에 의해 제거됩니다, 오 theta 입니다.
케이스 2입니다, 여기서 그것은 매우 쉽지만 여러분은 로그의 몇 가지 속성들을
알 필요가 있습니다. 케이스 2에서, 우리는 이것들이 모두
기본적으로 같은 것이라고 가정합니다. 제가 말하는 것은,
우리가 위의 것이 아래 것과 같다고 가정했습니다. 그리고 이것은 매우
절차적인 방법에서 변화하고 있습니다. 그러므로,
중간에서 모든 것은 매우 많이 같을 것입니다.
아주 많이는 아니에요 왜냐하면 여기서 우리가 로그 인자를 가지지 않으니까요.
여기서 우리는 k의 로그를 가집니다. 우리는 n^(log_b(a)) 곱하기 kn의 로그를 가집니다.
여기서 우리는 k의 로그를 가지지 않습니다.
그래서, 로그는 여기서 사라집니다.
그것들이 사라지는 방법은 매우 느립니다.
여러분이 이 항의 위의 반을 본다면, 그것들은 모두 k의 로그일 것입니다.
아래의 반은 사라지기 시작할 것입니다.
저는 여러분에게 신탁의 정보를 줄 것입니다.
만약 여러분이 로그를 가지고 여러분이 인자를 너무 많이 바꾸지 않는다면,
로그는 남습니다.
아마 가운데는 너무 멀 거에요. 각 레벨은 대략적으로 같습니다,
특히 대부분의 윗 레벨은
모두 점진적으로 같습니다.
대략적으로 같다는 것입니다. 그러므로,
비용은 한 단계입니다, 여기서 f(n) 곱하기 레벨의 수 h 같은 것이지요.
그리고 h는 로그 b의 n 입니다.
B는 정수라서 우리는 신경 쓰지 않을 겁니다.
이것은 Theta(lg n) 입니다. 그러므로,
우리는 T(n) = (n^(log_b(a)) lg^(k+1)(n)) 곱하기 다른 log n을 얻습니다.
그래서 우리는 [f(n)lg n]을 얻게 됩니다.
이것은 매우 빠른 스케치 입니다. 미안해요, 제가 케이스 1과 2에서 매우 엉망이었군요.
증명을 읽어보세요 왜냐하면 여러분은,
어떤 점에서 그 방법으로 조작해야 할 것이기 때문입니다.
그리고 그것이 전부입니다. 질문 있나요?
여러분은 가고 싶어 하는 것 같군요. 좋아요.
고맙습니다. 수요일에 봅시다.