[음악 재생] 

교수 : 좋습니다. 이것은 CS50이고이다 일주일에 세 말. 그래서 우리는 오늘 여기있어,하지 샌더스에 대신 WEIDNER 도서관 극장. 그 중 내부 스튜디오입니다 하우저 스튜디오로 알려진, 또는 우리는 스튜디오 H 말, 또는 하리라 당신이 농담을 즐길 경우, 우리는 say--, 그것에서 실제로입니다 동급생, 마크, 온라인, 사람들은 트위터를 통해 많은 제안했다. 지금에 대한 멋진거야 스튜디오에서 여기에있는 나는이 녹색으로 둘러싸여있어된다 벽, 녹색 화면 또는 크로 마키, 그래서 CS50의 즉, 말하자면 나에게 알려지지 생산 팀, 지금, 퍼팅 수 나를 가장 세계 어디서나, 더 나은 또는 악화에 대한. 

이제 어떻게 앞서, 문제 설정있다 두 사람은, 이번 주 당신의 손에 하지만 문제 설정 세이 다음 주, 당신은에 도전한다 (15)의 소위 게임 오래된 파티 호의 그 당신은 수신 호출 수 전체 무리가있는 아이로 아래, 슬라이드 수있는 숫자, 왼쪽과 오른쪽, 한 차이가있다 퍼즐, 내의되는 당신 실제로 그 퍼즐 조각을 밀어 수 있습니다. 궁극적으로이 나타납니다 일부 반 임의의 순서로 퍼즐, 그리고 목표이다 하단, 상단을 정렬 하나에서, 왼쪽에서 오른쪽으로 15를 통해 모든 방법. 

불행하게도, 구현 당신은 손에있을 것이다 소프트웨어가 될 것입니다 기반이 아닌 물리적. 당신은 실제로 작성해야 할거야 코드가있는 학생 또는 사용자 캔과 15 게임을 재생할 수 있습니다. 실제로, 해커에 15 게임의 판, 당신은 도전 구현할 수있을 것입니다, 이 오래된 학교의 단지 재생 게임, 오히려 해결 그것의, 신 모드를 구현, 그래서, 말하자면 실제로 인간에 ​​대한 퍼즐을 해결, 힌트를 제공함으로써, 힌트 후, 힌트 후. 그 다음 주에 그래서 더. 하지만 그 앞에 놓여거야. 

지금은 기억이 이번 주 초 당신이 경우 우리는이 클리프 행어했다 이에 우리는 정렬하고 있었다 최고 현명한는 N의 O 큰의 상한했다 제곱. 즉, 거품 정렬, 선택 정렬, 삽입 정렬, 모두 상이한 반면 구현에있어서, 실행 제곱 N에 양도 아주 최악의 경우 시간. 그리고 우리는 일반적으로 가정 정렬 아주 최악의 경우 한 당신의 입력입니다 완전히 거꾸로입니다. 그리고 사실, 꽤 몇 가지 조치를 취했다 이들 각각의 알고리즘을 구현하는 방법. 

이제 클래스의 끝에서 리콜, 우리는 거품 정렬을 비교 다른 하나에 대한 선택의 종류에 대하여 것을 우리는 시간에 병합 정렬라고 나는 그것을 복용하는 것이 제안 주에서 수업의 장점 제로, 분할 및 정복. 그리고 어떻게 든 어떤 종류의 달성 로그 궁극적으로 시간을 실행, 대신 무엇인가 즉 순수하게 차있다. 그리고 그것은 매우 로그 아니다 그것보다 조금 더. 하지만이 클래스에서 호출하면, 그것은 훨씬 더 빨리, 훨씬이었다. 의 우리가 중단 된 부분을 살펴 보자. 

선택 대 버블 정렬 정렬 병합 정렬 대. 이제 그들은 모두, 실행중인 이론 동시에. CPU는 동일한 속도로 실행된다. 하지만 당신은 어떻게 지루한이 느낄 수 매우 빠르게 될 것입니다, 다만 얼마나 빨리, 우리는 때를 주입 주 제로의 알고리즘의 비트, 우리는 일을 속도를 높일 수 있습니다. 

그래서 마크 종류 놀랍다. 우리는 어떻게 순서를 활용할 수 더 빨리 숫자를 정렬합니다. 음의 다시 생각하자 성분에 그 우리 의는 주 제로에서 다시했다 전화 번호부에있는 사람을 찾고, 및 리콜 우리가 제안 의사, 어떤을 통해 우리가 찾을 수 있습니다 마이크 스미스 같은 사람, 이 같은 작은 선물을 보였다. 

지금 특히 봐 라인에서도 7 및도 8, 10, 11, 우리가 유지된다하는 그 루프를 유도 다시, 그리고 다시 3 행에 가고, 다시. 하지만 우리가 볼 수있는 것으로 나타났다 이 알고리즘, 여기에 의사에, 보다 전체적으로 약간. 사실, 내가 무엇을 찾고 있어요 여기에 화면에서, 검색하기위한 알고리즘은 일부 페이지 세트 중 마이크 스미스. 그리고 실제로, 우리는이 문제를 단순화 할 수 그 선 (7, 8)에서 알고리즘 10, 11는, 이런 말을 어느 나는 노란색으로 여기에 제시했습니다. 즉, 만약 마이크 스미스는 이전 책에 우리는 단계를 지정할 필요가 없습니다 단계가 지금 어떻게 그를 찾아 이동합니다. 우리는 지정할 필요가 없습니다 3 행으로 돌아갑니다, 왜 우리가 대신하지 않습니다, 말하자면,보다 일반적으로, 에 마이크를 검색 책의 왼쪽 절반. 

반대로, 마이크인지 실제로 나중에 책, 왜 우리는 인용을 끝내 검색을 인용하지 않습니다 이 책의 오른쪽 절반에 마이크합니다. 즉, 왜 우리는하지 않습니다 일종의 자신이 말에 펀트, 이에 마이크를 검색 책의 부분 집합, 우리가 기존에두고 알고리즘은 우리에게 얘기를 에 마이크를 검색하는 방법 책의 왼쪽 절반. 즉, 우리 알고리즘은 작동 여부 이의이 두께의 전화 번호부, 두께, 또는 어떠한 두께. 그래서 우리는 반복적으로 수 이 알고리즘을 정의합니다. 즉,에 여기에 화면이, 알고리즘 마이크 스미스를 검색 전화 번호부의 페이지 중. 그래서 라인 7, 10,의하자 바로 정확히 그런 말을. 그리고 나는이 용어 잠시 사용 전, 실제로, 재귀 화두는 지금이다 그리고이 프로세스의 어떻게 든 의해 순환 일을의 이미이 코드를 사용하여, 그리고, 다시 호출 다시, 다시. 지금은 중요 할 것 우리는 어떻게 든 아래 그 밖으로, 그리고 무한히 긴 그렇게하지 ​​않습니다. 그렇지 않으면 우리는 갈거야 참으로 무한 루프가 있습니다. 그러나 우리는이 아이디어를 빌릴 수 있는지 보자 재귀, 다시 일을하고 다시 다시, 해결하기 위해 병합을 통해 정렬 문제 정렬, 더욱 효율적으로. 

