[음악 재생] 

데이비드 J. 마란 :이 CS50입니다. 그리고이 주일의 시작이다. 그래서 우리는 흥분을 많이 가지고 일이 오늘 커버하는. 많은 기회에 대한 무대에서까지 자원 봉사. 그리고 궁극적으로, 오늘은 되지 않는 코드에 대한 모든. 하지만, 아이디어 그리고 이 알고리즘에 관하여, 실제로 일부를 다시 가져 주 제로에서 배운 교훈, 특징 리콜, 우리 이 괴물을 소개했다. 그리고 차입 영감 그에서 시작 더욱 정교한 해결하기 위해 알고리즘 문제. 하지만 먼저, 공지 사항의 커플. 그래서 하나, 당신은 가입하고자하는 경우 점심 시간에 CS50의 직원과 친구들 금요일, 모두 여기에 캠브리지, 및 뉴 헤이븐에서, 코스의 방문하시기 바랍니다 URL은 웹 사이트를 찾아 볼 수있다. 이 수요일 것이다 강의 샌더스 여기 수 없습니다. 너무, 온라인으로 만 할 것이다 CS50의 웹 사이트에서의 조정, 여기 캠브리지 여부 또는 뉴 헤이븐뿐만 아니라. 

그리고 문제는 두 설정 당신의 손에 이미 있습니다. 당신이 아직 아래쪽에서 날아하지 않은 경우에, 저를 허용 강하게 말로 제안을 제공합니다 특히 지금과 같은, 그 문제는, 미리 설정을 당신은 정말, 지금이 아니라면 시작 하시겠습니까 주말 또는 이전에 조금 손 대고 그들은 처음에 외출 할 때 금요일, 당신이 것이기 때문에 그들이 필요하지 않은 것을 발견 더 이상의 도전 당지고 그 자체. 나는, 당신은 그것을 찾을 수있을 거라 생각 일반적으로, 그들은 거의 가지고하는 경향이 시간의 같은 양의 주위에. 그러나 그것은 확실히 따라 학생, 그것에 사고 방식에 따라 달라집니다 있는 당신은 그것을 접근. 하지만 변함없이, 당신은거야 일부 벽에 실행하려면 당신은 칠거야 일부 버그, 그리고 당신이있어 단지 수 될 수 없습니다 어떤 시점에서 그것을 극복. 그리고 할 수있는 엄청난 가치의 멀리 단계 다음날 다시 와서, 근무 시간에 가서, CS50에 게시물 토론 등이, 실제로 차단 해제 얻을 수 있습니다. 그래서 명심. 가능한 한 빠른 시작 당신이 할 수있는 가장 좋은 방법입니다. 우리가 시작했던 곳 그래서 여기에 주 제로에 걸쳐 클래스. 그리고 우리는 자원 봉사를 얻을 수 있습니다 여기에 내가 마이크를 찾을 수 있도록하는 방법? 그래. 이미 서. 최대 어서. 그게 효과가 있을까 얼마나 같아요. 당신의 이름은 무엇입니까? 인영 에스트라다 : 앨런 에스트라다. 데이비드 J. 마란 : 앨런 에스트라다. 최대 어서. 만나서 반갑습니다. 인영 에스트라다 : 만나서 반가워요. 데이비드 J. 마란 : 그리고 당신은 여기에 있었다 우리 주 제로에, 물론 함께. 인영 에스트라다 : 나는이었다. 나는였다. 

데이비드 J. 마란 : 그래서 당신은 갈 수있다 앞서 마이크 스미스 우리를 찾아 당신이 할 수있는 한 빨리? 당신이 할 수있는만큼 빨리. 말 그대로 문제를 찢어 반에서 당신이 필요로. 

인영 에스트라다 : 음. 데이비드 J. 마란 : 말 그대로 반 문제 찢어. 

인영 에스트라다 : 오. 음. 아주 좋아. 

데이비드 J. 마란 : OK. 좋다. 고맙습니다. 인영 에스트라다 : 아주 좋아요. 그래. 

데이비드 J. 마란 : 그래서 지금, 당신은 그것을 아래로 깍습니다 문제의 절반 크기이다. 이제, 우리는 분기까지입니다. 당신이주의를 지불하고 우리는 유지하고 어느 쪽? 

[하하] 

인영 에스트라다 : 네, think-- 

데이비드 J. 마란 : 어떤 부분 우리는에? 인영 에스트라다 : 머플러, 그래서. 

데이비드 J. 마란 : OK. 그러나 마이크 스미스는 것입니다 머플러 이후 여야합니다. 그러니까 ... 

[하하] 

괜찮아. 인영 에스트라다 : 우리는 어디에서 찾고 계십니까? 데이비드 J. 마란 : 마이크 스미스. 인영 에스트라다 : 마이크 스미스. 데이비드 J. 마란 : 이제, 우리는 수술에있어. 이제, 의사. 들을 당장 

인영 에스트라다 :의 실제와 가자 Let's-. 진짜. 

데이비드 J. 마란 : 진짜. 그래. 당신은 진짜 필요합니다. 이제, 마이크 스미스는 어떤 방법이 있나요? 

인영 에스트라다 :이 방법. 

데이비드 J. 마란 : 방법은? 인영 에스트라다 : 잠깐. M is-- 맞죠? 우리는 일 해요 시작 

데이비드 J. 마란 : 그래. 그들은 왼쪽으로하고 있습니다. 당신의 권리. 

인영 에스트라다 : 네. 

데이비드 J. 마란 : 그래서 마이크 여기에. 인영 에스트라다 : 무엇? 

[하하] 

나쁜 예, 사람. 죄송합니다. 데이비드 J. 마란 :이 가르 칠 것 당신은 당신의 의자에서 뛰어. 

인영 에스트라다 : 오. 오. 나는 당신을 얻었다. 나는 당신을 얻었다. 오. 오. 이 확인을 is--, 나는 당신을 얻었다. 여기 스미스? 

데이비드 J. 마란 : 스미스, 감사합니다. 그래서 나는 스미스를 계속 찾고 있습니다? 

인영 에스트라다 : 오, 그래. 아니, 아니. 아니, 오. 이 내 꺼야. 

데이비드 J. 마란 : 오, 당신이 스미스를 얻었다. 그래. 

인영 에스트라다 : 네, 여기 스미스를 얻었다. 죄송합니다, 여러분. 나는 Michael-- 생각 우리 마이클를 찾고 있었다. 죄송합니다. 

데이비드 J. 마란 : 그것은 확인을합니다. 자, 이제 우리는있어 Paccini와 아들에. 

인영 에스트라다 : Paccini와 아들. 데이비드 J. 마란 : 당신 만 나는이에에 있습니다. 그래. 우리에게 마이크 스미스를 찾아보십시오. 스미스. 

인영 에스트라다 : 스미스. 

데이비드 J. 마란 : 스미스. 우리는 쓰레기에 대한 연구에있어. 인영 에스트라다 : 쓰레기. 오. 이 시간이 걸릴 것입니다. 

[하하] 데이비드 J. 마란 : 신발. 우리는 신발에있어. 

인영 에스트라다 : 이제 우리는 gonna--있어 

데이비드 J. 마란 : 반갑습니다. 인영 에스트라다 : Which-- [하하] 아,이 중대하다. [하하] 

데이비드 J. 마란 : 그것은 확인을합니다. 

인영 에스트라다 : 아,이 좋은 것입니다. 내가 갈거야 생각하지 않습니다 이 후 PSAT 친구가 있습니다. 데이비드 J. 마란 : 좋은. 스포츠. 인영 에스트라다 : 스포츠. 음, L, M, N, O, P. 데이비드 J. 마란 : OK. 그럼 반이 찢어 보자. 괜찮아요. 이것은, 어쨌든 제대로 종료 마이크 때문에 스미스는 옐로우 페이지에되지 않습니다. 

인영 에스트라다 : 아. 

데이비드 J. 마란 : 아니, 괜찮아요. 그러나 이제 척하자 그는이 페이지에 있습니다. 그래서 지금, 당신은 아래로 문제를 깍습니다 한 페이지에, 우리는 마이크 스미스를 발견했다. 

[환호] 확인, 감사합니다. 그래. 즉, 특별한했다. 하지만 여전히 빨랐다 선형 검색보다, 에있어서 우리가 시작 책의 시작, 왼쪽에서 오른쪽으로 우리는 우리의 길을 이동, 결국 마이크 스미스를 찾고. 그래서, 만약 전화 번호부 아마 1,000 페이지를했습니다 아마 촬영 한 것 우리 10 정도 페이지의 눈물. 

하지만 당신은 활용했을 수 있습니다 가정을 감동 이 모든 동안, 어떤 말을하는 것입니다 사전에 전화 번호부는 무엇이라고? 청중 : 정렬. 데이비드 J. 마란 : 그것은 분류입니다. 권리? 너무, 알파벳 순으로 정렬있어 그 이름과 전화 번호의 모든 의에로 분류되어 있습니다 Z, 그리고 알파벳 사이. 그러나 오늘, 우리는 지금 물어보세요 질문은 물론, 어떻게 버라이존 또는 전화했다 회사는 그 상태로 그것을 얻을? 

