[음악 연주] DAVID 마란 : 좋아요. 좋아, 다시 오신 것을 환영합니다. 그래서 이것은, 처음 4 주입니다 그 이미. 그리고 당신이 지난 주 기억 할 것이다, 우리는 둘 조금만 위해 따로 코드 우리는 좀 더 얘기를 시작했다 같은 높은 수준에 대한 것들 어느 있지만, 검색 및 정렬 약간 간단한 아이디어가있다 문제의 클래스 대표 당신은 특히 해결하기 위해 시작합니다 당신은 마지막에 대해 생각을 시작으로 프로젝트와 흥미로운 솔루션을 당신 실제 문제가있을 수 있습니다. 이제 버블 정렬은 가장 간단한 중 하나 이러한 알고리즘, 그리고 이 작은 숫자를함으로써 일 목록 또는 배열의 종류에 정상까지 거품 그들의 방법을하고, 큰 숫자는 그들의 방법을 아래로 이동 이 목록의 끝. 그리고 우리는 시각화 할 수있는 기억 버블 정렬 작은 이런 식으로 뭔가. 그래서 내가 가서 시작을 클릭하자. 나는 버블 정렬을 미리 선택했다. 그리고 당신이 기억하는 경우 그 키가 파란색 선 작은, 큰 숫자를 나타냅니다 파란색 선은 작은 숫자를 나타냅니다 우리는 또 다시 통과하고 또, 각각 다음 두 줄을 비교 빨간색 다른, 우리는을 교환 할거야 가장 큰 경우 작은 그들은 순서가. 이에 가서에 가서 갈 것이다 그래서 에, 당신은 그 큰 볼 수 있습니다 요소에 그들의 방법을하고 있습니다 오른쪽, 그리고 작은 요소는 왼쪽에 그들의 방법을 만드는. 그러나 우리는 정량화하기 시작했다 효율성, 이 알고리즘의 질. 그리고 우리는 말했다 최악의 경우,이 알고리즘했다 대략 몇 단계? 그래서 N 제곱. n은 무엇 이었습니까? 대상 : 요소의 수. DAVID 마란 : 그래서 n은이었다 요소 수. 그래서 우리는 종종이 작업을 수행 할 수 있습니다. 우리는 크기에 대해 이야기 할 때마다 문제 또는 크기의 입력하거나 걸리는 시간 출력을 생성하기 위해, 우리는 단지 거 일반화의 어떤 입력은 N 같습니다. 그래서 다시 주 0에서 수 페이지 전화 번호부에 N이었다. 학생 수 방에 n을했다. 그래서 여기, 너무, 우리는 다음과 같은거야 해당 패턴. 이제 N 제곱 특히 아니다 빠른, 그래서 우리는 더 잘하려고 노력했다. 그래서 우리는 몇 보았다 다른 알고리즘, 그중 선택 정렬되었습니다. 했다 선택 정렬 그래서 조금 다른. 거의 간단했다, 내가 감히, 나는의 시작에서 시작 약자 자원 봉사자의 목록 I 그냥 다시 다시하고 다시는 관통 작은을 뽑는 목록 시간 요소 또는 그 퍼팅 그녀의 목록의 시작 부분에. 하지만이 역시 일단 우리가 생각하기 시작 수학 및 큰을 통해 그림은 몇 번이나 생각 나는 앞으로 다시 되돌아 가게되었다 앞뒤로, 우리는 최악의 경우라고 선택 정렬도 무엇인가? N 제곱. 이제 현실 세계에서, 그것은 수도 실제로 소폭 빠르게합니다. 다시 있기 때문에, 계속해야하지 않았다 내가 분류 한 번 되돌아 작은 요소입니다. 그러나 우리는 매우 큰 N에 대해 생각하고 있다면 당신은 일종의 수학 등을 할 경우 나는 N 제곱으로, 보드에 한 마이너스 뭔가 다른 모든 N 제곱, N이 외에 정말 큰 가져온하지 않습니다 정말 많은 문제. 그래서 컴퓨터 과학자로, 우리는 일종의 작은에 외면 요소 만 요인에 초점 만드는 것 표현 가장 큰 차이. 음, 마지막으로, 우리는 보았다 삽입 정렬에서. 그리고이 정신 유사했지만, 반복을 통해 이동보다는 에서 작은 요소 하나를 선택 시간은 내가 대신 손을 잡고하는 I 모두, 처리, 나는 결정했다 좋아, 여기에 속한다. 그럼 난 다음 요소에 이동 하고 결정하는 그 또는 그녀는 여기에 지배했습니다. 그리고 난과에 옮겼습니다. 그리고, 길을 따라, 할 수도 없습니다 하기 위해서는 이러한 사람들을 이동 그들을위한 공간을 만듭니다. 그래서 그 정신 반전의 종류이었다 선택 정렬의 우리 삽입 정렬을했다. 그래서 발생하는 이러한 주제 현실 세계합니다. 몇 년 전, 때 특정 상원 의원은 대통령에 출마했다 에릭 슈미트 (Eric Sc​​hmidt),시 CEO 구글은 실제로 기회를 가졌습니다 그를 인터뷰. 그리고 우리는 우리가이 유튜브를 공유하는 줄 알았는데 우리가 좋아질 수 있다면, 여기 당신을 위해 클립 볼륨입니다. [동영상 재생] - 이제, 상원 의원, 당신은 구글에서 여기 나는 대통령의 생각처럼 면접 등. [웃음] - 지금은 구하기 힘든 거지 대통령으로 작업. 그리고 당신은을거야 지금은 엄격. 그것은 구글에서 일을하는 것도 어렵다. 우리는 질문을 가지고 있고 우리는 질문 우리의 후보 질문. 이 사람은 래리 쉬머에서이다. [웃음] - 너희들은 내가 농담하는 것 같아? 바로 여기이다. 가장 효율적인 방법은 무엇입니까 만 두 비트 정수를 정렬? [웃음] - 글쎄, 어 - - 미안 해요. 어쩌면 우리가해야 - - 아니, 아니, 아니, 아니, 아니. - 그게 아니라 - 확인을 클릭합니다. -I는 버블 정렬은 것 같아요 갈 길을 잘못합니다. [웃음] [갈채와 박수] 그이 말했다, 누가 - 가자! 확인을 클릭합니다. [END 동영상 재생] DAVID 마란 : 그래서 당신이 그것을 가지고. 그래서 우리는 이러한 실행을 정량화하기 시작했다 시간, 그래서 뭔가, 말하자면 이다 점근 표기법이라고 그냥 돌려 우리의 종류를 참조 장님 그 작은 요인에 눈 단지 실행 시간에 찾고, 이러한 알고리즘의 성능, 여기서 n은 시간이 지남에 정말 많은수록. 그래서 우리는 큰 O. 큰 O를 도입 우리가 생각하는 표현인가 상한으로의. 실제로, 배리, 우리는 낮출 수 있습니다 마이크 조금 이상? 우리는이 상한이다 생각했다. N 제곱을 의미하므로 큰 O에서 해당 최악의 경우, 같은 선택 정렬은 걸릴 것 제곱 단계를 명. 삽입 정렬처럼 또는 뭔가 N 제곱 단계는 것이다. 이제 삽입과 같은 뭔가를 정렬 최악의 경우 무엇 이었습니까? 배열을 지정해, 무엇 최악의 당신이 찾을 수있는 가능한 시나리오 스스로에 직면? 확실히, 완전히 거꾸로입니까? 완전히 거꾸로의 경우 때문에, 당신은 일의 전체를 많이해야 해요. 때문에 당신은 완전히 거꾸로 있다면, 당신을 찾을거야 여기에 가장 큰 요소에도 그것은 거기 속한다. 그래서 당신은에서 말 모든 권리거야 시간이 순간, 당신은 여기에 속한다 그래서 당신은 혼자 둡니다. 그럼 당신은, 오, 실현 빌어 먹을, 난에있다 이 약간 작은 요소로 이동 당신의 왼쪽. 그럼 난 다시 할 필요가 그리고 또 다시. 그리고 앞뒤로 걸어 경우, 의 성능을 느낄 일종의 것이다 이 알고리즘 때문에 지속적 나는 어디로 아래로 다른 사람을 걸어 갔다 그것을위한 공간을 만들기 위해 배열입니다. 그래서는 최악의 경우입니다. 대조적으로 - 이것은 마지막 클리프 행어이었다 - 우리는 말했다 삽입 정렬 무엇 오메가인가? 최상의 경우의 실행은 무엇입니까 삽입 정렬의 시간은? 그래서 실제로 보군. 그것은 우리가 떠난 빈이었다 보드의 마지막 시간입니다. 그리고 N의 오메가 이유 때문입니까? 물론, 가장 좋은 경우에, 무엇을 삽입 정렬이 전달 될 것? 완전히 분류의 우물, 목록 이미 할 수있는 최소한의 일. 하지만이 삽입 정렬에 대한 스트레이트의 그것은 여기 시작하고 있기 때문이다 결정, 오, 당신은 수있다 하나는, 당신은 여기에 속한다. 오, 행운. 당신은 두 번째입니다. 당신은 또한 여기에 속한다. 더 나은 셋째, 당신은 여기에 속한다. 그것은의 끝에 도달하자마자 목록, 당​​ 삽입 정렬의 의사 우리는 구두를 걸어 마지막으로, 그것은 이루어집니다. 하지만, 선택 정렬, 대조적으로, 뭐 계속? 보관은 목록을가는 다시하고 다시하고 다시. 키 통찰력 만이 있었으므로 당신은 모든 방법을 검토 한 후 목록의 끝에 당신은 확신 할 수 있습니다 선택한 요소라고 실제로 현재 가장 작은 요소입니다. 서로 다른 정신 모형의 끝은 이렇게 매우 현실 세계를 산출까지 우리의 차이뿐만 아니라, 이러한 이론적 점근 차이. 그래서 그냥 N 큰 O, 다음, 요점을 되풀이하는 제곱, 우리는 몇 가지 예를 본 적이 지금까지 알고리즘. N의 큰 O? 수있는 알고리즘은 무엇입니까 N 큰 O라고 할? 최악의 경우, 그것은 걸립니다 단계의 선형 수. OK, 선형 검색 할 수 있습니다. 그리고 최악의 경우, 어디에 요소 당신은 언제 찾고 선형 검색을 적용? OK, 최악의 경우, 심지어이 아니다. 또는 두 번째 최악의 경우, 그것은이다 는 결국 모든 방법, 플러스 마이너스 한 단계의 차이. 그래서 하루의 끝에, 우리는 선형 말할 수 있습니다. N의 큰 O는 선형 검색 될 것 최악의 경우, 때문에 요소도이 아니라 나입니다 끝에서 끝까지. 음, N의 로그의 큰 O. 우리에 대해 아주 자세하게 얘기하지 않았다 이, 그러나 우리는 전에 본 적이 있어요. 무엇 소위 대수에서 실행 시간, 최악의 경우? 네, 이진 검색. 최악의 경우와 이진 검색 어딘가에있는 요소가있을 수 있습니다 중간, 또는 어딘가에 배열의 내부. 그러나 당신은 일단 당신이 그것을 발견 에 반으로 목록을 나눕니다 절반, 절반, 절반합니다. 그리고 짜잔, 그것은이있다. 아니면 다시, 최악의 경우, 심지어이 아니다. 하지만 당신은 그것이 존재하지 모르겠어요 당신은 종류의 마지막에 도달 할 때까지 절반으로 최하위 요소 그리고 절반과 절반. 1 큰 O. 그래서 우리는 3 중 2 큰 O의 큰 O 할 수 있습니다. 당신은 단지 상수를 원하는 언제든지, 우리는 그냥 간단하게 일종의 그 1 큰 O로. 도 현실적으로 걸리는 경우 비록 그것은의 2 또는 100 단계, 경우 단계 상수, 우리는 단지 1 큰 O 말한다. 의 알고리즘은 무엇입니까 1 큰 O에서? 대상 : 길이를 찾기 변수의. DAVID 마란 : 찾기 변수의 길이는? 대상 : 아니, 길이 그것은 이미 정렬 거라면. DAVID 마란 : 좋은. 좋아, 그럼 뭔가의 길이를 찾는 만약 같은 무언가의 길이, 배열은, 어떤 변수에 저장됩니다. 당신은 그냥 변수를 읽을 수 있기 때문에 또는 변수를 인쇄하거나, 그냥 일반적으로 해당 변수에 액세스 할 수 있습니다. 일정 시간이 소요 봐라. 대조적으로, 스크래치 다시 생각합니다. C의 첫 주에 다시 생각, 그냥 printf의 호출 및 인쇄 화면에 무언가가 틀림없이 있습니다 일정 시간이, 그냥 걸리기 때문에 표시하는 CPU 사이클의 일부 수 경우, 화면에 텍스트를 입력합니다. 또는 대기 - 그것은 무엇입니까? 어떻게 다른 우리를 모델링 할 수 printf의 성능? 누군가가 동의하고 싶습니다 어쩌면 정말 일정 시간이 아니다? printf를 달리고 있습니다 어떤 의미에서 시간은 사실에 문자열을 출력 화면이 뭔가 상수가 아닌. 대상 : [들림]. DAVID 마란 : 네. 그래서 우리의 관점에 따라 달라집니다. 우리가 실제로에 대한 입력으로 생각하면 문자열 것으로 printf를하고, 그러므로 우리는 그것의 크기를 측정 그 길이로 입력 - 지금의 호출하자 그뿐만 아니라 길이 N - 틀림없이, printf의 자체 n은 큰 O입니다 당신 N 조치를 취할 것 때문에 그 N의 각을 인쇄하려면 대부분 문자. 적어도 우리가 생각하는 정도 아마 루프를 사용하고 있다고 후드 아래에. 그러나 우리는보고해야 할 것 그것을 더 잘 이해하기 위해 코드입니다. 그리고 실제로, 일단 너희들 시작 당신은 당신의 자신의 알고리즘을 것이다 분석 그대로 그냥 그렇게. 안구의 정렬 코드와 생각 약 - 괜찮아,이 루프를 가지고 여기 아니면 여기에 중첩 루프가 N 물건을 n 번 수행 할거야 그 그리고 당신은 이유의 방법을 정렬 할 수 있습니다 코드를 경우에도 그것은의 의사가 아닌 실제 코드입니다. 그래서 제곱 N의 오메가 어떨까요? 알고리즘은 무엇입니까있는 베스트의 사건은 여전히​​ 갔다 N 제곱 단계? 그래? 대상 : [들림]. DAVID 마란 : 그래서 선택 정렬. 이 문제에 실제로 감소하기 때문에 또, 내가 모르는 사실 내가 때까지 현재 작은 발견했습니다 난 이놈의 요소를 검사했다. N, 말, 너무 오메가, 우리 단지 하나 내놓았다. 삽입 정렬. 목록 정렬 할 것을 일어나는 경우에 이미 최상의 경우에 우리는 단지이 그것을 통해 하나의 통과를 만들기 위해, 이는 우리가 확실 시점에서. 그리고 말할 수있다 그 확실히, 선형 수 있습니다. 1 오메가 어떻습니까? 최상의 경우에 걸릴 수 있는가, 단계 상수? 그래서 선형 검색, 당신은 단지 운 경우 당신이 찾고있는 요소 , 목록의 시작 부분에 맞는 당신이 시작하는 곳이라면 이 목록의 선형 탐색. 그리고 이것은 마찬가지입니다 가지 수. 예를 들어,도 진 검색 결과 1의 오메가이다. 당신은 정말 터무니 무엇을 얻는 경우에 때문에, 의 중간에 행운과 입맛을 다시 한 덩어리 귀하의 배열은 번호 당신이 찾고있는거야? 그래서 당신은뿐만 아니라, 거기에 운이 수 있습니다. 이 하나, 마지막으로, N 로그 N의 오메가. 그래서 N 로그 N, 우리가 정말하지 않았다 아직 얘기하지만 - 대상 : 정렬 병합? DAVID 마란 : 병합 정렬. 즉, 마지막의 클리프 행어했다 우리는 제안, 우리는 보여 주었다 곳 시각적 알고리즘이 있다는 것을. 단지 하나의 정렬 병합 기본적으로 빠른 알고리즘 다른 사람의 일부보다. 사실에서뿐만 아니라 짧은 병합 최악의 최상의 경우 N 로그 N, 경우 N 로그 N. 그리고 당신이 우연의 일치가있을 때 오메가 큰 O는 같은 것 인? 우리가 실제로 무엇으로 그렇게 설명 할 수 그것은 비록, 세타라고 덜 일반적인. 하지만 단지 두 개의 범위를 의미 이 경우 동일합니다. 그래서 정렬을 병합이 어떤 작업을 수행 우리에게 정말 졸이다? 그럼, 동기를 기억합니다. 내가 다른 애니메이션이를 끌어하자 우리는 지난 시간에 보이지 않았다. 이 하나의 같은 생각하지만, 조금 더 크다. 내가 가서 지적하는거야 첫 번째 - 우리에 삽입 정렬을 왼쪽, 다음, 선택 정렬, 버블 정렬, 다른 종류의 몇 - 쉘 및 빠른 - 우리가 이야기하지 않은 에 대한, 그리고 힙 정렬을 병합합니다. 적어도 당신의 눈을 집중하려고합니다 그래서 그런 다음 왼쪽에있는 세 개의 상단 및 내가 클릭하면 정렬 병합 이 녹색 화살표. 하지만 난 그냥에, 그들 모두 실행할 수 있습니다 당신의 다양성의 감각을 제공합니다 세계에 존재하는 알고리즘. 나는이 실행을 두지 않을거야 몇 초. 그리고 당신은 당신의 눈을 집중하면 -를 선택 단지에 대한 알고리즘은, 그것에 초점 초 - 당신을보고 시작합니다 이 구현 그건 패턴입니다. 병합 정렬 통지가 이루어집니다. 힙 정렬, 빠른 정렬, 쉘 - 우리는 세 가지를 소개하므로 보인다 최악의 알고리즘 지난 주. 그러나 그것은 우리가 오늘 여기에 걸 좋은 병합 정렬 보면, 그 중 하나입니다 쉽게 사람도, 보는 것입니다 아마 당신의 마음을 구부릴하지만 단지 조금. 여기에 우리가 볼 수있는 얼마나 많은 선택 정렬 안됐다. 하지만 플립 측면에서, 그것은이다 구현하기가 정말 쉽습니다. 그리고 아마 P 세트 3, 그 중 하나 당신이 구현하는 선택 알고리즘 표준 에디션. 완벽하게 정확하고 완벽하게 정상적으로. 그러나 다시, n은 많은수록, 만약 당신 빠른 알고리즘을 구현하도록 선택할 정렬 병합 좋아 확률이있는 크고있다 큰 입력, 코드는 단지 빠르게 실행하는 것. 귀하의 웹 사이트가 잘 작동거야. 사용자가 행복 할 것입니다. 그리고 이러한 효과가 있습니다 실제로주는 우리 좀 더 깊은 생각했다. 그럼 병합했는지 살펴 보자 정렬에 관한 모든 사실이다. 좋은 점은 병합이다 정렬은 이것이다. 이것은 우리가 호출 한 것을 다시이며, 의사, 의사의 존재 영어의 문법. 그리고 단순하다 매력의 종류. 따라서 해당 요소의 입력에 - 그래서 그냥 의미, 여기 배열입니다. 그것은 그것에서 N 물건을 가지고있다. 그것은 우리가 말하고 전부입니다. n은 2보다 적은 경우, 반환합니다. 그래서 그냥 사소한 사건. n은 2보다 작은 경우, 분명히이다 1 또는 0,이 경우 일 이미 정렬 또는 존재하지 않는, 그래서 그냥 돌아갑니다. 할 수있는 아무것도 없습니다. 그래서 떨어져 당기기하는 간단한 경우입니다. 그렇지 않으면, 우리는 세 단계가 있습니다. 요소의 왼쪽 절반, 정렬 정렬 요소의 오른쪽 절반, 그리고 정렬 된 반쪽을 병합합니다. 무엇을 여기에서 흥미로운 것은 그 금방, 평저선 (punt)을 타보는 종류 해요? 원형 정의의 종류가있다 이 알고리즘. 이 알고리즘의 어떤 의미에서 정의 원형? 대상 : [들림]. DAVID 마란 : 그래, 내 정렬 알고리즘 그 단계의 두 "일종의 을 구걸 그래서 뭔가. "그리고 질문 그럼, 내가 사용하는 것입니다 왼쪽 절반을 정렬하려면 그리고 오른쪽 절반? 그리고 여기에 아름다움입니다 비록 다시, 이것은 마음 절곡입니다 일부 잠재적으로, 당신은 동일한 사용할 수 있습니다 왼쪽 절반을 정렬하는 알고리즘입니다. 그러나 분을 기다립니다. 당신을 정렬하라고 할 때 왼쪽 절반이 두 무엇입니까 단계는 다음이 될 것? 우리의 왼쪽 절반을 정렬 할 수 있습니다 왼쪽 절반과 오른쪽 왼쪽 절반의 절반. 젠장, 내가 어떻게 그 두 정렬 않는다 반쪽 또는 분기, 지금은? 하지만 그건 괜찮아. 우리는 여기에서 정렬 알고리즘이 있습니다. 그리고 당신은에 걱정하더라도 처음이 무한의 종류 루프, 그것은 결코 사이클의 끝날 것 - 그것은 것입니다 무슨 한 끝? 일단 N 이하 2입니다. 이는 결국 일어날 당신이 유지하는 경우에 등분하기 때문에 이러한 반쪽 절반의 절반, 확실히 결국이 끝날거야 다만 1 또는 0 요소를 백업합니다. 이 시점,이 알고리즘에 작업을 완료했다. 따라서이있는 진짜 마술 알고리즘에있을 것 그 최종 단계 병합. 단지 두 가지를 병합하는 간단한 아이디어 일, 그 궁극적 무슨 일이야 우리의 배열을 정렬 할 수 있도록하려면, 하자, 여덟 요소를 말한다. 그래서 최대 8 개의 더 많은 스트레스 공을 가지고 여기에 여덟 종이 조각, 한 구글 유리 - 이는 내가 계속 얻는다. [웃음] DAVID 마란 : 우리는 팔을 수 있다면 자원 봉사자, 그리고 어디 보자 우리가 할 수있는 경우 그래서,이를 재생할 수 있습니다. 와우, 확인을 클릭합니다. 컴퓨터 과학은 재미를 얻고있다. 좋아. 그래서 방법에 대해 당신이 세 거기 큰 손. 다시 네. 그리고 방법에 대해 우리는 당신을 다하겠습니다 이 행에서 세? 앞과 네. 그래서, 여덟 올라옵니다. [웃음] DAVID 마란 : 실제로 해요 아니 그것이 무엇인지 확인하십시오. 그것은 긴장 공입니까? 책상 램프? 재료? 인터넷? 확인을 클릭합니다. 그래서 올라옵니다. 누가 좋아 - 오고 유지합니다. 보자. 그리고이 위치에 당신을두고 - 당신은 위치 하나입니다. 어 - 오, 잠깐만. 1, 2, 3, 4, 5, 6, 7 - 좋아, 오. 좋아, 우리는 좋은거야. 좋아, 그래서 모두가 자리를 하지만 구글 유리합니다. 나 대기열이 업을 할 수 있습니다. 당신의 이름은 무엇입니까? MICHELLE : 미셸. DAVID 마란 : 미셸? 좋아, 당신은 같이 얻을 괴짜, OK 그건 경우. 음, 나도 할, 나는 가정, 단지 순간을 위해. 대기, 좋아. 우리는 함께 올 시도를하고 있어요 구글 유리 케이스를 사용하고, 우리 그것은 마찬가지로 재미있을 것이라고 생각 이 사람들은 무대 때. 우리는 세계를 기록합니다 자신의 관점에서. 좋아. 하지 아마도 Google이 의도 한. 당신이 괜찮다면 괜찮아 착용 다음 어색한 분 동안이, 그 멋진 될 것입니다. 좋아, 그래서 우리는 여기의 배열을 요소, 그리고 당이 배열, 이 사람들 종이 조각 ' 손은 현재 정렬되지 않은 있습니다. MICHELLE : 아, 그건 너무 이상하다. DAVID 마란 : 그것은 거의 무작위입니다. 그냥 순간에, 우리 시도 할거야 함께 일종의 통합 구현 그 키에 대한 통찰력이 어디를 참조하십시오. 및 병합 정렬과 함께 여기에 트릭은 우리가 아직 생각하지 않은 무언가. 우리가 실제로 어떤 필요 추가 공간. 그래서 특히 될 것 이것에 대해 흥미는 그이 사람은 조금을 이동하려고 비트 때문에 가정려고하는 공간의 여분 배열이있다 바로 그 뒤에 말한다. 그들은 자신의 의자 뒤에, 그래서 경우 보조 배열이 있습니다. 그들은 여기 앉아 있다면, 그건 기본 배열입니다. 그러나 이것은 우리가 가지고있는 자원이다 거품 지금까지 활용되지 정렬, 선택 정렬과 함께, 삽입 정렬과 함께. 지난 주 기억, 모두 단지 의 종류는 장소에 단행. 그들은 어떤 메모리를 추가로 사용하지 않았다. 우리가 사람들을위한 공간을 만들어 사람들을 이동. 그래서도 중요한 통찰력이다. 이 트레이드 오프에 일반적으로있다 자원의 컴퓨터 과학. 당신이 뭔가를 가속화하려는 경우 시간처럼, 당신은에 갈거야 가격을 지불해야합니다. 그리고 그 가격 중 하나가 매우 자주 공간, 메모리 용량 또는 하드 당신이 사용중인 디스크 공간. 아니면, 솔직히 양 프로그래머의 시간. 얼마를 그것은 인간의, 당신을 소요 시간 실제로는 좀 더 구현하기 복잡한 알고리즘입니다. 그러나 오늘, 트레이드 오프 시간과 공간입니다. 너희들은 그냥 잡을 수 있도록 경우 그래서 우리는 당신이 걸 번호를 볼 수 있습니다 실제로, 2, 4, 6, 1, 3, 7, 8을 일치. 우수. 그래서 조율을 시도하는거야 일, 만약 너희들이 할 수있는 단지 여기 내 리드를 따르십시오. 그래서 먼저 구현 예정 는 의사의 첫 번째 단계 n은 N이면 요소의 입력에 2보다 작은 경우 반환합니다. 물론, 그하지 않습니다 적용한다, 그래서 우리는에 이동합니다. 따라서 요소의 왼쪽 절반을 정렬합니다. 그래서 내가 초점을거야 의미 내 다음에 그냥 잠시 주목 여기 네 사람. 좋아, 다음에 무엇을해야합니까? 대상 : 왼쪽 절반을 정렬합니다. DAVID 마란 : 그래서 지금은 정렬 할 수 있습니다 이 녀석의 왼쪽 절반입니다. 다시 때문에 자신에 가정 목표는 왼쪽 절반을 정렬하는 것입니다. 당신이 어떻게해야합니까? 다만, 심지어 지침을 따르십시오 우리는 다시 일을하고 있지만. 그래서 왼쪽 절반을 정렬합니다. 이제이 두 사람을 분류하고 있습니다. 무엇을 다음 온다? 대상 : 왼쪽 절반을 정렬합니다. DAVID 마란 : 왼쪽 절반을 정렬합니다. 그래서 지금이, 여기 자리, 크기 1의 목록입니다. 그리고 당신의 이름이 뭐였더라? PRINCESS DAISY : 공주 데이지. DAVID 마란 : 공주 데이지는 여기에있다. 그리고 그녀는 이미 정렬되어 있기 때문에 목록의 크기는 1입니다. 나는 다음에 무엇을해야합니까? 그 목록입니다 때문에 OK, 반환 2보다 작은 크기 1. 다음 단계는 무엇인가? 그리고 지금 당신은 어떤 종류의에이 당신의 마음에있는 철수. 는 오른쪽 절반을 정렬 - 당신의 이름은 무엇입니까? LINDA : 린다. DAVID 마란 : 린다. 그래서 우리는 이제 무엇을해야합니까 우리는 크기 1의 목록을 가지고? 대상 : 돌아갑니다. DAVID 마란 : 조심. 우리가 먼저 반환, 그리고 지금 세 번째 단계 -와 난 경우 종류로 그것을 묘사 지금, 이제 두 개의 좌석을 수용 이 두 가지 요소를 병합해야합니다. 그래서 지금 불행히도 요소 순서가. 그러나 그것은 어디 병합 과정의 매력적인 얻을 시작합니다. 너희들은 일어서야 할 수 있도록하는 경우 순간, 난, 당신이 필요 해요 순간, 당신의 의자 뒤에 단계를합니다. 그리고 만약 린다, 2이기 때문에 4보다 작은, 왜하지 먼저 주변에 오는가? 거기있어. 린다 그래서, 먼저 돌아올. 지금 현실에서 그것은 단지 배열의 경우 우리는 단지 실시간에 그녀를 이동할 수 있습니다 이 의자에서이 자리합니다. 그래서 몇 가지 상수를했다 그 상상 1 단계의 수. 그리고 지금 - 그러나 우리는 당신을 넣어해야합니다 여기에서 첫 번째 위치입니다. 그리고 지금 당신은 돌아올 수 있다면 뿐만 아니라, 우리가가는거야 위치 두합니다. 그리고 그것은처럼이 느낌에도 불구하고 잠시 복용이며, 지금은 좋은거야 그의 왼쪽 반 왼쪽 절반은 현재 정렬됩니다. 지금 우리 경우에 따라서 다음 단계는 무엇 이었습니까 이야기에 더 되감기? 대상 : 오른쪽 절반. DAVID 마란 : 오른쪽 절반을 정렬합니다. 그래서 너희들은뿐만 아니라,이 작업을 수행 할 수 있습니다. 당신은 일 어설 수 있도록하는 경우 단지 순간을 위해? 그리고 당신의 이름은 무엇입니까? JESS : 제스. DAVID 마란 : 제스. 좋아, 그럼 제스 지금은 왼쪽입니다 오른쪽 절반의 절반. 그리고 그녀는 크기 1의 목록입니다. 그녀는 분명히 소팅. 그리고 당신의 이름을 다시? MICHELLE : 미셸. DAVID 마란 : 미셸 분명히 크기 1의 목록입니다. 그녀는 이미 정렬있어. 이제 마법은 어떻게 병합 프로세스입니다. 그럼 누가 먼저 온거야? 물론 미셸. 당신은 다시 돌아올 수 있도록합니다. 지금 우리가 그녀를 위해 준비해 공간 여기이 의자 뒤에. 그리고 지금 당신은뿐만 아니라 다시 올 수 있다면, 우리는 지금 두 명확하게 가지고 반쪽 사이즈 2 각 - 단지 묘사의를 위해서, 만약 당신 약간의 공간을 만들 수 있습니다 - 하나는 절반 여기 남아 여기에 오른쪽 절반. 이야기에 더 되감기. 어떤 단계에서 다음인가? 대상 : 병합합니다. DAVID 마란 : 그래서 지금 우리는 병합해야합니다. 그래서 OK, 이제 다행히도, 우리 단지 네 개의 의자를 해제. 그래서 우리는 많은 메모리를 두 번 사용하지만, 한 우리는 플립 툭 사이를 줄 수 두 배열. 그래서 어떤 번호가 먼저 와야하는 것입니다? 그래서 분명히, 미셸. 그래서 돌아올 취 여기에 좌석. 그리고 숫자 2는 분명히 다음, 당신은 여기에 온다. 4 번, 6 번. 그리고 또있다하더라도 관련 걷는 조금, 정말, 이들은 즉시 일어날 수 - 하나를 이동하여 OK, 잘했다. [웃음] DAVID 마란 : 그리고 지금 우리입니다 꽤 좋은 모양있다. 전체의 왼쪽 절반 입력은 이제 정렬 된. 좋아, 그래서이 사람들이 있었다 제의 장점 - 어떻게 모든 여자를 끝낼 않았다 왼쪽과 오른쪽에있는 모든 남자? 좋아, 그럼 너희들은 이제 설정 '. 그래서 나는 과정을 안내하지 않습니다 이러한 단계. 우리가 다시 적용 할 수 있다면 우리는 볼 수 있습니다 같은 의사. 당신은 가서, 일어서려면 그리고 너희들은 내가 당신에게 마이크를 제공 할 수 있습니다. 당신이 복제 할 수 있는지 무엇을 우리는 단지 여기에 한 목록의 다른 쪽 끝을. 누가 먼저 말을해야합니다 알고리즘을 기반으로? 그래서 당신이 전에 무슨 일을하는지 설명 당신은 어떤 다리 운동을합니다. 스피커 1 : 좋아, 그래서 이후 나는의 왼쪽 절반입니다 왼쪽 절반, 나는 반환합니다. 오른쪽? DAVID 마란 : 좋은. - 그리고 스피커 : 1 DAVID 마란 : 수행 마이크 옆에 가서? 스피커 1 : 다음 번호입니다. 스피커 2 : 그래서 오른쪽 절반 해요 의 왼쪽 반 왼쪽 절반, 나는 반환합니다. DAVID 마란 : 좋은. 당신이 돌아갑니다. 그래서 지금 당신이 두 가지의 옆에 무엇입니까? 스피커 2 : 우리는 작은이야 누가합니다. DAVID 마란 : 그렇습니다. 우리는 병합 할. 우리는 병합하는 데 사용거야 공간 당신들이있어, 비록에 분명히 이미 정렬, 우리는거야 동일한 알고리즘을 따르십시오. 그럼 누가 다시 먼저 간다? 3 그래서, 다음 7. 지금은 마이크가 간다 이 녀석까지 OK? SPEAKER 3 : 그래서의 오른쪽 절반 해요 왼쪽 절반, 내 N 이하이다 1, 그래서 난 그냥 통과 할거야 - DAVID 마란 : 좋은. 스피커 4 : 내가의 오른쪽 절반 해요 오른쪽 오른쪽 절반의 절반, 그리고 난 또한 한 사람, 난 그렇게 반환 할 것. 그래서 지금 우리가 병합합니다. 스피커 3 : 그래서 우리가 돌​​아갑니다. DAVID 마란 : 그래서 당신은 뒤로 이동합니다. 그래서 5는 8 번째 간다. 는 이제 청중, 우리가 지금 되감기 할 단계 우리의 마음에서 등을 맞댄? 대상 : 병합합니다. DAVID 마란 : 병합 왼쪽 부분과 오른쪽 원래 왼쪽 절반의 절반. 그래서 지금 - 다만,이 명확하게하기 약간의 공간을 당신 사이에 두 사람. 이제 두 목록의 즉, 왼쪽과 오른쪽. 그렇다면 우리는 이제 너희들은 병합합니까 좌석 앞줄 다시? 3 먼저갑니다. 그런 다음 5, 분명히. 그런 다음 7, 현재 8. OK, 이제 우리는? 대상 : 수행되지 않습니다. DAVID 마란 : 수행하지 않음 때문에, 물론, 나머지 한 단계가있다. 그러나 다시, 이유는이를 사용하고 있습니다 "당신의 마음에있는 되감기"와 같은 용어 그 정말 때문이다 무슨 일이 일어나고. 우리는이 모든 단계거야 그러나 우리는을 위해 일시​​ 중지의 일종입니다 에 순간 잠수 깊이 알고리즘 잠시 동안 일시 중지, 알고리즘에 깊은 다이빙, 그리고 이제 우리는 우리의 되감기의 정렬이 마음은 이러한 레이어를 모두 취소 우리는 일종의 보류했다고. 그래서 지금 우리의 크기는 4 개의 목록이 있습니다. 너희들이 마지막으로 한 번 일어 서서 수 있다면 그리고 여기에 공간의 비트를 만들 이 왼쪽인지 명확하게 원래의 절반 원래의 오른쪽 절반. 누가 첫 번째 숫자이야 우리 뒤로 당길 필요? 물론 미셸. 그래서 우리는 여기에 미셸을 넣어. 그리고 누가 숫자 2가? 2 번 다시도 켜집니다. 3 번? 우수. 4 번, 5 번, 6 번, 7 번과 8 번. OK, 그래서 많은 느낌 단계, 확실히. 하지만 지금 우리가 확인할 수없는 경우에 보자 일종의 직관적으로 그이의 근본적으로 알고리즘, 특히 등 여기서 n은 우리가 보았 듯이, 정말 큰 가져옵니다 애니메이션과입니다 근본적으로 빨리. 그래서 나는 최악의,이 알고리즘을 주장 최선의 경우 경우에도, n 번 로그 N 큰 O입니다. 즉, 이것의 일부 측면이있다 N의 조치를 취하고 있지만, 알고리즘 또 다른 측면은 어딘가에있다 해당 반복 그 반복, 그 로그 n 개의 단계를 수행합니다. 우리는 어떤 사람에 대한 우리의 손가락을 넣어 수 있습니다 두 개의 숫자를 언급하는? 그럼 여기서 - 마이크는 어디로 갔지? 스피커 1 : 로그 N 수 있을까 두 가지로 우리를 파괴 - 기본적으로 두 가지로 나누어. DAVID 마란 : 그렇습니다. 우리는 따라서 어떤 알고리즘에서 볼 때마다 지금까지이 패턴이있었습니다 , 분할 분할, 분할. 그리고 그것은 일반적으로 감소거야 뭔가에 로그, 로그 자료 2. 하지만 정말 아무것도 될 수 하지만베이스 2를 기록합니다. 이제 N 어떨까요? 나는 우리가 어떤 종류의 당신을 나눈 것을 볼 수 있습니다 사람들은 - 당신을 나눈, 당신을 분할 당신을 나눈, 당신을 나눈 값입니다. 끝은 어디에서 오는가? 그래서 합병이다. 그것에 대해 있기 때문에 생각합니다. 당신은 함께 8 명이 병합 할 때 그들 중 절반은 4의 집합입니다 빼앗아 나머지 절반은 다른 수 있습니다 4 개의 설정, 당신은 어떻게 가야합니까 병합을 수행 어떻습니까? 그럼, 너희들은 그것을했다 상당히 직관적. 내가 대신 그것을 한 경우에 조금 더 질서에 제가 지적 할 수 내 왼쪽에 첫 번째 왼쪽 사람 손, 왼쪽 사람을 지적 그 오른손 절반, 그리고 다만 이후 걸었다 작은 요소를 가리키는리스트 때마다 내 손가락을 통해 이동하고 이상으로 목록을 통해 필요. 그러나이 병합에 대한 열쇠 프로세스 나는이 쌍을 비교 해요입니다 요소. 오른쪽 절반에서와 왼쪽에서 반 한 번 되돌아 적이 있어요. 따라서 병합 자체가 복용 더 이상의 단계 n보다가 없습니다. 얼마나 많은 시간을 내가 가지고 있었다 병합 그렇게하려면? 음, n보다 더 아니, 우리 단지 최종 병​​합하여 해당 보았다. 그리고 당신이 걸립니다 뭔가를 할 경우 , N 단계를 n 번, 또는 그 반대의 경우도 마찬가지 로그인 그것은 우리 n 번 로그 N 줄거야. 그리고 왜이 더 나은 무엇입니까? 음, 우리는 이미 해당 로그를 알고있는 경우 여기서 n은 n보다 낫다 - 권리? 우리는 이진 검색에서 전화 번호부를 보았다 예를 들어, 로그 n을 분명히했다 선형보다. 의미 n 번 로그 N은 그래서 다른 N 시간보다 확실히 더 N, AKA N 제곱. 그리고 우리가 궁극적으로 어떤 느낌이다. 박수 너무 큰 둥근 경우 우리는이 사람 들어, 수 있습니다. [박수] DAVID 마란 : 그리고 당신의 이별 선물 - 당신은 번호를 유지할 수 있습니다 당신이 좋아하면 것인지. 그리고 당신의 이별 선물, 평소와 같이. 아, 그리고 우리는 당신을 보낼 것이다 영상, 미셸. 감사합니다. 좋아. 스트레스 볼에 자신을 도와줍니다. 그리고 내가 그 동안 끌어 보자 제안하는 우리의 친구 롭 보덴 이것에 약간 다른 관점, 당신이 생각 할 수 있기 때문에 다소에서 일어나는 단계 다른 방법입니다. 약 롭은 무엇에 대한 사실, 셋업 우리를 보여 것은 우리가했습니다 가정 이미 분할까지의 수행 8 개의 작은 목록으로 큰 목록 크기 1의 각. 그래서 우리는 의사에게 변경하고 약간은에 이곳에 정렬하려면 작품을 병합하는 방법의 핵심 아이디어. 그러나의 실행 시간 수행 할 작업에 대해 그는의 여전히 동일 할 것. 그리고 또, 여기에 셋업은 그가 점이다 사이즈 1을 8로 시작. 그래서 당신은 그가의 부분을 놓친 실제로 로그 N 로그 N 로그 N 수행 입력의 분할. [동영상 재생] 단계 하나는 - 그건. 반복 두 번째 단계에 대한 목록의 쌍을 병합합니다. DAVID 마란 : 흠. 오디오 만이오고있다 내 컴퓨터 밖으로. 의는 다시 시도 할 수 있습니다. - 그냥 임의로 어느 선택 - 지금 우리는 네 개의 목록이 있습니다. 전에 알아보십시오. DAVID 마란 : 거기 우리는 간다. - 병합 108 15 우리는 끝 최대 목록 15, 108. 우리는 50 4 병합 4, 50로 끝. 우리는, 8, 42 병합 8, 42에 결국. 그리고 우리는, 23, 16 병합 16와 23을 끝낸다. 지금 우리의 모든 목록의 크기는 2의이다. 주의 그 각각의 네 개의 목록이 정렬됩니다. 그래서 우리는 병합을 시작할 수 있습니다 다시리스트의 쌍. 우리는 15 108 4 50 병합 먼저, 다음 15 일 4을 50 후 108. , 23 8, 42, 16 병합, 우리는 첫째로 포획 8 일 후 16 일 후 23 일 다음 42. 그래서 지금 우리의 크기는 단지 두 개의 목록을 가지고 4 정렬 각. 이제 우리는 이러한 두 목록을 병합합니다. 첫째, 우리는 4 받아, 우리는을 8, 우리는 그 16 다음 15을 그런 다음 다음 다음 23, 42, 50, 108. [END 동영상 재생] DAVID 마란 : 다시 말하지만, 통지, 그는 결코 주어진 컵 두 개 이상의 시간을 감동 그 이상 진행 후. 그래서 그는 반복 결코. 그래서 그는 항상 옆으로 움직입니다 우리가 N을 가지고 어디 때문입니다. 왜 내가 하나의 애니메이션을 당겨하지 우리는 앞에서 살펴본하지만,이 시간 병합 정렬에만 초점을. 내가 가서 확대하자 이 여기에있다. 첫째 날은 임의의 입력을 선택할 수 있습니다, 이를 확대하고, 당신은 볼의 정렬 할 수 있습니다 우리는 부여 이전에 걸린 것을 병합 정렬은 실제로하고있다. 당신은 또는 이러한 반쪽을 얻을 수 있도록 통지 이러한 분기 또는이 8 분 문제가 갑자기 좋은 모양을 가지고 시작합니다. 그리고 마지막으로, 당신은에서 볼 끝까지 그 빵, 모든 것을 함께 병합됩니다. 그래서 이건 그냥 세 가지입니다 같은 생각을합니다. 하지만 단지 분할과 같은 키 통찰력, 그리고, 첫 번째 클래스 정복 우리는 어떻게 든 분할하기로 결정했다 에 큰 뭔가에 문제가 정신 동일 뭔가 정렬, 하지만, 더 작고 더 작은 작고. 생각의 정렬 이제 또 다른 재미있는 방법 이들에 대해, 비록 그것이 아닙니다 당신에게 동일한 직관적 인 줄거야 이해이며, 다음 애니메이션. 그래서 함께 넣어 비디오 사람입니다 서로 다른 연결 에 대한 다양한 작업과 소리 삽입 정렬, 병합 정렬을 위해, 그리고 다른 사람의 커플. 그래서 순간에, 나는 플레이를 칠거야. 그것은 긴 약 1 분입니다. 그리고 당신은 여전히​​ 볼 수 있지만 패턴은, 당신이 할 수있는이 시간을 벌어 이러한 알고리즘이 얼마나도 듣고 다르게와 수행 약간 다른 패턴. 이 삽입 일종이다. [톤 재생] DAVID 마란 : 그것은 다시 시도합니다 각 요소를 삽입 자신이 속한 곳으로. 이 버블 정렬됩니다. [톤 재생] DAVID 마란 : 그리고 당신은 느낌으로 정렬 할 수 있습니다 상대적으로 적은이 어떤지 작업 각 단계에. 이 지루함이 같은 소리 것입니다. [톤 재생] DAVID 마란 :이 선택 일종이다, 우리가 우리가 원하는 요소를 선택 위치 다시 겪고 다시하고 다시 그리고 처음에 그것을 넣어. [톤 재생] DAVID 마란 :이 병합 일종이다, 그 당신은 정말 느낌을 시작할 수 있습니다. [톤 재생] [웃음] DAVID 마란 : 그놈이라는 것을 우리가보고되지 않은 종류. [톤 재생] DAVID 마란 : 그래서, 지금, 어디 보자 당신이 희망으로 그대로 정신 조금을 풀 수 있다면 음악, 여기에 수학의 비트. 그래서 우리가 할 수있는 네 번째 방법이 그것이 무엇을 의미하는지에 대해 생각 빠른 것보다하는 기능 우리는 전에 본 적이. 그리고 당신은에서 코스에서오고 있다면 수학 배경, 당신 실제로 이미 아마 알고 당신 이 기술에 대한 용어를 때리고 할 수 있습니다 - 즉 재귀 함수 즉, 어떻게 든 자신을 호출합니다. 그리고 또, 그 병합 정렬을 불러 의사는 의미에서 재귀 적이었다 이 병합 정렬의 단계 중 하나 일종의 전화를했다 - 즉, 그 자체입니다. 그러나 다행히도, 때문에 우리는 계속 , 정렬을 호출, 또는 정렬 병합 특히,에 더 작은 작고 목록, 우리는 결국 우리가 전화 할게 무엇을 저점으로 감사 기본 케이스, 하드 코딩 된 경우 그 목록이 작 으면 미만 말했다 이 경우, 다만 즉시 반환. 우리가 특별한 경우를 가지고 있지 않은 경우, 알고리즘은 바닥, 절대로 당신은 참으로 얻을 것이다 정말 영원히 무한 루프. 그러나 우리가 지금두고 싶어한다고 가정 이에 대한 몇 가지 숫자는 다시 N을 사용하여 입력의 크기. 그리고 어떻게, 당신에게 물어보고 싶은게 에 포함 된 총 시간 병합 정렬을 실행? 또는 더 일반적으로, 무엇을 시간에 그것의 비용? 잘은 것을을 측정하기 매​​우 쉽습니다. n은 2보다 작은 경우, 시간 관련 n 개의 요소를 정렬에서, n은 2이고, 0입니다. 우리는 단지 반환하기 때문입니다. 수행 할 작업이 없습니다. 지금 틀림없이, 아마의 한 단계 또는 두 개의 금액을 계산하는 단계 작동하지만, 그것은 0에 가까운만큼이야 난 그냥 아무 작업을하지 말거야 목록이 너무 작은 경우 필요 재미 수 있습니다. 하지만이 사건은 흥미 롭다. 재귀 경우의 지점이었다 다른 말한 의사, 정렬 왼쪽 절반은 오른쪽으로 정렬 반 두 반을 병합합니다. 지금 왜 이런 표현한다 그 비용을 나타냅니다? 음, N의 T 그냥 의미 N 요소를 정렬하는 시간입니다. 다음의 오른쪽에 거기에 등호 (=), N의 T가 분할 2 무엇의 비용을 언급하고있다? 왼쪽 절반을 정렬. 2로 나누어 n의 또 다른 T는 아마에 대한 비용을 참조 오른쪽 절반을 정렬합니다. 그리고 플러스 N? 병합됩니다. 때문에 두 목록 중 하나가있는 경우 크기 2에 n과 다른 크기의 N 2 이상, 당신은 기본적으로 터치해야 다만 롭 같이 이러한 요소 각각 컵의 각 감동, 그냥 우리의 각각 지적 무대에 자원 봉사자. 그래서 여기서 n은 병합의 비용입니다. 지금 불행히도,이 수식 자체는 재귀도 있습니다. N 인 경우 그렇다면이 말, 질문을 16 경우 단계 16 개 사람들이의 또는 비디오 16 컵, 얼마나 많은 총 단계는 그들을 정렬 걸립니까 병합 정렬 있나요? 그것은 실제로 확실한 대답이 아니다 지금 당신은 일종의해야하기 때문에 재귀 적으로이 수식을 응답합니다. 내가 제안하자 때문에 즉, OK의 우리는 다음과 같은 작업을 수행합니다. 16 명이 정렬하거나 참여 시간 16 컵 표시 될 것입니다 일반적으로 16 T로. 그러나 그것은에 따라, 동등한 우리 이전 공식의 2 배 금액 시간이 정렬됩니다 8 컵 플러스 16. 그리고 또, 플러스 16, 병합 할 시간입니다 8의 두 배 T는 왼쪽 부분과 오른쪽 절반을 정렬하는 시간. 그러나 다시, 이것은 충분하지 않습니다. 우리는 깊이에서 다이빙을해야합니다. 이것은 우리가 답을해야한다는 것을 의미 질문 8 T는 무엇입니까? 물론 8 T는 단지 2 4 플러스 8 배 T. 음, 4 T 무엇입니까? 4 T 2 플러스 4 단 2 회 T입니다. 음, 2의 T는 무엇입니까? 2 T 1 플러스 2 단 2 회 T입니다. 그리고 또, 우리는 점점 친절 이 사이클에 갇혀있다. 그러나 약 칠이야 기본 케이스 소위. 1 T 무엇 때문에, 우리는 주장 했는가? 0. 이제 마지막으로, 우리는 거꾸로 작업 할 수 있습니다. 1 T가 0 인 경우에, 나는 지금 하나 되돌아 갈 수 있습니다 여기이 사람에게 줄 내가 할 수 1 T 0에 연결합니다. 그래서 의미는, 2 번 제로와 동일 그렇지 않으면 0, 플러스 2로 알려져 있습니다. 그리고 그 전체 표현식은 2입니다. 나는 그 대답 2의 T를 취할 경우에 지금 2, 중간 선, T에 연결 4, 그 날의 2 배를 제공 2 더하기 4, 8, 그렇게. 나는 그 이전에 8 연결하는 경우 라인은, 그 날의 2 배 8, 16을 제공합니다. 그리고 우리는 그와 함께이 계속하는 경우 24, 16 추가, 우리는 마침내을 64 값입니다. 지금의 그 자체의 종류가 말하는 것을 N 표기법에 아무것도, 큰 O, 우리가 잘하고, 오메가 에 대해 얘기. 그러나 64 참으로 밝혀 16, 입력의 크기, 16베이스 2를 기록합니다. 그리고 이것은, 조금 익숙하지 않은 경우 단지 다시 생각하고, 다시 올 것이다 당신에게 결국. 이 로그 기본 2 인 경우, 2처럼 무엇을 당신에게 16 제공에 제기? 아, 네, 그래서 그것을 16 배 4입니다. 그리고 또, 그것은 큰 문제가 아니다이 경우 흐릿한 기억의 종류는 지금이다. 하지만 지금은 믿음에 걸릴 16 로그 16 64입니다. 그리고 실제로,이 간단한 정신을 가진 확인, 우리는 확인했습니다 - 하지만 공식적으로 입증되지 - 그 병합의 실행 시간 종류는 참으로 n 개를 기록합니다. 그렇게 나쁘지 않다. 그것은보다 확실히 낫다 우리가 지금까지 볼 수있어 한 알고리즘 우리가 활용했기 때문에 그것은 하나의 재귀이라는 기술. 즉,보다하지만, 더 재미있는 분열과 정복의 개념. 다시 말하지만, 정말 주 0 물건이 지금도으로 되풀이된다 더 강력한 방법입니다. 이제 재미 좀 운동, 당신이 한 경우 이런 짓을하지 않습니다 - 그리고 아마 하지 않았을 때문에 정상의 종류 사람들은 이렇게 생각하지 않습니다. 하지만 google.com에 그리고 만약 가면 내가 뭔가를 배우고 싶다 재귀 입력합니다. [웃음] [더 웃음] DAVID 마란 : 나쁜 농담이 서서히 확산. [웃음] DAVID 마란 : 그냥 경우가있다. 나는 그것을 잘못 철자하지 않았다, 그리고 농담이있다. 좋아. 당신 옆에있는 사람에게 그것을 설명하는 경우 꽤 아직 클릭하지 않았습니다. 그러나 재귀 더 일반적 의미 호출하는 함수의 과정 자체, 또는 좀 더 일반적으로 나누어 할 수있는 일에 문제가 동일 해결하여 조금씩 해결 대표적인 문제. 음,하자 변경 기어 단지 순간을 위해. 우리는 특정 cliffhangers를 종료하려면 이렇게 설정을 시작하자 단, 몇 분, 아주 간단한 생각에서 - 두 요소를 교환의 오른쪽? 모든 알고리즘 우리는 봤는데 지난 몇 이야기 강의 일부를 포함 교환의 일종. 오늘 그것은 그들을 점점에 의해 시각화 한 를 자신의 의자 밖으로 걷고 있지만, 코드에서, 우리는 것 하나의 배열에서 요소를 가지고 다른에 풍덩 그것. 우리는이 일에 대해 어떻게 가야합니까? 글쎄, 내가 가서 작성할 수 여기에 빠른 프로그램입니다. 내가 가서 할거야 이 다음과 같이. 자,이 호출 - 우리는이 하나를 호출하기 위해 무엇을 할 수 있습니까? 사실, 아니. 나 되감기를 할 수 있습니다. 난 그렇게하고 싶지 않아 아직 클리프 행어. 그것은 재미를 망칠 것입니다. 대신이 작업을 수행하자. 조금을 작성한다고 가정 프로그램 바로 지금이 포용 재귀의 생각. 나는 어떤 종류의 거기에 앞서 자신을 얻었다. 나는 다음과 같은 작업을 수행 할거야. 첫째, 빠른, 표준 io.h에는, 포함한다 cs50.h.의뿐만 아니라 포함 그리고 난 앞으로 갈거야 및 주요 int 무효를 선언 일반적인 방법으로합니다. 나는 파일 이름이 잘못 지어졌다 있었구나, 그래서 나 여기 너무. C 확장을 추가 할 수 우리는 제대로 컴파일 할 수. 이 기능을 시작합니다. 그리고 기능은 내가 꽤 쓰고 싶어요 단순히 부탁입니다 다음 번호를 사용자가 최대 추가 그 사이의 모든 숫자 수와 말, 0. 그래서 일단 내가 먼저 갈거야 그리고 INT N를 선언합니다. 그럼 몇 가지 코드를 복사하는 우리는 잠시 동안 사용했습니다. 뭔가 사실이지만. 나는 순간 그에게 돌아올 것입니다. 내가 무엇을 하시겠습니까? 나는 printf는 긍정적 인 말을 할 정수하시기 바랍니다. 그리고 난 갈거야 n은 INT을 얻는다 말한다. 그래서 다시, 어떤 상용구 코드 우리는 전에 사용했던. 그리고이 작업을 수행 할거야 여기서 n은 1보다 동안. 그래서 이것은 지킬 사용자 저에게 긍정적 인 정수를 제공합니다. 지금은 다음과 같은 작업을 수행 할거야. 나는 모든 숫자를 추가 할 N, 또는 0과 N 1 사이와, 동등하게, 총 합계를 얻을 수 있습니다. 그래서 큰 시그마 기호 당신이 기억 수도. 그래서 내가 먼저 호출하여이 작업을 수행 할거야 시그마라는 함수, N에 전달하고, 그 때 나는 갈거야 printf의 말, 대답은 바로 거기에있다. 그래서 짧은, 내가 얻을 사용자로부터 int로. 나는 긍정적 인 것을 보증합니다. 나는의 변수라는 대답을 선언 거기에 int 형 및 매장 반환 입력 n으로 전달 시그마의 값입니다. 그리고 그 답을 인쇄합니다. 불행하게도, 시그마 소리에도 불구하고 에있을 수 있습니다 뭔가처럼 math.h 파일 선언, 사실은 아니다. 그래서 괜찮습니다. 나는이에게 자신을 구현할 수 있습니다. I라는 함수를 구현하는거야 시그마, 그것은 걸릴 거예요 매개 변수 - 하자 그냥 m 전화, 단지 그래서 다릅니다. 그리고 여기까지 내가 말할거야 m이 1보다 작 으면 잘 - 이것이다 매우 프로그램을 재미. 그래서 앞서 갈 건데 즉시 0을 반환합니다. 그냥 모두를 추가하는 것은 의미가 없습니다 1 평방 미터 경우 사이의 숫자 자체는 0 또는 음수입니다. 그리고 난 앞으로 갈거야 매우 반복적으로이 작업을 수행합니다. 나는 구식 이런 종류의 작업을 수행 할거야 내가 먼저 갈거야 내가 갈거야 말 0으로 합계를 선언합니다. 그럼 내가해야 할거야 INT의 루프 - 나 그것은 우리 일치하도록하자 배포 코드는, 그래서 당신은 복사본이 집에서. INT 나는 최대에 1을 얻는다 나는보다 작거나 m 같습니다. 나는 플러스 플러스. 그리고 내부 루프에 대한이의 - 우리는 거의 다 - 합계는 합계에 1을 더한 가져옵니다. 그리고 나서 합계를 반환하는거야. 그래서 빨리 이런 짓을 아주 틀림. 그러나 다시, 주요 기능은 예쁘다 우리가했습니다 코드를 기반으로, 간단 지금까지 기록됩니다. 긍정적 얻기 위해 이중 루프를 사용하여 사용자로부터 int로. 그런 다음 새 기능이 INT를 전달 N, 다시 그것을 호출 시그마했다. 그리고 반환 값은 응답을 저장 현재 블랙 박스에서 변수에, 시그마로 알려진 대답했다. 나는 그것을 인쇄 할 수 있습니다. 우리가 지금 이야기를 계속하는 경우는, 시그마는 어떻게 구현? 나는 다음과 같이 구현 제안한다. 오류 검사 먼저, 조금 사용자가 아니라고 확인하기 위해 나와 함께 장난 및 전달 어떤 부정 또는 0 값을 반환합니다. 그럼 난라는 변수를 선언 요약하고 0으로 설정합니다. 지금은 내가 동등한에서 움직이기 시작 1 모든가는 길까지와 M을 포함, 나는 모든을 포함 할 때문에 M을 통해 하나의 숫자가 포함. 그리고 내부 루프이, 나는 그냥 할 합계는 지금​​ 무엇이든 얻을 플러스 I의 값입니다. 나는 더한 값입니다. 옆으로,이 보지 한 경우 전에 몇 가지 문법 설탕이있다 이 선합니다. 플러스 나는 같음 I이 다시 작성할 수 있습니다 단지 자신에게 몇 가지 키 입력을 저장합니다 및 비트 쿨러를 볼 수 있습니다. 하지만 그게 전부입니다. 그것은 기능적으로 동일한 것입니다. 불행히도,이 코드의 아직 컴파일하지 않을. 나는 어떻게 시그마 0을 만들 실행하는 경우 나는 화가나 것? 무엇을 좋아하지 않는거야? 대상 : [들림]. DAVID 마란 : 그래, 난 선언하지 않았다 위쪽, 오른쪽? 최대 기능 C는 종류의 바보 그것에 해당의 당신이 할 말 것을 수행하고, 그 순서대로 수행해야합니다. 여기 Enter 키를 누르면 그래서, 내가 갈거야 시그마에 대한 경고가 암시 적으로 얻을 선언. 아, 문제가되지 않습니다. 나는 정상까지 갈 수 있고, 내가 할 수 모든 권리, 말, 잠깐만. 시그마 반환하는 함수입니다 INT 그것은 예상 입력, 세미콜론 등의 INT. 아니면 전체 기능을 넣을 수 주 위의, 그러나 일반적으로, 나는 거라고 그것 때문에 그에 추천 항상 상단에 그렇게 기본을 가지고 좋은 당신의 오른쪽에있는 다이빙을 알 수있는 프로그램은 먼저 주요 읽는 거지. 그래서 지금 저 화면을 취소 할 수 있습니다. 리메이크 시그마 0. 모든 체크 아웃 보인다. 나 시그마 0을 실행하자. 긍정적 간. 나는 그것을 수를 줄 것이다 3 간단 유지합니다. 그래서 나에게 3 주어야한다 더하기 2 더하기 1, 등등 6. 입력, 실제로 나는 6 얻는다. 나는 더 큰 일을 할 수 있습니다 - 50, 12, 75. 그냥 접선으로, 내가 할거야 정말 큰처럼 어리석은 일 수는 아, 실제로 운동하는 - 어, 내가 바로 생각하지 않습니다. 보자. 의 정말 함부로 할 수 있습니다. 그게 문제입니다. 무슨 일이야? 코드는 나쁘지 않습니다. 그것은 여전히​​ 직선입니다. 휘파람하지만, 좋은 효과입니다. 무슨 일이야? 내가 들어 있는지 확실하지 않습니다. 그래서 밝혀 - 그리고 이 옆으로있다. 이것은의 핵심이 아닙니다 재귀의 생각. 내가에 노력하고있어 있기 때문에, 밝혀 대부분이 같은 큰 숫자를 나타냅니다 아마 그것은 잘못 해석 되 고 긍정적없는 번호로 C로, 하지만 음수. 우리는 이것에 대해 이야기하지만,하지 않은 그 음수가 밝혀 뿐만 아니라 세계에서 양수합니다. 그리고 당신이 할 수있는 수단 음수를 나타냅니다 기본적으로, 당신은 하나를 사용합니다 나타내는 특별한 비트 부정에 긍정적. 그것은보다 조금 더 복잡 하지만 그 기본 생각이다. 그래서 불행히도, C 1 개를 혼동하는 경우 실제로 의미로의 비트, 오,이 음수 내 루프 여기에, 예를 들어, 실제로는 결코 종료를하려고합니다. 나는 실제로 뭔가를 인쇄하는 그래서 만약 또 다시, 우리는 것 전체 많이 참조하십시오. 그러나 다시, 이것은 점 외에이다. 이건 정말 단지 일종이다 우리가 올 거라고 지적 호기심 결국에 백업합니다. 하지만 지금은이 올바른지 구현 우리가 가정하는 경우 그 사용자는 정수를 제공합니다 그 정수에 맞게. 하지만, 그이 코드 솔직히 주장 훨씬 더 간단하게 수행 할 수 있습니다. 손 목표는 숫자를 가지고하는 경우 같은 m와의를 추가 그것은 1, 또는 반대로 사이의 숫자 1 사이에 있고, 내가 주장 내가 병합하는이 아이디어를 빌릴 수있다 정렬 문제를 복용 한이 있었다 이 크기로 나눈 작은 일에. 어쩌면 반하지만, 작은, 그러나 대표적으로 동일합니다. 같은 생각하지만, 작은 문제. 그래서 실제로거야 - 나이 파일을 저장할 수 다른 버전 번호. 우리는이 버전을 호출합니다 1 대신 0. 그리고 나는 그것이 내가 실제로 할 수있는 주장 이런 종류의에서이 작업을 구현할 마음 구부리는 방법입니다. 나 혼자의 일부를 떠날거야. M이 작 으면 내가 말할거야 보다 작거나 0도 동일 - 난 그냥 좀 될거야 더 항문이 시간 - 내 오류 검사와 내가 가서 0을 반환하는거야. 이것은 임의의. 나는 단지 결정하고 만약 사용자가 저에게 부정적 번호를 제공합니다, 난 0을 반환하며 읽기해야 문서를 더 밀접하게. 다른 - 내가 할거야 알 수 있습니다. 또 나는 M 플러스를 반환하는 것입니다 - M의 시그마는 무엇인가? 음, M 플러스 M 1을 뺀 시그마, 플러스 마이너스 m 2, m을 더한 마이너스 3. 그 중 모두 쓰고 싶지 않습니다. 왜 내가 리면 그냥하지? 반복적으로 약간으로 자신을 호출 작은 문제, 세미콜론, 그것은 하루에 전화를? 오른쪽? 지금 여기, 너무, 당신이 느끼거나 걱정 수도 있습니다 이 난 것을 무한 루프입니다 제가 구현하고 그것에 유도, 전화 시그마 시그마. 하지만 그 때문에 완벽하게 OK의 I 이 선 어떤 추가 앞서 생각? 대상 : [들림]. DAVID 마란 : 23-26, 어떤 내 경우 상태입니다. 에 대한 좋은 무엇 때문에 여기 뺄셈, 나는 유지하기 때문에 나눠 시그마 작은 문제가 작고, 문제는, 작은 - 그렇지 않아 절반 크기입니다. 그것은 작은 만 아기 걸음 하지만 괜찮아요. 결국, 우리는 일할 수 있기 때문에 아래로 1 또는 0에 우리의 방법입니다. 그리고 일단 우리가 0 명중, 시그마 아니에요 더 이상 자신을 호출하는 것. 즉시 0을 반환하는거야. 그래서 효과는 바람으로 정렬이있는 경우 최대 당신의 마음에, M 모드를 추가하는 것입니다 M - 1, 플러스 M 마이너스 2 플러스 M 마이너스 3, 플러스 점, 점, 점, M 마이너스 M, 결국 0을 제공하고, 효과를 모두 추가 할 궁극적으로 함께이 있어요. 그래서 우리는, 재귀,하지 않은 문제를 해결하는 우리 전에 해결할 수 없습니다. 사실, 버전이 0, 모든 지금까지 문제는 해결할 수있다 단지 루프를 사용하여 함께 또는 while 루프 또는 이와 유사한 구조. 하지만, 재귀, 나는 아마 ..., 저희에게 제공합니다 생각의 다른 방법 문제는, 우리가 걸릴 수 있습니다 약자 경우 문제는, 어떤에서 분할 다소 무언가에 약간 큰 작은, 우리가 그것을 해결할 수 있다고 주장 아마 좀 더 우아 측면에서 디자인의 적은 코드로, 어쩌면 것이라고 문제를 해결 우리는 결국 겠지만, 어렵게 될 순수 반복적 해결을 참조하십시오. 내가 한하지만 클리프 행어 우리에 남겨두고 싶은 것은이 있었다. 내가 가서 열어 보자 에서 파일을 백업 - 사실, 내가 가자와 이 정말 빨리한다. 내가 가서 제안하자 다음. 오늘의 코드 사이에이 파일이 여기에있다. 여기 하나 noswap. 그래서 그 바보 같은 작은 프로그램입니다 나는 주장 할 것을 채찍질 다음. 주에서는 첫 번째 선언 INT는 X라고하고 할당 1의 값을 반환합니다. 그런 INT Y를 선언하고 그것을 2 값을 할당합니다. 다음은 x와 y가 무엇인지 출력합니다. 그런 다음, 점 점 점 스와핑 말한다. 그런 다음 함수를 호출 할 수 있다고 주장 X에 전달하고, 스왑이라는 그 희망 인 아이디어 어느 Y, x와 y는 다시 올 것이다 다른 그 반대. 그런 다음 스왑 주장! 느낌표. 다음은 x와 y를 출력합니다. 그러나 판명이 매우 아래 간단한 데모 여기에 실제로 버그가 있습니다. 나는 임시을 선언하고있어 비록 변수 일시적으로 퍼팅 그것은, 나는 재 할당 해요 B의 값 - 나는 하였으므로 이는 합리적인 느낌 온도에서의 사본을 저장. 그럼 동등한 B를 업데이트 온도에 어떤이었다. 이동의 쉘 게임의 종류 이것을 사용하여에로 B와 b 중간 사람이 임시 느낌이라고 완벽하게 합리적. 나는이 프로그램을 실행할 때 그러나 나는 그 주장 코드, 내가 지금 할 것 같은 - 내가 가서 그것을 여기에 붙여 넣을 수 있습니다. 나는이 noswap.c를 호출합니다. 이름에서 알 수 있듯이 그리고이 없습니다 올바른 프로그램이 될 것. noswap을하지. / NO 스왑. x는 1, y를, 2 스와핑, 교환. x는 1, Y는 2입니다. 이것도 근본적으로 잘못된 것입니다 이 완벽하게 보이지만 나에게 합리적. 그리고 거기 이유는,하지만 우리는 아니야 아직 이유를 공개하는 것. 내가 원하는 두 번째 클리프 행어 지금 당신을 떠날하려면, 이것이다 쿠폰 코드에 종류의 발표. 늦게 일을 가진 우리의 혁신이 올해 비 사소한 숫자를 자극했다 질문, 어떤이었다 아니 우리의 의도. 이 쿠폰 코드의 의도, 그것에 당신은 문제의 일부 작업을 수행 할 경우 따라서, 여분의 날 받고, 초기 설정 너희들이 도움이 도움이 정말로 자신이 초기 정렬을 시작 당신을 인센티브로의. 우리가 걸쳐 부하를 분산하는 데 도움이 근무 시간 잘되도록 그것은 윈 - 윈의 일종이다. 불행하게도, 나는 나의 지시를 생각 그래서 지금까지, 매우 명확하지 않은 난 이번 주말에 다시 가서 업데이트 에 크고, 대담 텍스트 사양 이와 같은 총알을 설명합니다. 그냥가, 더 공개적으로 대답 기본적으로 문제 세트 목요일 때문이다 정오에, 강의 당. 당신은의 일부를 마무리, 일찍 시작하면 12:00 수요일까지 설정 문제 PM, 쿠폰에 관한 부분 코드는 아이디어는 확장 할 수 있다는 것입니다 에 대한 귀하 마감 P 금요일까지 설정합니다. 즉, 비트 P의 작은 부분 떨어져있다 일반적으로 무엇을 기준으로 설정 더 큰 문제는, 당신은 구입 자신 여분의 날. 다시 말하지만, 그것에 대해 생각을 얻는다 문제 설정은, 당신을 얻는다 근무 시간은 빨리. 하지만 쿠폰 코드 문제는 여전히 당신이 그것을 제출하지 않는 경우에도이 필요합니다. 하지만 더 강력하게이있다. (STAGE 저소음) 그리고 그 사람이 떠나 초기 후회거야. 로 발코니에 사람이 있습니다. 에 사람들에 사전에 나는 사과 될 이유 발코니 다만 순간에 취소합니다. 그래서 우리는 중 하나를 가지고 운 에서 CS50의 전 머리를 가르치는 동료 dropbox.com라는 회사입니다. 그들은 매우 관대를 기증 이 정도의 공간이 여기 쿠폰 코드, 에서 어떤 업 보통 2기가바이트. 그래서 내가 생각했던 우리는이에 할 것 마지막 주, 공짜의 비트를 할 수 있습니다 그냥 순간에, 우리는 보여줄 것입니다 그것에 승자와 누가 쿠폰을 가지고 그런 다음 자신에 갈 수있는 코드 웹 사이트를에 입력하고 짜잔, 얻을 당신을 위해 훨씬 더 보관 공간 기기 및 개인 파일에 대한. 그리고 처음으로, 누가 참여하고 싶습니다 이 그림에서? OK, 이제 그것이 훨씬 더 재미 있습니다. 이 25 기가 바이트를받는 사람 쿠폰 코드 - 멀리 말보다 더 강력한 지금, 아마도 일 - 상단에 장착되어 하나 있어 아래에 방석 이 쿠폰 코드입니다. 이제 아래 보일 수 있습니다 좌석 쿠션. [동영상 재생] - 하나, 둘, 셋. [고함] - 당신은 차를 얻을! 당신은 자동차를 얻을! DAVID 마란 : 우리는 볼 것이다 수요일에. - 당신은 차를 얻을! 당신은 자동차를 얻을! 당신은 자동차를 얻을! 당신은 자동차를 얻을! 당신은 자동차를 얻을! DAVID 마란 : 발코니 사람들이 와서 여기 아래 전면, 우리는 여분이 곳. - 모두는 차를 가져옵니다! 모두가 차를 가져! [END 동영상 재생] 내레이터 : 다음 CS50에서 - 스피커 5 : 아이쿠 아이쿠 아이쿠 맙소사 아이쿠 아이쿠 아이쿠 아이쿠 아이쿠 아이쿠 - [우쿨렐레이 연주]