그래서 나는 당신이 일종의 병합 제공합니다. 이제 살펴 보자. 그래서 여기에 의사가 함께한다 우리가 정렬을 구현할 수있는, 병합 정렬이라는 알고리즘을 사용하여. 그리고 그것은 아주 간단하게이있다. N 개의 요소의 입력에, 즉, 당신이 있다면 주어진 n 개의 요소와 번호 입력되는 문자이든, 당신은 n 개의 요소, 만약 주어진다면 n이 2 미만이며, 단지 반환한다. 권리? N은 2보다 작은 경우이므로 즉, 요소​​의 마이리스트 크기는 0 또는 1 중 하나이고, 이러한 사소한 경우 모두, 목록이 이미 정렬됩니다. 더리스트가없는 경우, 분류하다. 그리고 길이의 목록이 있다면 도 1에서, 이것은 명백히 분류하다. 그래서 알고리즘은 필요 정말 흥미로운 일을, 우리는 두 개 이상이 있으면 요소는 우리에게 주어진. 그럼 다음 마법을 살펴 보자. 다른 원소의 좌측 절반을 정렬, 다음 요소의 오른쪽 절반을 정렬 다음 정렬 절반을 병합합니다. 그리고 굽힘 마음의 종류는 무엇입니까 여기에, 난 정말 없다는 것입니다 당신을 말한 것 같다 아직 아무것도, 오른쪽? 모든 I의 목록을 주어 말한 N 요소는 왼쪽 절반을 정렬 다음 오른쪽 절반, 다음 정렬 절반을 병합, 하지만 여기서 실제 비밀 소스는? 이 알고리즘은 어디에 있습니까? 그럼이 두 라인 밝혀 먼저, 요소의 종류 왼쪽 절반, 및 요소의 종류 오른쪽 절반, 재귀 호출은, 말하자면. 

결국,이에 시간에 점, 내가해야합니까 있는하는 알고리즘 요소의 전체 무리를 정렬? 네. 그것은 바로 여기입니다. 그것은 화면에 바로 여기, 그리고 그래서 나는 단계의 동일한 세트를 사용할 수 있습니다 왼쪽 절반을 정렬하려면, 오른쪽 절반은 내가 할 수있는. 그리고 실제로, 다시, 다시. 그래서 어떻게 든 또는 다른, 우리는 곧거야 병합 정렬의 마법을이 참조 바로 그 마지막에 포함 라인, 정렬 절반을 병합. 그리고 그것은 매우 직관적 인 것 같다. 당신은, 당신을 두 부분을 가지고 가고, 어떻게 든, 함께 병합, 우리는이를 볼 수 있습니다 구체적으로 잠시. 

그러나 이것은 전체 알고리즘이다. 그리고의는 이유를 정확하게 볼 수 있습니다. 그런데 우리는이 같은를 부여하고 있다고 가정 화면에 여기에 여덟 요소, 하나 팔을 통해,하지만 그들은있어 겉으로는 임의의 순서로. 그리고 손의 목표는 이러한 요소를 정렬합니다. 그럼 난에 대해 어떻게 갈 수 다시 사용하여 그 일을, 이 의사에 따라 정렬 병합? 그리고 또,이를 물들인 당신의 마음, 단지 잠시 동안. 첫 번째 경우는 꽤입니다 사소한,이 2 미만의 경우, 단지 할 수 할 일이 없다, 돌아갑니다. 그래서 정말 세 가지있다 단계는 정말 마음에 유지합니다. 다시, 다시, 나는 해요 가지고 싶은 것 왼쪽 절반을 정렬하려면, 오른쪽 절반을 정렬 다음 번에 ​​그 두 부분은, 분류되어 있습니다 나는 그들을 함께 병합 할 하나의 정렬 된 목록에. 그래서 명심. 

그래서 여기에 원래 목록입니다. 그럼으로이 치료하자 배열, 우리가되면서 일주일에 두, 이는입니다 메모리의 연속 블록. 이 경우, 팔을 포함 번호는 다시 다시 다시한다. 그리고의 지금 병합 정렬을 적용 할 수 있습니다. 그래서 내가 먼저 정렬 할 이리스트의 좌측 절반 그리고, 따라서하자 4, 8, 6 및 2에 초점. 

지금은에 대해 어떻게 가야합니까 크기 4의리스트를 정렬? 그럼 지금 고려해야 좌측 절반의 좌측 정렬. 다시 말하지만, 그냥 잠시 뒤로하자. 의사는이 경우, 나는 여덟 요소를 제공하고있어, 8 분명히 큰 이상 또는 2와 동일. 와 그래서 첫 번째 경우는 적용되지 않습니다. 그래서 여덟 요소를 정렬, 내가 먼저하기 요소의 좌측 절반을 정렬 그때 그때 병합, 오른쪽 절반을 정렬 두 개의 정렬 된 반쪽 크기 4의 각. 그래. 

당신은 그냥 나에게 이야기 한 경우에,를 정렬 지금 크기 4입니다 왼쪽 절반, 어떻게 왼쪽 절반을 정렬합니까? 그럼 난이있는 경우 네 가지 요소의 입력, 내가 먼저 왼쪽으로 정렬 두, 다음 오른쪽 두, 그리고, 나는 그들을 함께 병합합니다. 그래서 다시, 그것은 비트가된다 마음을 여기에 게임을 굽힘 당신 때문에, 가지,해야 당신이 이야기에 위치를 기억, 그러나 일의 마지막 임의의 개수의 요소를 주어진 먼저를 정렬 할 왼쪽 절반 다음 오른쪽 절반, 다음 그들을 함께 병합합니다. 의 정확히 그렇게 시작하자. 여기서 여덟 요소의 입력이다. 이제 우리는 여기에 왼쪽 절반 찾고 있습니다. 어떻게 네 가지 요소를 정렬 할 수 있습니까? 그럼 내가 먼저 왼쪽 절반을 정렬 할 수 있습니다. 이제 어떻게 왼쪽 절반을 정렬합니까? 잘 나는 두 가지 요소를 부여했습니다. 그래서이 두 요소를 정렬 할 수 있습니다. 2 인 이상의 2와 같은, 물론. 그래서 첫 번째 경우는 적용되지 않습니다. 

그래서 지금은 왼쪽으로 정렬해야 이 두 요소의 절반입니다. 좌측 절반은, 물론, 단지 4이다. 그래서 내가 어떻게 하나의 요소의 목록을 정렬 할 수 있습니까? 글쎄 지금은, 특별한 기본 케이스 상단까지, 말하자면, 적용됩니다. 1 미만이며, 내 목록은 참으로 크기 1입니다. 그래서 난 그냥 돌아갑니다. 난 아무것도하지 않습니다. 그리고 사실, 내가했습니다 무엇을보고 일, 4는 이미 정렬됩니다. 마찬가지로 나는 이미 해요 여기에 부분적으로 성공. 