그것은 한 가지이기 때문에 활용하기 그 전제로, 따라서, 문제를 해결 알고리즘보다 효율적으로. 그러나 우리는 결코 정말 주 제로에 요청, 잘, 비용 그것을 어떻게 많은 버라이존 또는 다른 사람 정렬 된 순서로 그 전화 번호부를 얻을 수 있습니까? 

권리? 이 경우 문제가되지 않습니다 마이크 스미스를 찾고 그것은 당신이 걸리는 경우, 슈퍼 빠른 올해는 처음에 페이지를 정렬합니다. 권리? 당신은뿐만 아니라 그냥 가려 낼 수 있습니다 무작위로 전화 번호부를 통해, 그것은 슈퍼 영웅이 될 것 경우 그것을 정렬 할 비용. 그래서 만약 우리가 또 다른 자원 봉사를 할 수 있습니다. 의이 걸릴 여기까지 살펴 보자 우리는 어떻게 up-- 어서 might-- 방법 우리는 이러한 분류에 대해 갈 수 있습니다. 

그리고 만약 요르단 실제로 수 무대에 여기에 우리를 가입 할 수 있습니다. 잠시 위해 가자. 당신의 이름은 무엇입니까? 그렇 : 캐롤라인. 데이비드 J. 마란 : 캐롤라인, 최대 어서. 그리고 당신은 가입 할 수 있습니다 여기에 나와 요르단. 캐롤라인, 감사합니다. 괜찮아. 그래서 우리는 여기에 대해 무엇을 캐롤라인 (26) 푸른 책입니다 FAS는 관리하는 데 사용하는 특정 최종 시험. 이것들은 찾기 힘들지고있다 하지만 우리는 사전에 무슨 짓을했는지 우리가 다른 사람의 이름을 넣어 한 것입니다 이들의 각각의 앞면에, 그러나 우리는에 의해 간단하게 유지했습니다 다음 전체 이름을 넣어. 그래서 우리는 이름을 가진 사람을 둘 것 L, D, J, B, 모든 방법 Z까지, 하지만 그들은 임의의 순서입니다. 그리고 당신은 것, 그래서 만약 당신의 이야기 당신과 같은 문제를 통해 방법 그것은 당신이 앞서 갈 수 않고 에서 Z.에, 우리를 위해이를 정렬 

청중 : OK, 그래서 L은 중간, 등이다. C를 시작했다. B. L. B 전에 J, Q : 

데이비드 J. 마란 : 그 상태에서 일초에 대해 생각했다. 그렇지 않으면 때문에, 이것은 단지입니다 당신, 나, 요르단에 흥미 롭군요. 우리는 거기에 갈. 청중 : [들림]. R. 데이비드 J. 마란 : OK. 당신은 뭐하는거야? 

CAROLINE : M은 오 후 제공 

데이비드 J. 마란 : OK. 

CAROLINE : O. 데이비드 J. 마란 : 오, 좋아. 

CAROLINE : E. 

데이비드 J. 마란 : E, F. 그래. 

CAROLINE : T, U, V. 

데이비드 J. 마란 : V, T, U, V. 그것은 그래서 당신이 계속 making--있는 것처럼 보인다. 당신이 만드는 것 같습니다 큰 더미 여기에, 그리고 저기 큰 더미 가지. 그래서 알파벳의 첫 번째 절반, 알파벳의 후반. 그래. 좋다. 두 종류의 문제점을 분할. M, N, X의 네. CAROLINE : K. 데이비드 J. 마란 : OK. 케이는 그래서 당신은 가지 선택하고 다른 후에는 하나, 왼쪽 또는 오른쪽 중 하나를 넣고, 또는 Z의 바닥에 가고. 그래. 

캐롤라인 : Z는 바닥에 것입니다. 

데이비드 J. 마란 : OK. Y는 바닥에 것입니다. 이제 우리는 X를 넣을 수 있습니다 

CAROLINE : G. 데이비드 J. 마란은 : G의 왼쪽 간다. S 바로 것입니다. 좋아, 왼쪽 모든 방법을 것입니다. 

CAROLINE : A, B, C, D 

데이비드 J. 마란 : 지금, 좋은. 우리는있어, B는 C를 W의 아래가 가고. 좋아, T. 

CAROLINE : H, I, J 데이비드 J. 마란 : H, I, J 좋은. 그렇 : 중앙, 나는 gonna-- 해요 데이비드 J. 마란 : OK. 그래서 지금, 우리는 종류에가는거야 이러한 다양한 더미를 병합합니다. 그래서 C를 통해, 그때 D를보고, E 및 F, 및 G, 및 H, 및 I. 니스. J, K. 그리고,이 더미는 거꾸로,하지만 괜찮아요. 물론. 우리는 약간의 모서리를 잘라 수 있습니다. 그래. 그리고 우리는 W, X, Y, Z를 필요 

그렇 : 네. 

데이비드 J. 마란 : 우수한. 그래서 큰는 당신을 감사합니다 이러한 정렬 캐롤라인. 

[환호] 

고맙습니다. 대단히 감사합니다. 그래서 지금의이 순간을 생각해 보자 어떻게 캐롤라인은 그 일에 대해 갔다, 그리고 정확히 우리 방법 이러시면 수 있었다 우리 것을 해결 할 수 있었다 문제 때 우리가했다 임의의 입력의 모두 주어진. 

음,이처럼 보이는 이 시스템의 비트입니까? 권리. 이전 글자 그래서 알파벳, 그녀 했다 왼쪽 퍼팅 및 알파벳에서 나중에 편지, 그녀는 오른쪽에두고 있었다. 그리고 곧 그녀는 발견 일부 인접 문자, 사람 즉, 서로 바로 옆에 이동 그녀는 위해 사람들을 둘 것입니다. 그래서 우리는 종류의이 작은 있었다 발생하는 정렬 된 입력의 더미. 

그리고 그것은 매우 어떤 건지 우리의 대부분의 인간은 할 것이다. 우리는 일종의 그것을 가려 낼 것이다, 우리는 종류의 메커니즘이있을 것이다. 그러나 쓰기 어려울 수 있습니다 그 아래 수식 자체에. 그것은보다 유기 조금 더 느꼈다. 그래서 보자 경우 우리는 바운드 지금 할 수있는 적은 수의 입력을 가진 문제. 

대신 26,하자 훨씬 적은 일을 바로 뒤에, 일곱, 함께 말 이 문은, 말하자면. 그냥 칠 수 있는가? 그리고 지금 목표의 경우 손의 값을 찾을 수있다, 의보고 얼마나 효율적으로하자 우리는이 일에 대해 갈 수 있습니다. 그리고 우리가 지금 할 수있는 경우에 보자 몇 가지 숫자를 적용하기 시작, 또는 일부 수식이있는 설명하기 우리의 전화 번호부의 효율성 알고리즘, 우리의 시험 책 알고리즘 및 보다 일반적으로, 정보 탐색. 

이것에 대한 그래서, 내가 앞서 가자하고, 터치 스크린에 여기에, 이 웹 브라우저를 올려 정확히이 일곱 문. 그리고 우리는 다른 하나를 얻을 수있는 경우 여기에 와서 자원 봉사, 나는 여기에이 같은 문을 넣었습니다. 빠른 자원 봉사. 

이 one-- 데모가는거야 빨리와 빨리 지금. 내려 가자. 당신의 이름은 무엇입니까? 트레버 : 트레버. 

데이비드 J. 마란 : 트레버? 좋아, 트레버는 아래에 제공됩니다. 그래서 트레버는 여기에 자원 봉사를하고있다 비슷한 문제를, 그러나의 하나 범위가 좁고, 그게 무슨 수 있도록 우리는 이제 공식화하려고합니다 이 숫자를 정렬하는 과정. 

그래서 트레버, 당신을 만나서 반갑습니다. 그래서 여기 배열에, 그래서이다 일곱 문의 목록을 말한다. 가서 우리에게 숫자 50를 찾을 수 있습니다. 그리고 사실 후, 당신이 그것을 발견하는 방법을 알려주십시오. 모든 권리를 이따가해야합니다. 그래, 여기에 하나는? 어 오. 그래. 당신은 그 중 하나를 클릭했습니다. 좋다. 

그리고 좋은. 지금 당신은 그 중 하나를 클릭했습니다. 그리고 내가 당신에게 마이크를 줄 수 있도록, 그래서 당신은 단지 한 순간에 있습니다. 가서 클릭 당신이 의도 옆집. 네, 좋아요. 트레버 : 나는 문을 unclick 수 있습니까? 데이비드 J. 마란 : 아니, 당신은 unclick 수 없습니다. 트레버 : OK. 이 하나. 데이비드 J. 마란 : 당신은 어디 가고 싶어? 어느 것? 

트레버 : 그 하나. 

데이비드 J. 마란 : 번호 

트레버 : OK. 이 하나. 

데이비드 J. 마란 : 예. 그게 좋았다. 괜찮아. 그래서 알고리즘이 뭔지 나 이, 트레버을 수행하기위한 절차? 

