1 00:00:00,000 --> 00:00:02,280 [Powered by Google Translate] [주 3 계속] 2 00:00:02,280 --> 00:00:04,110 >> [데이비드 J. Malan - 하버드 대학교 (Harvard University)] 3 00:00:04,110 --> 00:00:07,130 >> [이 CS50입니다. - CS50.TV] 4 00:00:07,130 --> 00:00:11,010 >> 괜찮아요. 다시 오신 것을 환영합니다. 이 CS50이며,이 주 (3)의 끝입니다. 5 00:00:11,010 --> 00:00:14,680 >> 그럼 그 익숙 지난 년 동안 하버드는 혁신 연구소라는 것을 시작 6 00:00:14,680 --> 00:00:18,530 HBS의 캠퍼스에서 강을 건너 훌륭한 건물에 자리 잡고 있습니다 또는 I-연구실, 7 00:00:18,530 --> 00:00:22,640 그 대학 학생, GSAS 학생, 모든 전체 캠퍼스의 학생들에 열려 8 00:00:22,640 --> 00:00:27,000 교수를 포함하고 혁신적인 일에 일을 함께 할 수있는 장소, 9 00:00:27,000 --> 00:00:29,180 특히 기업가 일 10 00:00:29,180 --> 00:00:33,410 당신과 0 또는 더 많은 친구들이 기업가 뭔가를하고 생각하는 경우 11 00:00:33,410 --> 00:00:37,080 이 클래스 중,이 클래스 후, 또는 초과 중. 12 00:00:37,080 --> 00:00:41,540 >> 그래서이 J 기간 동안 할 일 중 하나는,이 여행이다 13 00:00:41,540 --> 00:00:44,510 뉴욕, 실리콘 밸리 인 중 하나입니다 중 하나입니다. 14 00:00:44,510 --> 00:00:47,530 공간은 매우 한정되어 있지만 MBAs과 어깨에 문지르 할 수있는 기회 15 00:00:47,530 --> 00:00:52,200 및 캠퍼스에서 실제로 대학원 학생들은 그 각각의 분야에서 시간을 보내 16 00:00:52,200 --> 00:00:55,500 , 신생를 채팅 기업가를 채팅하고 좋아요. 17 00:00:55,500 --> 00:00:57,870 관심이 있다면,이 URL을 여기에 확인하시기 바랍니다. 18 00:00:57,870 --> 00:01:01,220 또한 온라인 슬라이드에서 사용할 수 있습니다. 19 00:01:01,220 --> 00:01:04,610 >> 우리는 톤 다운 하우스 오디오를 조금이라도 할 수 없나요? 20 00:01:04,610 --> 00:01:08,640 이 금요일 점심 시간에 우리와 함께하려는 경우, 화재 및 아이스의 1시 15분 오후은 거기로 향할하시기 바랍니다. 21 00:01:08,640 --> 00:01:11,390 경우 죄송는 양식은 이미 자네가 도착할 때 쯤엔 가득 차 있습니다. 22 00:01:11,390 --> 00:01:13,750 그러나 우리는이 전통 이후를 계속합니다. 23 00:01:13,750 --> 00:01:17,350 >> 오늘 우리는, 우리가 해결할 수있는 다양한 문제의 높은 수준의 토론을 계속 24 00:01:17,350 --> 00:01:21,330 적어도, 코드와 더 많은 아이디어 오늘날 훨씬 더 초점. 25 00:01:21,330 --> 00:01:24,720 그래서, 우리는 반으로 전화 번호부를 찢고 때 다시 주 0 생각 26 00:01:24,720 --> 00:01:28,260 의 목적은 뭔가를 보면 조금 극적인했다 27 00:01:28,260 --> 00:01:32,360 하지만 검색은 반드시 할 필요는 없습니다하는 지점을 보내려면 28 00:01:32,360 --> 00:01:35,100 당신이 생각 하듯이 첫 눈에 같은 명백한. 29 00:01:35,100 --> 00:01:40,200 일반적으로 문제 해결이 반드시 최선의되지 않을 수 있습니다 - 30 00:01:40,200 --> 00:01:44,130 가장 눈에 띄는 솔루션은 반드시 가장 좋은 건 수 있습니다. 31 00:01:44,130 --> 00:01:47,300 그래서 우리는,이 방에있는 우리 모두가 직감을 가지고, 솔직히,이 전화 번호부를 가지고 32 00:01:47,300 --> 00:01:51,470 대부분 다음, 마이크 스미스를 찾을 때 중간에 시작하고하는 것은 왼쪽이나 오른쪽으로 이동 33 00:01:51,470 --> 00:01:54,280 우리가에 종료 일어난 알파벳의 어떤 문자를 기반으로. 34 00:01:54,280 --> 00:01:57,560 >> 그러나 우리 인간을 위해 촬영 한 간단 아이디어는 오랫동안 부여 35 00:01:57,560 --> 00:02:00,670 정말 마음의 최전선에 와서 시작해야합니다 36 00:02:00,670 --> 00:02:03,900 문제가 훨씬 더 복잡 전화 번호부보다 질수록 때문에, 37 00:02:03,900 --> 00:02:07,420 그 같은 간단 화려한 통찰력은 우리에게 허용하는거야 뭐야 38 00:02:07,420 --> 00:02:10,259 훨씬 더 복잡하고 더 재미있는 문제를 해결하려면, 39 00:02:10,259 --> 00:02:12,930 요즘 이미 승인을 위해 중 몇 가지 우리가 걸릴. 40 00:02:12,930 --> 00:02:15,720 아직 웹 저기 페이지, 구글과 빙과 같은 수십억 41 00:02:15,720 --> 00:02:17,660 그런 식으로 우리 것을 발견 할 수 있습니다. 42 00:02:17,660 --> 00:02:22,300 그래서 가능한 모든 웹 페이지를 검색, 선형 검색을 사용하여 안될 겁니다. 43 00:02:22,300 --> 00:02:25,290 페이스 북은 친구의 친구의 친구이거나 누군지는 말해 줄 수 있습니다 44 00:02:25,290 --> 00:02:28,250 그 역시 요즘 순식간에 겉으로 수행 할 수 있습니다 45 00:02:28,250 --> 00:02:30,820 그들은 사용자의 수백만이 있어도. 46 00:02:30,820 --> 00:02:34,250 >> 그리고 우리가 실제로 규모 문제를 해결하는 방법 궁극적으로 줄일 수 있습니다 47 00:02:34,250 --> 00:02:37,830 아이디어를 오늘 조금 더 주 0을 검토. 48 00:02:37,830 --> 00:02:42,320 우리는이 알고리즘을 다시 실행하지만, 기억하지 않습니다 우리는 주 0이 운동을 할에 한 49 00:02:42,320 --> 00:02:44,780 우리 모두가 서 한 곳, 숫자 1에서 수행 50 00:02:44,780 --> 00:02:48,720 그리고 우리는 함께 숫자를 추가 해제 페어링하여 모든 자기 수를 가지고 51 00:02:48,720 --> 00:02:51,930 다음 갱의 절반은 모든 반복에 앉았다. 52 00:02:51,930 --> 00:02:56,750 그래서 우리는 500 학생들 250-125에 가서 등등. 53 00:02:56,750 --> 00:03:00,080 거기에 우리가 월요일에 말한대로, 강력한 아이디어 54 00:03:00,080 --> 00:03:02,460 이었다 우리는 그 문제의 크기를 두 배로하는 경우 55 00:03:02,460 --> 00:03:06,480 와 정의 또는 EC 10 일부터 모든 아이들은 방으로 돌아 와서 우리에 합류 56 00:03:06,480 --> 00:03:09,510 그래, 우리가 아마 그 전체 집계 그룹을 계산 할 수 57 00:03:09,510 --> 00:03:13,380 루프의 단 1의 큰 반복과 사람들은 아마도 크기를 두 배로 때문에 58 00:03:13,380 --> 00:03:15,630 또는 더블 사이즈보다 조금 더 EC 10의 경우 인치 59 00:03:15,630 --> 00:03:18,440 그래서 우리는, 조금 더 시간을 투자해야 60 00:03:18,440 --> 00:03:22,000 하지만 우리는 400 또는 700 이상의 단계를 지출 할 필요가 없습니다 것입니다. 61 00:03:22,000 --> 00:03:26,550 >> 그냥 좀 덜 추상적이지 방식으로이 그림을 그릴 위해 모두들이 서있다하지 맙시다. 62 00:03:26,550 --> 00:03:31,100 하지만 오늘은 오케스트라에 앉아하도록 선택한 분들이 괜찮 으면, 잘 서 63 00:03:31,100 --> 00:03:34,580 우리가 가장 높은 사람이 어떤 사람인지 사이 알아낼 수 있다면합시다 볼 64 00:03:34,580 --> 00:03:36,730 비교 알고리즘의 이와 같은 일을하여. 65 00:03:36,730 --> 00:03:41,830 당신은 오케스트라, 사과 있지만, 1 단계에서 앉아다면, 일어나, 66 00:03:41,830 --> 00:03:44,650 2 단계 인근 사람과 오프 쌍, 67 00:03:44,650 --> 00:03:49,360 키가 누군지 알아내는, 그리고 짧은 경우 앉아. 68 00:03:49,360 --> 00:03:51,360 그런 다음 반복합니다. 69 00:03:51,360 --> 00:03:56,280 [학생들이 웅성 대는 소리] 70 00:04:13,450 --> 00:04:15,320 >> 좋아요. 71 00:04:15,320 --> 00:04:19,010 좋아요. 하나는 서 남아 있습니다. 이름이 무엇입니까? >> 앤드류. 72 00:04:19,010 --> 00:04:21,959 >> 앤드류, 당신은 오케스트라 섹션에서 가장 높은 사람 오늘입니다. 73 00:04:21,959 --> 00:04:28,100 >> 축하합니다. [박수와 환호] 좋아요. 자리에 앉으 시죠. 그래서 우리는 앤드류를 찾았습니다. 74 00:04:28,100 --> 00:04:30,870 그러나 얼마나 저를 촬영했을 예를 들어, 앤드류를 찾을 수 75 00:04:30,870 --> 00:04:33,740 50 + 정도의 사람들이 오케스트라 섹션에? 76 00:04:33,740 --> 00:04:36,900 나는 매우 간단한 접근 방식을 촬영하고 여기서 시작했을 수 있습니다. 77 00:04:36,900 --> 00:04:39,270 그리고 난 2 사람이 일어 서서하고 난을 비​​교 78 00:04:39,270 --> 00:04:42,120 그리고 제가 약간 짧은 사람에게 말, "그래, 당신이, 앉아" 79 00:04:42,120 --> 00:04:44,380 그리고 내가 키가 사람이 누군지 기억거야. 80 00:04:44,380 --> 00:04:49,030 그럼 난 반복 반복 반복, 그리고 가장 높은 사람에게 기다려 81 00:04:49,030 --> 00:04:51,920 나는 어떤 시점에서, 그들보다 사람이 약간 키를 찾을 때까지 82 00:04:51,920 --> 00:04:54,950 약간 짧은 사람이 그러면 앉아있다. 83 00:04:54,950 --> 00:04:57,690 그러나이 오케스트라 섹션에서 해당 알고리즘에 경우의 N이 84 00:04:57,690 --> 00:05:00,480 데려 갈 그 알고리즘은 얼마나 많은 단계입니까? >> [학생] N. 85 00:05:00,480 --> 00:05:03,580 >> 그것은 최악의 경우에, 말하자면 때문에, 오른쪽, n을 걸릴 거예요 86 00:05:03,580 --> 00:05:09,090 가장 높은 사람은 그냥 무작위로 운로 갈 바로 그 마지막 사람입니다. 87 00:05:09,090 --> 00:05:14,260 따라서 최악의 경우에, 그 알고리즘의 실행 시간은 선형이며, 그것은 N입니다 88 00:05:14,260 --> 00:05:18,070 n은 공간에서 사람들의 총 수, 문제의 크기입니다. 89 00:05:18,070 --> 00:05:19,600 이 알고리즘은 어때? 90 00:05:19,600 --> 00:05:22,080 당신은 모두 당신을 다시 이분의 일 후 일어나서는 사실이 앉아서 91 00:05:22,080 --> 00:05:23,950 당신의 절반 앉아, 당신의 절반이 앉았다. 92 00:05:23,950 --> 00:05:26,070 당신의 n은 여기이 있다면 그 몇 단계 데리고해야하나요? 93 00:05:26,070 --> 00:05:30,200 [학생] N 로그 N. 악화 될 것입니다 >>. n을 기록합니다. 94 00:05:30,200 --> 00:05:32,930 >> 그래서 꽤 로그가 무엇인지 기억하지 않더라도, 로그 N 95 00:05:32,930 --> 00:05:38,410 지금, 그냥이 이등분하고 반턱과 반턱 든 관련 감사드립니다. 96 00:05:38,410 --> 00:05:41,000 이 2 요소 필요가 없습니다. 이 3 요소 수 있습니다. 97 00:05:41,000 --> 00:05:46,560 그러나 문제의 크기는 여기에 시작되는 등 요소의 같은 종류의 반복입니다 98 00:05:46,560 --> 00:05:49,620 하지만 바로 다음 여기, 여기, 그러면 여기에, 간다. 99 00:05:49,620 --> 00:05:53,580 당신은 문제가 작은 물기를 데려 갈 수 없어, 당신은 진짜에 떨어져 구조 중이다 100 00:05:53,580 --> 00:05:56,160 큰 폭발음과 함께 할 때마다 떨어졌다. 101 00:05:56,160 --> 00:06:00,810 그래서 우리는, 12 ½ 또는 13 사람들이 서 그 다음에 25, 50 명의했다 102 00:06:00,810 --> 00:06:05,370 그리고 마지막으로 단지 앤드류가 남은 지위까지 등등 6 ½합니다. 103 00:06:05,370 --> 00:06:08,710 그래서 우리는 N의 로그에 전화를하고, 당신이 다음과 같이 시각화 할 수 있습니다. 104 00:06:08,710 --> 00:06:12,570 선형 알고리즘이 빨간색 선처럼이고, 여기에서이 사진을 기억 105 00:06:12,570 --> 00:06:17,520 노란색 선은 우리가 계산 학생들을 위해 사용했던 거 고요 알고리즘에 의해 계산했다 106 00:06:17,520 --> 00:06:22,300 과거에, 오늘은 성배가이 녹색 선 남아 것입니다 107 00:06:22,300 --> 00:06:25,470 우리가 오케스트라 섹션에있는 사람의 수를 두 배로 있거나 말 곳 108 00:06:25,470 --> 00:06:29,170 이런, 그렇게 큰 거래, 일어나가 전체 방에있는 모든 사람이하지 말자 109 00:06:29,170 --> 00:06:31,560 우리는 대략 여기까지 얼마나 많은 사람들이 두 번, 때문에 110 00:06:31,560 --> 00:06:33,500 1 개 반복이 아닌 문제가 발생했습니다. 111 00:06:33,500 --> 00:06:36,200 >> 우리는 앤드류 또는 사람 앤드류보다 클에서 일어나는 발견 한 112 00:06:36,200 --> 00:06:38,770 중간층 또는 발코니 인치 113 00:06:38,770 --> 00:06:42,140 전화 번호부에서 부여를 위해 우리가 많이 가지고 있다는이 간단한 아이디어 자, 114 00:06:42,140 --> 00:06:46,170 우리가 적용 할 수있는 많은 다른 장소가 있다는 것을 알고 있습니다. 115 00:06:46,170 --> 00:06:50,810 먼저, 사실이 아닌 전문 용어 - 그냥 전문 용어 폭력이나 휘두르는 116 00:06:50,810 --> 00:06:52,750 내가이 사진에 여기 가자. 117 00:06:52,750 --> 00:06:56,970 지금 우리는 N과 N / 2에 대해 얘기하고 다음에 n의 로그 118 00:06:56,970 --> 00:07:00,500 우리가 학기 과정을 통해 의지로 우리는 분명, 가지고 올 수 119 00:07:00,500 --> 00:07:05,130 수학 공식의 다른 종류의 시간을 실행이 일반적인 개념을 설명합니다. 120 00:07:05,130 --> 00:07:07,580 오래 전에 우리가 볼 수 있기 때문에 지금에 대한 컨텍스트를 벗어 121 00:07:07,580 --> 00:07:09,900 이 실제로 대표하는 알고리즘. 122 00:07:09,900 --> 00:07:17,990 >> 하지만 여기주의 선형 N 라인, 직선, 지금 지적 실제로 매우 낮은 것입니다. 123 00:07:17,990 --> 00:07:22,950 우리가 그냥 X 축가 무엇을 나타내는 지 변경에 착시의 일종 이죠 124 00:07:22,950 --> 00:07:26,130 과 Y 축, 그리고 우리가 원하는 방향으로 직선 지점을 만들 수 있습니다. 125 00:07:26,130 --> 00:07:30,350 하지만 지금은 그렇게 보이는 평평 이유 126 00:07:30,350 --> 00:07:35,690 우리가 많이 느린 실행 시간이 그래프에 공간을 확보하기 위해 필요하기 때문입니다. 127 00:07:35,690 --> 00:07:39,030 지금, 인생에서 꽤 많이 알고리즘이 있다는 것을 알고 128 00:07:39,030 --> 00:07:43,790 N 단계 만 더 로그인 아직 더 나은, N 조치를 취하거나하지 않는 중. 129 00:07:43,790 --> 00:07:48,820 따라서 선 위의 N 여기에서 하단 통지에 n의 n 번 로그,이 130 00:07:48,820 --> 00:07:51,410 우리는이 현상이 오래 전부터 무슨 뜻인지 볼 수 있습니다. 131 00:07:51,410 --> 00:07:56,010 그 위의 제곱 습니하고 있으며, 우리는 아직 N 제곱 알고리즘을 보지 못하지만 우리는 간다. 132 00:07:56,010 --> 00:07:57,660 그리고 정말 나쁜 보입니다. 133 00:07:57,660 --> 00:08:01,610 2 더 나쁜 느낌 지수 무언가, N주고있어. 134 00:08:01,610 --> 00:08:05,760 아직, 호기심, 다음 앞서 생각의 일종 경우 N cubed는,이 135 00:08:05,760 --> 00:08:10,000 어떤 종류의 N에 수학, 2한다면 실제로 많은 똑바로됩니다 136 00:08:10,000 --> 00:08:15,930 당신은 지금까지 충분히 축에서 보면 N보다 더 많은 이상은 cubed. 137 00:08:15,930 --> 00:08:19,890 따라서 이러한 축 임의로 X 축에 2~10아르 지금 확인합니다. 138 00:08:19,890 --> 00:08:21,770 >> 그리고 그게 무슨 뜻 이죠? 139 00:08:21,770 --> 00:08:23,890 그 방에서 2 명까지 10 명의 사람을 의미합니다. 140 00:08:23,890 --> 00:08:27,200 문제의 크기, 문맥이 무엇이든 : 그 모든 X 수단입니다. 141 00:08:27,200 --> 00:08:30,420 그리고 수직 축 지금 초 단계의 수의 개수입니다 - 142 00:08:30,420 --> 00:08:31,840 시간의 일부 단위입니다. 143 00:08:31,840 --> 00:08:34,740 그러나가 0 60 0-10 있다는 것을. 144 00:08:34,740 --> 00:08:38,549 그러나 만약 당신이 Excel 또는 일부 차트 소프트웨어의 수도로, 축소의 우리 종류 145 00:08:38,549 --> 00:08:43,370 우리는주의, 200,000에 올라가 그 2와 같은 N에 뭔가 146 00:08:43,370 --> 00:08:47,520 완전히 제곱 n의 실행 시간을 압도 것입니다, 147 00:08:47,520 --> 00:08:50,960 n은 cubed, N 로그 N - 우리가 지금까지 이야기했던 모든 것. 148 00:08:50,960 --> 00:08:54,190 당신은 페이스 북과 같은 것들에 대해 얘기 시작할 때 그리고 아직 캐치입니다 149 00:08:54,190 --> 00:08:57,150 당신은 많은, 많은 사람들은 모든 상호 연결 한 곳, 150 00:08:57,150 --> 00:09:00,650 당신이 사람들을 향한 한 각 누구의은 N의 친구로 많은이있을 수 151 00:09:00,650 --> 00:09:02,860 모든 사람이 세계에서 친구 - 친구의 일종이며, 경우 152 00:09:02,860 --> 00:09:08,100 글쎄, 그 n 번입니다 N 이미 있으므로 제곱 가능한 우정을 보군 그 153 00:09:08,100 --> 00:09:10,950 최소 1 방향, N 제곱 가능 우정 인치 154 00:09:10,950 --> 00:09:15,330 그래서 이미 말하자면, 페이스 북의 소셜 그래프를 검색하는 것이 좋습니다, 155 00:09:15,330 --> 00:09:18,090 수식의 이러한 종류의 표현 할 수 있습니다. 156 00:09:18,090 --> 00:09:19,820 >> 우리는 다시 와서이 훨씬 더 구체적인 할게요 157 00:09:19,820 --> 00:09:23,280 다음 몇 주 동안 지금 들어, 목표 158 00:09:23,280 --> 00:09:27,170 구현 알고리즘이나 코드에 대해 이동하지 않도록 될 것입니다 159 00:09:27,170 --> 00:09:29,870 그 같이만큼 시간을 내 주셔서 결국. 160 00:09:29,870 --> 00:09:33,110 그러나 컴퓨터 과학에 대한 흥미 점은이 분야에서의 지속되는 경우 161 00:09:33,110 --> 00:09:38,320 , CS121, CS124과 같은 수업을 이론 과정 아르 둘 다 복용​​, 162 00:09:38,320 --> 00:09:41,300 이 세상에서 존재하는 문제가 실​​제로 있다는 것입니다 163 00:09:41,300 --> 00:09:45,710 근본적으로, 우리가 아는 한, 빨리 해결 할 수없는 164 00:09:45,710 --> 00:09:48,880 이 그래프의 최악 실제로 제안보다. 165 00:09:48,880 --> 00:09:53,660 따라서 인간은 지금까지이보다 더 할 수있는이 세상에서 열려 많은 문제가 있습니다. 166 00:09:53,660 --> 00:09:56,130 >> 그래서 예를 누른 다음 시작하자. 167 00:09:56,130 --> 00:09:59,650 우리는 너무 어색 비디오에서이에 카메라 숀 투쟁을 보았다. 168 00:09:59,650 --> 00:10:05,270 션이 7 번과 같은 보드에 찾는가 주어 때하지만 현실은,이었다 169 00:10:05,270 --> 00:10:10,300 나는 "이러한 종이 조각 또는 흰색 문 뒤에 어딘가에있다, 그런 말 한걸 기억 170 00:10:10,300 --> 00:10:12,570 "숫자 7. 션, 우리가 찾아." 171 00:10:12,570 --> 00:10:14,200 그리고 감상 할 이상하게 거북 하군요 172 00:10:14,200 --> 00:10:15,790 그는 정말이 문제를 고민했기 때문. 173 00:10:15,790 --> 00:10:19,720 하지만 현실은 션이 방에있는 사람이 수행 할 수 있습니다뿐만 아니라 한이었다. 174 00:10:19,720 --> 00:10:21,890 그는이있을 좀 더 일반적인 사람보다했습니다 175 00:10:21,890 --> 00:10:24,760 그러나 그는 어떤 트릭이 문제가 있었다고 생각 176 00:10:24,760 --> 00:10:26,590 그는 뭔가를 누락라고 생각 했었습니다. 177 00:10:26,590 --> 00:10:29,320 그리고 눈의 수백이 그를 향하고 있다고 도움이되지 않았다. 178 00:10:29,320 --> 00:10:34,250 >> 문제에 대한 입력이 임의의 숫자의 무리 경우하지만 현실은했습니다 179 00:10:34,250 --> 00:10:37,120 하면, 1 등 번호를 알아 보라고 받고 있어요 180 00:10:37,120 --> 00:10:39,770 당신이 할 수있는 최선의 방법은 선형 검색입니다. 181 00:10:39,770 --> 00:10:44,060 왼쪽에 시작, 오른쪽으로 이동하거나 왼쪽으로 이동, 오른쪽부터 시작합니다. 182 00:10:44,060 --> 00:10:48,300 소급하여, 우리가 생각 될 수 있습니다, "숀, 왜 당신은 다른 쪽 끝에서 시작하지 못 했을까?" 183 00:10:48,300 --> 00:10:52,120 음, 7 단지 쉽게, 무작위로 여기 온 수 184 00:10:52,120 --> 00:10:54,980 난 그가 말에 시작하지 않을거야 생각하기 때문에 나는 의도적으로 거기에 넣어. 185 00:10:54,980 --> 00:10:59,320 그래서 가지 상황을 조작하지만, 임의의 기회 (7)에 의해 어느 해놨을 수도있다. 186 00:10:59,320 --> 00:11:02,380 그럼, 오른쪽 끝에서 시작하여 다음 좋겠지 만 187 00:11:02,380 --> 00:11:04,320 하지만 만약 내가 다른 곳에서 7로 이동 다음 해? 188 00:11:04,320 --> 00:11:06,830 그게 문제에 대한 근본적으로 새로운 솔루션이 아니에요 - 189 00:11:06,830 --> 00:11:10,520 한 끝 또는 다른에서 시작 - 당신이 다른 가정을 제공하지 때. 190 00:11:10,520 --> 00:11:13,620 그럼 숀이 숫자를 통해보고 시작, 그는 "5. 그건 여기 없어요." 191 00:11:13,620 --> 00:11:17,280 그럼 그 사람은 여기 가서 19 본, 그는 약 20 초 동안 일시 중지 192 00:11:17,280 --> 00:11:22,330 그 다음에 그는 13이을 열어 다음은 뻔 했지요 193 00:11:22,330 --> 00:11:24,270 여기에 패턴이있을 것하지 않습니다. 194 00:11:24,270 --> 00:11:28,090 이 1, 2, 3, 4 또는 같은 아니 었습니다. 도움이되지 않은 숫자 격차가 발생했습니다. 195 00:11:28,090 --> 00:11:32,320 그리고 나도 종이의 이러한 저렴한 조각을 사용한 사실은 숫자를 덮기 위해서 196 00:11:32,320 --> 00:11:35,270 때문에 종이의 모든 조각을 제거한 경우, 실제로 의도적으로입니다 197 00:11:35,270 --> 00:11:38,760 우리 대부분은, 숀 포함, 아마 종류 macroscopically의 훑어 것이다 198 00:11:38,760 --> 00:11:43,410 칠판에 그리고 "오, 7 거기 분명히"고 말했다. 우리는 즉시 했어요. 199 00:11:43,410 --> 00:11:46,460 >> 그래서, 인간의 뇌는 어느 정도 작동하는 방식 일 수도 200 00:11:46,460 --> 00:11:50,730 하지만 현실에서, 그의 눈 또는 마음이, 오른쪽에서 왼쪽으로 가며 번호를 아마도 201 00:11:50,730 --> 00:11:55,190 밖으로 오른쪽, 중간 왼쪽 - 무슨 일이 생리 학적으로 일이 있었던거야 202 00:11:55,190 --> 00:11:57,640 그 즉시 일어나는 것처럼이 느껴지도록 203 00:11:57,640 --> 00:12:01,360 하지만 아이가 내부적으로 7 찾는 방법 어떤 종류의가 있다고도합니다. 204 00:12:01,360 --> 00:12:05,160 그리고 실제로 지금 우리는 배열과 데이터 구조에 대해 얘기하는 205 00:12:05,160 --> 00:12:08,780 그리고 컴퓨터의 메모리 내부의, 우리 인간이 유일한 것은 할 수 206 00:12:08,780 --> 00:12:13,070 한 번에 개별 메모리 위치에 1을 볼 수 있습니다. 207 00:12:13,070 --> 00:12:16,600 >> 따라서 다른 모든 위치뿐만 아니라 종이의 일부 조각을 은폐 될 수 있습니다 208 00:12:16,600 --> 00:12:21,170 우리는 어쨌든 그것을 볼 수 없습니다 때문입니다. 우리는 한 번에 한 가지 작업을 수행 할 수 있습니다. 209 00:12:21,170 --> 00:12:25,030 따라서이 경우에는, 션의 경우, 우리는 여기에 가서 다음에 우리가 여기 갔다 210 00:12:25,030 --> 00:12:31,040 그리고 우리가 간, 여기, 여기, 여기, 마지막으로 영리한있어 211 00:12:31,040 --> 00:12:34,450 불과의 종류 임의로이 하나를 건너 뛰고도 7 발견했다. 212 00:12:34,450 --> 00:12:37,470 이 사람은 특히 특별 아니 었습니다. 이거 너무 고장이었다. 213 00:12:37,470 --> 00:12:39,530 그러나 그는 결국 7 발견했다. 214 00:12:39,530 --> 00:12:45,360 그러나 지금은 테이크 아웃 정말 당신이 할 수있는 최선의 어떠한 정보를 제공 없을 때이다 215 00:12:45,360 --> 00:12:50,400 무작위로 정렬 된 숫자 이외는 왼쪽에서 시작하거나 오른쪽에서 시작하는 것입니다. 216 00:12:50,400 --> 00:12:54,950 또는 대체, 당신은 무작위로 문을 열 수 있습니다,하지만 다음에 어떻게가 무작위로 의미합니까? 217 00:12:54,950 --> 00:12:57,220 음, 우리가 어찌 여기 시작하는 데 의미를 공식화해야 할 218 00:12:57,220 --> 00:13:01,150 그리고 여기에서, 여기에 이​​동합니다. 숀 아주 잘 했어, 그리고 볼 그냥 재미로했다. 219 00:13:01,150 --> 00:13:06,340 우리는 문제에게 조금 변경하고, 당신이 가만히 있으면 올해의 숀을 표시 무엇입니까 대신한다면? 220 00:13:06,340 --> 00:13:09,460 사람이 무대에 와서 약간 다른 문제를 해결 편 221 00:13:09,460 --> 00:13:12,330 카메라에 게재? 222 00:13:12,330 --> 00:13:15,720 >> 당신들이 매우 이미 오늘 관여했기 때문에가 오케스트라 넘어 가자. 223 00:13:15,720 --> 00:13:21,430 방법에 대한 분홍색에 모자? 이리 오게. 당신의 이름은 무엇입니까? >> 알렉스. >> 알렉스. 좋아요. 224 00:13:21,430 --> 00:13:24,580 그래서 알렉스는 올해 숀되며 향후 몇 년간에 나타납니다 225 00:13:24,580 --> 00:13:27,770 CS50 강의의 가치. 226 00:13:27,770 --> 00:13:30,340 알렉스, 반가워요. >> 저도 반가워요. 227 00:13:30,340 --> 00:13:33,470 당신 손에있는 문제는 당신이 좀 더 쉽게되어 있다는 것입니다 228 00:13:33,470 --> 00:13:38,950 거기에 내가 여기 당신에게 같은 번호를 아르 말하는데,하지만 지금은 정렬됩니다. 229 00:13:38,950 --> 00:13:41,800 이제 당신의 목표는 숫자 7을 찾는 것입니다. 230 00:13:41,800 --> 00:13:45,370 그리고 실제로 우리가이 일을해야 - 부정 행위의 넌 종류를 컴퓨터 하시겠습니까 아니라 231 00:13:45,370 --> 00:13:47,990 무엇을보고 숫자는 잠시 전에 있었다. 232 00:13:47,990 --> 00:13:50,360 분필로이 사실은 모두 많이 도와 줘야하지 233 00:13:50,360 --> 00:13:52,810 하지만 원래 배열이 뭔지 모르는가 가정합시다. 234 00:13:52,810 --> 00:13:56,600 지금 아는 한 당신은 정렬 숫자의 배열을 가지고 있다는 것입니다 235 00:13:56,600 --> 00:14:00,360 그 둘 사이 간격이있는 것, 그리고 목표는 7 번을 찾을 것입니다. 236 00:14:00,360 --> 00:14:05,080 어떻게,되는 합리적인 인간은 숫자 7을 찾는 것에 대해 갈거야? 237 00:14:05,080 --> 00:14:07,770 >> 낮은 가격순에서 이동? 좋아요 >>. 낮은 가격순 이동합니다. 238 00:14:07,770 --> 00:14:10,990 그리고 그것들을 찢어하지 않습니다. 우리가 그들을 재사용 할 수 있도록 그냥 올려 들어 보자. 239 00:14:10,990 --> 00:14:14,730 그래, 그럼 1. 기다립니다. 당신이 계속하기 전에, 그 분명 잘못 1이었다. 240 00:14:14,730 --> 00:14:17,270 그래서 우리가 옆에 무슨 생각을하고있어? 다음 계획은 무엇입니까? 241 00:14:17,270 --> 00:14:23,250 다음. 좋아요 >>. 다음. 좋아. 그래서 잘못된 3. 다음 계획은 무엇입니까? 242 00:14:23,250 --> 00:14:27,670 가보 거라. >> 좋아. 가보 거라. 5. 243 00:14:27,670 --> 00:14:31,110 그럼 계속하고 있으며, 내가 후대를 위해 당신에게를 건네 보자. 244 00:14:31,110 --> 00:14:35,720 7. >> 좋아요. 아주 좋아. 숫자 7을 찾았습니다. [박수] 245 00:14:35,720 --> 00:14:39,720 그럼 좋은했지만, 숀도 수 7 발견했다. 246 00:14:39,720 --> 00:14:44,490 그리고 당신이 정말 정보의 추가 조각을 이용하지 않은 주장 247 00:14:44,490 --> 00:14:47,780 이는 숫자가 정렬된다는 것입니다. 248 00:14:47,780 --> 00:14:51,520 그래서 우리가 더 잘할 수 있습니까? 여기 방법은? 네, 다시 인치 249 00:14:51,520 --> 00:14:54,710 [학생] 이진 검색 할 수 있습니다. >> 나는 이진 검색이 뭔지는 전혀 감이 없습니다. 250 00:14:54,710 --> 00:14:58,030 >> [학생]는 중간에 시작합니다. >>는 중간에 시작합니다. 좋아요. 그럼 우리가 할 수 있나 보자. 251 00:14:58,030 --> 00:15:02,580 당신이 중간에서 시작을시키는 대신다면, 가서 중간 문을 엽니 다. 252 00:15:02,580 --> 00:15:04,580 이 중 8 야하므로 임의로 하나를 선택해야 할 것 253 00:15:04,580 --> 00:15:09,800 약간 왼쪽이나 오른쪽으로. 좋아요. 7! [박수] 아주 좋네요. 254 00:15:09,800 --> 00:15:11,410 그래,하지만 우리는이와 함께 어디로 갈거야? 255 00:15:11,410 --> 00:15:14,990 우선은 여기 시작했습니다 넥타이를 부러 가정 256 00:15:14,990 --> 00:15:16,670 그 똑같이뿐만 아니라 일어날 수있는 일 때문입니다. 257 00:15:16,670 --> 00:15:19,540 우리는 7가 있다는 사실을 알게되어 일. 그래서 13입니다. 258 00:15:19,540 --> 00:15:21,980 들은 정렬 된 경우 그래서 우리는 그냥 중간에 시작 259 00:15:21,980 --> 00:15:24,600 최적의 다음 행동은 뭐야 갔었을거야? 260 00:15:24,600 --> 00:15:27,740 왼쪽 이동합니다. 그리고 여기에 다시 전화 번호부 예를 제공합니다. 261 00:15:27,740 --> 00:15:30,130 13 여기 우리는 목록이 정렬되어 알고있는 경우는, 262 00:15:30,130 --> 00:15:33,900 그리고 종이의 이러한 조각의 모든 이제 우리에게 흥미 아르 263 00:15:33,900 --> 00:15:37,400 우리는 이미 7 왼쪽에 있어야합니다 알고 있기 때문에 264 00:15:37,400 --> 00:15:39,510 이 번호는 정렬하고 13를 발견하는 경우. 265 00:15:39,510 --> 00:15:42,500 >> 그래서 여기 다음 계획은 뭐죠? >>는 왼쪽으로 이동합니다. >> 그래, 좋아. 266 00:15:42,500 --> 00:15:45,080 헤이, 헤이, 헤이, 잠깐만 요 - 그럼 왼쪽으로 이동합니다. 그건 반칙이야. 267 00:15:47,140 --> 00:15:51,350 그래서 7을 발견하지만, 우리가 적용된 알고리즘은 무엇입니까? 268 00:15:51,350 --> 00:15:56,450 중간에 시작합니다. >> 좋아. 그래서 같은 생각의 논리적 확장은? 269 00:15:56,450 --> 00:15:58,970 아, 그냥이에. 정확히 >>. >> 그래서 여기 시작합니다. >> 좋아. 270 00:15:58,970 --> 00:16:02,020 이제 우리는 다시 왼쪽으로 약간 갔다. 은 3입니다. 271 00:16:02,020 --> 00:16:05,310 그러나 흥미로운 테이크 아웃은 지금 당신이 신경이없는인가요? 272 00:16:05,310 --> 00:16:08,040 이 2. >>이 2. 이제이 사람이 멀리 갈 수, 이건 갈 수 있습니다. 273 00:16:08,040 --> 00:16:12,330 그럼 이제 8 살 문제는 크기 (4) 지금 크기가 2이었다. 274 00:16:12,330 --> 00:16:16,430 우리는 아주 가까이 접근하고 있습니다. 다시 말하지만,이 두 요소의 가운데로 이동합니다. 275 00:16:16,430 --> 00:16:20,430 >> 좋아요. 그럼 우리가 내려 라운딩이기 때문에 지금 우리가 항상 떠 가고 있다는 것을 종류의 불운입니다. 276 00:16:20,430 --> 00:16:25,150 지금 우리가 7 우릴 떠나, 거리에 있으며 다른 모든이를 포기하기 때문에하지만 그건 괜찮아요. 277 00:16:25,150 --> 00:16:30,490 가 박수를 쳐. 우리는 다시 7 발견했다. [박수] 좋아. 그래. 278 00:16:30,490 --> 00:16:32,220 단지 1 개 초 기다려. 279 00:16:32,220 --> 00:16:36,630 의 다음 프로세스 종류의 우리가 그러 생각보다 조금 더 걸렸습니다, 비록 280 00:16:36,630 --> 00:16:40,150 솔직히, 당신의 첫번째 본능은 바로, 최고였다? 우리는 즉시 7 발견했다. 281 00:16:40,150 --> 00:16:46,740 그러나 우리는 빠르고 이것 대에 상관없이이 예에서 무엇을 7를 발견하지 않았을 282 00:16:46,740 --> 00:16:50,100 번호가 모두 정렬하는 경우 때문에 많은 전화 번호부의 페이지처럼 283 00:16:50,100 --> 00:16:54,580 당신은 실제로 다시하고 다시하고 다시 문제의 절반을 버려야 할 수 있습니다. 284 00:16:54,580 --> 00:16:56,740 그리고 이건 그냥 8 자리 숫자로이를 볼 수 매우 쉬운 일이 아닙니다 285 00:16:56,740 --> 00:17:00,100 등 정말 시각적으로 볼 1000 페이지 전화 번호부에 반대, 286 00:17:00,100 --> 00:17:03,120 하지만 여기이 경우에는 숀, 7 검색 한 경우 287 00:17:03,120 --> 00:17:06,020 얼마나 많은 최악의 경우의 단계가 그를 데리고까요? >> [학생] 7. 288 00:17:06,020 --> 00:17:11,670 최악의 경우 7. 음, 최악의 경우하지 7 8 문이 여기있을 경우 인치 289 00:17:11,670 --> 00:17:13,440 그것은 그에게 8 단계를 취 것이다. 290 00:17:13,440 --> 00:17:18,170 >> 그래서의 N 문 경우, 몇 년 전에 N 단계를 션을 촬영했을 수 있습니다. 291 00:17:18,170 --> 00:17:21,520 자, 그렇다면,이 숫자가 정렬되는 알렉스, 주어진 - 292 00:17:21,520 --> 00:17:25,130 우리는 우리가이 이야기에서 지금까지했던 곳에서 추론이 종류의 수 - 293 00:17:25,130 --> 00:17:28,300 알렉스의 더 지능 알고리즘의 실행 시간이 뭐야 294 00:17:28,300 --> 00:17:30,770 중간부터 시작하고 반복? 295 00:17:30,770 --> 00:17:36,490 [학생] 3. >> 그래서 당신은 2 1로 8-4에서 이동하는 경우, 약 3거야. 296 00:17:36,490 --> 00:17:40,660 3 단계 그래서 나보다 일반적으로, 그 로그 N 다시입니다. 297 00:17:40,660 --> 00:17:43,380 당신은 이등분하고 반턱과 반턱과 반턱 할 때마다, 298 00:17:43,380 --> 00:17:45,290 그 로그 n의이 아이디어의 표현입니다. 299 00:17:45,290 --> 00:17:48,140 그리고 그렇게 단지 당신 3 단계를 취했습니다 것이며, 실제로는 한 300 00:17:48,140 --> 00:17:50,890 일단 우리는 문을 이등분하고 반턱 오픈 301 00:17:50,890 --> 00:17:53,770 이 숀에게 7-8 조치를 취 것이다 반면. 302 00:17:53,770 --> 00:17:56,330 그래서 우리와 함께 올해 주셔서 감사합니다. >> 감사합니다. 회의를 웠어요. 303 00:17:56,330 --> 00:18:00,170 알렉스에게 감사합니다. >> 저도 요. [박수] 304 00:18:00,170 --> 00:18:02,150 >> 어떻게 다음이의 실제 의미 야? 305 00:18:02,150 --> 00:18:06,050 지금은 솔직히, 우리 모두가 뭔가를 찾을 수있을, 8 문, 아닌 건 상상 306 00:18:06,050 --> 00:18:10,430 단지 종이 조각을 찢어 우리의 본능에 이동하여 너무 빨리 뒤로 8 문. 307 00:18:10,430 --> 00:18:14,430 그러나 만 문을 어떻게됩니까? 그런 일이 4,000,000,000 문 있다면 요? 308 00:18:14,430 --> 00:18:19,630 4000000000 문의 경우에, 당신은 정말로, 알렉스의 알고리즘에 가고 싶어 할거야 309 00:18:19,630 --> 00:18:23,150 우리가 전화를 시작하거나 더 일반적으로, 나눠서 맡을 것 같은 이진 검색, 310 00:18:23,150 --> 00:18:25,220 당신은이 문제를 이등분하고 반턱 보관, 311 00:18:25,220 --> 00:18:30,510 당신은 4,000,000,000 문이있는 경우, 몇 번이 반으로 40 억 자르다 수 있기 때문에? 312 00:18:30,510 --> 00:18:33,870 [학생] 32. >> 실제로 32입니다. 당신은 종이 또는 머리에이 운동을하실 수 있습니다. 313 00:18:33,870 --> 00:18:38,490 당신은 250 만 점, 점, 명확히 설명하는 데, 4 billion to 2000000000-1000000000 억으로 이동합니다. 314 00:18:38,490 --> 00:18:41,620 당신이 수학을하면, 당신은 실제로 32받을거야 315 00:18:41,620 --> 00:18:44,950 우리가 보통 2의 거듭 제곱으로 계산하기 때문에 그 사실은 컴퓨터 과학에 관한 것이다. 316 00:18:44,950 --> 00:18:47,600 2 32는 4000000000로 발생합니다. 317 00:18:47,600 --> 00:18:51,440 따라서 컴퓨터 과학 2의 거듭 제곱 이러한 종류의 관련성이 많이있어. 318 00:18:51,440 --> 00:18:55,120 >> 그런데 억 8? 8000000000 문이있을 경우 몇 단계 그건 걸릴까요? 319 00:18:55,120 --> 00:19:00,350 [학생] 33. 따라서 33 >>. 무엇 16000000000 문이 있다면? 얼마나 많은 단계 그건 걸릴까요? 320 00:19:00,350 --> 00:19:05,020 [학생] 34. >> 34. 우리는 가지이 광고 nauseam을 계속 수 있습니다. 하지만 강력한 것입니다. 321 00:19:05,020 --> 00:19:09,430 귀하의 문제에 더 많은 입력 수십억을 소개하지만, 아니 큰 일, 수 322 00:19:09,430 --> 00:19:14,140 당신은 단지 1 추가 한입 아웃을하기 때문에 우리에게 이진 검색과 같은 일을 할 수 있습니다 323 00:19:14,140 --> 00:19:15,920 이상 일반적으로, 나눠서 맡을. 324 00:19:15,920 --> 00:19:17,990 하지만, 여기서 바람을 피우고있는 것 같아요? 325 00:19:17,990 --> 00:19:22,410 알렉스의 알고리즘의 경우, 그녀는 숀 이상의 이득도 있었다. 326 00:19:22,410 --> 00:19:27,780 그녀는이 숫자가 정렬 된 것을 알고 있지만, 알렉스는 그들에게 자신을 정렬 할 필요가 없습니다 않았다. 327 00:19:27,780 --> 00:19:30,520 사전에 잘 만든의 칠판과 종류까지왔다 328 00:19:30,520 --> 00:19:33,670 전 정렬 순서로 모두를 그린 다음, 나는 종이를 덮었다. 329 00:19:33,670 --> 00:19:35,850 그러나 저를 얼마나 일을 가져 갔어? 330 00:19:35,850 --> 00:19:40,110 우리는 임의 순서로 숫자와 도망을 시작했다면 - 331 00:19:40,110 --> 00:19:43,320 이 경우에 이러한 간단한 숫자, 여기 8 1 - 332 00:19:43,320 --> 00:19:46,090 우리는 이러한 값을 정렬 어떻게해야할까요? 333 00:19:46,090 --> 00:19:52,530 이 임무를 맡은 사람이라면, 직관적 인 접근 방법 어떤 종류의 당신은 걸릴거야 334 00:19:52,530 --> 00:19:54,800 숫자를 왕창 정렬에? 335 00:19:54,800 --> 00:19:57,050 이러한 것들이 퍼즐 조각으로 배치되었다. 그래. 336 00:19:57,050 --> 00:19:59,950 >> [학생] 내가 각 번호를 가지고 각 비교 것 337 00:19:59,950 --> 00:20:03,180 왼쪽으로 계속. >> 그래, 좋아. 338 00:20:03,180 --> 00:20:05,720 그래서, 옆의 비교, 각 번호를 339 00:20:05,720 --> 00:20:09,610 그리고 당신이가는대​​로 물건을 rejiggering 목록, 친절을 따라 전진. 340 00:20:09,610 --> 00:20:13,800 그래서 여기에 우리가 참여 더 어쩌면 몇 사람들의 기회가 있습니다. 341 00:20:13,800 --> 00:20:16,290 우리는 와서 싶지만 8 더 많은 자원 봉사자가 있습니까? 342 00:20:16,290 --> 00:20:23,950 귀하 이후 약간 덜 압력이 있던 건 아니다. 1, 2, 3, 4, 5, 6, 7, 8. 343 00:20:23,950 --> 00:20:28,190 이리 오게. 너희들은 8을 통해 숫자 1이 될거야. 344 00:20:28,190 --> 00:20:36,050 만약 우리가 사전에 짓 같은 방법으로 많은 알렉스이 정렬 작업을 수행 할 수없는 경우 봅시다. 345 00:20:36,050 --> 00:20:37,640 1, 2, 3, 4. 346 00:20:37,640 --> 00:20:40,760 계속하고 싶다면, 여기에 음악 스탠드와 나 사이의 무대에 정렬 347 00:20:40,760 --> 00:20:44,960 화면의 슬라이드와 같은 순서를 유지해야합니다. 348 00:20:47,910 --> 00:20:49,680 어 - 어. 349 00:20:50,370 --> 00:20:53,230 우리는 다음 예 여러분을 도와 드리겠습니다. 아, 잠깐만, 잠깐만. 여기 우리는 간다. 기다립니다. 350 00:20:53,230 --> 00:20:57,570 다음 예제는 지금입니다. 여기. 번호 8. 어서 올라 와요. 351 00:20:57,570 --> 00:21:00,270 괜찮아요. 정렬이에 따라 붙들어. 352 00:21:00,270 --> 00:21:03,620 음악의 측면에 조금 밀어은 여기 서 계세요. 353 00:21:03,620 --> 00:21:12,310 그래서 우리는 4, 2, 6을 가지고 - 거기, 여기에, 거기에 요 - 3. 354 00:21:12,310 --> 00:21:17,570 그래. 좋아요. 당신은 여기 이동합니다. 아니, 당신은 거기에있어. 355 00:21:17,570 --> 00:21:21,840 그래, 바로 거기. 아니 잘못입니다. 바로 거기. 좋아요, 아주 좋아요. 좋아요. 356 00:21:21,840 --> 00:21:24,930 그래서 지금의이 증가 순서로 정렬 보자. 357 00:21:24,930 --> 00:21:26,210 >> 어떻게 이런 짓을에 대해 갈 수 있을까요? 358 00:21:26,210 --> 00:21:28,630 좀 전에 제안 된 알고리즘은 왜 우리가 비교 그렇지 않아 359 00:21:28,630 --> 00:21:31,970 그런 다음 서로 옆에 가지이며, 사람들이 어떤 실수를 수정 360 00:21:31,970 --> 00:21:33,540 왼쪽에서 오른쪽으로 이동. 361 00:21:33,540 --> 00:21:36,580 그래서 여기에 우리가 분명히 아웃 ​​순서, 4, 2가 있습니다. 의 당신을 교환 보자. 좋아요. 362 00:21:36,580 --> 00:21:40,760 그래서 지금 내가 선을 아래로 이동거야. 4 번과 6 번, 아뇨. [웃음] 363 00:21:40,760 --> 00:21:45,010 6 8, 정말 좋은. 8 1, 나에게 사람들을 교환 보자. 괜찮아요. 364 00:21:45,010 --> 00:21:48,030 8 세 그래서, 당신들을 교환. 365 00:21:48,030 --> 00:21:52,280 8 7, 나에게 사람들을 교환 보자. 5 뛰어난 8. 366 00:21:52,280 --> 00:21:54,820 내가 정렬 목록을 제공합니다. 367 00:21:54,820 --> 00:21:56,860 괜찮아요. 그래서별로 요. 368 00:21:56,860 --> 00:22:01,180 하지만 더 좋아하기 때문에 더 큰 숫자 - 사례 지점 8 - 369 00:22:01,180 --> 00:22:04,030 가지의 오른쪽에있는 왼쪽에서 이상 떠오르 있습니다. 370 00:22:04,030 --> 00:22:08,010 그래서 바로 그 1도,하지만 그건 정말 문제가 해결되지 않아서 인 것 같아요. 371 00:22:08,010 --> 00:22:11,150 >> 당신은 우리가 다음에 어떻게 그럼 무엇을 제안까요? >> [학생] 그러는하세요. >> 우리가 일을 계속. 372 00:22:11,150 --> 00:22:13,740 그리고 다시 실현, 우리는 모든 인간을함으로써 일을 설정 373 00:22:13,740 --> 00:22:17,180 종류의 지능적 그 사진을 바탕으로 자신을 준비하는 것은 374 00:22:17,180 --> 00:22:19,040 지금 우리는 훨씬 더 체계적으로해야합니다. 375 00:22:19,040 --> 00:22:21,510 우리는 코드를 작성하는 것처럼에 대한 알고리즘 있어야 - 376 00:22:21,510 --> 00:22:23,520 이 경우 구두 의사 인치 377 00:22:23,520 --> 00:22:26,040 그럼 내가 그 다시 시도해 보자. 꽤 잘했습니다. 그것은를 해결할 수 없습니다. 378 00:22:26,040 --> 00:22:30,400 하지만 의심되면, 그냥 해하고 다시 시도하십시오. 그런데 2, 4, 더 이상 도움이되지 않았다. 379 00:22:30,400 --> 00:22:33,200 4 6. 아! 약간 더 나은 지금 6과 1. 380 00:22:33,200 --> 00:22:39,740 6 좋은 3. 6, 7, 7, 5, 7, 8, 좋아. 381 00:22:39,740 --> 00:22:44,060 그는 목록의 끝 부분에 있기 때문 그리고 당신이 알다시피, 난 아마 8 무시할 수 있습니다. 382 00:22:44,060 --> 00:22:47,250 우리가 누군가가 그의 옆을지나 갈 걱정을 할 필요가 없습니다. 383 00:22:47,250 --> 00:22:49,240 하지만 그게 안전한 가정 있는지 보자. 384 00:22:49,240 --> 00:22:52,340 지금 목록입니다 - 젠장 - 정렬 없습니다. 가 다시 해 보자. 385 00:22:52,340 --> 00:22:56,440 2 자, 4, 4, 1, 4, 3. 386 00:22:56,440 --> 00:22:59,230 4 번과 6 번, 좋아. 6 5, 좋아요. 387 00:22:59,230 --> 00:23:04,890 6, 7, 8, 좋아. 그러나 통지, 내가 지금 여기에 중단하고 지금 중지 할 수 있습니까? 388 00:23:04,890 --> 00:23:07,770 [학생] 예. >> 응? 389 00:23:07,770 --> 00:23:11,160 당신 중 하나가 저 멀리 9 번이었다 있다면 요? 390 00:23:11,160 --> 00:23:13,640 이 정렬 된 것입니다. >> 좋아. 이들이 처음에는 정렬 된 것입니다. 391 00:23:13,640 --> 00:23:16,050 좋아. 그러니 다시 가자. 거의 다 왔어. 392 00:23:16,050 --> 00:23:22,800 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8. 393 00:23:22,800 --> 00:23:26,640 >> , 지금은 완료합니다하지만 또 다시, 난 단지 내가 할 말한 건 할 수있는 컴퓨터입니다 394 00:23:26,640 --> 00:23:30,120 내 유일한 기억은 지금은 실제로 작품의 비트 짓을한다는 것입니다. 395 00:23:30,120 --> 00:23:31,700 여기서 뭔가 바뀌 었습니다. 396 00:23:31,700 --> 00:23:37,100 그래서 기술적으로 시각 또는 알고리즘이 목록은 실제로 정렬되어 확인되지 않았습니다. 397 00:23:37,100 --> 00:23:40,720 그냥 좋은 측정을 위해 그래서, 그냥이에 대한 항문을 위해이 1 시간을 더 해보자 구. 398 00:23:40,720 --> 00:23:44,040 1 자, 2, 2, 3, 3, 4. 그리고 당신은 알아요? 399 00:23:44,040 --> 00:23:46,190 그냥 좋은 측정을 위해, 나는 내 손에이 시간을 추적 할 거예요 400 00:23:46,190 --> 00:23:51,110 내가 일을 얼마나 알아 둬 있도록 만들어 얼마나 많은 스왑 사실은 제가 했어요. 401 00:23:51,110 --> 00:23:56,930 3, 4, 4, 5, 5, 6, 6, 7, 7, 8. 어떤 스왑 없습니다. 402 00:23:56,930 --> 00:24:00,800 그래서 지금은 합법적으로 다시이 작업을 수행 할 수있는 바보 같은 것 403 00:24:00,800 --> 00:24:03,330 때문에 나는 인간이 패스를 통해 작품 아무런 짓도하면 404 00:24:03,330 --> 00:24:06,710 그들 중 아무도 종류 무작위로없는 경우 다음과 명확하게 다시 똑같은 일이 405 00:24:06,710 --> 00:24:10,410 adversarially 자신을 주변에 이동. 그래서 지금은 중지 할 수 있습니다. 406 00:24:10,410 --> 00:24:15,120 지금의이 질문을 물어 보자,이 사실을 얼마나 많은 일을 했어요? 407 00:24:15,120 --> 00:24:18,260 그 얼마나 많은 조치를 취할거야? >> N 제곱. 408 00:24:18,260 --> 00:24:20,400 그래, N 제곱. 당신은 어디로에서 제곱 얻을 N합니까? 409 00:24:20,400 --> 00:24:22,660 당신은 각각의 NUM을 확인해야 - 410 00:24:22,660 --> 00:24:26,530 이 N 번호가 있으며, 당신이 다른 N 번호와 각 번호를 확인해야합니다. 411 00:24:26,530 --> 00:24:29,030 좋아. >> 그래서 그것은 제곱 보군. >> 좋아. 412 00:24:29,030 --> 00:24:31,060 >> 그래서 아주 잘 맞아, 제곱 N 수 것 같지? 413 00:24:31,060 --> 00:24:33,820 8이 경우에는 특히,이 사람들의이 보군, 414 00:24:33,820 --> 00:24:37,590 하지만이 목록을 겪었 때마다 나는 두 번째에 대한 최초의 사람을 비교 한 415 00:24:37,590 --> 00:24:39,650 다시 다시 다시 세 번째에 대한 두 번째와 416 00:24:39,650 --> 00:24:42,450 내가 마지막에 도착했을 때, 나는 무슨 짓을 한거야? 난 redid. 417 00:24:42,450 --> 00:24:46,280 우리가이 설명을 일반화하는 경우 그래서, 우리는 우리가 사람들에게 습니했습니다 418 00:24:46,280 --> 00:24:51,090 그리고 난 분명, 8 단계 N 단계,이 알고리즘을 통해 갈 때마다 만드는 중이에요. 419 00:24:51,090 --> 00:24:56,070 그러나 얼마나 많은 최악의 경우 시간이 나는 사람들이 목록을 통과해야합니까? 420 00:24:56,070 --> 00:24:59,370 [학생] N 번. >> 아마 N, 오른쪽, 때문에 최악의 경우에 421 00:24:59,370 --> 00:25:03,410 무엇은 아마도 첫인상에서 이러한 사람들의 최악의 경우 배치거야? 422 00:25:03,410 --> 00:25:06,520 그들은 완전히 순서를 반대로하는 경우 423 00:25:06,520 --> 00:25:09,310 때문에 그냥 정신 let's을 가정 - 당신의 이름은 무엇입니까? >> 브라운이에요. 424 00:25:09,310 --> 00:25:12,510 보웬. 좋아요. 그냥 잠시 동안 여기에 온 보웬,. 425 00:25:12,510 --> 00:25:16,150 >> , 보웬은 알고리즘의 시작 부분에서 여기 있다고 가정 426 00:25:16,150 --> 00:25:19,790 우리는이 알고리즘에 따라, 여기 모든 사람들이 알고 있지만, 보웬하지 않습니다 - 427 00:25:19,790 --> 00:25:23,820 당신이 저와 함께 산책을하고 싶다면 - 그는 주변의 처음처럼, 풍선까지가는되며, 428 00:25:23,820 --> 00:25:25,740 끝으로 모든 방법입니다. 429 00:25:25,740 --> 00:25:29,400 그러나 보웬 옆에있는 사람이 7 번이라고 가정 해 보겠습니다. 430 00:25:29,400 --> 00:25:33,450 난 다시 가서 내가 다시 여기 길을 가야 의미 숫자 7을 얻을 수 있습니다. 431 00:25:33,450 --> 00:25:36,980 지금은 번호 7 사람과 같은 산책을 가지고 있어야합니다. 432 00:25:36,980 --> 00:25:40,140 그러나 번호 6가 그 옆에 있었고 다음 면요? 433 00:25:40,140 --> 00:25:42,180 그럼 내가 가서 6를 얻을 수 있습니다. 434 00:25:42,180 --> 00:25:46,490 그럼 다시,이 루프의 모든 반복에 나는 N 사람들의 각 얘기 435 00:25:46,490 --> 00:25:50,090 그리고 내가 찾고 있어요 있는지 확인하려면 다음과 산책의 N을해야 할 수도 있습니다 436 00:25:50,090 --> 00:25:53,760 다시 다시 다시 목록의 맨 끝에 가장 큰 요소의 모든. 437 00:25:53,760 --> 00:25:58,230 따라서 N 일 n 번은 n 번 N 또는 n 제곱입니다. 438 00:25:58,230 --> 00:26:02,050 >> 그래서 여기 이미 우리는 더 이상 로그 N없는 더 이상없는 알고리즘 n을,이 439 00:26:02,050 --> 00:26:04,820 우리가 전에했던 것보다 실제로 더 있습니다. 440 00:26:04,820 --> 00:26:09,840 따라서의 알렉스 종류, 난 일을 그녀에게 분명히까지 앞의 모든 짓을한다는 점에서 운이 좋았죠 441 00:26:09,840 --> 00:26:14,690 그녀가 이진 검색 알고리즘에 즐길 수 있도록 고가의 작업의 모든, 442 00:26:14,690 --> 00:26:16,420 n의 로그하는 것입니다. 443 00:26:16,420 --> 00:26:18,240 그러나 월요일의 주제와 일치 수 있습니다. 444 00:26:18,240 --> 00:26:23,260 우리는 우리의 실행 시간을 단축하기 위해 더 많은 비트를 사용, 조금 더 공간을 주었다. 445 00:26:23,260 --> 00:26:26,170 많은 시간과 공간 간의 트레이드 오프가 같은 446 00:26:26,170 --> 00:26:31,060 시간이 갈 일 준비의 앞에 정렬을 보냈다 사이에 역시 무역 오프가있을 수 있습니다 447 00:26:31,060 --> 00:26:35,000 실제로 검색과 같은 알고리즘을 실행. 의 다른 하나를 시도해 보자. 448 00:26:35,000 --> 00:26:39,050 너희가 빨리 재 배열 상관하지 않을 경우 스스로는 다시 한번 일치하는 449 00:26:39,050 --> 00:26:42,240 별로 간단하게는 어디 약간 다른 무언가를 시도 두자 450 00:26:42,240 --> 00:26:45,760 슈퍼 직관적있는 모든 pairwise 실수를, 그냥 수정으로. 451 00:26:45,760 --> 00:26:48,150 의 대신 조금 더 천천히이 짓을 보자. 452 00:26:48,150 --> 00:26:51,010 너무 제가 제안 것 하나는 아마도 매우 직관적입니다. 453 00:26:51,010 --> 00:26:55,070 >> 또 한번, 또 한번 목록에서 가장 작은 사람을 선택하자. 그래서 여기에 우리가 이동합니다. 454 00:26:55,070 --> 00:26:57,350 네, 당신은 내가 이렇게까지 ​​본 가장 작은 사람입니다 455 00:26:57,350 --> 00:27:00,520 그래서 정신적으로 단지 지금 당신줌으로써 그 기억거야. 456 00:27:00,520 --> 00:27:05,020 2. 와우! 4 번 잊어 버려요. 난 그냥이 목록의 새로운 작은 요소를 발견했습니다. 457 00:27:05,020 --> 00:27:07,410 나는 어떤 종류의 기억이에 갈거야. 6, 8. 458 00:27:07,410 --> 00:27:11,190 와우! 1. 안녕히 가세요. 그래서 지금은 숫자 1을 기억하는거야. 459 00:27:11,190 --> 00:27:14,790 우리는 1 작은 것을 알아,하지만 난 컴퓨터입니다. 어떤 0이 있다면 요? 460 00:27:14,790 --> 00:27:17,140 어떤 -1이 있다면? 나는 계속해야합니다. 461 00:27:17,140 --> 00:27:20,990 따라서 3, 7, 5, 아뇨. 좋아요. 그래서 숫자 1은 가장 작은이었습니다. 462 00:27:20,990 --> 00:27:23,640 제가 목록에서를 선택하자 - 꼭이 길을 갈 - 463 00:27:23,640 --> 00:27:27,760 와 목록의 시작 부분에서 임의로을 넣어. 464 00:27:27,760 --> 00:27:29,740 자, 기다려 봐. 사기에 드는데. 465 00:27:29,740 --> 00:27:34,010 이 남자들은 8 명 목록 만 배열을 나타냅니다 경우 466 00:27:34,010 --> 00:27:37,050 연속 메모리 8 덩어리가 - 당신은 한 순간을 위해 다시 스테핑 줄래? 467 00:27:37,050 --> 00:27:39,060 바로 여기 공간은 실제로 없습니다. 468 00:27:39,060 --> 00:27:41,840 그럼 우리는 공간을 어떻게해야합니까 - 이름이 뭐야? >> 새미. >> 새미. 469 00:27:41,840 --> 00:27:43,710 우리가 어떻게 새미를위한 공간을 어떻게해야합니까? 470 00:27:43,710 --> 00:27:46,760 >> 우리는 내 앞에있는 N 이동합니다. 좋아요 >>. 471 00:27:46,760 --> 00:27:48,850 그래서 우리는 그 전에있는 N 사람들을 움직일 수 472 00:27:48,850 --> 00:27:52,400 너희들이 왼쪽으로 한 고의적, 극적인 조치를 취할하고 싶다면. 473 00:27:52,400 --> 00:27:57,000 , 그들은 모두 한마음으로 그 짓을하지만, 지난번에 내가 몇 가지 코드를 작성 474 00:27:57,000 --> 00:27:59,740 여러분 모두 한 번에 많은 물건을 움직일 분류 할 수 없습니다. 475 00:27:59,740 --> 00:28:02,450 우리는 한 번에 한 번 모두를 이동, 루프에서 할 수 있습니다. 476 00:28:02,450 --> 00:28:04,340 너희들이, 오른쪽으로 돌아 가야할 거 신경 안 써요면 477 00:28:04,340 --> 00:28:07,230 그리고, 새미의 여지가 아직 없습니다 때문에 물러 할 수 있다면, 478 00:28:07,230 --> 00:28:11,420 지금 한번 해보자 구. 어디 새미 순간 전 이었어요? 바로 거기. 479 00:28:11,420 --> 00:28:16,140 그래서 차이가 있습니다. 그럼 당신은 새미의 장소로 이동 수 있습니다. 480 00:28:16,140 --> 00:28:20,580 지금 옆에있는 사람까지 지금 현재 다음 사람, 다음 사람. 이제 우리는 새미을위한 공간을 갖추고 있습니다. 481 00:28:20,580 --> 00:28:23,490 관객에서 이제 사람 - 잘 했어, 정확 했지 482 00:28:23,490 --> 00:28:27,070 그 느낌이 시간이 많이 걸리는 약간 - 어떤 빠른 게있어? 그래. 483 00:28:27,070 --> 00:28:29,440 [학생] 새로운 배열? >> 무슨 뜻이지? >> [학생] 새로운 배열? >> 그래, 좋아. 484 00:28:29,440 --> 00:28:33,200 >> 단지 무역 오프의 테마가 너무 일관성, 왜 난 그냥 새로운 배열을 만들지 마 485 00:28:33,200 --> 00:28:36,570  그리고 새미 예를 들어,이 사람들의 앞에 공간에서 수영됩니다 486 00:28:36,570 --> 00:28:39,600 그리고 우리는 모두 새로운 배열을 작성하실 수 있습니다. 너무 일 것입니다. 487 00:28:39,600 --> 00:28:42,450 하지만 오늘은 더 많은 공간을 소비에 관심 없어. 또 다른 방법은 무엇입니까? 488 00:28:42,450 --> 00:28:46,630 [학생] 스왑. 좋아요 >>. 우리는이 두 녀석을 교환 수 있습니다. 이름이 무엇입니까? 489 00:28:46,630 --> 00:28:49,390 마리오. >> 마리오. 마리오 그래서 현재 여기에 있었다. 490 00:28:49,390 --> 00:28:52,480 새미, 당신은 잠시 동안 백업 할 수 있습니다? 마리오가 여기 있었어요. 491 00:28:52,480 --> 00:28:55,830 당신이 새미가 어디가는 거 신경 안 써요 만약 그렇다면 우리는 더 이상 당신을위한 공간이 없어요 492 00:28:55,830 --> 00:29:02,430 우리는 깨 놓을 게요, 지금은 새미의 교환 작업이 훨씬 더 빨리이라고 주장 할. 493 00:29:02,430 --> 00:29:06,370 우리는이 사람들을 교환하거나, 어쩌면이 녀석을 교환 한 작업을 한 494 00:29:06,370 --> 00:29:11,210 하지만 우리는 더 나은 느낌 그 때문에, 1, 2, 3, 4 안 했어요. 자, 기다려 봐. 495 00:29:11,210 --> 00:29:14,660 4 번이 처음에 가까운 가지했기 때문에 나는 가지 문제가 악화했다. 496 00:29:14,660 --> 00:29:19,470 지금 4 번이 마지막에 좀 더 가까이하지만, 난 정말 알고 또는 그것에 대해 관심이 없었어요. 497 00:29:19,470 --> 00:29:23,330 그래서이 4 번이 좀 멀리의 운명 곳에서입니다 단지 운이 나빴군요. 498 00:29:23,330 --> 00:29:25,110 따라서이 알고리즘을 반복 지금 까. 499 00:29:25,110 --> 00:29:28,410 >> 오래 그 이야기를했는데, 요점을 되풀이하기 위해, 우리 모두가 목록을 걸어 었어요 500 00:29:28,410 --> 00:29:31,130 가장 작은 번호가 사람을 찾고 있어요. 501 00:29:31,130 --> 00:29:34,530 이제 다시 한번 해보자 구. 우리는 더 이상 새미에 대해 걱정할 필요가 없습니다. 502 00:29:34,530 --> 00:29:37,590 우리는 여기에서 할 수 있습니다. 와우! 번호 2. 아주 적은 수의 기록이다. 503 00:29:37,590 --> 00:29:41,180 6, 8, 4, 3, 7, 5. 그래, 좋아. 504 00:29:41,180 --> 00:29:43,770 그리고 다행히, 우연의 일치에 의해 움직일 필요가 없습니다 - >> 윌리 있습니다. 505 00:29:43,770 --> 00:29:45,910 윌리 그는 지금 자신의 올바른 위치에 때문입니다. 506 00:29:45,910 --> 00:29:48,110 다시이 작업을 수행하자 이러한 두 녀석을 무시합니다. 507 00:29:48,110 --> 00:29:50,460 6. 아주 적은 수의 기록이다. 와우! 8 확실히 큽니다. 508 00:29:50,460 --> 00:29:53,410 4. 의 4에 초점을 보자. 와우! 3 더 있습니다. 509 00:29:53,410 --> 00:29:58,290 7 5. 그럼 우리가 이제 어떻게하지 - >> 로저. >> 로저? 510 00:29:58,290 --> 00:30:00,250 의 번호는 6 그를 교체 보자. 511 00:30:00,250 --> 00:30:03,570 따라서 6 3 교환하고 싶은 경우 512 00:30:03,570 --> 00:30:07,320 우리는 이제 가지, 그녀가 있어야 할 자리에 가까운입니다 6 운이 생겼는지 513 00:30:07,320 --> 00:30:10,300 하지만 여기 우연의 일치입니다. 그럼 지금 여기 가자. 514 00:30:10,300 --> 00:30:13,430 8 매우 작은 숫자입니다. 와우! 4 작습니다. 515 00:30:13,430 --> 00:30:17,130 6, 7, 5. 우리는 지금 무엇을해야합니까? >>의 스왑. 정확히 >>. 516 00:30:17,130 --> 00:30:19,010 이제 빠르게 이러한 종류의 한번 해보자 구. 517 00:30:19,010 --> 00:30:24,460 8, 6, 7, 5. 5 어디가는 거지? 좋아. 좋아요. 518 00:30:24,460 --> 00:30:28,380 6, 7, 8. 6 그녀가 어디 있어야됩니다. 이름이 무엇입니까? >> 로잘리. 519 00:30:28,380 --> 00:30:31,770 로잘리 그녀가 어디 있어야됩니다. 7에 도착 - 봅시다. 7, 8. 좋아요. 520 00:30:31,770 --> 00:30:35,100 그럼 7 그녀가 어디 있어야됩니다. 이름이 무엇입니까? >> Amna. >> Amna. 521 00:30:35,100 --> 00:30:39,670 >> 그럼 Amna는 그녀가 어디 남아 도착, 그는 지금 있어야 할 곳에 숫자 8은 이미 있습니다. 522 00:30:39,670 --> 00:30:43,960 그래, 좋아. 우리가 있지만, 여기에 자신에 대한 작품을 만드는 것 같아요. 523 00:30:43,960 --> 00:30:47,440 어떤 궁극적으로이 알고리즘의 실행 시간있어? 524 00:30:47,440 --> 00:30:51,900 우리가 아니라, 8과 같은하지만, N 이러한 사람들에 대해 생각한다면? >>은 N입니다. 525 00:30:51,900 --> 00:30:55,440 이 단계를 보군,하지만 우리는 매일 시간을 확인하고 있습니다. 526 00:30:55,440 --> 00:30:57,570 좋아요. N하지만 매번를 확인 건가요? 527 00:30:57,570 --> 00:31:03,450 이 단계를 보군 경우 좋아,하지만, 난 그냥 1, 2, 3, 4로 이동하여 귀하를 정렬 할 수 없었을해야합니까? 528 00:31:03,450 --> 00:31:05,590 오! 그래요, 그게 큰 차이입니다. 529 00:31:05,590 --> 00:31:08,050 따라서 n은 왜 제곱? 정말 무슨 일이에요? 530 00:31:08,050 --> 00:31:12,130 이 목록의 N 사람들이지만, 목록에서 가장 작은 사람을 찾을 수 531 00:31:12,130 --> 00:31:16,200 최악의 경우 몇 단계 나 데려 가야 해요? >> N. 532 00:31:16,200 --> 00:31:19,160 >> N, 오른쪽, 최악의 경우, 숫자 1, 저기 모든 방법이기 때문에 533 00:31:19,160 --> 00:31:20,990 그래서 그 사람을 얻거나 그녀 가야 해요. 534 00:31:20,990 --> 00:31:25,500 그리고 드디어 1 작은 였지만 때, 죽음이 그들을 교환 꽤 빠르입니다. 535 00:31:25,500 --> 00:31:28,450 하지만 지금은 처음부터 시작하여 사람을 찾아 있습니까? 536 00:31:28,450 --> 00:31:31,980 2 다음 작은 사람. 최악의 경우에 2 어디있는거야? 537 00:31:31,980 --> 00:31:34,320 오, 맙소사. 이 말에 여기까지입니다. 538 00:31:34,320 --> 00:31:37,000 그래서 지금은 다른 N 단계, 다른 N 단계를 완료했습니다. 539 00:31:37,000 --> 00:31:41,200 그리고 우리는 N 사람들을 보유하고 있으며 최악의 경우에 가장 작은 사람이 거리에 N 단계 인 경우, 540 00:31:41,200 --> 00:31:45,230 다시는 n 번 N이고, 그래서 우리는 다시 제곱 습니했습니다. 541 00:31:45,230 --> 00:31:47,280 이건 너무 기분이 좋다되지 않습니다. 542 00:31:47,280 --> 00:31:52,150 그리고 사실, 심지어 가장 경우에 - 소위 정렬 시작하는 가정 - 543 00:31:52,150 --> 00:31:59,080 내가이 N 사람들을 정렬하려면이 알고리즘을 사용하기 위해 얼마나 많은 단계를 수행합니까? 544 00:31:59,080 --> 00:32:01,010 N은 제곱. >> 나도 들었어 N 제곱. n은 제곱 이유는 무엇입니까? 545 00:32:01,010 --> 00:32:05,240 당신은 여전히​​ 매번 확인해야합니다 때문입니다. >> 그래. 546 00:32:05,240 --> 00:32:08,060 그리고 당신이 그들을 교체해야합니다. 우리 인간은 신이의 종류 >>하더라도 547 00:32:08,060 --> 00:32:10,770 의미에서 시각적으로 우리가이이 정렬되는 것을 볼, 그냥 할 수있을 548 00:32:10,770 --> 00:32:12,140 컴퓨터는 스마트하지 않습니다. 549 00:32:12,140 --> 00:32:14,040 그것은, 여기, 그리고 여기와 여기 보는거야 550 00:32:14,040 --> 00:32:16,610 하지만이 찾고있어하는 가장 작은 요소입니다 경우, 551 00:32:16,610 --> 00:32:22,110 당신은 단지 무슨 점으로 가장 작은 요소를 발견 한 거 알아요? 일단 당신이 마지막에와 있습니다. 552 00:32:22,110 --> 00:32:25,880 그러나 그 시점에서 당신은 단지 현재 가장 작은 요소를 발견했습니다. 553 00:32:25,880 --> 00:32:28,810 당신은 반드시 세상의 상태에 대한 다른 아무것도 몰라요. 554 00:32:28,810 --> 00:32:30,880 그럼 당신은 다시 다시 다시 가야 해. 555 00:32:30,880 --> 00:32:34,880 >> 난 괜찮을 2를 선택하기 때문에 정말로이 시간이 바보 그래서, 당신은 가장 작은이야 556 00:32:34,880 --> 00:32:37,530 하지만 아직 총을 압니다하지 않습니다. 557 00:32:37,530 --> 00:32:41,090 3, 4, 5, 6, 7, 8. 그래, 좋아. 2 실제로 작은이었습니다. 558 00:32:41,090 --> 00:32:43,150 지금의이 다음 작은를 찾으실 수 있습니다. 좋아요. 559 00:32:43,150 --> 00:32:48,350 3, 현재 가장 작은이야. 어디 봅시다. 4, 5, 6, 7, 8. 좋아, 다시 운이 좋군. 560 00:32:48,350 --> 00:32:53,170 3 오른쪽 장소에 실제로이었다. 하지만 다시이 일을 다시하고 다시 유지거야. 561 00:32:53,170 --> 00:32:55,990 우리가 어떻게 아무리 약간 더 할 수 있습니까? 562 00:32:55,990 --> 00:33:00,120 대신에 pairwise 작은에서 큰 사람들에게 풍선을 갖는 563 00:33:00,120 --> 00:33:04,350 대신 다음 작은 사람을 선택 목록을 앞뒤로가는, 564 00:33:04,350 --> 00:33:09,780 왜 우리가 대신 단계하여 새 목록 단계로이 사람들을 삽입하지 마십시오? 565 00:33:09,780 --> 00:33:13,080 의이 일을 해 보자. 지금 내가이 일을 삽입 정렬이라고 불러. 566 00:33:13,080 --> 00:33:17,250 그래서 여기에 우리가 여기에 있습니다. 번호 1. 이 목록에있는 다른 사람에 대해 신경 쓰지 않습니다. 567 00:33:17,250 --> 00:33:21,310 내 목표는 지금 정렬 목록의 처음에 숫자 1을 넣어하는 것입니다. 568 00:33:21,310 --> 00:33:23,910 제가 메모리 만 8 덩어리가 있기 때문에 그리고, 제안거야 569 00:33:23,910 --> 00:33:28,670 임의로 지금은, 내 추측 정렬되지 않은 목록 사이의 벽이다 570 00:33:28,670 --> 00:33:32,740 내가 주장하는거야 저 뒤에있는 사람이 정렬됩니다. 571 00:33:32,740 --> 00:33:34,680 이제 우리는 숫자 1이 있습니다. 572 00:33:34,680 --> 00:33:39,240 내 정렬 목록에 그를 삽입 할, 난 그냥 여기에 벽을 이동로 갈 거에요 573 00:33:39,240 --> 00:33:43,930 지금 내가이 목록이 정렬됩니다 주장이 목록은 정렬되지 않은 수 있습니다 - 적어도 지금까지 내가 아는 한. 574 00:33:43,930 --> 00:33:46,070 한 번에 모든 숫자를 볼 수 없습니다. 575 00:33:46,070 --> 00:33:49,000 >> 지금은 숫자 2가 발생하기 때문입니다. 그와 함께 무엇을해야합니까? 576 00:33:49,000 --> 00:33:54,380 나는 정렬 목록에 당신을 삽입합니다. 하지만 그게 얼마나 쉽게 확인합니다. 577 00:33:54,380 --> 00:33:59,650 난 그냥 볼 수 있습니다. 숫자 1이 있습니다. 아, 분명 2 숫자 1의 측면으로 이동합니다. 578 00:33:59,650 --> 00:34:03,700 지금은 3 어떻게해야 하죠? 나는 정렬 목록에 귀하를 삽입합니다. 하지만 그건 아주 쉽게했다. 579 00:34:03,700 --> 00:34:07,250 이 쉬운 슈퍼입니다이 아주 쉽게, 이쪽은 아주 쉽게, 아주 쉽게, 아주 쉽게합니다. 580 00:34:07,250 --> 00:34:12,790 그리고 이제 모든 것을 내 뒤에 정렬하고 있으며, 그 얼마나 많은 조치를 취할거야? 581 00:34:12,790 --> 00:34:15,620 [학생] N. >> 따라서 만 보군. 우린 운이 좋아. 582 00:34:15,620 --> 00:34:18,860 단지 N 이유 였죠? >> [학생] 목록이 정렬되었습니다 때문입니다. 583 00:34:18,860 --> 00:34:21,630 이 목록은 이미 정렬됩니다. 그래서 우리는 운이 좋았 군. 584 00:34:21,630 --> 00:34:25,639 그러나 우리는, 알고리즘 행운의 종류를 이용합니다이 시간을 설계 585 00:34:25,639 --> 00:34:29,420 불필요한 시간을 낭비하지 않는 방법으로에 가장의 경우. 586 00:34:29,420 --> 00:34:31,750 그래서 우리는 지금 우리는 거품 정렬을 뭐라고 할 수 있습니다 587 00:34:31,750 --> 00:34:33,949 어디에서 pairwise까지 거품의 사람들 이란다. 588 00:34:33,949 --> 00:34:38,100 우리가 다시 다시 작은 사람을 뽑아 낸 곳 우리는 지금 선택 정렬되어 있습니다. 589 00:34:38,100 --> 00:34:42,350 그들이있을 곳은 우리가 어떤 종류의 사전 명을 넣는 이제 지금은 우리가 삽입 정렬을 590 00:34:42,350 --> 00:34:45,000 점점 정렬 명단에 없어요. 591 00:34:45,000 --> 00:34:49,679 우리가 할 수 있다면, 여기 애들에게 박수. [박수] 592 00:34:49,679 --> 00:34:52,310 의은 우리가 5 분 쉬었다합시다. 593 00:34:52,310 --> 00:34:55,139 그리고 우리가 돌​​아 왔을 때, 우리는 물 밖으로 이러한 알고리즘을 모두 버릴거야 594 00:34:55,139 --> 00:35:00,260 더 나은 뭔가를. 괜찮아요. 정말 감사합니다. 당신은 기념품으로 사람들을 유지할 수 있습니다. 595 00:35:01,710 --> 00:35:04,330 괜찮아요. 우리가 다시 있습니다. 596 00:35:04,330 --> 00:35:08,420 >> 그리고 정말 빨리 요점을 되풀이하기 위해, 정렬 이러한 3 가지 방법을 가지고 597 00:35:08,420 --> 00:35:13,000 전체 점은 지점에 도착 곳 알렉스 같은 사람 598 00:35:13,000 --> 00:35:16,930 숀 할수 같은 사람보다 더 빨리 숫자의 목록을 검색 할 수 있습니다. 599 00:35:16,930 --> 00:35:19,830 그리고 우리는 8 자리 숫자와 같은 간단한 예제를 가지고하더라도, 600 00:35:19,830 --> 00:35:24,000 당신은 쉽게 8 웹 페이지, 8000000000 웹 페이지를 추정 할 수 601 00:35:24,000 --> 00:35:26,680 페이스 북이나 800,000,000 친구. 602 00:35:26,680 --> 00:35:30,090 따라서 이러한 알고리즘은 확실히 값을 그 종류의 확장 할 수 603 00:35:30,090 --> 00:35:32,300 그리고 아이디어는 궁극적으로 동일합니다. 604 00:35:32,300 --> 00:35:36,140 따라서 버블 정렬은 우리가 가지 가장 큰 사람을 부풀어 오른 곳 처음 605 00:35:36,140 --> 00:35:39,110 pairwise 사람들을 교환하여 오른쪽에있는 모든 방법입니다. 606 00:35:39,110 --> 00:35:42,040 그럼 우리가 어디 좀 더 의도적으로 우리가 선택 정렬을 뭐라고했다 607 00:35:42,040 --> 00:35:46,480 다시, 목록을보고 또 한번, 또 한번 가장 작은 번호를 선택하고 계속 608 00:35:46,480 --> 00:35:49,530 의 논리적 결과 목록이 결국 정렬되어 있습니다. 609 00:35:49,530 --> 00:35:53,780 그런 다음 세 번째는, 내가, 적합한 장소로 사람들을 삽입 610 00:35:53,780 --> 00:35:57,720 우리는 목록이 이미 정렬 된 것을 매우 인위적인 예를 했어, 611 00:35:57,720 --> 00:36:01,100 하지만 그 메시지를 보낼이었다 삽입 정렬의 경우에 612 00:36:01,100 --> 00:36:02,670 당신은 행운을 가질 수 있습니다. 613 00:36:02,670 --> 00:36:07,930 숫자가 이미 정렬되어 경우에만 많이 확인하는 N 조치를 취할 겁니다 614 00:36:07,930 --> 00:36:10,870 선택 정렬 반면 당신은 좀 더 터널 비전이야 615 00:36:10,870 --> 00:36:14,360 그리고 당신은 목록이 이미 정렬 않는다는 것을 깨닫게하지 않습니다. 616 00:36:14,360 --> 00:36:16,830 그래서 여기 활동에 거품 정렬을 살펴 보자. 617 00:36:16,830 --> 00:36:19,590 다음 예제에서, 우리는 수직 막대를 볼 것입니다 618 00:36:19,590 --> 00:36:23,030 우리가 시각화 일을 정렬의 정렬 할 수 있도록 그의 높은 숫자를 나타냅니다. 619 00:36:23,030 --> 00:36:26,630 작은 바, 숫자 작은, 큰 바, 더 큰 수를 표시합니다. 620 00:36:26,630 --> 00:36:28,860 >> 그리고 우리는이 기본 속도에서 재생됩니다. 621 00:36:28,860 --> 00:36:33,460 그것은 지금 조금 빨리 이동하는거야,하지만 빨간색은 2 개의 바 보여줄 수있어 622 00:36:33,460 --> 00:36:35,480 나란히 비교된다. 623 00:36:35,480 --> 00:36:39,520 당신이 자세히 볼한다면, 어떤 일이 생기 것은 그 바의 순서, 경우 624 00:36:39,520 --> 00:36:42,300 하나 작은은 왼쪽으로 오른쪽으로 더 큰 하나를 이동됩니다 625 00:36:42,300 --> 00:36:44,360 그리고 당신은 발전 유지. 626 00:36:44,360 --> 00:36:48,520 우리가 다시 다시이 작업을 수행다면,주의 그 작은 바 627 00:36:48,520 --> 00:36:51,090 왼쪽의 길을 인칭 둘 건가요 628 00:36:51,090 --> 00:36:54,130 그리고 가장 큰 막대는 오른쪽으로 길을 인칭 유지하려고합니다. 629 00:36:54,130 --> 00:36:58,490 그리고 실제로, 우리는 패턴을 오른쪽에있는 모든 방법을보기 시작하고 630 00:36:58,490 --> 00:37:04,790 처럼 우리는 8 본 후 7 결국 인간 목록의 맨 끝 부분에 품어. 631 00:37:04,790 --> 00:37:08,750 그래서이 매우 빠르게 조금 지루한 얻을 것입니다, 그러니 내가 잠시 동안이 일을 막아야 해. 632 00:37:08,750 --> 00:37:10,980 나를 훨씬 더 빨리 될 속도를 변경 보자. 633 00:37:10,980 --> 00:37:15,380 제가 알고리즘을 바꾸지는 않을 겁니다, 그냥 애니메이션이 빠르게 일어날 만드는 중이에요. 634 00:37:15,380 --> 00:37:18,410 아직도 거품 정렬, 동일 알고리즘 635 00:37:18,410 --> 00:37:21,910 지금 당신은 우리의 언어 데모보다 훨씬 빠르게 볼 수 있습니다 636 00:37:21,910 --> 00:37:25,900 하는 가장 큰 요소는 실제로 정상에 품어 있습니다. 637 00:37:25,900 --> 00:37:29,860 >> 옆으로,이 작은 하단 왼쪽에 사각형과 하단 바로 638 00:37:29,860 --> 00:37:33,520 당신이하고있는 얼마나 많은 비교를 같은 단지 약간의 알림입니다. 639 00:37:33,520 --> 00:37:37,620 하지만 지금은 모양을 이루고있는 피라미드에 집중할 수 있으며, 거기에 간다. 640 00:37:37,620 --> 00:37:41,510 가장 작은 요소는 왼쪽, 오른쪽에있는 큰, 그리고 다른 사이에 모든에 있습니다. 641 00:37:41,510 --> 00:37:44,470 지금의 대신 선택 정렬을 살펴 보자. 642 00:37:44,470 --> 00:37:47,260 나는 가서 정지를 누르거야. 우리는 바의 새로운 임의의 집합을받을거야. 643 00:37:47,260 --> 00:37:50,930 선택 정렬, 리콜, 다시 다시 다시 목록을갑니다 644 00:37:50,930 --> 00:37:54,900 가장 작은 요소를 뜯어. 그래서 여기 선택 정렬입니다. 645 00:37:54,900 --> 00:37:58,390 우리가 pairwise 비교하지 않았기 때문에 지금은 상황이의 더 적은 일 것 같습니다 646 00:37:58,390 --> 00:38:02,590 하지만 우리는 오른쪽에서 왼쪽으로 작은 요소를 체리 따기의 정렬하고 있습니다. 647 00:38:02,590 --> 00:38:06,890 그건 거의 시간이 걸렸습니다, 이분법 이미 혼자 야. 648 00:38:06,890 --> 00:38:11,820 알고리즘은 버블 정렬과 같은 N 제곱 시간이 걸릴이라고합니다해서 649 00:38:11,820 --> 00:38:16,100 및 선택 정렬처럼, 그건 최악의 경우 실행 시간은 정말 있습니다. 650 00:38:16,100 --> 00:38:21,790 예를 들어,의 경우,,, 말의 선택 정렬하게 651 00:38:21,790 --> 00:38:27,240 사실은 가장 작은 사람을 선택하고 있고, 여기 그 사람 그녀를 넣어 652 00:38:27,240 --> 00:38:29,620 그럼 다시하고 있어요, 그럼, 또 이러 네 653 00:38:29,620 --> 00:38:32,070 하지만 할 수있는 약간의 최적화가 발생했습니다. 654 00:38:32,070 --> 00:38:35,040 >> 이 경우 새미 - 나 숫자 여기에 1을 이동 자마자 - 655 00:38:35,040 --> 00:38:38,630 난 이후 그와 함께 어떻게해야 했어? >> [학생] 그 둡니다. 656 00:38:38,630 --> 00:38:40,140 자, 그를 떠나? 아무것도. 657 00:38:40,140 --> 00:38:44,310 제가 가장 작은 요소를 선택한 경우 때문에 다시 본 새미 이야기 할 필요 없어 658 00:38:44,310 --> 00:38:48,580 여기 바꿔, 왜 시간 낭비 내 전체 목록의 끝으로가는거야? 659 00:38:48,580 --> 00:38:54,590 다음 반복에서 내 실제 만 3 번, 2 번 만 이동하세요. 660 00:38:54,590 --> 00:38:57,640 그래서 현실에서, 나는 N 일 n 번 짓도 안했습니다. 661 00:38:57,640 --> 00:39:05,380 1 일, 다음에 n - - 2 일, 다음에 n - 3 일, 나는 다음에 n 일, n을 짓 662 00:39:05,380 --> 00:39:07,080 다음에 n - 4, 점, 점, 점입니다. 663 00:39:07,080 --> 00:39:09,470 우리는 의미 기하학적 시리즈의 조금 있습니다 664 00:39:09,470 --> 00:39:11,450 당신은 점점 더 작은 숫자를 추가하고 있습니다. 665 00:39:11,450 --> 00:39:17,940 안 N + N + N + N 있지만, N + 7 + 6 + 5 + 4 + 3 + 2 + 1. 666 00:39:17,940 --> 00:39:21,380 그리고 일반적으로 무엇을 작동합니다 - 667 00:39:21,380 --> 00:39:24,280 난 그냥 잠시 여기 내 보드 망치지에 갈거야 - 668 00:39:24,280 --> 00:39:28,990 / 2 - 그 N과 같이 (1 N)으로 운동을거야 669 00:39:28,990 --> 00:39:31,930 당신은 모든 치트 시트가 수학 책의 뒷면 모습의 경우 우리가 어떤 670 00:39:31,930 --> 00:39:33,410 수식하십시오. 671 00:39:33,410 --> 00:39:37,760 당신이 뭔가를 추가하는 경우 n은 + N - 1 + N - 2, 그건이 같은 것으로 밝혀 작동합니다. 672 00:39:37,760 --> 00:39:42,320 의 우리는 그냥 종류가이 문제를 곱하면, 우리가 2 제곱 마이너스 N / N있어. 673 00:39:42,320 --> 00:39:46,400 그래도, 난 말을 N 제곱 보관, 나는 정신 바로 가기를 복용 종류 있었기 때문 이네 674 00:39:46,400 --> 00:39:51,950 현실에서, N 마이너스 제곱 N 2로 나누어은 참으로 단계의 진정한 수 있기 때문에 675 00:39:51,950 --> 00:39:55,510 우리가 정말 일어나 계산하는 경우 선택 정렬과 같은 알고리즘이 소요될 것으로 676 00:39:55,510 --> 00:39:58,800 이러한 비교의 우리가 뭘하고 있었 좀 바쁜 일 모두. 677 00:39:58,800 --> 00:40:03,210 그러나 솔직히, n은 도대체 관심 만 또는 억처럼하게 678 00:40:03,210 --> 00:40:07,160 당신은 2로 나누어 억 제곱 마이너스 억을하고 있다면 요? 679 00:40:07,160 --> 00:40:09,320 제곱 억은 큰 숫자입니다. 680 00:40:09,320 --> 00:40:13,580 당신은과 다른 억원에서 걸릴 수 있습니다 - n을. 정말 큰 문제가 아니에요. 681 00:40:13,580 --> 00:40:18,770 그래서 더 큰 숫자가 가서 덜 중요한이 낮은 명령 조건이 있습니다. 682 00:40:18,770 --> 00:40:24,230 이 단계의 번호 quadrillions에 대해 얘기하고 경우 2로 나누어 무슨 상관이 있어요? 683 00:40:24,230 --> 00:40:29,710 >> 따라서 일반적으로, 컴퓨터 과학자, 그래도 가장 큰 용어를 던져하는 경향이 684 00:40:29,710 --> 00:40:33,140 우리는, 그냥 세계를 단순화하고 그런 말을 그 알고리즘 685 00:40:33,140 --> 00:40:38,130 약 N 제곱 단계를했다. 그 알고리즘의 실행 시간입니다. 686 00:40:38,130 --> 00:40:40,760 그래서 우리는 몇 가지 구체적인 예와 함께 한 순간이 다시 올거야 687 00:40:40,760 --> 00:40:45,940 하지만 지금은, 그 직관적 인 동기 부여의 종류는 우리의 세계를 단순화 배후 688 00:40:45,940 --> 00:40:51,170 그리고 오히려 이러한 모든 멋진 수식에 들어가기보다 가장 중요한 조건에 대해 얘기. 689 00:40:51,170 --> 00:40:53,540 그래서 그런 선택이었는데, 우리는 거기에 약간의 운이 좋군. 690 00:40:53,540 --> 00:40:57,360 가 삽입 정렬 살펴 보도록하겠습니다. 내가 가서이 하나를뿐만 아니라 시작하자. 691 00:40:57,360 --> 00:41:00,330 지금 무슨 일이 패턴을 발견하는 것은 약간 다릅니다 692 00:41:00,330 --> 00:41:03,410 우리는, 임의의 숫자로 시작 693 00:41:03,410 --> 00:41:06,890 하지만 우리가 실제로 최악의 경우에 단계의 수를 계산하면, 694 00:41:06,890 --> 00:41:11,070 목록이 오른쪽 순서로 완전히 시작하는 경우 695 00:41:11,070 --> 00:41:13,380 우리는 많은을 실현하기 위해 N 조치를 취할 것입니다. 696 00:41:13,380 --> 00:41:18,240 >> 그러나 목록은 거꾸로 실제로 있다면 - 예를 들어, 여기이 경우에 - 697 00:41:18,240 --> 00:41:23,860 우리가 실제로이 경우 더 많은 일을해야 할 다음 확인합니다. 698 00:41:23,860 --> 00:41:27,080 이 하나가 더 힘들어 종류 인 것 그리고 가지 당신 생각해야 699 00:41:27,080 --> 00:41:30,900 왼쪽에있는 작은 요소를, 우리는 운이 가지고 있기 때문에 그건합니다. 700 00:41:30,900 --> 00:41:34,210 이 목록은 역에서 실수로 정렬되었습니다. 701 00:41:34,210 --> 00:41:38,110 대조적으로, 삽입 정렬과 우리가 여기 우리 인간과 무슨 짓을 모방하는 경우 702 00:41:38,110 --> 00:41:42,670 시작 정렬 사람들로 시작하고 그때까지, 바로, 아주 좋은 알고리즘거야? 703 00:41:42,670 --> 00:41:45,010 이미 사실 정렬있어. 704 00:41:45,010 --> 00:41:48,670 따라서 이것들은 우리에게 데려가는거야 정확히 얼마나 많은 시간을 요약 해 두자 705 00:41:48,670 --> 00:41:52,360 실제로 훨씬 더 간단 단지 전문 용어의 비트 또는 표기법을 도입하여 706 00:41:52,360 --> 00:41:54,320 의 fanciness 분류가 제안보다. 707 00:41:54,320 --> 00:41:59,030 여기에있는 것이 큰 O가 화면에, 컴퓨터 과학자는 일반적으로 사용 무엇 708 00:41:59,030 --> 00:42:03,640 알고리즘의 최악의 경우 실행 시간을 설명합니다. 709 00:42:03,640 --> 00:42:07,360 >> 다시 말하지만, 최악의 경우에, 그것은 완전히 상황에 따라 달라입니다. 710 00:42:07,360 --> 00:42:10,890 우리는 최악의 경우에 의해 무슨 뜻인지 전혀 우리가 얘기하고있는 그 문제에 따라 달라집니다. 711 00:42:10,890 --> 00:42:14,550 그러나 정렬의 경우, 어떻게 최악의 시나리오? 712 00:42:14,550 --> 00:42:17,860 그냥 우리에게 많은 일을 의미처럼 그 느낌 때문에 모든 것은 반대로 할 필요가있다. 713 00:42:17,860 --> 00:42:21,330 나는 우리가 지금까지 본 적이있는 알고리즘의 몇을 메모 해 두었다했습니다 : 714 00:42:21,330 --> 00:42:24,930 선형 검색, 전화 번호부 또는 종이 조각과 같은 바이너리 검색 715 00:42:24,930 --> 00:42:28,960 그런 다음 버블 정렬, 선택 정렬 및 삽입 정렬처럼 우리는 우리의 인간으로 본 716 00:42:28,960 --> 00:42:31,770 그리고 1 명의 결국 정렬을 병합이라고 할 겁니다. 717 00:42:31,770 --> 00:42:37,710 따라서 최악의 경우 선형 검색에 얼마나 많은 단계가 숫자 7을 찾을 걸리나요 718 00:42:37,710 --> 00:42:40,690 숀 얼굴과 같은 N 문이 있다면? >> [학생] N. 719 00:42:40,690 --> 00:42:44,180 N. 그래서 우리는 n의 큰 O를 작성하는거야. 720 00:42:44,180 --> 00:42:47,010 전 그냥 빈칸을 채워거야. 이건 그냥 빈 칸의 격자입니다. 721 00:42:47,010 --> 00:42:52,990 그러나 선형 검색에 가장 좋은 경우에, 7, 목록의 맨 시작 됐을 722 00:42:52,990 --> 00:42:55,520 숀은 목록의 시작을보고 시작했습니다 수 있습니다. 723 00:42:55,520 --> 00:42:58,940 당신은 선형 검색을 사용하고 그냥 왼쪽에서 오른쪽으로 또는 왼쪽으로 어쩌면 바로 확인하고면 - 724 00:42:58,940 --> 00:43:02,650 그들은 동등한 야 - 최고의 경우에 얼마나 많은 단계 수도 선형 검색 725 00:43:02,650 --> 00:43:05,550 션의 알고리즘 같은 겠지? 단 1 단계. 726 00:43:05,550 --> 00:43:09,450 >> 그래서 오메가 표기법 야 말거야. 727 00:43:09,450 --> 00:43:11,570 이것은 단지 자본 오메가 있습니다. 728 00:43:11,570 --> 00:43:15,000 오메가는 가장 사건이 시간을 실행 말하는 섹시한 방법입니다. 729 00:43:15,000 --> 00:43:18,900 따라서 가장 좋은 경우에 실행 시간은 단일 단계 또는 상수 단계입니다 - 730 00:43:18,900 --> 00:43:24,270 이 경우 1 -하지만 최악의 경우에, 큰 O, 실제로 N 단계입니다. 731 00:43:24,270 --> 00:43:28,110 그리고 여기이 한 세타, 우리는 실제로 지금 보는 않을거야. 732 00:43:28,110 --> 00:43:30,090 그것은이 특정 예제 관련이 없습니다. 733 00:43:30,090 --> 00:43:31,990 하지만, 지금은 이진 검색을 해 봅시다. 734 00:43:31,990 --> 00:43:35,990 이진 검색과 최악의 경우 몇 단계는 숫자 7을 찾을 걸릴 것입니다 735 00:43:35,990 --> 00:43:38,340 또는 우리가 찾고있는 무엇이든? >> [학생] 로그 N. 736 00:43:38,340 --> 00:43:40,980 아직도 알렉스 재수가있어처럼 있으므로 로그 n을 데려 갈 737 00:43:40,980 --> 00:43:44,030 우리가 정말 methodically 문제를 통해 일할 때 738 00:43:44,030 --> 00:43:48,220 그리고 그녀는 그녀를 바라 보았다 매우 마지막 문까지 7 번을 찾을 수 없습니다 739 00:43:48,220 --> 00:43:51,720 하더라도, 공정성에 그녀는 길을 따라 특정 문을 던져 해 740 00:43:51,720 --> 00:43:56,920 최악의 경우에는 이진 검색 로그 n의 실행 시간이 있습니다. 741 00:43:56,920 --> 00:43:59,230 또, 이번 나누어과 정복을 말한다. 742 00:43:59,230 --> 00:44:01,140 그런데 가장 좋은 경우는? 743 00:44:01,140 --> 00:44:04,790 그녀가 무대에 왔을 때 알렉스는 실제로 오른쪽에 가장 사건을 경험했다. 744 00:44:04,790 --> 00:44:07,290 그건 바이너리 검색에 얼마나 많은 조치를 취할거야? >> [학생] 1. 745 00:44:07,290 --> 00:44:09,380 1 단지 그녀는 운이 좋았을 때문입니다. 746 00:44:09,380 --> 00:44:12,520 오메가 가장의 경우 시나리오를 의미하기 때문에 그 사실은 괜찮아 747 00:44:12,520 --> 00:44:15,770 그냥 무작위로 엄청난 행운이라도 최선의 경우 입력. 748 00:44:15,770 --> 00:44:18,900 >> 자,이 역시 우리는 지금 휴가를 비워, 그냥가는거야. 749 00:44:18,900 --> 00:44:21,010 버블 정렬하는 방법에 대해 지금은? 750 00:44:21,010 --> 00:44:24,290 버블 정렬과 함께 최악의 경우, 모두, 역 순서입니다 751 00:44:24,290 --> 00:44:26,380 그래서 우리는 버블 링을 많이해야 해요. 752 00:44:26,380 --> 00:44:30,190 그러나 얼마나 많은 단계 최악의 경우에 데려 갈 것을? >> 제곱 [학생] N. 753 00:44:30,190 --> 00:44:32,550 당신이 생각하는 경우 때문, N 제곱했습니다 754 00:44:32,550 --> 00:44:36,410 목록이 완전히 거꾸로 인 경우 - 8 여기에있다, 1 여기있어 - 755 00:44:36,410 --> 00:44:40,530 문제는 거품이 시작할 때, 숫자 8은, 이쪽을 이동하는 것이다 756 00:44:40,530 --> 00:44:44,540 이런 식으로, 이런 식으로, 어디에은 최악의 경우에 7 번입니까? 757 00:44:44,540 --> 00:44:47,720 여기 그녀가 저기 남아 있습니다. 그래서 우리는 다시하고 다시 수행해야합니다. 758 00:44:47,720 --> 00:44:53,190 1 단계 다음에 n - - 2 단계 우리가 다음에 n 단계 N받을 곳 고. 759 00:44:53,190 --> 00:44:55,960 그리고 당신은 내 말을하면 - 당신은 가지를, 나가 곱하면 760 00:44:55,960 --> 00:45:00,110 그것은 약 우리가 지금 무시한다고 다른 조건을 결국 제곱 보군 - 761 00:45:00,110 --> 00:45:06,890 다음 최악의 거품 정렬에 제곱 습니되어 있지만요. 762 00:45:06,890 --> 00:45:09,490 그러나 버블 정렬과 최선의 경우는 어떤가요? 763 00:45:09,490 --> 00:45:13,050 어떻게 가장의 경우입니까? 숫자의 모든 이미 정렬됩니다. 764 00:45:13,050 --> 00:45:15,920 그리고 사용되는 경험적, 내가 사용하는 트릭, 무슨 일 일까 765 00:45:15,920 --> 00:45:20,110 나는 더 일을 한 적이 없음, 따라서 초기에 막을 수 있다는 것을 깨닫게? 766 00:45:20,110 --> 00:45:23,590 [학생]을 한 번 확인합니다. >> 한번 확인합니다. 하지만 길을 따라 대체 뭘 한 거지? 767 00:45:23,590 --> 00:45:26,130 내가 만든 얼마나 많은 스왑을 추적하는 데되었습니다. 768 00:45:26,130 --> 00:45:30,650 그리고 내 손가락에있는 모든 스왑을 계산하지 않은 경우, 그럼 더 일을 한 게 없어 깨달았습니다. 769 00:45:30,650 --> 00:45:34,300 난 분명히 다시 더 작업을 수행하지해야하지 않아요, 그럼 난 그냥 중지 할 수 있습니다. 770 00:45:34,300 --> 00:45:37,830 >> 따라서 버블 정렬의 가장 경우에 목록이 이미 정렬 된 경우, 771 00:45:37,830 --> 00:45:41,530 당신은 최고 사건이 시간을 실행 오메가 표기법이 무엇을 말을하는거야? 772 00:45:41,530 --> 00:45:48,040 이제 막 보군. 우리는 일을해야하지만, 우리는 작품의 한 거리의 가치를해야합니다. 773 00:45:48,040 --> 00:45:50,490 그리고 여기에이 부분을 공백으로 남겨거야. 774 00:45:50,490 --> 00:45:52,430 이제 선택 정렬. 775 00:45:52,430 --> 00:45:56,010 선택 정렬 내가 다시 다시 작은 사람을 뜯어했다. 776 00:45:56,010 --> 00:45:58,380 그리고 우리가 그였다의 실행 시간이 무슨 얘기를 했죠? 777 00:45:58,380 --> 00:46:00,590 - 그게 N 최악의 경우 제곱. 778 00:46:00,590 --> 00:46:05,220 그리고 불행하게도, 가장 경우에 또한 제곱 보군 779 00:46:05,220 --> 00:46:08,840 이 세상의 신이보기의 정렬이 없기 때문에, 780 00:46:08,840 --> 00:46:13,140 나는 내가 실제로 가장 작은 사람을 발견 한 전체 반복에 알아요. 781 00:46:13,140 --> 00:46:15,860 정말 선택 정렬 종류, 그 의미에서 엿 782 00:46:15,860 --> 00:46:17,920 하지만 거꾸로은 직관적는 거입니다. 783 00:46:17,920 --> 00:46:21,470 당신이해야 할 모든 루프에 대한 중첩 된 몇를 작성 있기 때문에, 잘 코딩 아주 쉽게 784 00:46:21,470 --> 00:46:24,620 일반적으로, 그 가장 작은 요소를 찾고지나 785 00:46:24,620 --> 00:46:27,840 다음이 목록의 끝 부분에 속하는 가장 작은 요소를 넣습니다. 786 00:46:27,840 --> 00:46:29,900 그래서 여기 너무 트레이드 오프가있을거야. 787 00:46:29,900 --> 00:46:34,440 당신이 생각하고 실제로 코드를 작성하여 무언가를 개발하는 데 걸리는 시간의 양 788 00:46:34,440 --> 00:46:39,460 당신은 알고리즘보다 빠르고 성능을 원하는 경우 잘 시간이 더 걸릴 수 있습니다. 789 00:46:39,460 --> 00:46:41,780 >> 그러나 최대 코드 무언가 당신이 정말로 단지 종류의 경우 신속하고 더러운 790 00:46:41,780 --> 00:46:45,000 불과 가지, 당신이 생각할 수있는 바보 가능한 아이디어를 791 00:46:45,000 --> 00:46:47,580 코드에 몇 분 정도 걸릴 수 있습니다,하지만 큰 데이터 세트 792 00:46:47,580 --> 00:46:49,580 당신의 알고리즘은 실행 시간이 걸릴 수 있습니다. 793 00:46:49,580 --> 00:46:51,690 그리고 I 대학원 때때로 이러한 무역 오프를 만들 수있을거야. 794 00:46:51,690 --> 00:46:55,660 그것은 오전 3시 것, 몇 매우 큰 데이터 세트를 분석하려고했던 795 00:46:55,660 --> 00:46:59,650 제가하는 보안 연구에 관한, 그리고 중 5 분 지출되었다 796 00:46:59,650 --> 00:47:03,210 조정 데이터를 분석하고 잠을 잘 나의 프로그램을 797 00:47:03,210 --> 00:47:08,420 그 즉시 실행하고 다시 잠을 갈 수 있도록하거나 제대로 받고 8 시간 보내십시오. 798 00:47:08,420 --> 00:47:10,530 그리고 거기에 너무 그것은 의식의 결정 이죠. 799 00:47:10,530 --> 00:47:12,740 적은 개발 시간 더 잠을 자고있어. 800 00:47:12,740 --> 00:47:14,780 돌이켜 보면, 아마 권장 안됩니다 801 00:47:14,780 --> 00:47:19,120 여기에 목표는 코드 품질을 최적화 할 때하면 802 00:47:19,120 --> 00:47:21,280 하지만 너무 현실 세계에서 매우 합리적인 트레이드 오프입니다. 803 00:47:21,280 --> 00:47:25,130 적은 시간, 적은 성능이나 반대도 마찬가지입니다. 804 00:47:25,130 --> 00:47:28,110 그래서 여기에 우리가 결국 세타에 대해 이야기 할 수있는 기회를 얻을. 805 00:47:28,110 --> 00:47:32,830 세타 표기법은 컴퓨터 과학자 대화에서 가져 할 수있는 일입니다 806 00:47:32,830 --> 00:47:36,160 큰 O와 오메가는 동일 일어날 때. 807 00:47:36,160 --> 00:47:40,160 당신은 세타가 정말이 빡빡 행의 종류입니다 메시지를 보내 말한다. 808 00:47:40,160 --> 00:47:43,340 시나리오 좋은 또는 나쁜 여부에 상관없이, 그것은 제곱 습니 없어요. 809 00:47:43,340 --> 00:47:46,510 그래서 여기이 기사에 단지 관련 없습니다. 810 00:47:46,510 --> 00:47:48,560 삽입 정렬은 우리가 바라 보았다 마지막입니다 811 00:47:48,560 --> 00:47:50,830 어디 단지 적절한 장소에 모두 삽입되었습니다. 812 00:47:50,830 --> 00:47:54,930 우리가 본 것을 본다면 가장 좋은 경우 어떻게 삽입 정렬의 실행 시간 였죠? 813 00:47:54,930 --> 00:47:57,250 [학생] 최고의 사건? >> 가장 좋은 케이스. 814 00:47:57,250 --> 00:48:00,100 >> 가장 좋은 경우에 모두 정렬 있기 때문에 그것은, N되었습니다 815 00:48:00,100 --> 00:48:02,580 그리고 새미하고 다른 하나는 정말 전혀 이동했다. 816 00:48:02,580 --> 00:48:04,610 그들은 바로 이곳에서 이미 있었다. 817 00:48:04,610 --> 00:48:08,570 가장 좋은 경우에 따라서 삽입 정렬이 경우, N입니다. 818 00:48:08,570 --> 00:48:12,770 그러나 최악의 경우는 제곱 N의 종류입니다. 이유는 무엇입니까? 819 00:48:12,770 --> 00:48:16,230 인간의 내 목록에 역순 인 경우는, 820 00:48:16,230 --> 00:48:21,260 처음 숫자 8을 시작하고 바로 여기에 올바른 위치에 그를 삽입하거나 그녀. 821 00:48:21,260 --> 00:48:25,270 옆으로 이사어요. 이 사람들은 그 사람을 정렬되지 않은 있거나 그녀는 정렬됩니다. 822 00:48:25,270 --> 00:48:28,970 하지만 지금은 누가 다음에 찾을 일이야? >> [학생] 7. 823 00:48:28,970 --> 00:48:31,250 최악의 경우 7은 반대 순서로 잖아. 824 00:48:31,250 --> 00:48:34,920 >> 그래서 여기 7입니다. 7 어디에 속해 있습니까? 물론 제 뒤에. 825 00:48:34,920 --> 00:48:39,460 그러나 지금은 7 사실은, 바로 내 뒤에 만 8 번 뒤에하지 귀속 826 00:48:39,460 --> 00:48:41,880 나는 "말 실례지만, 8 번해야하므로,이 방법을 이동합니다 수 있습니다 827 00:48:41,880 --> 00:48:44,640 "7를위한 공간을 마련하기 위해?" 지금은 6 발생합니다. 828 00:48:44,640 --> 00:48:48,530 "아,, 숫자 8 숫자 7 실례, 당신은 6 공간을 확보하기 위해 이동할 수?" 829 00:48:48,530 --> 00:48:52,360 다시 말해, 삽입 정렬로, 나는 많은 운동을하고 안하더라도, 830 00:48:52,360 --> 00:48:56,330 제 뒤에 사람들이 더 많은 일을하고 있으며, 사람이 시간을 비용있어 그. 831 00:48:56,330 --> 00:48:58,000 이 컴퓨터 시간을 비용거야. 832 00:48:58,000 --> 00:49:01,450 따라서 삽입 정렬의 경우 우리는 여전히 고통 받고 있습니다. 833 00:49:01,450 --> 00:49:06,260 이 단계의 총 수를 추가 할 경우, 약 N 제곱 때리고 결국 834 00:49:06,260 --> 00:49:11,160 이 사람들은 그 목록에 다시 삽입 할 인간을위한 공간을 확보해야합니다 때문입니다. 835 00:49:11,160 --> 00:49:15,960 그리고이 경우에는 세타는 손에 특정 이야기에 적용되지 않습니다. 836 00:49:15,960 --> 00:49:21,100 그거 좋네요 좋은 전부입니다. 우리는 실행 시간에 대해 얘기 중이 3 가지 다른 방법이 있습니다. 837 00:49:21,100 --> 00:49:26,370 우리가 실제로 알고리즘을 코딩하려한다면이 실제 측면에서 무엇을 의미합니까? 838 00:49:26,370 --> 00:49:31,620 >> 거기에 더 나은 알고리즘이 있다는 내가 제안하자 839 00:49:31,620 --> 00:49:33,740 그거 자체는 몇 가지 무역 오프가 있습니다. 840 00:49:33,740 --> 00:49:36,890 우리는 정렬 병합 전화를하고 있으며,이 마법의 알고리즘의 일종 이죠 841 00:49:36,890 --> 00:49:42,840 그건 정말 빠르고 어떻게 든 작동, 그것은 적어도 의사에 표현하기 위해 너무 쉬운 일이야. 842 00:49:42,840 --> 00:49:46,900 이 알고리즘 병합 정렬의 구현은 다음과 같이 될 것입니다. 843 00:49:46,900 --> 00:49:50,860 정신 검사가 먼저 - 무엇이든 N 번호, N 사람들 - 당신은 N 요소를 제공 할 때. 844 00:49:50,860 --> 00:49:56,340 n은 2보다 적은 경우, 정렬 방금 중지 병합합니다. 너무 말을 반환합니다. 845 00:49:56,340 --> 00:50:00,830 n은 2보다 작다면 왜 멈출까요? >> [안 들리게 학생 응답] 846 00:50:00,830 --> 00:50:04,480 맞아. 또, n은 목록의 번호입니다, n은리스트의 크기입니다. 847 00:50:04,480 --> 00:50:07,660 n은 2보다 적은 경우 즉, 귀하의 목록 중 1 의미 848 00:50:07,660 --> 00:50:09,640 이 1 번이라면 어디서 분명히 정렬하고 849 00:50:09,640 --> 00:50:11,710 또는 정렬 할 수있는 게 없다고이 경우 0,, 850 00:50:11,710 --> 00:50:13,570 그래서 우리는 기본 케이스의 종류가 필요합니다. 851 00:50:13,570 --> 00:50:20,350 목록 상관 방금 없습니다 너무 짧은 경우, 문자 그대로 아무 짓도하지 않습니다. 돌아갑니다. 852 00:50:20,350 --> 00:50:25,090 그렇지 않으면 요소의 왼쪽 절반을 정렬 한 다음, 요소의 오른쪽 절반을 정렬 853 00:50:25,090 --> 00:50:27,410 그런 다음 2 정렬 절반을 병합합니다. 854 00:50:27,410 --> 00:50:32,130 >> 내가 얼마나 요소를 정렬하는 방법을 부탁 해요된다 이런 종류의 작은 컨닝 것 같습니다 855 00:50:32,130 --> 00:50:34,900 당신은 "오른쪽 절반을 정렬, 왼쪽 절반을 정렬합니다."말씀이신가요 856 00:50:34,900 --> 00:50:37,240 난 대답 "좋아. 어떻게 왼쪽 절반을 정렬합니까?" 857 00:50:37,240 --> 00:50:40,670 "완료 후, 왼쪽 반은 왼쪽 절반을 정렬 왼쪽 반은 오른쪽 절반을 정렬합니다." 858 00:50:40,670 --> 00:50:44,060 당신은 주기적는 정렬의 의미 정의는거야 859 00:50:44,060 --> 00:50:46,790 하지만이 경우 실제로 화려한 걸 밝혀졌다. 860 00:50:46,790 --> 00:50:50,230 그것은 진정으로 끝나지 않는이 악순환의 고리 아닙니다 861 00:50:50,230 --> 00:50:52,550 언제까지 이래야 않기 때문에? >> [학생]는 당신이 한 일에 도달합니다. 862 00:50:52,550 --> 00:50:54,220 당신이 한 일에 도달합니다. 863 00:50:54,220 --> 00:50:57,850 당신이 8 사람들과 시작 될 수도 있고 내가 무슨 말을하더라도 자, "이 사람들의 왼쪽 절반을 정렬 864 00:50:57,850 --> 00:51:00,480 이 사명은 "그럼 말,"어떻게 왼쪽 절반을 정렬합니까? " 865 00:51:00,480 --> 00:51:03,450 "자, 여기 12 명을 정렬합니다." 그리고 당신은 같은거야 "좋아, 좋아." 866 00:51:03,450 --> 00:51:05,520 "어떻게 사람들의 왼쪽 절반을 정렬합니까?" 867 00:51:05,520 --> 00:51:09,040 "그냥 여기에 1 명을 정렬." 이제 화려한 계시은 무엇입니까? 868 00:51:09,040 --> 00:51:13,050 나는 1 인을 정렬해야합니다. 완료. 어떤 작업을 수행 할 필요가 없습니다. 869 00:51:13,050 --> 00:51:16,580 하지만 지금은이 사람을 정렬해야하지만 한 사람, 상관이야. 870 00:51:16,580 --> 00:51:21,490 >> 그래서 마법은 분명이 세 번째 단계에 있습니다 정렬 절반을 병합합니다. 871 00:51:21,490 --> 00:51:25,770 따라서 병합 정렬이 뛰어난 통찰력을 필요 당신은 큰 문제를 어기면 872 00:51:25,770 --> 00:51:28,650 이 작은 동일한 크기의 문제로 873 00:51:28,650 --> 00:51:32,710 그리고 끝 부분에있는 작은 솔루션을 함께 접착제, 그냥, 874 00:51:32,710 --> 00:51:34,720 나는 우리가 훨씬 더 [터치 소리]를 많이 할 수 있다는 제안 875 00:51:34,720 --> 00:51:38,050 선택 정렬이나 삽입 정렬의 초과했습니다. 876 00:51:38,050 --> 00:51:40,690 사실 난 반 시간 동안이나 그렇게 무시하고있어,하지만 난 정말 무슨 일이 일어난 거지? 877 00:51:40,690 --> 00:51:45,040 오늘 밖에. [지 - 잉 소리] [웃음] 878 00:51:45,040 --> 00:51:49,660 그래서 우리는 우리의 친구 롭 보덴에서 약간의 도움을 볼 수 있는지 보자. 879 00:51:49,660 --> 00:51:52,810 병합 정렬의 과정에서 2 개의 대형 단계가 있습니다. 880 00:51:52,810 --> 00:51:56,400 첫째, 지속적으로 절반으로 컵의 목록을 분할 881 00:51:56,400 --> 00:51:59,610 우리는 그들, 그냥 1 컵과 목록의 무리가 될 때까지. 882 00:51:59,610 --> 00:52:02,150 목록 홀수가 포함되어있는 경우 걱정하지 마세요 883 00:52:02,150 --> 00:52:04,830 당신은 그들 사이 완벽하게 깨끗한 몫을 할 수 없습니다. 884 00:52:04,830 --> 00:52:08,740 그냥 임의로 추가 컵 인치를 포함하는 목록을 선택 885 00:52:08,740 --> 00:52:11,320 그럼이 목록을 분할 보자. 886 00:52:12,420 --> 00:52:14,570 이제 우리는이 목록을 수 있습니다. 887 00:52:18,930 --> 00:52:20,930 이제 우리는 4 목록이 있습니다. 888 00:52:25,730 --> 00:52:28,740 이제 우리는 각 목록에서 컵 8리스트를 갖추고 있습니다. 889 00:52:28,740 --> 00:52:31,520 그래서 단계 1 거에요. 890 00:52:31,520 --> 00:52:37,280 단계 2 우리는 반복적으로 우리가 전에 배운 병합 알고리즘을 사용하여 목록의 쌍을 병합합니다. 891 00:52:37,280 --> 00:52:44,320 108 15 병합 우리는 목록을 15, 108이 생깁니다. 892 00:52:45,240 --> 00:52:51,330 50 4 병합 우리는 4, 50이 생깁니다. 893 00:52:51,330 --> 00:52:56,950 8 42 병합 우리는 8, 42에서 소개합니다. 894 00:52:57,790 --> 00:53:04,360 23와 16을 병합 우리는, 16과 23이 되죠. 895 00:53:04,360 --> 00:53:08,030 지금 우리의 모든 목록의 크기는 2의합니다. 896 00:53:08,030 --> 00:53:10,980 4 목록의 각이 정렬되고 있다는 사실을 알 수, 897 00:53:10,980 --> 00:53:14,230 그래서 우리는 다시리스트의 쌍을 병합 시작할 수 있습니다. 898 00:53:14,230 --> 00:53:22,150 15 108 4 50 병합하면 우리는 먼저 다음 15 4을 899 00:53:22,150 --> 00:53:26,250 다음 50 후 108 번. 900 00:53:26,250 --> 00:53:33,020 8, 42 및 16, 23을 병합 먼저 다음 8 16, 가져 901 00:53:33,020 --> 00:53:37,170 다음 23 다음 42. 902 00:53:37,170 --> 00:53:42,490 이제 우리는 크기가 4 단 2 목록을 가지고 각각의가 정렬됩니다. 903 00:53:42,490 --> 00:53:45,940 이제 우리는 이러한 두 목록을 병합합니다. 904 00:53:45,940 --> 00:53:54,230 먼저 우리가 4를 손에 넣은 다음 우리는 8을, 우리는 15을 905 00:53:54,230 --> 00:54:05,280 16 23, 42 및 50과 108. 906 00:54:05,280 --> 00:54:09,020 그리고 우리는 끝났어. 우리는 지금 정렬 목록을 수 있습니다. 907 00:54:09,020 --> 00:54:13,740 >> 롭은 우리가 아직 완료하지 않은 것을 활용하는 것 같아요. 908 00:54:13,740 --> 00:54:16,540 이 제안되었지만, 우리는 실제로하지 않았어. 909 00:54:16,540 --> 00:54:19,230 그는 제안 컵 물리적 짓을했습니다 910 00:54:19,230 --> 00:54:23,680 그는 시간 외에 어떤 리소스를 소비했다. >> [학생] 우주. >>는 공간이었다. 911 00:54:23,680 --> 00:54:27,360 여기 공간을 한 곳에서 그는 이중 레벨 테이블이 종류가 있다는 사실 912 00:54:27,360 --> 00:54:31,960 여기 아래 공간은 실제로 사람이 두 배나 많은 공간을 사용한다는 뜻되었다 913 00:54:31,960 --> 00:54:36,390 삽입 정렬, 버블 정렬, 또는 선택 정렬 - - 지금까지 알고리즘의 등 914 00:54:36,390 --> 00:54:40,780 그는 앞뒤로 이동 일인데이 추가 공간을 활용 한 915 00:54:40,780 --> 00:54:42,600 순서로 일을 유지하면서. 916 00:54:42,600 --> 00:54:47,540 우리가 정렬 목록에있어 기분이 비록 그 때까지 시간이 좀 걸 렸어요처럼, 그 느꼈다. 917 00:54:47,540 --> 00:54:51,060 현실에서는, 어떤 롭 일이 것은 정확히이 알고리즘했다. 918 00:54:51,060 --> 00:54:56,780 그는 먼저 크기 N의 문제를 가져다가 왼쪽 반 오른쪽 절반에를 나눈 값입니다. 919 00:54:56,780 --> 00:54:59,380 그는 컵을 이동 때입니다. 그리고 그 과정을 반복했다. 920 00:54:59,380 --> 00:55:03,390 그는 여기 이상 여기에 2 개 중 2 개의 세트로 4 나눈 값입니다. 921 00:55:03,390 --> 00:55:08,520 그리고 그 과정을 반복하고 이러한 다양한 컵 각 1 2 세트로 2 분할. 922 00:55:08,520 --> 00:55:11,000 화려한 기회가 발생 곳 고. 923 00:55:11,000 --> 00:55:15,840 이야기 그 시점에서, 롭, 크기 1의 8 목록을 가지고 924 00:55:15,840 --> 00:55:18,860 하는 모든이 이미 정렬되었습니다. 925 00:55:18,860 --> 00:55:20,630 >> 그래서 그 사람은 뭘를 진행 했죠? 926 00:55:20,630 --> 00:55:25,260 Pairwise 그는이 정렬 목록이 정렬 목록을 데리고을 통합. 927 00:55:25,260 --> 00:55:28,200 그리고,이 하나를 들고 그들을 병합, 다음이 하나를하고이를 통합 928 00:55:28,200 --> 00:55:30,670 다음이 하나 그들을 병합. 929 00:55:30,670 --> 00:55:32,390 그리고 그가 무슨 다음 짓을 한거야? 930 00:55:32,390 --> 00:55:36,580 그 후 더 큰 목록을 다시 합병 후 큰 목록을 다시 합병. 931 00:55:36,580 --> 00:55:41,170 당신은 지금 막 직관적으로 생각해면, 정말이 대체 뭘 한 거지? 932 00:55:41,170 --> 00:55:45,450 그는 반으로 반으로 반으로 반으로 문제를 분리했습니다 933 00:55:45,450 --> 00:55:47,600 이 슈퍼 작은 목록을 보려면 여기를 클릭하십시오. 934 00:55:47,600 --> 00:55:51,290 그럼 그 사람은 더블, 더블, 더블, 더블를 결합하는 것 같아요. 935 00:55:51,290 --> 00:55:54,120 그래서 그는 우리가 지금까지 본 적이만큼 작품으로 두 번 짓 936 00:55:54,120 --> 00:55:56,930 분리와 정복,하지만 큰 거래를 포함하는 걸로. 937 00:55:56,930 --> 00:55:59,630 두 배는 더 일을 그렇게 큰 거래되지 않습니다. 단지 상수 요소입니다. 938 00:55:59,630 --> 00:56:03,920 그리고 전에도 많이 우리의 산술 식처럼, 단지 일정한 요인을 건너 갈거야 939 00:56:03,920 --> 00:56:10,170 2 배처럼. 누가 무슨 상관이야? 아직도 단계 많이의 2 배, 2 억 이죠. 940 00:56:10,170 --> 00:56:13,160 그래서이 합병 단계는 키 통찰력을 것 같습니다. 941 00:56:13,160 --> 00:56:17,000 의 전에 단지 숫자 이런 식으로 걸어 가자 - 아, 그건 아직 계속 할 수 없습니다. 942 00:56:17,000 --> 00:56:22,890 의는이 숫자 만 실제로 어떻게되는지 볼 수 통과 보자. 943 00:56:22,890 --> 00:56:25,940 이 대부분이 좀 가난한 사람의 애니메이션입니다. 944 00:56:25,940 --> 00:56:27,750 의이을 제안 보자. 945 00:56:27,750 --> 00:56:31,480 병합 정렬의 실행 시간은 - 우리가 이런 이야기의 방법이 필요합니다. 946 00:56:31,480 --> 00:56:34,380 이건 수학이 아니에요,이 자신을 표현하는 간결 방식이긴합니다. 947 00:56:34,380 --> 00:56:39,080 따라서 T는 시간을 나타내며, n은 무엇을 제시 하는가? >> [학생]의 크기 - 948 00:56:39,080 --> 00:56:41,400 >> [Malan] 문제의 크기, 사람의 번호입니다. 949 00:56:41,400 --> 00:56:45,470 그래서 N 사람들을 정렬 할 수있는 실행 시간 시간 0 금액이 될 거라 주장하고있어 950 00:56:45,470 --> 00:56:50,290 N은 1 컵 또는 전혀 컵이 경우 정렬 아무 상관이 없기 때문에, 2보다 작습니다. 경우 951 00:56:50,290 --> 00:56:55,160 하지만 더 일반적으로, 내가 실행 시간이 N 요소를 정렬 할 것을 제안거야 952 00:56:55,160 --> 00:56:59,350 그 왼쪽 절반을 정렬하는 데 걸리는 시간을 더한 오른쪽 절반이 될 것입니다 953 00:56:59,350 --> 00:57:03,110 플러스 -이 추가 + n은 뭐죠? >> [학생] 병합 정렬. 954 00:57:03,110 --> 00:57:07,260 [Malan] 당신이 여기 N / 2 요소가있는 경우 때문에 실제로, 합병있어 955 00:57:07,260 --> 00:57:11,500 당신이 여기 N / 2 요소를 가지고이 그들을 병합하는 방법을 많은 시간이 걸립니까? 956 00:57:11,500 --> 00:57:15,050 그냥 롭처럼, 당신이 여기이 뽑은해야 아마, 여기에 뽑아 내다 957 00:57:15,050 --> 00:57:17,120 여기에 털을 뽑아 내다, 여기 다듬 여기에 뽑아 내다. 958 00:57:17,120 --> 00:57:19,400 당신은 한 번 컵의 각을 터치해야합니다. 959 00:57:19,400 --> 00:57:22,030 4 컵 + 4 컵이 있다면 그리고, 그 8 컵입니다 960 00:57:22,030 --> 00:57:25,200 또는 더 일반적으로, 8 N 컵. 961 00:57:25,200 --> 00:57:28,470 따라서 합병 단계는 우리는 N으로 표현할 수 962 00:57:28,470 --> 00:57:31,330 그 말 그대로 횟수 물리적으로 접촉 로브를 포함 963 00:57:31,330 --> 00:57:33,410 그 스티로폼 컵 중 하나입니다. 964 00:57:33,410 --> 00:57:35,850 이제 임의의 예를 한번 해보자 구. 965 00:57:35,850 --> 00:57:41,850 16 컵이 있다면, 어떻게 롭의 알고리즘, 16 컵을 사용하여 정렬의 실행 시간있어? 966 00:57:41,850 --> 00:57:44,710 이 8 컵을 정렬 할 걸리는 시간이 2 배 양 967 00:57:44,710 --> 00:57:46,920 여기, 우리가 8 컵을 가지고 있기 때문에, 8 컵. 968 00:57:46,920 --> 00:57:51,520 난 정말 우리가 잠시 동안 T로 일반화하고 얼마나 오래 걸리는지 모르겠어요. 969 00:57:51,520 --> 00:57:53,320 누가이 몇인지 아는 사람? 970 00:57:53,320 --> 00:57:58,990 하지만 지금은 반복적으로 또는 반복적으로 같은 질문을을 정렬 할 수 있습니다. 971 00:57:58,990 --> 00:58:01,920 8 컵을 정렬하는 데 시간이 얼마나 걸리나요? 972 00:58:01,920 --> 00:58:07,030 내가 무슨 말을하려고 해요 8 컵, 이건 4 컵 + 4 컵을 정렬하는 데 걸리는 시간의 양을 필요 973 00:58:07,030 --> 00:58:08,880 그것들을 함께 병합. 974 00:58:08,880 --> 00:58:13,080 좋아요. 우리는 이미주기에 있어요. 4 컵을 정렬하는 데 얼마나 걸리나요? 975 00:58:13,080 --> 00:58:19,150 이 4 컵을 정렬하는 데 걸리는 시간은 2 컵 플러스 2 컵 정렬 플러스 합병 과정입니다. 976 00:58:19,150 --> 00:58:21,440 좋아요. 2 컵을 정렬하는 데 얼마나 걸리나요? 977 00:58:21,440 --> 00:58:26,290 2 컵은 1 컵을 정렬하는 데 걸리는 시간의 양이 플러스가 다른 컵을 정렬하는 데 걸리는 시간입니다 978 00:58:26,290 --> 00:58:29,040 플러스가 병합하는 데 걸리는 시간의 양이되는데,이 단 2 명입니다. 979 00:58:29,040 --> 00:58:33,340 >> 좋아요. 마지막 질문입니다. 1 컵을 정렬하는 데 얼마나 걸리나요? 980 00:58:33,340 --> 00:58:37,260 여기에 우리가 이전에 죽이 잘 맞는 친구 예측하는 기본 케이스입니다. 981 00:58:37,260 --> 00:58:42,250 이 문제의 가장 작은를 정렬하려면 어떠한 노력이 필요 없다는 사실 982 00:58:42,250 --> 00:58:44,120 수단 이제, 초등학교 스타일의 종류, 983 00:58:44,120 --> 00:58:46,460 우리는 인치 다시이 숫자를 연결해 시작할 갈 수 984 00:58:46,460 --> 00:58:50,630 우리는 지금 1 T가 뭔지 알아, 그래서 제가 1 T 0에 연결 할 수 있습니다. 985 00:58:50,630 --> 00:58:54,420 그때 에게라도에 연결할 수 있습니다 (2)의 T, 나에게 대답을 할 것입니다. 986 00:58:54,420 --> 00:58:56,930 그건 내게 내가 에게라도에 연결할 수 4 T를 제공 할 것입니다. 987 00:58:56,930 --> 00:58:58,920 그건 내게 내가 에게라도에 연결할 수 8 T를 제공 할 것입니다. 988 00:58:58,920 --> 00:59:04,330 그리고 실제로이 답변에 꽂아 그 수학을 할 경우, 989 00:59:04,330 --> 00:59:08,590 그때 나는 16 T 64 드리고 있습니다. 990 00:59:08,590 --> 00:59:12,090 그리고 64 무엇을 나타 냅니까? 991 00:59:12,090 --> 00:59:15,700 T는 16 인 경우, 예, 16 시간 4입니다. 992 00:59:15,700 --> 00:59:20,120 그래서이 물건의 실행 시간이 좀 병합라고 지금 주장 - 993 00:59:20,120 --> 00:59:22,590 이 우리가 지금까지 본 것들 중에서 가장 좋은 될 것입니다 - 994 00:59:22,590 --> 00:59:26,160 라고 할 것 N 로그 N입니다 995 00:59:26,160 --> 00:59:31,140 얼마나 많은 시간이 반으로 컵을 아주 많이 분할 롭 수 있기 때문에? n을 기록합니다. 996 00:59:31,140 --> 00:59:34,370 그것은 전화 번호부의 예와 같은, 이것은 그 자체 계산 예를 들어 같은입니다. 997 00:59:34,370 --> 00:59:36,380 >> 몇 번 반으로 무언가를 나눌 수 있습니까? 998 00:59:36,380 --> 00:59:38,410 그러나,이 병합 단계가 있습니다. 999 00:59:38,410 --> 00:59:42,920 당신은 다시 다시 다시 이분의 일에 컵을 나누어해야 할 수도 있습니다 1000 00:59:42,920 --> 00:59:45,640 하지만 자네는 자네가가는 때마다 병합해야합니다. 1001 00:59:45,640 --> 00:59:48,270 그리고 우리는 N 개의 컵을 통합하는 N 조치를 취하고 있다고 밝힌 바있다 1002 00:59:48,270 --> 00:59:52,060 당신은 한 잔을 뽑아 낸하기 때문에, 한 잔을 뽑아 낸, 당신은 한 번 잔을 터치해야 1003 00:59:52,060 --> 00:59:53,510 단지 롭처럼 했어요. 1004 00:59:53,510 --> 00:59:59,430 우리가 뭔가 로그 n 번을하고 우리는 그 반복의 각에 대한 N 일을하고있는면은, 1005 00:59:59,430 --> 01:00:03,090 그 halvings 각, 우리는 n 번 로그 N 수 있습니다. 1006 01:00:03,090 --> 01:00:07,220 우리가이 예제에서 16에 플러그를 꽂으면, 16 시간 16 로그인 - 1007 01:00:07,220 --> 01:00:10,600 제가베이스를 그려 적이 없다 때문에이 지금의 경우 이유에 대해 걱정하지 마십시오 - 1008 01:00:10,600 --> 01:00:16,100 하지만 16 기지 2 로그, 시간 4 64 16 4. 1009 01:00:16,100 --> 01:00:22,350 그러나 반대로, 우리는 16의 숫자를 버블 정렬이나 선택 정렬이나 삽입 정렬을 사용했을 경우, 1010 01:00:22,350 --> 01:00:26,420 여기서 n은 16 경우 실행 시간은 어떻게 갔었을거야? 1011 01:00:26,420 --> 01:00:33,310 이는 256입니다, 16 제곱, 귀하가 매우 모든 수학을 준수하지 않은 경우에도 것입니다 1012 01:00:33,310 --> 01:00:38,390 256은 64보다 큰 수 있습니다. 그건 정말 여기에 마법의 테이크 아웃입니다. 1013 01:00:38,390 --> 01:00:41,990 그리고 pset에 의지으로 작은 예제에서이 일을 일하는 실현 1014 01:00:41,990 --> 01:00:44,260 그 훨씬 더 직관적 모두 있습니다. 1015 01:00:44,260 --> 01:00:49,070 하지만 실제로는이 알고리즘의 느낌의 관점에서 어떤 의미인지하면이 있습니다 : 1016 01:00:49,070 --> 01:00:54,520 우리가 실제로 여기에 병합 정렬을 보면 - 내가 여기이 창에 올려 보자 - 1017 01:00:54,520 --> 01:00:58,560 이게 우리가 이러한 알고리즘의 모든 3이된다 약간 다른 예입니다 - 1018 01:00:58,560 --> 01:01:01,440 버블, 선택, 그리고 병합 - 옆으로 단 측면을. 1019 01:01:01,440 --> 01:01:03,740 >> 그들은 모두 랜덤 바 시작했으며, 좋네요. 1020 01:01:03,740 --> 01:01:06,240 아무도 다른 이상의 근본적인 이점이 없습니다. 1021 01:01:06,240 --> 01:01:09,500 나는 순간에 갈거야하면 이러한 애니메이션의 각 클릭 - 시작 시작 시작 - 1022 01:01:09,500 --> 01:01:13,270 제가 할 수있는 한 빠른 속도로, 그래서 그걸 동시에 약, 그들은 모든 시작, 1023 01:01:13,270 --> 01:01:17,450 시간을 실행하는 버블 정렬의 최악 사건이 무엇인지가 생각 해요? >> 제곱 [학생] N. 1024 01:01:17,450 --> 01:01:21,560 N은 제곱. 시간을 실행하는 선택 정렬의 최악의 경우는? N은 제곱. 1025 01:01:21,560 --> 01:01:25,150 그리고 병합 정렬은 분명히 있습니다 - 당신은 매우 모든 수학을 준수하지 않은 경우에도, 지금 1026 01:01:25,150 --> 01:01:30,610 그것은 훨씬 더 직관적으로 시간이 지남에 따라이 될 것 - 우리가 주장 n 번 로그 N입니다. 1027 01:01:30,610 --> 01:01:35,210 그리고 로그가 N보다 엄격하게 적은 N 일단 큰 숫자를 가지고 있기 때문에하면, 1028 01:01:35,210 --> 01:01:40,230 n 번 로그 n은 n 번보다 작은 n 또는 N 제곱입니다. 1029 01:01:40,230 --> 01:01:44,410 그래서, 사실 실행 시간의 측면에서 더 나은 알고리즘을 할 기분이 1030 01:01:44,410 --> 01:01:50,380 n 번 로그 N 등의 제곱 N에 반대? 여기 우리는 간다. 를 클릭, 클릭, 클릭합니다. 1031 01:01:55,690 --> 01:01:58,650 >> 그게 병합 정렬과 같은 무언가를 사용하는의 의미입니다. 1032 01:01:58,650 --> 01:02:01,680 우리는 순간을 갖추고 있습니다. 여기서 무슨 일이 일어날 지 보자. 1033 01:02:09,440 --> 01:02:12,440 누구 돈 버블 정렬에 ㅠ ㅠ? 1034 01:02:14,960 --> 01:02:16,730 그것은 오히려 가끔 입력에 따라 달라집니다. 1035 01:02:16,730 --> 01:02:18,120 어디 봅시다. 1036 01:02:18,120 --> 01:02:23,320 이리와. 그는 따라 잡는 느낌. >> [학생] 버블 정렬로 이동합니다! 1037 01:02:23,320 --> 01:02:27,370 [학생들이 웅성 대는 소리] 1038 01:02:27,370 --> 01:02:29,120 [Malan] 네, 네. 1039 01:02:29,120 --> 01:02:34,520 [웅성 대는 학생]가,가,가! 1040 01:02:37,210 --> 01:02:40,450 [박수] [모두 환호]를 1041 01:02:40,450 --> 01:02:46,240 이제 한 마지막으로, 최종 데모와 함께하면 수학은 주위에 마음을 포장하기 조금 어렵습니다 1042 01:02:46,240 --> 01:02:49,280 아니면 시각화 종류의, 당신은 실제로 속도를들을 수 1043 01:02:49,280 --> 01:02:51,000 다르게 서로 다른 알고리즘. 1044 01:02:51,000 --> 01:02:53,900 이와 같은 사실은 실제로 동료가 들리는 것을 만든 애니메이션 사람입니다 1045 01:02:53,900 --> 01:02:56,980 교환의 과정과 바의 높이. 1046 01:02:56,980 --> 01:03:00,440 우리가 보 겠지만, 몇 가지 더 정렬 알고리즘은 사람들이 생각 한 그쪽 있습니다. 1047 01:03:00,440 --> 01:03:03,660 첫 번째 사람은 삽입 정렬 될 것입니다, 그리고 이것은 날고 1048 01:03:03,660 --> 01:03:07,090 그리고 당신에게 어떻게 이러한 다양한 알고리즘 작업의 음성 느낌을 제공합니다. 1049 01:03:07,090 --> 01:03:09,080 다음은 삽입 정렬입니다. 1050 01:03:09,080 --> 01:03:18,410 [전자음] 1051 01:03:18,410 --> 01:03:20,730 [Malan] 버블 정렬. 1052 01:03:20,730 --> 01:03:46,850 [전자음 빠르게] 1053 01:03:46,850 --> 01:03:48,950 [Malan] 선택 정렬. 1054 01:03:48,950 --> 01:04:03,580 [전자음 빠르게] 1055 01:04:03,580 --> 01:04:05,770 [Malan] 병합 정렬. 1056 01:04:05,770 --> 01:04:17,270 [전자음] 1057 01:04:17,270 --> 01:04:20,180 [웃음] [삡는 속도가 느려]를 1058 01:04:20,180 --> 01:04:22,590 [Malan] 그​​놈 정렬. 1059 01:04:22,590 --> 01:04:38,580 [전자음] 1060 01:04:39,740 --> 01:04:46,150 >> 이 CS50입니다. 우리는 다음 주에 볼 수 있습니다. [박수와 환호] 1061 01:04:46,150 --> 01:04:48,000 >> [CS50.TV]