이제 그 종류의 바보 같다 주장하지만, 그것은 사실입니다. 4 크기 1의 목록입니다. 그것은 이미 정렬입니다. 즉, 왼쪽 절반입니다. 지금은 오른쪽 절반을 정렬 할 수 있습니다. 제 8 입력, 하나의 원소이며 유사하게, 이미 정렬. 바보, 너무, 그러나 다시, 이 기본 원칙 우리가 지금 구축 할 수 있도록하는 것입니다 이 꼭대기에 성공적으로. (4)는 현재, 8 정렬, 분류 마지막 단계는 무엇인가? 그래서 세 번째이자 마지막 단계, 어떤 시간은 당신이, 목록, 리콜을 정렬하고 두 반쪽을 병합하는 것이 었습니다 왼쪽 및 오른쪽. 그럼 정확히 할 수 있습니다. 내 좌측 절반은, 물론, 4이다. 내 오른쪽 절반은 8입니다. 

그래서이 작업을 수행 할 수 있습니다. 우선은 할당 할거야 일부 추가 메모리, , 내가 여기에 표현 것이다 그 단지 차 배열로, 즉,이 들어갈만큼 크다. 하지만 당신은 연장 상상할 수 그 사각형 전체 길이, 우리는 더 이상 필요합니다. 나는 4 받아 8 및 병합 어떻게 함께 크기 1의 두리스트? 여기, 너무, 아주 간단합니다. 4는, 먼저 8 온다. 나는를 정렬 할 경우 때문에 왼쪽 절반 다음 오른쪽 절반, 다음 두 반쪽을 병합 함께 정렬 된 순서로, 4는, 먼저 8 온다. 

그래서 우리는 심지어, 진전 될 것으로 보인다 나는 어떤 실제 작업을 수행하지 않은 있지만. 우리는 이야기를 어디하지만 기억. 우리는 원래 여덟 요소를했다. 우리는 4 왼쪽 절반을, 분류. 그 다음 우리는 왼쪽 절반을 정렬 2이었다 좌측 절반의. 그리고 여기 우리는 간다. 우리는 그 단계를 완료. 

우리가 분류 한 경우에 따라서 우리는 지금, 2의 절반 왼쪽 2의 오른쪽 절반을 정렬 할 수 있습니다. 따라서 (2)의 오른쪽 절반은 여기에이 두 값, 6, 2. 그래서 지금 크기의 입력을 할 수 (2) 다음의 왼쪽 절반을 정렬하고, 우측 절반하고 함께 병합. 그럼 어떻게 크기의 목록을 정렬 할 1, 단지 숫자 6을 포함? 난 이미 끝났어요. 크기 1의 목록이 정렬됩니다. 

나는 또 다른 목록을 정렬하려면 어떻게 크기 1, 소위 오른쪽 절반. 글쎄 그것은, 너무, 이미​​ 정렬됩니다. 숫자 2는 단독이다. 그래서 지금은 두 부분이, 왼쪽 좋아, 함께 병합 할 필요가있다. 나 자신에게 약간의 여분의 공간을 제공 할 수 있습니다. 그리고, 거기에 2를 넣어 다음 6 거기하여 그 목록을 정렬, 좌우 궁극적으로, 함께 병합. 그래서 나는 약간 더 나은 모양입니다. 나는이 일 때문에 아니에요 분명히 4, 8, 2, 6 내가 원하는 마지막 순서가 아닙니다. 하지만 지금은, 그 크기 2의 두 목록을 양쪽에 각각 정렬되어있다. 그래서 지금 당신은 당신의 마음의에서 되감기 경우 눈이 곳은 우리를 떠나지 않았다? 그때, 여덟 요소 시작 나는 , (4)의 좌측 절반으로 줄였다 아래 다음 (2)의 왼쪽 절반 및 다음 (2)의 오른쪽 절반 나는 왼쪽 정렬, 따라서 완료 (2)의 절반, 및 (2)의 오른쪽 절반 그래서 세 번째와 마지막 단계는 여기에 무엇입니까? 나는 함께 병합해야 크기 2의 두 목록. 그래서 앞서 가자. 그리고 여기에 화면에 제공 나 일부 추가 메모리, 기술적으로하지만, 내가했는지 알 빈 공간까지 상단의 모두를 가지고 가. 나는 특히 싶은 경우 효율적인 공간 현명한, 난 그냥 요소를 이동 시작할 수 앞뒤로, 상단과 하단. 그러나 단지 시각적 명확성을 위해, 나는 아래를 내려 놓고거야 친절하고 깨끗한 물건을 유지합니다. 

그래서 크기 2의 두 가지 목록을 가지고있다. 첫 번째 목록은 4와 8이 있습니다. 두 번째 목록 2와 6이있다. 의 그 병합하자 함께 정렬 된 순서로. 도 2는 물론, 먼저 다음 4, 다음 (6), 다음 (8). 그리고 지금 우리는 점점 것 같습니다 어딘가에 재미. 의 지금은 분류 한 반 목록과 일치하여, 그건 모든 짝수 있지만, 실제로, 단지 우연의 일치입니다. 그리고 지금은 왼쪽 정렬 한 절반은 2, 4, 6 및 8이다되도록. 아무것도 순서가 없습니다. 즉 진보 것 같은 느낌이 든다. 

나는 것 같은 지금은 느낌 이제 영원히 얘기, 그래서이 경우 볼 일이다 알고리즘은 참으로, 더 효율적이다. 그러나 우리는을 통해거야 그것은 슈퍼 질서. 컴퓨터는 물론, 그런 식으로 할 것. 그래서 우리는 어디인가? 우리는 여덟 요소 시작했다. 나는 4의 왼쪽 절반을 분류. 나는 그와 함께 할 것 같다. 이제 다음 단계에있다 4의 오른쪽 절반을 정렬 할 수 있습니다. 그리고이 부분은 우리가 갈 수 좀 더를 통해 빨리, 당신이있어 있지만 다만, 되감기 또는 일시 중지에 오신 것을 환영합니다 그것을 통해 생각 자신의 페이스, 그러나 우리는 지금 기회가있다 사에 동일한 알고리즘을 다른 번호. 