트레버 : 그냥 통해 갔다 문 전까지는 (50)를 발견했다. 데이비드 J. 마란 : OK. 우수한 알고리즘. 그래서 괜찮아요. 사실, 만약 내가 공개하기 때문에 무엇입니다 이 두 가지 다른 문 뒤에 무엇을 우리는 여기에 찾을 수 있습니다 우리는 무작위로 입력을해야합니다. 그래서 같은 사실이었다 당신이 얻을 수있는 좋은. 그리고 사실, 당신은보다 더있어 철저하게 전체 배열을 검색, 정말이었을 것 때문에 불운 한 당신이 수를 맞았 더라면 맨 마지막 문 (50). 하지만 대신에 우리 경우 당신에게 가정을했다. 종류 모든 I를 가정 주변이 문, 그래서 당신은이 번호는이 시간을 정렬 하지만 이번에는 실제로이다 이 시간을 different-- 실제로 당신을 위해 분류입니다. 손에 이제 목표 숫자 50를 공격하는 것입니다. 

트레버 : OK. 

데이비드 J. 마란 : 무엇이야 될 것 알고리즘? 

트레버 : 그것은 음, 경우 분류, 그건 어느 것 가장 큰 경우 최대로 이따가하고, 내림차순, 그것은 첫 번째있을 것이다 또는 그 반대의 경우, 그것은 마지막 하나가 될 것입니다. 그래서 난 그냥이 문을 누른 것 그럼 그냥 마지막 문을 누릅니다. 데이비드 J. 마란 : 우수한. 괜찮아. 그래서 우리는 수 (50)를 발견했다. 그래서 빨리 당신이 알고로 그들은 분류하고, 우리 이 가정을 활용할 수 있었다. 그래서 그들은 같은 너무 많은 것 전화 번호부 예. 최대한 빨리, 심지어 함께 가지고 이 같은 작은 문제, 당신의 입력을 미리 분류, 우리는 할 수 실제로 틀림없이 값을 찾을 수 보다 효율적으로. 

그리고 당신이 인 경우를 말하지 않았다 작은에 큰 작은, 또는 큰 분류 그리고 그것은 매우 합리적이었다 한쪽 또는 다른에서 시작 실제로 목표 값을 찾을 수있다. 그래서뿐만 아니라 트레버에 감사드립니다. 그리고 나는 잘 수행 propose-- 것이다. 우리는, 실제로, 약간의 클립을 가지고 , CS50에서 우리가 제일 좋아하는 순간 중 하나입니다 이에 때때로 이러한 데모 아주 계획에 따라 가지 않는다. 그리고 실제로 지금, 나는 잘못된 인터페이스를 뽑아 있는 터치 스크린을 사용하는 방법. 그래서 내 잘못이 있었다. 

따라서이에 대한 것 내년의 클립 나는 내 자신의 화면을 클릭 한 이유에. 그러나의 짧은 살펴 보자 작년에 무슨 일이 있었는지에 많이 와서 제이,과 여기 트레버처럼, 자원 봉사 이 짧은 클립에, 당신은 볼 수 있습니다 이 같은 데모는 매우하지 않았다 방법 배운 같은 교훈을 알 수있다. [비디오 재생] 나는 당신이 원하는 -all 지금 나를 위해 찾아하는 우리를 위해, 정말, 수 (50) 한 번에 한 단계 씩. 

년 - 수 (50)? 

년 - 수 (50). 그리고 당신은 무엇을 밝힐 수 이 문을 각 뒤에 단순히 손가락으로 터치하여. 젠장. 

[하하] 

[END 재생] 데이비드 J. 마란 : 그래서 아주 잘했다. 사람들은 정렬되지 않은 문이었다. 그리고 제이, 물론, 너무 빨리 모든 것을 발견했다. 트레버는 훨씬 더 나은 일을했다 가르침을받을만한 순간의 관점에서, 그래서이 해에, 말하자면 오래 복용을 찾을 수 있습니다. 물론, 우리는 준 제이 두 번째 기회, 이에 우리는 문을 분류 우리는 트레버를 위해했던 것처럼, 트레버 슈퍼 아니라이 시간을했다. 그러나 제이는 절반 빨리했다. [비디오 재생] 년 - 목표는 이제하다 우리에게 숫자 50를 찾을 수 하지만 알고리즘을 수행하고 당신이 그것에 대해가는 여러분의 의견을 알려주세요. 

-그래. 

당신이 그것을 발견하면 - 그리고, 당신은 영화를 유지한다. 당신이 그것을 찾을 수없는 경우, 당신은 그것을 다시 제공합니다. 

-man. 

오! 

- [들림] 확인을 클릭합니다. 그래서 끝을 확인하는거야 오 there's-- 여부를 결정하는 첫 번째. 

[박수] 

[END 재생] 데이비드 J. 마란 : OK. 그래서 명확하게 문을 정렬 효율성으로 이어집니다. 그리고, 두 배 빠른 내가 거기에 의미하는 것입니다. 그리고 제이는 운이 둘 시간을 얻었다. 그리고 그는 또한 마지막에 운이있어 올해는 좀 블루 레이 디스크를 주문 실제로 밖으로 제공합니다. 나는 올해 미안 해요, 우리 트레버을 동일하지 않았다. 그러나 더 나은 여전히​​ 몇 년이었다. 그리고 여러분 중 몇몇은 이것을 알고 있습니다 그는 CS50에 있던 동료, 숀, 정확한에 도전했다 같은 문제, SD에이기는하지만, 당신은 곧 다시 하루에 볼 수있다. 그리고 당신은하지 않았다 것을 확인할 수 있습니다 그는, 제이보다 조금 더 오래 걸릴 트레버보다 조금 더, 그것은이었다 실제로이 좋은 기회 거의 모든 사람이 참여하는 군중 라 가격 격려, 오른쪽입니다 그에게 우리가 찾고 있던 번호를 찾을 수 있습니다. 의하자. 빠른 살펴보십시오. 

[비디오 재생] 

-그래. 그래서 여기에 귀하의 작업, 션은, 다음과 같다. 나는이 뒤에 숨겨진 문 일곱 번째. 그러나 이러한 문 중 일부에 자리 잡고 뿐만 아니라 다른 음수입니다. 그리고 당신의 목표는 생각하는 것입니다 숫자의 맨 윗줄의 단지 배열, 또는 그냥 종이 조각의 순서 그들 뒤에 숫자. 그리고 당신의 목표는 정상을 사용한다 배열 여기, 나에게 일곱 번째를 찾을 수 있습니다. 그리고 우리는 비판 예정 당신은 그 일에 대해 가지 방법. -괜찮아. 우리에게 일곱 번째를 바랍니다 -find. 아니. 다섯, 19, 13. 

[하하] 

이 트릭 질문이 아니다. 하나. 

[하하] 이 시점에서, 당신의 점수는 매우 아니다 좋은, 그래서 당신은뿐만 아니라 계속 있습니다. 세 가지. 

[하하] 

계속해. 솔직히, 나는 도움이되지만 궁금 수 없습니다 당신이 심지어 그러니까 ...에 대해 생각하고 

[하하] 만 맨 윗줄, 그래서 세 왼쪽 있어요. 그래서 나에게 일곱을 찾을 수 있습니다. 

[하하] 17. 세븐. 

[박수] 

괜찮아. 

[END 재생] 

데이비드 J. 마란 : 그래서 우리는 할 수 이 하루 종일보세요. 의 그리고 물론, 일부 올해의 데모 아마도 지금 다음에 종료됩니다 올해의 비디오뿐만 아니라. 그래서 지금 실제로하자 알고리즘에 초점 우리가 할 수없는 경우에는 여기에, 볼 지금 공식화하기 시작 우리는 우리의 데이터를 가져 오는에 대해 갈 수있는 방법 이 상태로는 분류 있다고, 그래서 궁극적으로, 우리가 실제로 할 수있는 더 효율적으로 검색 할 수 있습니다. 그리고 우리는거야에도 불구하고 상당히 작은 데이터 세트를 사용하려면 8 자리 숫자의 우리처럼 보드에 여기있다, 궁극적으로이 같은 아이디어를 적용 할 수 1000 입력에, 만 입력, 40 억 투입, 알고리즘 때문에 근본적으로 동일 할 것입니다. 

그리고 이것이 우리의 마지막 자원 봉사자 오늘의 기회, 하지만 아마도 가장 참여 하나, 있는 우리는 여덟 자원 봉사자가 필요 와서 통해 우리를 걸어 정렬 방법 무엇 곧 것 이러한 음악에있을 여기에 서있다. 내가 여기 다시 시작하자. 

그래서 turquoise-- 녹색 하나는 무엇입니까? 당신은 커밋하고 있습니까? 두. 내려 가자. 그래. 세 가지. 네. 다섯 확인 가구 있구만하자. 당신은 당신의 친구에 의해 지명되는 것입니다. 여섯, 일곱, 여덟. 최대 어서. 괜찮아. 정말 고맙습니다. 최대 어서. 최대 어서. 

괜찮아. 그래서 우리는 here--이가 무엇을 더 어색한 것 중 하나입니다, 이 이후 그에게 유머가 필요합니다 시간이 조금 저. 당신은 숫자 하나가 될 것이다. 당신의 이름은 무엇입니까? 

아난 : 아난. 

데이비드 J. 마란 : 아난. 데이비드. 당신의 이름은 무엇입니까? 

조셉 조셉. 

데이비드 J. 마란 : 조셉, 당신은 두 번째입니다. 

세레나 : 세레나, 3 번. 스테판 네 번째. CYNTHIA : 신시아. 데이비드 J. 마란 : 신시아, 5 번. [들림] 데이비드 J. 마란 : [들림]. 데이비드, 여섯 번째. 매트 : 매트. 데이비드 J. 마란 : 매트의 일곱 번째. 그리고? 

WAVERLY : 웨버. 

데이비드 J. 마란 : 웨버, 여덟. 괜찮아. 경우에 당신은 으악를 could--. 여러분 모두의 경우, 같은 거기에 첫 도전, 여덟 음악 스탠드는 여기에 관객을 직면. 당신은 당신의 숫자를 넣을 수 있다면 이러한 음악은 가로막는 그들은 함께 줄 것을 보드에 같은 번호. 그래서 자신에 의해처럼 보이게 이러한 음악에 당신의 숫자를 넣어 여기에 서있다. 우수 지금까지. 

우수. 그래. 그래서 지금, 우리는 물어거야 몇 가지 다른 방법으로 질문입니다. 우리는 어떻게 정렬에 대해 갈 수 있습니다 여기이 사람들까지? 우리는 몇 가지 방법을 가지고 있기 때문에 이전에, 우리는 이에했다 종류의 서로 다른 두 가지 버킷을. 그리고 우리가 일반적이었다 함께 일을 조립할. 곧 우리는 두 숫자를 보았다로 즉, 함께 지배 우리가 함께 넣어. 함께 속해 두 글자. 

그러나의가 있는지 확인하자 우리 이 공식화 할 수 없습니다, 우리가 궁극적으로이 너무 당신은 몇 가지 의사 코드, 있는 이러한 문제를 해결할 수 있습니다. 그래서 지금, 내가 찾고 있어요 여기에이 숫자에서. 그리고 실수의 전체 무리를 참조하십시오. 결국, 내가 하나를 원하는 왼쪽과 오른쪽 팔. 

그래서 내가 찾고 있어요 이들 2 개, 4 개 및 두. 그리고 문제는 분명히 무엇인가? 그래. 겠어요 - 두 분명히하기 전에 온다 네, 그래서 당신은 무엇을 알아? 내가 먼저 욕심 방법을 보자, 많은 같은 문제가됩니다 당신이에서 기억 경우 one-- 설정 문제 하나를 설정의 표준 버전, 여기서 난 그냥 로컬 문제를 해결 즉, 내 앞에 바로 여기 이 날 리드 어디를 참조하십시오. 

그래. 그래서 두 네, 날 가자 앞서 단지 당신에게 두 가지를 교환. 당신은 물리적으로 이동 할 수있는 경우 자신과 당신의 종이, 나는를받은 것 같다 더 나은 상태로 나열합니다. 

지금, 그들은 좋은거야. 나는, 이동거야 네 여섯, 좋은 보인다. 문제가 아니다. 여섯 여덟, 확인을 클릭합니다. 여덟 하나, 또 다른 문제. 팔 하나에 대한 사실 무엇 때문에? 하나는, 여덟 전에 온다 그래서 우리는 어떻게해야합니까? 의이 두 가지를 교환 할 수 있습니다. (1 ~ 8). 그리고 지금, 나는 계속거야. 나는 계속 찾고 유지하는거야. 그리고 이제 어떻게되는지 보자. 여덟 세의 물론, 순서가. 의 스왑을 보자. 물론 여덟 일곱. 고장난. 의 스왑을 보자. 여덟 다섯, 물론,하자의 스왑. 괜찮아. 목록 정렬됩니다. 네? 

확인을 분명하지. 그러나 그것은 바로, 조금 더 나은 무엇입니까? 무슨 일이 있었 통지 무엇 때문에. 때마다 우리는 스왑을 수행 작은 수 종류의 그런 식으로 여과 된, 그리고 더 큰 수 이 방법으로 여과 된, 또는 우리는거야 에 버블 말했다고 전했습니다 시작 왼쪽 또는 오른쪽으로 버블. 

지금, 그것은 때문에, 충분하지 않습니다 기껏해야 수는 수도 한 자리를 옮겼습니다 순방향 또는 최악 숫자가있을 수 있습니다 추가로 한 자리를 옮겼습니다. 그래서 당신은 무엇을, 이런 종류의 알 의 지금까지 꽤 잘했다. 나 그냥 다시 해보자. 두 네, 그들은 OK입니다. 네 여섯, 그들은 OK입니다. 여섯 하나, 순서가. 그럼 두를 교환 할 수 있습니다. 그리고 지금, 문제의 통지 더 나은 다시 조금지기 시작. 여섯 세, 순서가. 이제 두를 교환 할 수 있습니다. 여섯 일곱, 당신은 좋은거야. 세븐 다섯 물론, 순서가. 순서대로 일곱 여덟. 그리고 지금, 내가해야 할 수도 있습니다 더이 몇 번을한다. 그리고 사실, 자신에 대한 생각 아마도 얼마나 많은 시간을 최대로 나는 앞뒤로 걸어해야 할 수도 있습니다? 

우리는 다시 그에게 올 것이다. 그래서이 네 아직 확인합니다. 네 하나, 아니. 그래서, 스왑을 할 수 있습니다. 그리고 다시, 시각적으로 알 하나는 버블 링 종류 그것이 있어야 왼쪽에. 네 세 스왑. 네 여섯. 여섯 다섯 스왑. 여섯 일곱. 일곱 여덟은 좋다. 

좋다. 우리는 더 나은 있어요. 그래서 보자. 이제, 우리는이 하나 있습니다. 물론, 교체. 2와 3, 3과 4, 넷 다섯, 여섯 일곱, 일곱 여덟. 좋다. 그리고 당신은 무엇을 알아? , 내가 거기에 하나의 변화를 만들었 기 때문에 나 하나의 전성 검사를 할 수 있습니다. 나에게 모든 방법을 가자 다시 처음으로. 그래. 하나, 그래 two-- 참조? 뭔가 잘못이었다. 셋, 넷, 다섯, 여섯, 일곱, 여덟. 그리고이 마지막 패스입니다 내 지금 당신 편안 그것은 정렬 소유권 주장? 그래. 시각적으로, 그 절대적으로 사실입니다. 그러나 기능적으로, 무엇을 또한 단지 일어 났습니까 당신을 허용하는 마지막 단계에서 이 목록이 실제로 있는지 확인하기 분류? 

나는 무엇을 또는​​이 마지막 패스를하지 않았다? 청중 : 아무 변화가 없었다. 데이비드 J. 마란 : 죄송합니다? 청중 : 변경 사항이 없습니다. 데이비드 J. 마란은 : 어떤 변화가 없었다. 그래서 나를 바보 될 것 다시 동일한 알고리즘을 나는 어떤을하지 않은 경우 첫 번째 시간을 변경합니다. 그리고 상태가 변경되지 않았습니다. 분명히, 내가 만들려고하고 있지 않다 어떤 두 번째 시간을 변경합니다. 그리고, 지금은 안전 말을, 목록 정렬됩니다. 

그리고 실제로, 이것은 지금 뭔가 우리가 일반적으로 정액을 전화 거품 정렬, 이에 페어, 당신은, 다시 실수를 수정 다시, 다시, 당신에게 앞뒤로 계속, 앞뒤로, 당신까지 이러한 스왑을 확인하지 않는 점에서 당신은 내가, 그래, 확신 할 수 있습니다 실수의 모든 고정 마쳤다. 의 재설정과 다른 접근 방식을 해보자. 너희들은 다시 갈 수 있다면 순서는 당신이 순간 전이었다 이는이처럼 보였다. 이제, 접근을 보자 더 시험 책처럼 작은, 이에 우리는 지속적으로 있었다 알파벳의 문자를 선택 우리는 종류의 원이 다음을 처리합니다. 아마 높은 편지였다, 또는 낮은 편지 Z. 등 

그래서 모든 사람들이 다시이 순서입니다. 그리고 지금 내가이 작업을 수행 할 수 있습니다. 의는 내가 알고 보자 여기에 8 자리 숫자. 나는 앞서 갈거야 및 다만 의도적으로 선택 가장 작은 요소. 권리? 이것도 직관적 보인다. 이유는 작은 발견하지 않습니다 그것이 어디에 속하는 원소, 넣어 그 다음 작은 요소를 얻을 넣어 그것은 그것이 속하는 단지 반복한다. 

직관적 때문에 그것도 작동합니다. 그래서 네, 그건 아주 작은 수입니다. 나는이 곳을 기억하겠습니다. 분을 기다립니다. 두 작다. 내가 지금 위치를 기억하자 두 이며, 약 4 잊지. 우리는 나중에 다룰 것이다. 여섯, 난 관심 없어. 여덟, 나는에 관심이 아니에요. 하나는 내 새로운 작은 수입니다. 그래서 하나는 위치를 기억거야. 세, 관심이 없습니다. 세븐, 관심이 없습니다. 다섯, 관심이 없습니다. 