그래서 앞서 가자, 및 초점 우리가 여기에 오른쪽 절반,. 그의 왼쪽 절반 오른쪽 절반, 그리고 지금 왼쪽의 왼쪽 절반 그 오른쪽 절반의 절반, 나는 크기의 목록을 정렬 어떻게 단지 하나의 숫자를 포함? 그것은 이미 이루어집니다. 나는 목록에 대한 동일한 작업을 수행하려면 어떻게 단 7을 포함하는 크기 1? 그것은 이미 이루어집니다. 다음이 절반 단계 세 이 두 가지 요소를 병합하는 것입니다 크기 2, 1, 7의 새 목록에. 모든 짓을하지 않는 것 그 많은 흥미로운 작품. 의 다음에 어떻게되는지 보자. 나는 단지의 왼쪽 절반을 정렬 내 원래의 입력의 오른쪽 절반. 이제 오른쪽으로 정렬 할 수 (5)와 (3)을 포함 절반. 의 다시 왼쪽을 살펴 보자 반, 분류, 오른쪽 절반, 분류, 과 함께 두 병합 추가 공간으로, (3) 다음, 먼저 5 온다. 그리고 지금, 우리가 분류 한 오른쪽 절반의 왼쪽 절반 원래의 문제, 그리고 오른쪽 절반의 오른쪽 절반 원래 문제. 세 번째와 마지막 단계는 무엇입니까? 그럼 함께 두 반쪽을 병합합니다. 그래서 나 자신에게 약간의하자 다시 여분의 공간,하지만, 내가 그 여분의 공간 구성 Top을 사용 될 수 있습니다. 그러나 우리는 계속거야 시각적으로는 간단합니다. 내가 지금 1에 병합하자,과 다음, (3), (5) 다음, 다음 7. 이것으로 지금 날 떠나 원래 문제의 오른쪽 절반 즉 완벽하게 정렬합니다. 

그래서 남아? 내가 자꾸 같은 느낌 또 다시 동일한 것들 하지만 그 반영이다 우리는 재귀를 사용하고 있다는 사실. 을 사용하는 과정 또 다시 알고리즘 작은 부분 집합에 원래 문제. 그래서 지금은 왼쪽 정렬 한 원래 문제의 절반입니다. 나는 오른쪽 정렬 반이 원래 문제. 세 번째와 마지막 단계는 무엇입니까? 아, 병합입니다. 그럼 그렇게하자. 의 몇 가지 추가 할당하자 메모리, 그러나 나의 하나님, 우리 지금 어디를 둘 수 있었다. 우리는 너무 많은 공간을 사용할 수있다 우리에게, 그러나 우리는 간단하게 할 것이다. 대신에 다시가는 및 앞으로 우리의 기존 메모리와, 그냥 해하자 시각적으로 여기 아래에 아래로, 합병 마무리합니다 왼쪽 절반과 오른쪽 절반. 

병합하여 그래서, 어떻게해야합니까? 나는 위해 요소를 먹고 싶어. 그래서 왼쪽 절반을보고, 나는 첫 번째 숫자는 2 참조하십시오. 나는 오른쪽 절반 보면, 나는 첫 번째 숫자를 참조 그래서 당연히, 1 인 수는 내가 뽑아 싶어 내 최종 목록에서 첫 번째 넣어? 물론, 1. 지금은 그 같은 질문을 할 수 있습니다. 왼쪽 절반에, 나는했습니다 여전히 숫자 2를 얻었다. 오른쪽 절반에, 나는 숫자 3을 가지고있다. 어느 내가 선택 하시겠습니까? 물론, 숫자 2와 이제 후보를 통지 오른쪽에서 왼쪽으로, 3 상 4이다. 의는 물론, 3을 선택할 수 있습니다. 이제 후보는 4에있다 오른쪽에서 왼쪽으로, 5. 우리는 물론, 4를 선택합니다. 오른쪽에서 왼쪽으로, 5 6. 우리는 물론, 5를 선택합니다. 오른쪽에서 왼쪽으로, 7 (6). 우리는 6을 선택한 다음 우리를 (7)를 선택한 다음, 우리는 (8)를 선택합니다. 짜잔. 

단어 그래서 엄청난 수의 후에, 우리 여덟 요소의 목록을 분류 한 팔을 통해 하나의 목록으로, 즉, 각 단계에 따라 증가 있어요 하지만 얼마나 많은 시간이했다 그것은 그렇게 우리를 데려. 잘 나는 일부러했습니다 그림으로 누워 것들을 밖으로 여기에, 그래서 우리가 할 수있는 종류의 참조하거나 분할을 주셔서 감사합니다 정복에 그 일이 됐어요. 

당신이 이후에 다시 보면 참으로 경우, 나는이 점선을 모두 떠 났어요 장소 홀더에, 당신이 할 수있는, 종류의 역순으로, 참조 당신은 가지에 다시 보면 역사 지금, 내 원래의 목록 크기 8의 물론이다. 그리고 이전에, 내가했다 크기 4의 두 목록을 처리, 다음 크기 2의 네 개의 목록, 다음 크기 1의 여덟 목록. 

그래서이 무엇을하는지, 종류의, 당신을 생각 나게? 의 자, 참으로, 어떤 우리가했습니다 알고리즘 지금까지 바라 보았다 우리가 어디 분할하고, 분할 및 분할, 다시 일을 가지고 유지하고, 다시,이 일반적인 생각을 초래한다. 그래서 뭔가있다 로그 여기에 무슨. 그리고 그것은 N 꽤 로그, 아니지만 로그 구성 요소가있다 우리가 무슨 짓을했는지에. 

이제이 실제로 어떻게 생각해 보자. 그래서 다시, N의 기록이었다 좋은 실행 시간, 우리는 같은 것을했을 때 이진 검색, 우리가 지금 전화로, 분할 및 정복 전략 어떤 통해 우리는 마이크 스미스를 발견했다. 지금 기술적으로. 즉, 심지어 N의 로그베이스 2의 대부분의 수학 수업을하지만, (10)는 일반적으로 가정 기지입니다. 그러나 컴퓨터 과학자 거의 항상 생각하고베이스 2의 관점에서 이야기 그래서 우리는 일반적으로 단지의 로그를 말한다 N, N 대신 로그베이스 (2)의, 그러나 정확히 하나있어 컴퓨터의 세계에서 같은 과학, 옆으로, 일정한 요인이있다 둘 사이의 차이가 너무 재 더 공식적인 이유로, 어쨌든 논쟁. 

하지만 지금, 우리는 무엇을 걱정 약이 예이다. 그럼 예에 의해 증명하지 말고 오직에서 최소 수의 예를 사용하여 손 전성 검사로, 경우에 당신은 것입니다. 그래서 이전에 공식 로그 기본이었다 N 2,하지만이 경우 N은 무엇인가. 나는 N 원래의 번호를 가지고, 또는 8 원래 숫자의 구체적. 지금은 조금이었다 동안,하지만 난 꽤 반드시 해당 로그베이스 2 (8)가 3의 값, 실제로 무슨 일이 즉 약 좋네요 3 것이이 시대의 정확히 번호 당신은 목록을 나눌 수 있음 다시, 다시 길이 8, 다시, 당신은 남겨까지 단지 크기 1의 목록과. 권리? 8, 4로 이동 2로 이동, 1로 진행하고, 그건 정확하게 반영 사진 우리는 잠시 전했다. 그래서 조금 정신이 곳으로 확인 로그는 실제로 참여하고있다. 