탈락하지 않고 그래서 단 올해, 나는 수를 잡아 갈거야 one-- 당신의 이름은 또 무엇인가? 

아난 : 아난. 

데이비드 J. 마란 : 아난. 그리고 당신은 저에 가입 할 수 있다면 리스트의 처음 당신이 속한 곳의 당신을 만들어 보자. 아쉽게도 당신의 이름은 무엇입니까? 

스테판 : 스테판. 

데이비드 J. 마란 : 스테판 방법입니다. 스테판이를 해결하기 전에 그래서 문제는, 우리는 무엇을해야합니까? 우리는 스테판 무엇을해야합니까? 

청중 : [들림]. 데이비드 J. 마란 : OK. 그래서 우리는 그렇게 할 수 있습니다. 우리는 종류의 스테판과이 걸릴 수 있습니다 자신의 네, 그냥 변수에 넣어 과 위해에 개최 일정 시간, 따라서 번호를 하나의 공간을 만들기. 그리고는 나쁘지 않다. 나는 왜 안 할, 제안 할 수 우리는 여기 스테판를 넣어? 왜이 일을 위반할 수 아이디어 우리가 시작 지난 주, 지난 시간에 대해 얘기? 그래? 

청중 : [들림]. 

데이비드 J. 마란 : 그것은에 대한 인덱스가 없습니다. 이 같은 사실이 생각하는 경우 배열이 음의 하나처럼, 그래서 메모리는 실제로 없다 여기가 참으로 배열 인 경우, 같은 우리는 강연에서 지난 주 선언했다. 그래서 우리는이 작업을 수행해서는 안됩니다. 우리는 변수에 저장할 수 있습니다. 

아니면 그거 알아? 나는 다른 사람이 그것을 제안 들었다. 우리는 스테판과 다른 무엇을 할 수 있습니까? 왜 우리가 그를 축출하지 않고 번호 하나는 어디를 통해 그를 넣어. 당신이 거기 가고 싶어한다면. 그리고 실제로, 이것이 꽤 좋은 솔루션입니다. 이제 한 손에, 나는 종류했습니다 의 악화 문제를했다. 네 멀리 떨어져 지금이다 그것이 있어야하는 곳에서. 그것은이 절반으로해야한다. 

하지만 당신은 알아? 즉 불운 수 있었다. 아마 여덟 여기에 있었다. 그래서, 어쩌면 우리는 것 운이 입수했습니다, 끝까지 여덟 가깝게 밀려. 하루의 끝에서 그래서, 그것은 종류의 모든 평균 밖으로. 우리는 약 4 상관 할 필요가 없습니다. 내가 지금 걱정하는 모든입니다 작은 요소를 선택하는 단계를 포함한다. 

그리고 지금, 나는 무슨거야 번호 하나 잊어하면된다 영구적으로, 내가 알고 있기 때문에 내 뒤에 목록은 현재 정렬됩니다. 그래서 내 목록은 이전에 크기 여덟 살. 지금, 그것은 크기 일곱입니다. 그래서 내 문제는 점점 선형이기는하지만, 작은. 그래서 지금, 나는를 선택하는거야 현재 가장 작은 요소, 두. 여섯, 여덟, 넷, 셋, 일곱, 다섯. 즉, 가장 작은 요소였다. 그래서 나는 일 해요 할 예정입니다 이름이 다시 무엇입니까? 

조셉 조셉. 

데이비드 J. 마란 : 조셉? 우리는 장소에 요셉을 떠날 것입니다. 지금, 나는 척하는거야 이 사람들이 잘으로 죠 것을, 내가 알고있는이 두 이미 분류되어 있습니다. 의 현재에 집중하자 목록의 나머지. 식스 전류 작다. 여덟 크다. 네 지금 현재 가장 작다. 세 지금 현재 가장 작다. 그리고 지금, 나는 세 가지를 선택하는거야 누가 이름이 다시 무엇 is--? 세레나 : 세레나. 데이비드 J. 마란 : 세레나, 당신이 할 수있는 경우 전화 번호 및 스왑 일 해요 잡아 KALSANG : Kalsang. 데이비드 J. 마란 : Kalsang. 돌아 가자, 우리는있어 그 두 가지를 교환하는 것. 그리고 지금, 자동 조종 장치에이를 만들어 보자. 내가 가서 너희에게 맡겨거야 다음 작은 요소를 선택합니다. 던, 암갈색, 암갈색, 암갈색. 네 번째, 당신은 무엇을해야합니까? 우수. 지금, 나는 또 다른 패스를 만들려고 해요. 던, 암갈색, 암갈색, 암갈색. 나는 다섯 다음 작다 참조하십시오. 지금, 나는 또 다른 패스를 받아 갈거야. 던, 암갈색, 암갈색, 암갈색. 식스 작다. 좋다. 세븐은 작은 것입니다. 변경 없음. 여덟 작은 것입니다. 완료. 

그래서 우리가 반복적으로 수행 한 이후 다른 하나의 요소를 선택 우린 뭔가를 구현한다 선택의 일종으로 공식화 것. 그것도 아마의 설명이 간단, 말 그대로 모든 당신을한다는 점에서 다만 계속되고 싶지 목록을 앞뒤로가는 선택한 다음 작은 소자 당신이 완료 될 때까지. 

그래서 아마도, 심지어 간단 직관적으로, 지난보다. 이제 마지막 하나를 해보자. 너희들은 스스로를 재설정 할 수 있다면 다음과 같은 위치에 마지막 시간, 보자 경우 우리는 할 수 없습니다 지금 한 다른 접근 방식을 공식화. 사실, 것 사람 거기에서 제안하고자 우리는이 일에 대해 어떻게 다른 사람을 갈 수 있습니까? 전문 용어 또는 정렬을 던지기없이 이미 알려진 답변, 그냥 직관적으로, 우리는 무엇을 할 수 있습니까? 

청중 : [들림]. 데이비드 J. 마란 : 그래. 그래서 거기에 훌륭한 직관이있다. 좋은 일들이 지금까지 일어날 것 우리가 분할 컴퓨터 과학 및 분할의 문제를 극복 그 절반의 절반과 절반. 그리고 참으로, 우리 그렇게 시작할 수 있습니다. 그리고 사실, 즉,로 우리가합니다거야 아직, 우리의 최상의 솔루션 중 하나를 참조하십시오. 그러나 이제 오래 전에 다시 그에게 올 수 있습니다. 사실, 우리는 할거야 조금 이번 주 그. 이 문제를 해결하기 위해 우리는 다른 무엇을 할 수 있는가? 그래서 여기에 모두에 겉으로는 임의의 순서. 당신은 무엇을 알아? 오히려 앞뒤로 이동보다, 앞뒤로 앞뒤로 때마다,이 같은 느낌 나는 산책을 많이하고 있어요. 이유는 단지에서 시작되지 않습니다 리스트의 처음 그냥 자신이 속한 네를 넣어? 그래서 내가이 순간을 위해 가정하자 그 내 목록은이 첫 번째 요소입니다. 네 시간이 순간에 정렬됩니다, 만약 내가 걱정 모두 다 여기에있다? 이 종류의 사소 사실, 권리인가? 하나의 숫자를 포함하는 목록과 마찬가지로 그 네 번째 분명 정렬됩니다. 

그래서 내가 그냥 규정하자 것을이 목록 정렬됩니다. 하지만 지금은이 목록의 나머지 부분을 가지고있다. 그래서 지금, 나는 두 발생합니다. 여기서 분명히 두 개의 작업을 수행 사에 대한 속해? 네 전에. 그래서 여기에 무엇을 할 수 있는가? 이름이 뭐라고? 

조셉 조셉. 

데이비드 J. 마란 : 조셉, 당신은 한 걸음 뒤로 물러나 수 있다면 전화 번호 그냥 잠시. 그리고 스테판 여기 지금 무엇을해야합니까? 의는 여기 스테판를 이동하자. 그리고 지금, 요셉이 여기에 오게. 그리고 지금, 내가 그 주장하자 여기에 모든 정렬됩니다. 따라서, 유사한 결과이지만 근본적으로 다른 접근 방식. 난 거기 무엇을보고하지 않았습니다. 난 그냥 요소를 계속 복용 그들이 나에게 건네있는 한, 그리고 그들과 거래. 

그래서 지금, 나는 여섯 번째를 참조하십시오. 어디 숫자 여섯 속해 있습니까? 우리는 2, 4, 여섯 있습니다. 정확히 그녀는 바로 지금입니다. 그래서 지금의이 혼자 떠나게하고, 목록의이 부분 주장 지금 정렬됩니다. 그리고, 이것은 근본적으로 느낀다 그 다른 난 그냥 해요 여기에 목록을 이동 선형, 나는 결코 다시 배로없는거야. 네. 괜찮아. 그래서 여덟, 당신은 어디에 속하십니까? 바로 여기에. 완벽한. 그래서 지금, 하나. 어 오. 이처럼이 느낌 비용이 될 것이다. 이제 이전 알고리즘에서 난 그냥 사람들을 바 꾸었습니다. 그래서 나는 그에게 모든 방법을 넣을 수 있습니다 시작은, 그러나 요셉을 움직였다. 하지만 지금은, 요셉을 이동하는 경우 무엇을 잘못 될 것? 

지금, 나는 일종의 내가했습니다 undone--했습니다 앞으로 다음 한 단계를 촬영 한 단계 뒤로, 지금 때문에 요셉은 순서가 될 것이다. 그래서이 작업을 수행 할 수 있습니다. 당신은 번호 하나를 수행 할 수 있다면 단지 잠시 뒤로 물러나. 우리는 어떻게 put-- 수있는 당신의 이름을 다시했다? 

아난 : 아난. 

데이비드 J. 마란 : 장소에서 아난? 무엇과 관련하여 일어날 필요 2, 4, 여섯, 8에? 그들은 모두 이동해야합니다. 여덟 그래서 만약 것은 이동하고 싶습니다 먼저, 다음 여섯, 다음 네, 다음 두 가지. 그리고 아난, 경우에 당신은 좋겠 좋은, 여기에 올 것을 좋아합니다. 그러나 여기, 우리는 단지했습니다 종류의 가격을 지불 알고리즘에서 다른 지점에서. 선택과 마지막 반면 종류, 심지어 거품 정렬, 내가 다시 걷고하고있어 앞으로, 뒤로, 확실히 어떤을 추가하고있다 시간적, 문자 그대로 단계적. 

삽입 정렬, 처음 이처럼 눈이 보인다 슈퍼 스마트하고 있다는 점에서 그냥 해요 천천히, 점진적 진전, 하지만 난 앞뒤로이 않을거야. 그러나 누군가가 실제로있는 경우 순서 예고 중 난 그냥해야했다 모든 작업. I는리스트의 절반을 이동했다 단지 숫자위한 공간을 마련합니다. 그래서 동일한 양의 작업의 지금까지를 작품의 단지 다른 종류의, 느낀다. 

의 계속하자. 그래서 지금 우리는 모든 것을 알고있다 (1 ~ 8) 사이에 분류되어 있습니다. 자, 내가 3 번 있습니다. 당신이 데리러 좋아하는 경우 3 번, 다시 한 단계. 그리고 무엇 너희들은 어떻게해야합니까? 네. 그래서 다른 한 개, 두 개, 세 단계입니다. 단지 비용을 시간의 세 가지 단위 나, 세 지금은 들어갈 수 있도록. 마지막으로, 일곱. 

이제 가서 보자 당신은 단계를 다시 가져 가라. 이것은 단지 우리를 비용 것입니다 한 시간 단위,하지만 괜찮아요. 그리고 지금, 다섯의 정보는 다음의 제품에가는 조금 더 비싼. 당신은 다시 단계를 원하는 경우. 우리는 팔을 이동해야 일곱, 여섯. 그리고 모든 사람들이 지금 정렬됩니다. 그래서 여기에 우리의 자원 봉사자에 큰 손. 정말 고맙습니다. 

[박수] 

여러분 모두 감사합니다. 여러분 모두 감사합니다. 그럼 지금 얼마나 보자 이 모든 비용이 많이 드는 것은이었다. 의 아마 생각해 보자 이들의 간단한 거품 정렬. 그리고, 단지 때문에 단순한 말 당신은 단지에 의해 탐욕을 해결할 수 있습니다 여기 페어의 문제를 해결. 페어의 문제를 해결 여기에, 또 다시 다시, 많은 반복 당신이 배는 실제로 필요가있다. 

그래서 밝혀 버블 정렬과, 음, 얼마나 많은 단계를 내가 걸릴해야합니까 그 알고리즘의 첫 번째 패스? 나는의 하나 see--하자 take-- 수 있습니다 둘, 셋, 넷, 다섯, 여섯, 일곱. 그리고 여기에 여덟 요소가있다. 그래서 n에 마이너스 1 단계처럼 목록의 시작 부분에서 얻을 리스트의 마지막. 

그러나 선택의 종류와, 난 리콜 또 다시 요소 선택 다시 즉, 최소의 나는 장소에 걸었습니다 하지만 난 아니에요 다시 내 뒤에 찾고. 그래서 조금 더 명확 생각 다음 처음 그, 나는 수도 모든 N 마이너스 1 단계를 수행해야 작은 요소를 찾을 수 있습니다. 그럼 난 자리에 넣어, 그리고 이전에 여기에 있었던 누구든지 퇴거. 

하지만 난 필요 없어 이 요소에서 계속 찾고, 내가 알고 있기 때문에 그것은이다 이미 작은. 그래서 지금, 난 그냥 7시에 볼 수있다 요소, 다음 여섯 요소, 다음 다음 다섯 가지 요소, 네 가지 요소. 그리고 수학적으로, N은이면 요소 나 숫자의 개수 우리가 시작, 당신이 상상할 수있는 N이 마이너스 1과 동일 함, 플러스 N 마이너스 2 단계, 플러스 N 마이너스 3 단계, 플러스 N 마이너스 4 단계, 모든 길 아래로 한 단계. 그리고 내 마지막 사람에있어. 

그리고 당신은 많은 것을 기억하는 경우 의 책이나 수학 책을 통계 에 그 공식을 가지고 다시 하드 커버 또는 그들 앞에서, 그것은이 시리즈 밝혀 더 간단하게 표현 될 수있다 n 배 n은 마이너스 2 이상 1. 그게 아니라면 그리고 그것은 괜찮아요 당신의 마음의 최전선에. 그러나 이것은 참으로 사실이다. 즉, 쓰기의 단지 간단한 방법입니다. 그리고 당신이 생각하는 경우 다시 초등학교에, 당신은 단지 곱 시작할 때 일 밖으로 물론이, 단지 N 제곱 마이너스 N 2로 나누어 져 있습니다. 내가했던 모든 확장이다 이 표현. 그리고이 해 다시 보자 약간 다르게. 즉 마이너스 N 2 N / 2의 제곱으로 나눈 것. 

그래서 다시, 난 그냥 가지 적용 해요 일부 연산이 규칙. 하지만 지금은 알이 큰 용어 이런 식으로, 말하자면 n은 제곱이다. 그래서 그래, 그것은 N 제곱의 2, 마이너스 N / 2로 나눈 값. 

그러나 일반적으로, n은,이면 큰 값이 될 것, 나는 그 N 제곱 항에 갈거야 지배적 인 요소가 될 것입니다. 그냥 될 것 더 큰 기여 N / 2보다 단계의 수. 그래서 나는이 무엇을 의미합니까? 심지어, 간단한 예제를 해보자 수학은 조금 큰를 얻을 수 있지만. 

그래서 우리는 백만명 있다고 가정 단, 또는 100 만 가지에 우리는 정렬 할 것이다. 의 백만을 연결하자 정확히 식으로 이 총 소요 얼마나 많은 단계를 확인합니다 말 사용 만 요소를 정렬하려면, 선택 정렬. 

그래서 우리는 이전과 동일한 공식이있을 것이다. 내가 얻을 수 있도록 나는 백만 플러그 것 백만, 2로 나눈 제곱 마이너스 만 2로 나눈. 나는 사전에 그 수학을하는 경우 여기에, 우리는 5000 억이 마이너스 50 만, 어떤 , 499,999,500,000 우리에게 제공 이는 무척 큽니다. 

사실, 당신은 지금 비교하는 경우 499000000000, 999000000, 우리의 원래 값에 대한 50 만, 5000 억, 그것은 그렇게 망할 가까이. 권리? N 2가 제공 나눈 제곱 us-- 또는 오히려, n은 2로 나눈 제곱 우리에게 5000 억을 주었다. 즉 무척는 가까이 499999500000로, 오프 50 만 뺀 말을하다, 또는보다 일반적으로, 오프 감산 N은 정말 큰 거래를 제곱. 이러한하게 N은 제곱 숫자는 정말 빨리 성장한다. 

이제, 이것은 단지 중요한 것이면 우리와 같은, 컴퓨터 과학자로서, 일반적으로 너무 많은 걱정하지 않을 수 있습니다 이러한 식의 뉘앙스에 대한 정확히 무엇을 정확한 답변입니다. 우리는 그, 그거 알아 케어? 하루의 끝에서,이 수식 제곱 N 정도이다. 

예, 우리는 거기에 2로 나눈 것입니다. 예, 우리는 오프 N 마이너스 2를 뺀 것입니다. 그러나 결국, 용어 정말 우리를 상처 우리를 비용 많은 단계는 정사각형 용어이다. 그래서 어떤 컴퓨터 과학자 일반적으로 할 것입니다 그 모두를 무시한다 작은 순서 조건, 단지 하나를 보면 그 비용에 가장 기여한다. 