그래서 지금, 그 밖의 무엇을 여기에 포함된다? N. 그래서 모든 것을 알 수 시간 나는 목록을 분할 역사의 역순이기는하지만 여기에, 나는 아직도 n 개의 일을했다. 즉, 병합 단계는 필요 나는, 숫자 하나 하나를 터치 로 밀어 넣하기 위해 그것의 적절한 위치. 순간에도이의 높이 도면, n 또는 (3)의 크기 n의 로그 인 구체적으로 말하면, 여기 3 개 부문을했다. 얼마나 많은 일을 내가 가로 했는가 이 차트마다 따라? 

글쎄, 난의 N 단계를했다 내가했습니다 경우 때문에, 작업 네 개의 요소 네 가지 요소를 가지고 나는 함께 병합 할 필요가있다. 난을 통해 갈 필요가 이 네와이 네, 궁극적으로 병합하기 다시 여덟 요소로. 반대로 경우에 나는 여덟 손가락을 가지고 내가하지 않는, 여기, 8 fingers-- sorry-- 내가 한 경우 , 여기에 4 개의 손가락을 가지고 나는, 네 손가락 않는 여기에, 내가하는, 그 동일한의 예를 들어 이전에, 나는 할 경우 에서 비록 여덟 손가락을 나는, 가지, 할 수있는 총. 나는 정확히, 여기에 수행 할 수 있습니다 나는 확실히 할 수 이 목록을 모두 병합 함께 크기 (1). 그러나 나는 확실히보고있다 각 요소에서 정확히 한 번만. 따라서이 과정의 높이는, n은 로그 이 프로세스의 폭이 있으므로, 말하자면 그래서 우리는 무엇을 보인다, n은 궁극적으로,이다,이합니다 크기 n 번의 실행 시간은 N 로그인합니다. 

즉, 우리는 분할 목록, 로그 n 번, 그러나 우리는 그것을했다 때마다, 우리는 있었다 요소 하나 하나를 터치합니다 병합하기 위해 모두 함께하는 단계를 N, 그래서 우리는이 n 번 n을 기록했다, 또는 컴퓨터 과학자가 말하는 것처럼, 점근 적으로, 어떤 큰 말 것 상부를 설명하는 데 실행 시간에 바인딩, 우리는 큰 O를 실행하는 로그 N 시간, 말하자면. 

지금이 있기 때문에 중요하다 실행 시간이 무엇인지 기억 버블 정렬 및 선택과 정렬 및 삽입 정렬, 와 존재조차 몇 가지 다른, N은 우리가 있었던 곳이었다 제곱. 그리고 당신은, 가지, 여기를 볼 수 있습니다. n은 제곱하면 분명히 n 번입니다 N, 그러나 여기에서 우리가 n 번이 N 로그 우리는 이미 주부터 알고 제로, 그 로그 N, 대수, 뭔가 선형보다 낫다. 결국, 화상을 기억 빨간색과 노란색 우리는 그린과 그린 라인, 녹색 로그 라인이 훨씬 낮았다. 그러므로, 훨씬 더 빠르게 직선 노란색과 빨간색 선 이상, n 번 참이고, n은 로그, 더 나은 N 회보다 N 또는 N 제곱. 

그래서 우리는 갖고있는 것 같다 알고리즘 병합을 확인 종류 훨씬에서 실행 빠른 시간, 참으로, 그 이유는, 이번 주 초, 때이다 우리는 거품 사이의 경쟁을 보았다 정렬, 선택 정렬 및 병합 종류, 종류 정말, 정말 원 병합합니다. 그리고 실제로, 우리는 심지어 기다리지 않았다 거품 정렬 및 선택 정렬에 대한 마칩니다. 

이제 다른 하나의 패스를 보자 이에, 조금 더에서 형식적인 관점, 그냥 경우에, 이것은 더 공진 그 높은 수준의 토론보다. 그래서 여기 알고리즘은 다시입니다. 의 자신을 물어 보자, 어떤 실행 시간 이 여러 단계를 알고리즘인가? 이제 처음으로 나뉘게 경우와 두번째 경우. IF 케이스와 ELSE IF, n이 2 미만이면, 단지 반환한다. 일정 시간 같은 느낌. 이 두 단계와 같은 종류의,이다, n이 2 미만이면, 리턴한다. 그러나 우리는 월요일에 말했듯이, 일정 시간, 또는 1의 O 큰, 두 단계, 세 수 있습니다 단계, 심지어 1,000 단계. 중요한 것은이 점이다 단계의 상수. 그래서 노란색 의사를 강조 여기, 우리가 전화 할게에서 실행 일정 시간. 그래서 더 공식적으로, 그리고 우리는이 이러시면거야 정도 될 것입니다있는 우리 N의 T들을 당장이 권리를 공식화, 문제의 실행 시간 즉, 입력으로 n 개의 일도 소요 하나의 O 큰 동일 N이 2보다 작을 경우. 그래서 그 조건으로합니다. n은보다 작은 경우 그래서, 명확하게하기 (2) 그리고 나서, 매우 짧은 목록을 가지고 n은 실행 시간의 N, T, 1 또는 0이 매우 구체적인 경우에, 그냥 일정 시간이 될 것. 그것은 하나를 걸릴 거예요 무엇이든, 두 단계를 단계. 이 단계의 고정 된 수이다. 

따라서 수분이 많은 부분은 반드시 있어야합니다 의사 코드에서 다른 경우. ELSE 케이스. 요소의 정렬 왼쪽 절반, 일종의 권리 요소의 절반, 정렬 절반을 병합합니다. 이들 각 단계는 얼마나 걸립니까? 음, 만약 실행 N 요소를 정렬하는 시간 이며, 현실을 매우 부르 자 일반적으로, T, N의, 다음 왼쪽 정렬 요소의 절반 이다, 가지, 말처럼, 2로 나눈 N의 T, 마찬가지로 우측 절반 정렬 요소이며, 가지, 말처럼, N의 T는 2 분할 한 다음 정렬 절반을 병합. 그럼 내가 가지고있는 경우에 어떤 여기에 요소 수, 네, 어떤 수를 같은 여기 요소, 네처럼, 나는이 네 가지의 각각을 병합해야 에서, 이들 네 개의 각각 하나의 다른 후, 그래서 궁극적으로 나는 여덟 요소를 가지고있다. 그것은 즉, n 개의 단계의 오 크다 같은 느낌? 나는 손가락과 각각의 N을 가지고 있다면 그들 대신에 병합하는, 그것은 또 다른 N 단계처럼. 

그래서 참으로 공식을 통해 (formulaically), 우리는이를 표현할 수 처음에는 조금 무섭게이기는하지만 눈,하지만 뭔가 즉, 정확히 논리를 캡처합니다. 실행 시간, T, N의, IF N 2 이상이다. 이 경우, ELSE 경우에서, N의 T이고 2로 나눈 값 (N)의 플러스 T 2로 나눈 플러스 N의 O 큰 일부 단계의 선형 수, 어쩌면 정확히 N, 어쩌면 2 회 N이지만, 대략 N의 순서이다. 있도록, 너무, 어떻게 우리가 할 수있는 것입니다 공식을 통해 (formulaically)이를 표현한다. 지금 당신은 않는 한이 모르는 것 당신은, 당신의 마음에 그것을 녹음 한 또는 그것을 찾아 다시 교과서, 그 조금있을 수 있습니다 마지막에 시트를 사기, 그러나 이것은, 실제로 것입니다 N 로그 n의 O 큰 우리에게주고, 재발 그 때문에 당신은 화면에 현재보고있는 실제로, 그것은을 한 경우 예 무한한 수, 또는 당신이 공식을 통해 (formulaically)을했다, 당신은 것 이 볼이 공식 때문에 자체의 T로, 재귀 N 오른쪽에 뭔가 이상, 왼쪽에 이상 (N)의 T와,이 수 실제로 표현 될 궁극적 N 로그 n의로 큰 이동합니다. 확신하지 않으면, 그건 , 지금은 잘 단지 참, 그건 있다는 믿음에 걸릴, 그 재발에 이르게 무엇을, 그러나 이것은 단지 조금 더 보고 수학적 접근 병합 정렬의 실행 시간 혼자의 의사에 기초. 

이제 조금 보자 이 모든에서 숨, 과를 살펴 특정 전 상원 의원, 사람들 조금 익숙해를 보일 수 있습니다, 누가 구글의 에릭과 함께 앉아 인터뷰 얼마 전에 슈미트, 무대에서, 전체 무리의 앞에 사람들의 궁극적에 대한 이야기 주제, 즉 꽤 이제 익숙하다. 이제 살펴 보자. 

에릭 슈미트 (Eric Sc​​hmidt) : 이제 상원 의원, 당신이 구글에서 여기 내가 생각하기 좋아 면접으로 대통령. 지금은 대통령으로 취업을하기 어렵다. 오바마 대통령 : 오른쪽. 에릭 슈미트 (Eric Sc​​hmidt) : 그리고 당신이있어 이제 [들림] 할 것. 그것은 구글에 취직하는 것도 어렵다. 오바마 대통령 : 오른쪽. 

에릭 슈미트 : 우리는 질문이, 우리는 우리의 후보의 질문을, 이 사람은 래리 쉬머에서입니다. 

오바마 대통령 : OK. 

에릭 슈미트 (Eric Sc​​hmidt) : 무엇? 너희들은 내가 농담하는 것 같아? 그것은 바로 여기입니다. 가장 효율적인 방식은 무엇입니까 만 32 비트 정수를 정렬? 

오바마 대통령 : 저기 ... 에릭 슈미트 : 때때로, 어쩌면 내가 미안 해요, 봐 주길 오바마 대통령 : 아니, 아니, 아니, 아니, 아니, 나는 think-- 에릭 슈미트 : 그건 그건 ... 아니다 오바마 대통령 : 나는 생각 나는 거품을 생각 종류의 갈 길을 잘못 될 것입니다. 에릭 슈미트는 : 자. 누가 그에게이 말? 그래. 나는 컴퓨터 과학하지 않았다 on-- 

오바마 대통령 : 우리는했습니다 거기에 우리의 스파이를 얻었다. 교수 : 좋습니다. 의 이제 우리 뒤에 남겨 두자 알고리즘의 이론적 세계 점근 적 분석 이들의 일부 항목을 반환 주 0과 1, 그리고 처음부터 일부 훈련 바퀴를 제거하려면 당신이됩니다. 당신이 정말로 이해할 수 있도록 결국 처음부터, 무엇이다 , 때를 후드 아래에가는 프로그램의 작성, 컴파일 및 실행. 이 것을, 특히 기억 우리가 바라 보았다 첫 번째 C 프로그램, 표준, 간단한 프로그램 종류의, 상대적으로 말하기, 특징으로는, 안녕하세요 세계를 인쇄합니다. 그리고이 과정 말했다 리콜 것을 그 소스 코드를 통과 바로 이것이다. 당신은 당신의 소스 코드를 받아 통과 그것은 컴파일러를 통해, 연타 등, 아웃은, 오브젝트 코드를 제공 이, 0과 같을 수 있습니다 컴퓨터의 CPU, 중앙이 프로세싱 유닛 또는 뇌 궁극적으로 이해하고 있습니다. 

그것은 그가 있다고 밝혀 지나친 단순화의 비트, 우리가 지금하고 있는지 위치 떨어져 애타게 정말하고 있는지 이해하기 후드 아래에가는 당신이 실행할 때마다 연타, 또는 더 일반적으로, 때마다 당신은 프로그램을 확인하고 CF (50) IDE 사용. 특히, 재료 등 이 먼저 생성됩니다 때 처음 프로그램을 컴파일합니다. 즉, 때를 소스 코드를 가지고 무엇을 먼저, 그것은 컴파일 연타에 의해 출력되는 어셈블리 코드로 알려진 무언가이다. 그리고 사실, 정확히 다음과 같습니다. 

나는에서 명령을 실행 이전 명령 행. 연타 대시 자본의에서는 hello.c, 이것은 파일을 만든 저라는 hello.s를 들어, 이는 내부에 정확하게 있었다 이러한 내용과 조금 더 위보다 약간 아래, 하지만 수분이를 넣었습니다 여기에 화면에 정보를 표시합니다. 당신이 자세히 보면, 당신은 볼 수 있습니다 최소한 몇 친숙한 키워드. 우리는 정상에 주요 있습니다. 우리는 중간에서 아래로는 printf있다. 그리고 우리는 또한 세계 안녕하세요이 아래로 아래 따옴표로 백 슬래시 명. 

여기에 다른 모든 것을 매우 낮은 수준의 지침입니다 컴퓨터의 CPU는 이해하고있다. 메모리를 이동 CPU 지시 주위에, 메모리에서로드하는 문자열, 궁극적으로, 인쇄 화면에 것들. 지금 무슨 일이 후 비록 발생 이 어셈블리 코드가 생성된다? 궁극적으로, 당신은 참으로 수행, 여전히 오브젝트 코드를 생성한다. 그러나 단계는 정말이 그 후드 아래 진행되고 이 같은 좀 더 봐. 소스 코드, 어셈블리 코드가된다 이는 다음 오브젝트 코드가된다, 여기에 수술 단어는, 그 당신이 당신의 소스 코드를 컴파일 할 때, 아웃 후, 어셈블리 코드, 온다 당신이 당신의 어셈블리 코드를 조합 할 때, 아웃 오브젝트 코드를 제공됩니다. 