그리고 이는 우리가 할 수있는, 좋은 지금 훨씬 더 일반성에 이야기 알고리즘에 대해, 그리고 그것들을 비교할 수있다. 난 그것과 사실 이 O를 사용하여 의도적이다. 나는 순서에 말할 때 의, 내가 특별히 해요 뭔가를 참조 큰 O. 큰 O라는 표기하는 컴퓨터 과학자는 설명하기 위해 사용 이 상단 뭔가에 바인딩됩니다. 

당신이 알고리즘이 있다고한다면 n은 제곱의 큰 O에, 내가 제안으로 단지 순간 전, 그 수단 자사의 실행의 관점에서 시간이나 효율성, 그것은 순서 취 n 개의 단계를 제곱. 어쩌면 이하, 어쩌면 더. 그러나 N의 제곱에 순서이다. 그리고 그 상한을합니다. 그것은 수 없을거야 보다 더 고통스러운. 그것은 N 제곱이 될 것, 또는 2 아니에요 N, 또는 훨씬 더 큰 뭔가. 이것은 바운드 위입니다 무엇에 그 비용이다. 그래서,하자 주어진 몇 가지 예를 고려해보십시오. 그리고 이것은 단지 유한 한 목록입니다 매우 일반적인 실행 시간 될 운명이야 알고리즘 우리가했습니다 몇 가지의 예시 이미 본. 

예를 들어, 케이스에 따라서 선택 정렬, 나는 여기에 무엇을 주장하고있어 그 선택 정렬의 실행이다 시간 N의 제곱에 순서이다. 최악의 경우, 내가 가진거야 여기에 임의의 숫자의 전체 무리. 그리고 우리는 수학적으로 본 것과 같이, 나는 계속 걸어 경우 목록을 통해 목록, 작은 다음을 선택 또 다시 요소, 나는 경우 실제로 모든 단계를 적어 나는 공식을 통해 (formulaically) 제안으로 내가 데려 갈거야 전에 제곱 N의 순서에있어 내가 데려 갈거야 단계. 

그리고 그 거품을 밝혀 정렬과 삽입 정렬 최악의 경우만큼 느리다. 예를 들어, 고려, 삽입 정렬, 우리가 처리 맨 마지막 알고리즘, 이는, 우리가 요소를 보면했다 자신이 속한 곳 다음 삽입합니다. 그리고 우리는 다음 요소로 보았다, 그것이 속하는 곳을 삽입하고. 

그래서 최상의 시나리오를 고려하십시오. 내 자원 봉사자들이 줄을했다 가정 말 그대로이 같은 여덟 통해 하나, 이미 정렬. 삽입 정렬은 얼마나 많은 단계입니다 팔명를 정렬하는 걸릴 것, 그들은 무대에 도착하는 경우 이처럼 보이는? 

8 명이이 이미 정렬. 그리고 삽입 정렬을 사용합니다. 알고리즘의 마지막. 음, 정말 빨리를 재현 할 수 있습니다. 여기 시작 그래서 만약, 내가 하나를 참조하십시오. 어디 하나에 속해 있습니까? 그것은 바로 여기에 속한다. 나는 두 가지를 참조하십시오. 어디 두 속해 있습니까? 바로 여기에. 나는 3을 참조하십시오. 어디 세 속해 있습니까? 바로 여기에. 

나는 네를 참조하십시오. 바로 여기에. 다섯, 여섯, 일곱, 여덟. 자신을 반복 할 이유가 없습니다. 그리고, 얼마나 많은 단계 즉, N의 관점에서 무엇입니까? 또한 N의 순서에있어 단계, 오른쪽? N 마이너스 1. 하지만 선형 수를했다 단계로, 지금은 끝났어요. 그래서하지만, 최상의 경우이다. 어떤 최악의 경우는 어떻습니까? 무엇 여덟, 저기 있었다 일곱은이 아래로했다 그리고 하나, 둘, 그래서, 여기에 있었다 목록은 정말 반전 있다고? 

글쎄, 무슨 일이 실제로 발생 이 번호는 경우? 그리고 우리는 예 단지 몇을 다하겠습니다. 어떤 숫자 8 참으로, 경우 여기에, 그리고 number-- 으악. 그래서 만약에, 참으로, 수 여덟, 여기에 모든 방법입니다 나는 삽입 정렬을 사용하고 있습니다? 

그래. 나는 그것이 장소에서의 순간에 주장한다. 하지만 지금은, seven-- 곳 일곱 갈입니까? 물론, 여기 간다. 그래서 한 곳 이상 팔을 이동해야합니다. 지금 여섯, 어디로 가야합니까? 음, 좋아. 지금, 나는 이상 팔을 이동해야 장소와 장소를 통해 일곱, 그리고, 나는 여섯 아래로 풍덩. 

그래서 처음, 그것은 선정 일을 해결하기 위해 나를 한 단계, 다음은 일을 해결하기 위해 나에게 두 단계를 요했다. 얼마나 많은 단계입니다 해결하기 위해 걸릴 것 바로 이곳에 오 넣어 것? 세 가지. 지금은해야하기 때문에 하나 둘, 셋을 이동합니다. 얼마나 많은 단계를이 걸릴 것입니다 바로 이곳에서 네를 넣어? 4 플러스 5 플러스 6 플러스 7. 

그리고 그것은 수학적으로 동일한이다 우리는 선택의 종류에 대한 설명 무엇. 우리는이 시리즈가 그것은 단지 증가합니다. 1 플러스 2 플러스 3 플러스 4, 또는 반대로, 7 플러스 (6) 플러스 5 플러스 4 오늘의를 위해 추가 N의 순서에에 목적 제곱. 

그래서 나도 그 규정하자 버블 정렬은 n이 제곱에 있습니다. 때문에 거품 정렬, 각각 시간 나는 목록을 이동 나는 대략 얼마나 많은 단계를 데려 갈거야? 때마다 나는 그대로 거기에서 거기까지 걸어? 대략 N 단계. 그러나 얼마나 많은 시간 나는 수도 목록을 갈 필요가? 

음, 대략 N 시간. 아마 N 마이너스 1 만 약 n 배. 글쎄, 그건 왜? 음, 거품 정렬과, 경우 우리는 거품 정렬 시작 최악의 목록 다시 완전히 상황, 거꾸로, 어떤 일이 일어날? 나는 목록을 이동 한 수 하나는 거기에 모든 방법을 속한다. 

그러나 버블 정렬로, 얼마나 멀리 하나를 수행합니다 목록을 내 첫 번째 패스를 이동? 얼마나 많은 명소 것은 그가 나올까요 올바른 위치에 가까운? 딱 하나만. 그래서이 과정의 경우 가지 이유 이 알고리즘을 통해마다 다윗의 복용 약 N 단계. 그러나 얼마나 많은 패스 리스트를 통한 인 거품에 하나 걸릴 것 자신이 속한 왼쪽으로? 

그는, 같은 이동있어 n 개의 공간이 방법. 그러니 그냥 목록의 정렬을 수행하기 위해, 나는 앞뒤로 N 시간을 걸어야한다. 그리고 때마다, 나는 해요 N 요소를 찾고 있습니다. 그래서에 n 개의 물건 n 번을 N의 순서가 제곱. 

이제, 우리는 일부에서 볼 수 있습니다 반바지의 CS50의 다음 문제에 포함 된 다음에, 또 다른 접근 방법을 설정, 하지만 지금은, 그냥 생각 해보자 다른 실행 시간, 특히 정렬 사람이 취할 경우 약간의 시간이에서 침몰합니다. 어떻게 우리가 이미 본 적이 알고리즘의 즉, N 단계의 순서를 취한다? 

선형 수를 취해야 의는 우리가 지금까지 본 적이 있다고 단계? 그게 뭔데? 전화 번호부 검색. 첫 번째 알고리즘. 권리? 우리는 선형있어 어디 마이크 스미스을 검색 하시나요? 사실. 주 제로에서, 나는 시작했을 때 한 번에 한 페이지를 선회, 나는 심지어 종류라고 말했다 선형 느낌 알고리즘, 우리는에 그 사진을 가지고 있었다 직선 레드 라인 보드 과 직선 노란색 라인, 그 참이었다 N의 큰 O에있는 알고리즘. 

휴대폰에 마이크 스미스를 찾을 수 있기 때문에 최악의 경우에 해당 페이지의 책, 나 N 조치를 취할 수 있습니다. 출석을 복용에 대해 무엇? 일이 삼 사 오 육. 이것의 실행 시간에 무엇입니까 출석을 촬영 알고리즘? 때문에 이론적으로 N의 빅 오, 나는 방에있는 모든 사람을 가리 키도록해야합니다. 

이제 옆으로, 일에 대해 주 제로에서 다른 최적화? 둘, 넷, 여섯, 여덟, 열, 12. 컴퓨터 과학자 것 실현 잠깐, 그 순서에의 n은 두 단계로 나눈. 권리? 내가 한 번에 두 사람이하고 있어요 때문입니다. 그러나 우리는 무시하는거야 그 낮은 순서의 조건, 그리고 우리는 단지에가는거야 (2)에 의해 분할을 버리고, 그냥 말 N의 큰 O 뿐만 아니라 그 알고리즘. 