이제 연타, 슈퍼 정교 컴파일러의 많은 것, 그리고 이러한 모든 단계를 수행합니다 동시에, 그것은 반드시 수행 출력 중간을 당신도 볼 수있는 파일입니다. 그냥 물건을 컴파일, 이는 일반적인 용어입니다 이 전체 과정을 설명합니다. 하지만 당신이 정말로 원하는 경우 특히 수,있다 많은 더뿐만 아니라이 진행. 

그러나의는 또한 지금도 생각해 보자 그 슈퍼 간단한 프로그램에서는 hello.c, 기능이라고. 그것은 printf의를했다. 하지만, 참으로, printf와 쓰기하지 않았다 즉 말하자면, C와 함께 제공됩니다. 그것은의 기능 리콜의 표준 io.h에 선언하는 헤더 파일 인 주제는 우리가 실제로 것입니다 오래 전에 더 깊이로 잠수. 그러나 헤더 파일입니다 일반적으로 동반 코드 파일, 소스 코드 파일, 그렇게함으로써 표준 io.h.이 존재 많은처럼 

얼마 전, 사람, 또는 누군가도 썼다 에, 표준 io.c라는 파일 이는 실제 정의, 또는 printf의 구현, 및 기타 기능의 움큼, 실제로 기록됩니다. 우리가 가진 생각한다면, 주어진 여기에 왼쪽에서는 hello.c에, 때 컴파일 된 경우에도, hello.s 우리에게 제공 연타는 장소에 저장 귀찮게하지 않습니다 우리는 그것을보고, 그 어셈블리 코드 수 hello.o로 조립 도착하는 실제로, 기본 이름입니다 당신이 소스를 컴파일 할 때마다 주어진 오브젝트 코드로 코딩되지만 아니다 아직 그것을 실행하는 것은 매우 준비, 또 다른 단계 때문에 일이 있으며,이 지난 몇 위해 일어나고 주, 당신에게 아마 모르는. 

특히 어딘가에 CS50 IDE에서,이, 도 조금있을 것입니다 잠시 단순화, 이, 또는 시간에했다, 표준 io.c라는 파일, 누군가로 컴파일하는 것이 표준 io.s 또는 동등한, 누군가는 조립 된 것을 표준 io.o에, 또는 그것으로 밝혀 약간 다른 파일 다른를 가질 수 있습니다 형식 모두 확장 파일, 이론 및 개념적으로 정확히하지만 그 단계는 어떤 형태로 발생했다. 말을 지금하는 것입니다 어떤 내가 프로그램을 작성하고있을 때, 에서는 hello.c, 단지 말한다 것을, 안녕하세요, 나는 누군가 다른 사람의 코드를 사용하고 있습니다 에 한때 printf와 같은 시간, 표준 io.c라는 파일에, 다음 어떻게 든 내을해야 오브젝트 코드, 제 0과 1, 그 사람의 목적 코드, 또는 0과 1, 어떻게 든으로 그들을 함께 연결 것을, 안녕하세요라는 하나의 최종 파일, 이 제로의 모든과 내 주요 기능에서 사람, 그리고 제로의 모든 과의 printf에 대한 것. 

그리고 실제로, 마지막 과정이다 라는 개체 코드를 연결. 출력 중 어느 실행 파일이다. 그래서 공정성에,에 일, 아무것도 끝 주 한 이후 변경된, 때 처음 프로그램을 컴파일하기 시작했다. 실제로,이 모든왔다 후드 아래에 일어나고, 그러나 지금 우리는 위치에있어 여기서 우리가 실제로 할 수있는 이러한 여러 단계 떨어져 애타게. 그리고 실제로, 말 오늘, 우리는 여전히있어 0과 1, 왼쪽있는 좋은 SEGUE 지금 실제로 C의 또 다른 기능에, 그 우리는 대부분 활용할 수 없었습니다 현재까지, 비트 연산자라고도합니다. 즉, 지금까지, 우리는 언제했습니다 C에서 C 또는 변수의 데이터 처리, 우리는 같은 일을 했어 문자와 수레와 기능 및 정수 (Long)과 복식 등을하지만, 그 모두는 적어도 8 비트이다. 우리는 아직 본 적​​이 없습니다 개별 비트를 조작, 심지어 개별 비트하지만, 우리 , 0과 1을 표현 할 수 있습니다 알고 있습니다. 지금은 C에 그 밝혀, 당신 개별 비트에 대한 액세스를 얻을 수있다, 당신은 구문을 알고있는 경우, 있는 그들을 얻을 수 있습니다. 

그럼 살펴 보자 비트 연산자에서. 그래서 여기에 사진 몇 가지 기호는 그 우리는 종류의, 일종의 전에 봤어요. 나는, 수직을 앰퍼샌드 참조 바,뿐만 아니라 일부 다른, 그 앰퍼샌드 앰퍼샌드 리콜 우리가 전에 본 무언가이다. 당신이 가지고있는 논리 AND 연산자, 이들 둘이 또는 논리 OR 연산자, 어디를 두 개의 수직 바있다. 비트 연산자, 우리는거야 개별적으로 비트에서 작동 참조 단지 하나의 앰퍼샌드를 사용, 하나의 수직 바, 캐럿 기호 다음, 작은 온다 물결, 다음 왼쪽 브래킷 브래킷을 왼쪽, 오른쪽 대괄호 오른쪽 대괄호. 이들 각각은 서로 다른 의미를 갖는다. 

사실, 이제 살펴 보자. 의 오래된 학교 오늘, 사용 가자 근년에서 터치 스크린 화이트 보드라고도합니다. 그리고이 화이트 보드 우리를 허용하는 것입니다 몇 가지 아주 간단한 기호를 표현하는, 또는 오히려 몇 가지 아주 간단한 공식, 즉, 우리는 궁극적으로 다음 수 활용, 순서 개인에 액세스 할 수 C 프로그램 내에서 비​​트. 즉,이 해 보자. 대한하자 첫 번째 이야기 앰퍼샌드에 대한 순간, 이는 비트 AND 연산자입니다. 즉,이다 수있는 연산자 나 왼손 변수가하는 전형적으로, 그리고 우측 변수 또는 개별 값, 그 경우 우리와 함께 그들에게, 나에게 최종 결과를 제공합니다. 그래서 나는 무엇을 의미합니까? 프로그램에서, 당신은 변수가있는 경우 이 값을 저장 한 그, 또는 이제 간단하게, 그냥하자 개별적으로 0과 1을 기록, 앰퍼샌드 연산자가 어떻게 작동하는지 여기. 0 앰퍼샌드 0 0과 동일 할 것입니다. 이제 그 이유는 무엇입니까? 

그것은 매우 유사 부울 식, 것을 우리는 지금까지 논의했습니다. 모든 후 생각한다면, 0이됩니다 거짓, 0, 거짓 거짓과 거짓 우리가 언급 한 바와 같이, 인 논리적으로, 또한 거짓. 그래서 우리는뿐만 아니라 여기에 0을 얻는다. 당신은 0 앰퍼샌드을 경우 1, 우물, 너무, 이 때문에 들어, 0이 될 것입니다 왼쪽 표현은, true 또는 1이어야합니다 그것은 사실과 진실해야합니다. 그러나 여기에서 우리는 거짓이 참, 또는 0과 1. 이제 다시, 우리는 1 앰퍼샌드가있는 경우 0, 역시 0이 될 것입니다 것을, 우리는 1 앰퍼샌드 (1)이있는 경우, 마지막으로 우리는 1 비트가 않습니다. 즉 그래서 우리는 일을하지 않을 이 연산자와 흥미로운 아무것도 아직,이 앰퍼샌드 연산자. 그것은 비트 AND 연산자입니다. 그러나 이러한 성분은 어떤을 통해 우리가 할 수있는 우리가 곧 보 겠지만 흥미로운 것들. 

이제 그냥 하나를 살펴 보자 여기에 오른쪽 위에 수직 막대. 나는 0 비트와 내가있는 경우 아니면와, 비트 OR 연산자, 다른 0 비트, 그 날 0을 제공하는 것입니다. 나는 0 비트 또는 그것으로 걸릴 경우 1 비트, 나는 1을 얻을거야. 그리고 사실, 단지에 대한 선명도, 나를 돌아 가자 그래서 내 수직 막대 1의 착각되지 않습니다. 나를 모두 다시 보자 제 1 좀 더있어 내가하면 명확하게, 그래서 우리는 다음을 참조하십시오 1 또는 0, 즉 1이 될 것있다, 내가 1 또는 1이있는 경우, 도 1이 될 것입니다. 그래서 당신은 논리적으로 볼 또는 수 운영자는 매우 다르게 동작합니다. 이 0 나에게 제공 또는 0 날 0을 제공하지만, 다른 모든 조합은 나에게 1을 제공합니다. 너무 오래 내가 한 일을 가지고 수식 결과는 1이 될 예정이다. 

과와 대조적으로 연산자, 앰퍼샌드, 나는 두 개의 1의 경우에만 방정식, 사실은 1 아웃을받을 수 있나요. 이제 몇 가지 다른있다 사업자뿐만 아니라. 그 중 하나는 조금 더 복잡하다. 그래서 내가 가서 삭제하자 이 공간을 확보합니다. 그리고 이제 살펴 보자 단지 잠시 캐럿 기호. 이는 통상적 인 문자는 입력 할 수 있습니다 키보드를 들고 이동에와 당신의 미국 꼭대기 숫자 다음 하나 키보드. 

그래서이 독점 OR 연산자, 배타적 논리합. 그래서 우리는 단지 또는 연산자를 보았다. 이것은 배타적 논리합 연산자입니다. 실제로 차이가 무엇입니까? 그럼 그냥 공식을 살펴 보자, 궁극적으로 재료로 사용. 0 XOR 0. 내가 말할거야 항상 0입니다. 즉, XOR의 정의입니다. 0 XOR 1은 1이 될 것입니다. 1 XOR 0, 1이 될 것입니다 1 XOR 1은 될 것입니다? 잘못? 아니면 오른쪽? 모르겠어요. 0. 지금 무슨 일이 일어나고 있는가? 잘 생각 이 연산자의 이름입니다. 배타적 OR, 그래서 이름, 종류, 제안 답은 될 것입니다 (1) 입력이 독점하는 경우, 독점적으로 다른. 그래서 여기에 입력은 동일하므로 출력은 0이다. 여기서 입력이 동일하므로 출력은 0이다. 여기서 출력들은 다르다 아르 배타적이고, 그래서 출력은 1이다. 그래서 매우 유사 AND, 그것은 매우 유사 또는 오히려 그것과 매우 유사 또는, 만 독점 방식으로. 이것은 더 이상 1 없다 우리가이 일의이 있기 때문에, 하지 독점적으로, 그 중 하나. 괜찮아. 어떤 사람들은 어떻습니까? 그럼 물결 한편,이다 실제로 좋은 간단한, 고맙게도. 그리고 이것은 단항입니다 의미 운영자, 또, 하나의 입력에인가있어 하나의 피연산자, 말하자면. 아니 왼쪽과 오른쪽으로. 즉,의 물결을 경우 0, 대답은 반대 할 것이다. 그리고 당신은 하나의 물결이 걸릴 경우, 대답은 반대가있을 것입니다. 그래서 물결 운영자입니다 비트를 부정하는 방법, 또는에서 비트를 뒤집기 0-1, 또는 1-0. 

그리고 마침내 우리를 잎 두 최종 사업자와, 은 왼쪽 Shift 소위, 그리고 오른쪽 시프트 연산자 소위. 의 어떻게 그 일을 살펴 보자. 서면 왼쪽 시프트 연산자, 그런 두 각도 브래킷, 다음과 같이 작동합니다. 만약 왼쪽으로 내 입력, 또는 내 피연산자, 시프트 연산자는 아주 간단하게 1입니다. 그리고 난 다음 컴퓨터를 말해 1, 일곱 곳이 말하는 것을 변화를 왼쪽, 결과는 내가 것처럼입니다 그 일을하고 이동 에 걸쳐 일곱 곳 왼쪽, 그리고 기본적으로, 우리는 가정거야 우측 공간 0으로 채워 될 것입니다. 즉, 1 시프트 7 가고 왼쪽 이어서, 1 말해 수득하여 1, 2, 3, 4, 5, 6, 7 제로. 방법 그래서, 그것은을 수행 할 수 있습니다 1과 같은 소수를 타고 명확하게 많이 만들 이 방식으로 훨씬 더 큰, 더, 그러나 우리가 실제로 보게 될 것입니다 그것은 더 영리한 방법 대신에,뿐만 아니라, 

괜찮아. 즉 주일을 위해 그것을이다. 우리는 당신이 다음 번에 ​​볼 수 있습니다. 이 CS50했다. 

[음악 재생] 

스피커 1 : 그는 간식에 있었다 핫 초콜릿 아이스크림을 먹는 바. 그는 자신의 얼굴에 모든 것을 가지고 있었다. 그는 수염처럼 그 초콜릿을 입고 스피커 2 : 뭐하시는 거예요? 스피커 3 : 흠? 뭐? 

스피커 2 : 당신은 그냥 더블 딥습니까? 당신은 더블 칩을 감소했다. 스피커 3 : 실례합니다. 스피커 2 : 당신은 칩을 담근 물린했다, 당신은 다시 감소했다. 스피커 3 : 스피커 2 : 그 퍼팅처럼 그래서 딥의 전체 입 오른쪽. 다음 시간 당신은 칩을 그냥 한 번 찍어, 그것을 끝낸다. 

스피커 3 : 당신은, 댄 무엇을 알아? 당신은 당신이 찍어 원하는대로 찍어. 내가 찍어 원하는 방식으로 찍어 것이다.