이건 어때? 우리는이 중 일부를 건너,하지만 거 야 N의 로그했다 알고리즘을했다? 즉 대략 N 단계를 기록 걸렸다? 분할 및 정복. 정확히. 전화 번호부 예 에서처럼 주 제로 오늘 아침, 여기서 우리는 문제를 분할 다시 다시 다시. 우리는 주에 칠판에 그린 곡선 녹색 선 제로, 우리는 그 날했다 로그 알고리즘. 

그리고 실제로, 수는 단계를 분할을 수행하고 정복하는 데 걸리는, 또는 이진 검색으로에게 우리는 시작합니다 전화 번호부에서와 같이, 그것을 호출 로그 및 단계의 순서이다. 그리고 이것은 이상한 하나의 비트입니다. 

한 단계 무엇이, 상세하게 단계의 상수? 어쩌면 그것은 어쩌면 세 가지이다, 2의, 그러나 컴퓨터 과학자 단지 1 큰 O로 단순화 일부 단계 상수. 당신이 그렇게 할 수있는 일이 무엇입니까 단계의 일정한 수를한다? 

박수의 실행 시간은 무엇입니까? 일정 시간. 권리? 마찬가지로,의 실행 시간 무엇을 한 소요 아무것도 동작, 같은 F 안녕하세요 세계를 인쇄 할 수 있습니다. 즉, 일정 시간이라고 할 수도 인쇄 F 덜 코너의 경우를 제외하고, 어떤 실행 시간을 수도 인쇄의 F 실제로 수? 그리고 왜? 이 경우에 N 측정은 무엇인가? 

청중 : [들림]. 데이비드 J. 마란 : 맞아요. 문자의 수 우리는 인쇄 할. 그래서 매우 상황에 맞는이다. 오늘, 우리는에 많은 초점을 맞추고있어 문자와 여기 보드에 숫자. 그러나 그것은 또한 수 있습니다 실제 문자열의 문자. 다른 거기 밖으로 그래서집니다 대한 배려가 시작됩니다 측정, 그 반대의 빅 오의, 말하자면. 

즉, 오메가 표기법입니다. 큰 O는 무엇을 의미하는 반면 상단 당신의 실행 시간에 바인딩? 최대로, 얼마나 많은 시간을 일이 걸릴 수 있습니다? Omega-- 죄송이오고 계속 up--은 그 반대입니다, 그것은 하한 켜져있다 시간 뭔가의 양이 걸릴 수 있습니다. 

겠어요 - 예를 들어, 어떤 일이 알고리즘이다 즉, 항상 N 제곱 단계를 수행? 음, 알고리즘 중 하나는 우리가 본 것 오늘은, 사실, 그뿐만 아니라이 될 수 있습니다. 선택 정렬. 선택 정렬 꽤 바보. 심지어 심지어 algorithm-- 죄송 경우 배열이 이미 정렬되어있는 경우, 선택의 종류에 가고 목록을 계속 걸어 이 작은이 있는지 확인합니다 요소 다시하고 다시하고 다시. 그리고 당신은에 인간하더라도 관객은 잠깐 것을 알고, 당신은 이미 통과 작은 요소, 컴퓨터 보이는 때까지 몰라 목록을 모든 방법. 마찬가지로,이 낮은 것을 바인딩 또한 고려 될 수도 선형 시간이 될 수 있습니다. 

그것은에 얼마나 많은 시간을 차지하나요 최적의 정렬 n 개의 요소 버블 정렬과 같은 것을 사용하는 경우? 목록이 이미 정렬됩니다 가정하자. 우리는 거품 정렬가 필요했다 N의 순서는 단계 제곱. 그러나 이미 무엇을 분류 거라면? 당신이 후 실현 경우 배열을 하나의 통과 것을 당신은 스왑을하지거야? 당신은 패스 더 만들고 유지해야합니까? 

아니. 그래서 낮은 버블 정렬에 바인딩 선형라고 할 수 있습니다. N의 오메가. 그리고 우리는 볼 수 있습니다 뿐만 아니라 이들의 다른 사람. 그럼 잠깐 살펴 보자 여기에 단지 시각화에서 이러한 자신을 구별하는 방법을 볼 수 있습니다. 나는이에 여기 아래로 갈거야 C50의 웹 사이트에서 확인할 수의 페이지, 하지만 작업을 얻을 수있는 고통이 될 것입니다, 그것은라는 기술을 이용하기 때문에 를 자바 애플릿, 요즘 대부분 지원되지 않는, 적어도 크롬과 어떤 다른 사람에 의해. 

그리고 내가 가서이 속도를하자 위로 무슨 일이 일어나고 있는지에 대해 설명합니다. 이 거품의 데모입니다 종류, 첫 번째 알고리즘은 우리가 바라 보았다. 그리고 그것은 그에서 시각화 각의 이 바의 수를 나타냅니다. 큰 바, 수 더 큰. 작은 바, 수치가 작을. 그리고 당신도, 시각적으로 볼 수있는 이 있지만, 슈퍼 빠른 것입니다 , 빨간색 막대 나 같은 점이다 뒤로 걷는 등의 문제를 해결. 당신은 더 큰 요소를 볼 수 있습니다 실제로 오른쪽까지 버블 링되어, 그리고 작은 요소 왼쪽까지 버블 링됩니다. 그리고 여기 아래, 우리의 경우 실제로 더 자세히 보면, 우리는 사실을 믿을 수 비교와 스왑의 수 즉 만들어지고 있었다. 

하지만 그 대신, 이제 살펴 보자 두 번째 알고리즘에 우리는 함께 이전 보았다 우리 자원 봉사자, 선택 정렬. 시각, 그것은이 매우 다른 효과. 그러나에, 다시, 매우 직관적 우리는 작은 다음을 선택 유지하는 것이 요소, 우리는 약간의 행운이있어. 즉, 근본적으로 빠르게 느꼈다. 그러나 우리는 또 다시이를 실행 한 경우 다시 입력이 많은, 우리는 그것이 실제로 있다고 볼 것이다 아직 N의 큰 O에 제곱. 

이제 마지막 하나를하자 여기에, 삽입 정렬, 이는 세 번째 알고리즘이었다 우리는 리콜 보았다 이 사람은 다루고 있음 요소가 그들을 발견으로, 그러나 그것은 어쩌면 이동 가지 이상 공간을 확보하기 위해 자신이 속한 요소를 삽입. 

그리고이 너무을주는 끝 최종 결과. 이제 그 모든 세 꽤 빨리 느꼈다. 그리고 사실, 나는 그들을 실행 꽤 좋은 클립에서. 그러나 근본적으로, 그들은 모든 것 꽤 무서운, 솔직히 말해서. 이러한 알고리즘은 모두 지금까지 N의 큰 O에서 실행되는 제곱 꽤 걸릴 시간은 결국 실행합니다. 

그리고 실제로, 우리는 볼 수 있습니다 그리고 마지막으로이 느낌 나는이 세 번째이자 마지막 데모를 끌어합니다. 이것은 또 다른입니다 그 시각화거야 왼쪽에 거품 정렬을 표시하려면, 중간에 선택 정렬, 뭔가 중 하나로서 우리 손, 이전 제안 제기 오른쪽 정렬을 병합합니다. 분할 및 정복 오른쪽 전략. 그리고 우리가하는지, 사실이야 수요일에 볼 것. 그러나의 병렬로 실행하려면 다음 시간을 할 수 있습니다. 이것은 대략 동일한 수의 요소들은 모두 동시에 실행. 선택 대 버블 정렬 병합 정렬 대 정렬. 

지금, 그들은 모두 실행하고 동시에 이론. CPU가 실행되고 같은 속도,하지만 이 얼마나 지루한 느낄 수있다 매우 빠르게 될 것, 다만 얼마나 빨리 할 때 우리는 주의 비트를 삽입 제로의 알고리즘 수 우리는 일을 속도. 

그리고 지금의 비교하자 마지막 형태의이. 나는 앞서 갈거야 CS50의 웹 사이트에 우리는 오늘이 마지막 링크가 어디 인터넷에서 사람 친절하게 비디오를 함께 넣어 그 어떤 다른 정렬을 캡처 알고리즘은 같은 소리. 이것은 삽입 정렬이다. 

[삐 '소리] 

이에 당신이 주파수를 적용하고 바 바의 높이를 기준으로합니다. 이 거품의 일종이다. 

[뒤틀린 '삐'소리] 

오는 is-- 다음 깨달음 위로 다음 is-- 선택 정렬, 여기서 다시, 우리는 선택하고 다음 작은 요소, 우리는 성장하고 볼 수 있습니다 왼쪽에서 오른쪽으로. 

우리의 우승자 지금까지 오늘, 일종의 병합합니다. 이 일을 나누어 어떻게 주목 [들림] 반 분기에. 우리가하지 않은 그놈 종류, 에 대해 이야기하고, 시각적으로 작성 그리고 조금 audally 다른 모양과 소리. 앞뒤로가는, 물건을 청소. 또한 힙 정렬을 체크 아웃 이 남자의 웹 사이트에. 

그리고 그것 뿐이다. 우리는 당신이 다음 번에 ​​볼 수 있습니다. 

[휙 음악]