1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [MUSIC CHƠI] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. Malan: Đây là CS50. 5 00:00:12,550 --> 00:00:14,612 Và đây là sự bắt đầu của tuần ba. 6 00:00:14,612 --> 00:00:16,820 Vì vậy, chúng tôi đã có rất nhiều thú vị thứ để trang trải ngày hôm nay. 7 00:00:16,820 --> 00:00:20,160 Rất nhiều cơ hội cho tình nguyện viên trên sân khấu. 8 00:00:20,160 --> 00:00:22,780 Và cuối cùng, hôm nay là không về mã nào cả. 9 00:00:22,780 --> 00:00:24,820 Nhưng đó là về ý tưởng, và đó là về các thuật toán, 10 00:00:24,820 --> 00:00:28,420 và thực sự mang lại một số các bài học kinh nghiệm từ tuần không, 11 00:00:28,420 --> 00:00:31,910 trong đó thu hồi, chúng tôi giới thiệu con quái vật này. 12 00:00:31,910 --> 00:00:33,880 Và vay mượn cảm hứng từ đó, để bắt đầu 13 00:00:33,880 --> 00:00:36,879 để giải quyết phức tạp hơn bao giờ hết vấn đề thuật toán. 14 00:00:36,879 --> 00:00:38,420 Nhưng trước tiên, một vài thông báo. 15 00:00:38,420 --> 00:00:42,020 Vì vậy, một, nếu bạn muốn tham gia Nhân viên và các bạn cùng lớp CS50 tại bữa ăn trưa 16 00:00:42,020 --> 00:00:44,670 Thứ Sáu tuần này, cả hai ở đây và ở Cambridge, và ở New Haven, 17 00:00:44,670 --> 00:00:48,060 xin vui lòng truy cập vào các khóa học của trang web, nơi một URL có thể được tìm thấy. 18 00:00:48,060 --> 00:00:50,390 Bài giảng thứ Tư này sẽ không được ở đây trong Sanders. 19 00:00:50,390 --> 00:00:53,610 Nó sẽ được trực tuyến chỉ, vì vậy điều chỉnh trong tại website của CS50, 20 00:00:53,610 --> 00:00:55,850 cho dù ở đây tại Cambridge hoặc New Haven là tốt. 21 00:00:55,850 --> 00:00:58,110 >> Và sau đó vấn đề đặt hai là đã có trong tay của bạn. 22 00:00:58,110 --> 00:01:03,067 Nếu bạn chưa lặn trong chưa, cho phép tôi cung cấp các gợi ý ngôn từ mạnh mẽ 23 00:01:03,067 --> 00:01:05,150 đó, đặc biệt là bây giờ, khi vấn đề đặt ra trước, 24 00:01:05,150 --> 00:01:08,669 bạn thực sự muốn bắt đầu bây giờ, nếu không vọc một chút vào cuối tuần hoặc trước 25 00:01:08,669 --> 00:01:10,710 khi họ lần đầu tiên đi ra ngoài vào Thứ Sáu, bởi vì bạn sẽ 26 00:01:10,710 --> 00:01:14,380 thấy rằng họ không nhất thiết nhận được lâu hơn hoặc nhiều thách thức cho mỗi 27 00:01:14,380 --> 00:01:14,950 se. 28 00:01:14,950 --> 00:01:17,575 Tôi nghĩ rằng bạn sẽ tìm thấy rằng, trong Nói chung, họ có xu hướng mất khoảng 29 00:01:17,575 --> 00:01:18,892 xung quanh cùng một lượng thời gian. 30 00:01:18,892 --> 00:01:20,850 Nhưng chắc chắn nó phụ thuộc vào học sinh, và nó 31 00:01:20,850 --> 00:01:22,880 phụ thuộc vào những suy nghĩ mà bạn tiếp cận nó. 32 00:01:22,880 --> 00:01:24,910 Nhưng lúc nào, bạn đang đi chạy lên chống lại một bức tường, 33 00:01:24,910 --> 00:01:26,350 và bạn đang đi để đạt một số lỗi, và bạn chỉ 34 00:01:26,350 --> 00:01:27,950 sẽ không có khả năng vượt qua được nó tại một số điểm. 35 00:01:27,950 --> 00:01:31,380 Và đó là cực kỳ có giá trị để có thể để bước đi, trở lại vào ngày hôm sau, 36 00:01:31,380 --> 00:01:35,286 đi đến giờ làm việc, bài đăng trên CS50 Thảo luận hay như thế, để thực sự có được cấm. 37 00:01:35,286 --> 00:01:36,160 Vì vậy, giữ cho rằng trong tâm trí. 38 00:01:36,160 --> 00:01:40,830 Bắt đầu sớm nhất có thể là điều tốt nhất bạn có thể làm. 39 00:01:40,830 --> 00:01:44,160 Vì vậy, đây là nơi chúng ta bắt đầu lớp, trong tuần qua không. 40 00:01:44,160 --> 00:01:47,441 Và chúng ta có thể có được một tình nguyện viên ở đây để giúp tôi tìm mics? 41 00:01:47,441 --> 00:01:47,940 ĐƯỢC. 42 00:01:47,940 --> 00:01:48,900 Đứng lên đã. 43 00:01:48,900 --> 00:01:50,080 Nào lên. 44 00:01:50,080 --> 00:01:53,707 Đoán đó là cách nó sẽ làm việc. 45 00:01:53,707 --> 00:01:54,415 Tên bạn là gì? 46 00:01:54,415 --> 00:01:55,570 ALAN Estrada: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 DAVID J. Malan: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Nào lên. 49 00:01:57,910 --> 00:01:58,619 Rất hân hạnh được biết bạn. 50 00:01:58,619 --> 00:01:59,910 ALAN Estrada: Rất vui được gặp bạn. 51 00:01:59,910 --> 00:02:02,772 DAVID J. Malan: Và em có ở đây với chúng tôi trong tuần bằng không, tất nhiên. 52 00:02:02,772 --> 00:02:03,028 ALAN Estrada: Tôi đã. 53 00:02:03,028 --> 00:02:03,160 Tôi đã. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. Malan: Vì vậy, bạn có thể đi trước và tìm cho chúng tôi Mike Smith, 55 00:02:05,868 --> 00:02:08,639 nhanh như bạn có thể? 56 00:02:08,639 --> 00:02:10,639 Nhanh như bạn có thể. 57 00:02:10,639 --> 00:02:13,756 Nghĩa đen rách vấn đề trong nửa như bạn cần. 58 00:02:13,756 --> 00:02:15,130 >> ALAN Estrada: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. Malan: Nghĩa đen rách vấn đề trong một nửa. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN Estrada: Oh. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Rất tốt. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. Malan: OK. 65 00:02:23,700 --> 00:02:24,200 Tốt. 66 00:02:24,200 --> 00:02:24,701 Cam on. 67 00:02:24,701 --> 00:02:25,700 ALAN Estrada: Rất tốt. 68 00:02:25,700 --> 00:02:26,210 ĐƯỢC. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. Malan: Và bây giờ, bạn đã đẽo nó xuống 70 00:02:27,610 --> 00:02:29,320 đến một nửa kích thước của vấn đề. 71 00:02:29,320 --> 00:02:31,267 Bây giờ, chúng tôi đang xuống đến một phần tư. 72 00:02:31,267 --> 00:02:33,475 Bạn đang chú ý đến mà bên chúng tôi đang giữ? 73 00:02:33,475 --> 00:02:34,405 >> [Cười] 74 00:02:34,405 --> 00:02:35,970 >> ALAN Estrada: Vâng, tôi think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. Malan: phần gì chúng ta đang ở? 76 00:02:37,594 --> 00:02:39,150 ALAN Estrada: Mufflers, như vậy. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. Malan: OK. 78 00:02:39,941 --> 00:02:42,810 Nhưng Mike Smith sẽ là sau khi Mufflers. 79 00:02:42,810 --> 00:02:44,130 So-- 80 00:02:44,130 --> 00:02:48,180 >> [Cười] 81 00:02:48,180 --> 00:02:48,742 >> Được rồi. 82 00:02:48,742 --> 00:02:50,200 ALAN Estrada: Chúng ta tìm ở đâu? 83 00:02:50,200 --> 00:02:52,049 DAVID J. Malan: Mike Smith. 84 00:02:52,049 --> 00:02:53,090 ALAN Estrada: Mike Smith. 85 00:02:53,090 --> 00:02:54,760 DAVID J. Malan: Bây giờ, chúng ta đang ở trong phẫu thuật. 86 00:02:54,760 --> 00:02:57,840 Bây giờ, các bác sĩ. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN Estrada: Let's- chúng ta hãy đi với thực tế. 89 00:02:59,856 --> 00:03:00,370 Real. 90 00:03:00,370 --> 00:03:00,970 >> DAVID J. Malan: Real. 91 00:03:00,970 --> 00:03:01,470 ĐƯỢC. 92 00:03:01,470 --> 00:03:03,700 Nếu bạn cần Real. 93 00:03:03,700 --> 00:03:05,250 Bây giờ, đó là cách Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN Estrada: Bằng cách này. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. Malan: Dùng cách nào? 96 00:03:07,333 --> 00:03:08,240 ALAN Estrada: Chờ. 97 00:03:08,240 --> 00:03:08,790 M is-- phải không? 98 00:03:08,790 --> 00:03:09,110 Chúng tôi bắt đầu with-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. Malan: Yeah. 100 00:03:10,090 --> 00:03:10,650 Họ đang trái. 101 00:03:10,650 --> 00:03:11,430 Quyền của bạn. 102 00:03:11,430 --> 00:03:11,710 >> ALAN Estrada: Yeah. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. Malan: Vì vậy, Mike ở đây. 104 00:03:13,126 --> 00:03:13,990 ALAN Estrada: Cái gì? 105 00:03:13,990 --> 00:03:14,665 >> [Cười] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Bad dụ, guys. 108 00:03:18,330 --> 00:03:18,830 Xin lỗi. 109 00:03:18,830 --> 00:03:21,610 DAVID J. Malan: Điều này sẽ dạy bạn nhảy ra khỏi ghế của bạn. 110 00:03:21,610 --> 00:03:22,318 >> ALAN Estrada: Oh. 111 00:03:22,318 --> 00:03:22,890 Oh. 112 00:03:22,890 --> 00:03:23,390 Tôi đã có em. 113 00:03:23,390 --> 00:03:24,670 Tôi đã có em. 114 00:03:24,670 --> 00:03:25,170 Oh. 115 00:03:25,170 --> 00:03:25,669 Oh. 116 00:03:25,669 --> 00:03:26,812 Đây is-- OK, tôi đã có em. 117 00:03:26,812 --> 00:03:27,520 Smith ngay tại đây? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. Malan: Smith, cảm ơn bạn. 119 00:03:28,894 --> 00:03:30,535 Vì vậy, tôi sẽ tiếp tục tìm lên Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN Estrada: Oh, yeah. 121 00:03:30,790 --> 00:03:31,340 Không không không. 122 00:03:31,340 --> 00:03:31,600 Ồ không. 123 00:03:31,600 --> 00:03:31,940 Cái này của tôi. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. Malan: Oh, bạn đã nhận Smith. 125 00:03:32,580 --> 00:03:33,415 ĐƯỢC. 126 00:03:33,415 --> 00:03:34,040 >> ALAN Estrada: Yeah, tôi đã Smith ngay tại đây. 127 00:03:34,040 --> 00:03:34,700 Xin lỗi các bạn. 128 00:03:34,700 --> 00:03:35,860 Tôi nghĩ chúng ta Michael-- đang tìm kiếm cho Michael. 129 00:03:35,860 --> 00:03:36,550 Xin lỗi. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. Malan: Đó là OK. 131 00:03:37,550 --> 00:03:39,950 Được rồi, bây giờ chúng tôi vào Paccini and Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN Estrada: Paccini và con trai. 133 00:03:41,242 --> 00:03:43,158 DAVID J. Malan: Chỉ có bạn và tôi ở trên này. 134 00:03:43,158 --> 00:03:44,050 ĐƯỢC. 135 00:03:44,050 --> 00:03:45,130 Tìm chúng tôi Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Smith. 137 00:03:45,830 --> 00:03:46,310 >> ALAN Estrada: Smith. 138 00:03:46,310 --> 00:03:46,750 >> DAVID J. Malan: Smith. 139 00:03:46,750 --> 00:03:47,728 Chúng tôi đang ở trong R rác. 140 00:03:47,728 --> 00:03:48,644 ALAN Estrada: rác. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Điều này sẽ mất một thời gian. 143 00:03:52,480 --> 00:03:54,340 >> [Cười] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. Malan: Giày dép. 146 00:03:56,720 --> 00:03:58,080 Chúng tôi đang ở trong giày. 147 00:03:58,080 --> 00:04:00,210 >> ALAN Estrada: Bây giờ chúng tôi đang gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. Malan: Nice. 149 00:04:01,105 --> 00:04:01,980 ALAN Estrada: Which-- 150 00:04:01,980 --> 00:04:03,620 [Cười] 151 00:04:03,620 --> 00:04:05,440 Oh, điều này là rất tốt. 152 00:04:05,440 --> 00:04:06,910 [Cười] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. Malan: Đó là OK. 155 00:04:09,390 --> 00:04:11,365 >> ALAN Estrada: Oh, điều này là tốt. 156 00:04:11,365 --> 00:04:14,425 Tôi không nghĩ rằng tôi sẽ có bạn bè PSAT sau này. 157 00:04:14,425 --> 00:04:15,300 DAVID J. Malan: Tốt. 158 00:04:15,300 --> 00:04:16,078 Sporting. 159 00:04:16,078 --> 00:04:17,036 ALAN Estrada: Sporting. 160 00:04:17,036 --> 00:04:18,668 Um, L, M, N, O, P. 161 00:04:18,668 --> 00:04:19,459 DAVID J. Malan: OK. 162 00:04:19,459 --> 00:04:21,600 Vì vậy, hãy xé này trong một nửa. 163 00:04:21,600 --> 00:04:22,270 Đó là OK. 164 00:04:22,270 --> 00:04:25,606 Điều này kết thúc kém anyway, vì Mike Smith sẽ không được trong các trang vàng. 165 00:04:25,606 --> 00:04:26,430 >> ALAN Estrada: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. Malan: Không, nó là OK. 167 00:04:27,140 --> 00:04:28,930 Nhưng chúng ta hãy giả vờ như ông trên trang này. 168 00:04:28,930 --> 00:04:33,260 Vì vậy, bây giờ, bạn đã đẽo vấn đề xuống một trang, và chúng tôi thấy Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Cổ vũ] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Được rồi cám ơn bạn. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 ĐƯỢC. 174 00:04:41,200 --> 00:04:43,646 Đó là điều bất thường. 175 00:04:43,646 --> 00:04:45,954 Nhưng nó vẫn còn nhanh hơn so với tìm kiếm tuyến tính, 176 00:04:45,954 --> 00:04:47,870 trong đó chúng tôi bắt đầu vào bắt đầu của cuốn sách, 177 00:04:47,870 --> 00:04:51,210 và chúng tôi di chuyển theo cách của chúng tôi từ trái sang phải, Cuối cùng tìm kiếm Mike Smith. 178 00:04:51,210 --> 00:04:53,540 Và như vậy, nếu cuốn sách điện thoại có lẽ 1.000 trang, 179 00:04:53,540 --> 00:04:56,300 có thể nó đã có thể lấy chúng tôi 10 hoặc để trang nước mắt. 180 00:04:56,300 --> 00:04:59,380 >> Nhưng bạn có thể đã thừa hưởng chạm vào một giả định 181 00:04:59,380 --> 00:05:03,602 trong tất cả điều đó, mà là để nói rằng các cuốn sách điện thoại trước là gì? 182 00:05:03,602 --> 00:05:04,310 Đung Sắp xếp. 183 00:05:04,310 --> 00:05:05,000 DAVID J. Malan: Nó được sắp xếp. 184 00:05:05,000 --> 00:05:05,160 Phải không? 185 00:05:05,160 --> 00:05:07,909 Nó được sắp xếp theo thứ tự abc, vì vậy rằng tất cả những tên và số 186 00:05:07,909 --> 00:05:11,230 đều được sắp xếp từ A đến Z, và theo bảng chữ cái ở giữa. 187 00:05:11,230 --> 00:05:13,100 Nhưng hôm nay, chúng ta bây giờ yêu cầu các câu hỏi, tốt, 188 00:05:13,100 --> 00:05:16,170 Làm thế nào mà Verizon hoặc điện thoại Công ty có được nó vào trạng thái đó? 189 00:05:16,170 --> 00:05:19,560 >> Bởi vì nó là một điều để tận dụng Giả định rằng, và do đó, 190 00:05:19,560 --> 00:05:22,570 giải quyết một vấn đề với một thuật toán hiệu quả hơn. 191 00:05:22,570 --> 00:05:24,900 Nhưng chúng ta không bao giờ thực sự hỏi trong tuần không, tốt, 192 00:05:24,900 --> 00:05:27,790 bao nhiêu đã làm nó chi phí Verizon hoặc người khác 193 00:05:27,790 --> 00:05:29,620 để nhận được rằng cuốn sách điện thoại để sắp xếp? 194 00:05:29,620 --> 00:05:29,780 >> Phải không? 195 00:05:29,780 --> 00:05:31,529 Nó không quan trọng nếu nhìn lên Mike Smith 196 00:05:31,529 --> 00:05:35,190 là siêu nhanh, nếu bạn cần một năm để sắp xếp các trang ban đầu. 197 00:05:35,190 --> 00:05:35,690 Phải không? 198 00:05:35,690 --> 00:05:38,620 Bạn cũng có thể chỉ chọn lọc thông qua một cuốn sách điện thoại ngẫu nhiên, 199 00:05:38,620 --> 00:05:40,690 nếu nó sẽ là siêu đắt tiền để sắp xếp nó. 200 00:05:40,690 --> 00:05:42,350 Vì vậy, nếu chúng ta có thể có tình nguyện viên khác. 201 00:05:42,350 --> 00:05:46,350 Chúng ta hãy nhìn lên tại đây làm thế nào chúng ta might-- đi trên up-- như thế nào 202 00:05:46,350 --> 00:05:48,100 chúng tôi có thể đi về phân loại này. 203 00:05:48,100 --> 00:05:51,990 >> Và nếu thực sự có thể Jordan tham gia chúng tôi lên đây trên sân khấu. 204 00:05:51,990 --> 00:05:55,100 Nào lên chỉ trong một khoảnh khắc. 205 00:05:55,100 --> 00:05:56,359 Tên bạn là gì? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. Malan: Caroline, đi lên trên. 208 00:05:58,691 --> 00:06:02,070 Và bạn sẽ được tham gia bởi tôi và Jordan ở đây. 209 00:06:02,070 --> 00:06:03,800 Caroline, cảm ơn bạn. 210 00:06:03,800 --> 00:06:04,300 Được rồi. 211 00:06:04,300 --> 00:06:08,330 Vì vậy, những gì chúng tôi có ở đây cho Caroline là 26 cuốn sách màu xanh 212 00:06:08,330 --> 00:06:10,747 mà FAS sử dụng để quản lý một số kỳ thi cuối cùng. 213 00:06:10,747 --> 00:06:13,330 Đây là nhận được khó khăn để tìm kiếm, nhưng những gì chúng tôi đã thực hiện trước 214 00:06:13,330 --> 00:06:15,800 là chúng ta đã đặt tên của ai đó trên mặt trước của mỗi trong số này, 215 00:06:15,800 --> 00:06:18,133 nhưng chúng tôi đã giữ nó đơn giản bằng sau đó đưa ra tên đầy đủ. 216 00:06:18,133 --> 00:06:22,720 Vì vậy, chúng tôi sẽ đưa cho người có tên L, D, J, B, tất cả các cách từ A đến Z, 217 00:06:22,720 --> 00:06:24,090 nhưng họ đang ở trong thứ tự ngẫu nhiên. 218 00:06:24,090 --> 00:06:26,890 Và do đó, nếu bạn muốn, bạn nói chuyện cách thức thông qua các vấn đề như bạn 219 00:06:26,890 --> 00:06:31,620 làm điều đó, bạn có thể đi trước và sắp xếp những đối với chúng tôi, từ A đến Z. 220 00:06:31,620 --> 00:06:34,070 >> Đung OK, do đó L là như thế, giữa. 221 00:06:34,070 --> 00:06:35,050 C đang bắt đầu. 222 00:06:35,050 --> 00:06:42,410 B. J trước khi L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. Malan: Giữ rằng suy nghĩ trong một giây. 224 00:06:45,140 --> 00:06:48,910 Bởi vì nếu không, đây chỉ là thú vị cho bạn, cho tôi, và Jordan. 225 00:06:48,910 --> 00:06:49,724 Hiện chúng tôi đi. 226 00:06:49,724 --> 00:06:50,640 Đung [không nghe được]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. Malan: OK. 229 00:06:58,090 --> 00:06:59,310 Bạn đang lam gi thê? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M đưa ra sau khi O. 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. Malan: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. Malan: O, Tốt. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: E. 235 00:07:04,970 --> 00:07:06,730 >> DAVID J. Malan: E, F. Yeah. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V. 237 00:07:07,620 --> 00:07:10,689 >> DAVID J. Malan: V, T, U, V. Vì vậy, nó Có vẻ như bạn đang making-- tiếp tục đi. 238 00:07:10,689 --> 00:07:12,730 Có vẻ như bạn đang làm một đống lớn trên đây, 239 00:07:12,730 --> 00:07:13,910 và loại một đống lớn trên đó. 240 00:07:13,910 --> 00:07:16,230 Vì vậy, nửa đầu của bảng chữ cái, nửa thứ hai của bảng chữ cái. 241 00:07:16,230 --> 00:07:16,460 ĐƯỢC. 242 00:07:16,460 --> 00:07:16,960 Tốt. 243 00:07:16,960 --> 00:07:19,680 Kind tách các vấn đề trong hai. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Yeah. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. Malan: OK. 247 00:07:22,980 --> 00:07:25,070 K. Vì vậy, bạn đang loại lựa chọn họ cái khác, 248 00:07:25,070 --> 00:07:27,620 đặt nó hoặc trái hoặc phải, hoặc Z đi trên sàn nhà. 249 00:07:27,620 --> 00:07:28,012 ĐƯỢC. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z đang xảy ra sàn. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. Malan: OK. 252 00:07:29,360 --> 00:07:30,920 Y đang đi trên sàn nhà. 253 00:07:30,920 --> 00:07:31,735 Bây giờ chúng ta có thể đưa X. 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 DAVID J. Malan: G của going trái. 256 00:07:33,700 --> 00:07:36,017 S được đi bên phải. 257 00:07:36,017 --> 00:07:37,642 Tất cả các quyền, A được đi tất cả các cách còn lại. 258 00:07:37,642 --> 00:07:38,790 >> CAROLINE: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> DAVID J. Malan: Bây giờ, tốt. 260 00:07:39,873 --> 00:07:43,260 Chúng tôi đã có A, B, C. W đi xuống đó. 261 00:07:43,260 --> 00:07:45,566 Tất cả các quyền, T. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, I, J. 263 00:07:46,611 --> 00:07:47,860 DAVID J. Malan: H, I, J. Tốt. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: Ở trung tâm, tôi gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. Malan: OK. 266 00:07:50,000 --> 00:07:52,375 Vì vậy, bây giờ, chúng ta sẽ loại của hợp nhất các cọc khác nhau. 267 00:07:52,375 --> 00:08:00,730 Vì vậy, từ A đến C, sau đó tôi thấy D, và E và F, và G, và H và I. Nice. 268 00:08:00,730 --> 00:08:05,540 J, K. Và sau đó, đống này là lộn ngược, nhưng đó là OK. 269 00:08:05,540 --> 00:08:06,040 Chắc chắn. 270 00:08:06,040 --> 00:08:07,240 Chúng tôi có thể cắt giảm một số góc. 271 00:08:07,240 --> 00:08:07,950 ĐƯỢC. 272 00:08:07,950 --> 00:08:10,530 Và sau đó chúng ta cần W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Yeah. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. Malan: Tuyệt vời. 275 00:08:11,880 --> 00:08:14,122 Vì vậy, một lớn, cảm ơn bạn Caroline để phân loại này. 276 00:08:14,122 --> 00:08:15,030 >> [Cổ vũ] 277 00:08:15,030 --> 00:08:17,287 >> Cam on. 278 00:08:17,287 --> 00:08:18,120 Cảm ơn rất nhiều. 279 00:08:18,120 --> 00:08:22,910 Vì vậy, bây giờ chúng ta hãy xem xét một lúc cách Caroline đã đi về làm điều đó, 280 00:08:22,910 --> 00:08:26,040 và chính xác những gì chúng tôi đã có thể đối với: làm thế nào chúng tôi 281 00:08:26,040 --> 00:08:28,409 đã có thể giải quyết điều đó vấn đề khi chúng tôi chỉ 282 00:08:28,409 --> 00:08:29,950 đưa ra một bó toàn bộ các yếu tố đầu vào ngẫu nhiên. 283 00:08:29,950 --> 00:08:31,610 >> Vâng, có vẻ như có là một chút của một hệ thống có? 284 00:08:31,610 --> 00:08:32,110 Phải. 285 00:08:32,110 --> 00:08:34,495 Vì vậy, các chữ cái đầu trong bảng chữ cái, cô 286 00:08:34,495 --> 00:08:37,120 đã đặt sang bên trái, và chữ sau trong bảng chữ cái, 287 00:08:37,120 --> 00:08:38,270 cô đã gửi gắm vào bên phải. 288 00:08:38,270 --> 00:08:40,500 Và ngay khi cô tìm thấy một số chữ cái gần, những người 289 00:08:40,500 --> 00:08:43,124 mà đi ngay bên cạnh nhau, cô sẽ đưa những người trong đơn đặt hàng. 290 00:08:43,124 --> 00:08:46,750 Và vì vậy chúng tôi đã có những loại nhỏ đống đầu vào được sắp xếp diễn ra. 291 00:08:46,750 --> 00:08:50,540 >> Và đó là khá giống như những gì nhất của con người chúng ta sẽ làm gì. 292 00:08:50,540 --> 00:08:53,530 Chúng tôi sẽ sắp xếp của sàng lọc thông qua nó, và chúng tôi chắc hẳn sẽ có một cơ chế. 293 00:08:53,530 --> 00:08:56,930 Nhưng nó có thể là khó khăn để viết nó xuống trong một công thức cho mỗi gia nhập. 294 00:08:56,930 --> 00:08:59,010 Nó cảm thấy nhiều hơn một chút hữu cơ hơn. 295 00:08:59,010 --> 00:09:02,560 Vì vậy, chúng ta hãy xem nếu chúng ta bây giờ có thể bị ràng buộc các vấn đề với ít đầu vào. 296 00:09:02,560 --> 00:09:05,170 >> Thay vì 26, chúng ta hãy làm một cái gì đó rất ít 297 00:09:05,170 --> 00:09:09,890 chỉ nói, bảy, đằng sau các cửa ra vào, vì vậy để nói chuyện. 298 00:09:09,890 --> 00:09:11,300 Là chỉ có bảy con số? 299 00:09:11,300 --> 00:09:15,240 Và nếu mục tiêu tại mặt là để tìm một giá trị, 300 00:09:15,240 --> 00:09:17,850 chúng ta hãy xem làm thế nào có hiệu quả chúng ta có thể đi về việc này. 301 00:09:17,850 --> 00:09:22,460 Và chúng ta hãy xem liệu chúng ta có thể bây giờ bắt đầu áp dụng một số con số, 302 00:09:22,460 --> 00:09:26,310 hoặc một số công thức nào đó để mô tả hiệu quả của cuốn sách điện thoại của chúng tôi 303 00:09:26,310 --> 00:09:31,060 Thuật toán, thuật toán sách thi của chúng tôi, và nói chung, việc tìm kiếm thông tin. 304 00:09:31,060 --> 00:09:34,770 >> Vì vậy, đối với chuyện này, tôi đi trước, và trên màn hình cảm ứng trên đây, 305 00:09:34,770 --> 00:09:41,100 đưa ra một trình duyệt web có chính xác những bảy cửa. 306 00:09:41,100 --> 00:09:46,670 Và nếu chúng ta có thể có được một khác tình nguyện đến trên hơn ở đây, 307 00:09:46,670 --> 00:09:48,480 Tôi đã đặt các cửa ra vào cùng ở đây. 308 00:09:48,480 --> 00:09:49,170 Tình nguyện viên nhanh chóng. 309 00:09:49,170 --> 00:09:51,130 >> Đây demo one-- đang đi đến một nhanh hơn và nhanh hơn bây giờ. 310 00:09:51,130 --> 00:09:51,600 Come on xuống. 311 00:09:51,600 --> 00:09:52,308 Tên bạn là gì? 312 00:09:52,308 --> 00:09:53,040 TREVOR: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> DAVID J. Malan: Trevor? 314 00:09:53,998 --> 00:09:55,770 Tất cả các quyền, Trevor, đi trên xuống. 315 00:09:55,770 --> 00:09:59,212 Vì vậy, Trevor đã tình nguyện ở đây để làm một vấn đề tương tự, nhưng một trong đó là 316 00:09:59,212 --> 00:10:02,170 hẹp trong phạm vi, và điều đó để cho phép chúng tôi cố gắng để chính thức hóa doanh nghiệp 317 00:10:02,170 --> 00:10:03,970 quá trình để phân loại những con số này. 318 00:10:03,970 --> 00:10:05,500 >> Vì vậy, Trevor, rất vui được gặp bạn. 319 00:10:05,500 --> 00:10:08,720 Vì vậy, đây là một mảng, do đó, để nói, một danh sách bảy cửa. 320 00:10:08,720 --> 00:10:10,327 Đi trước và tìm thấy chúng tôi số 50. 321 00:10:10,327 --> 00:10:12,410 Và sau đó sau khi thực tế, cho chúng tôi biết làm thế nào bạn tìm thấy nó. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Nên be-- tất cả các quyền. 324 00:10:20,040 --> 00:10:21,945 Vâng, đây là một trong đây? 325 00:10:21,945 --> 00:10:24,680 Uh-oh. 326 00:10:24,680 --> 00:10:25,560 ĐƯỢC. 327 00:10:25,560 --> 00:10:26,680 Bạn nhấp một. 328 00:10:26,680 --> 00:10:28,690 Tốt. 329 00:10:28,690 --> 00:10:29,780 >> Và tốt. 330 00:10:29,780 --> 00:10:30,970 Bây giờ bạn nhấp một. 331 00:10:30,970 --> 00:10:34,060 Và hãy để tôi cung cấp cho bạn các microphone, do đó bạn có nó chỉ trong một khoảnh khắc. 332 00:10:34,060 --> 00:10:37,000 Đi trước và nhấp vào cửa tiếp theo mà bạn dự định. 333 00:10:37,000 --> 00:10:39,812 Vâng tốt. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Tôi có thể bỏ chọn một cánh cửa? 335 00:10:41,020 --> 00:10:42,620 DAVID J. Malan: Không, bạn không thể bỏ chọn. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Cái này. 338 00:10:43,974 --> 00:10:45,640 DAVID J. Malan: Nơi nào bạn muốn đi đâu? 339 00:10:45,640 --> 00:10:46,410 Cái nào? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Đó là một trong. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. Malan: No. 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Cái này. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. Malan: Yes. 345 00:10:49,020 --> 00:10:49,700 Đó là tốt. 346 00:10:49,700 --> 00:10:50,380 Được rồi. 347 00:10:50,380 --> 00:10:53,900 Vì vậy, những gì đã được thuật toán của bạn hoặc thủ tục để làm điều này, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Tôi chỉ cần đi qua cửa cho đến khi tôi tìm thấy một 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. Malan: OK. 350 00:10:56,940 --> 00:10:58,150 Excellent thuật toán. 351 00:10:58,150 --> 00:10:59,540 Vì vậy, đó là tốt. 352 00:10:59,540 --> 00:11:03,120 Bởi vì trong thực tế, nếu tôi tiết lộ những gì đằng sau hai cánh cửa khác, những gì 353 00:11:03,120 --> 00:11:06,954 chúng ta sẽ tìm thấy ở đây là chúng ta chỉ có đầu vào ngẫu nhiên. 354 00:11:06,954 --> 00:11:08,870 Vì vậy, đó là thực sự là tốt như bạn có thể có được. 355 00:11:08,870 --> 00:11:12,509 Và trong thực tế, bạn đã tốt hơn so với triệt tìm kiếm toàn bộ mảng, 356 00:11:12,509 --> 00:11:15,300 vì nó đã thực sự không may mắn nếu bạn đã trúng số 357 00:11:15,300 --> 00:11:16,604 50 mua tại cửa cuối cùng. 358 00:11:16,604 --> 00:11:18,520 Nhưng nếu chúng ta thay vì đã cho bạn một giả định. 359 00:11:18,520 --> 00:11:20,630 Giả sử tôi sắp xếp tất cả các các cửa xung quanh, 360 00:11:20,630 --> 00:11:23,500 vì vậy mà bạn có số sắp xếp thời gian này, 361 00:11:23,500 --> 00:11:29,730 nhưng lần này nó thực sự một different-- thời gian này, 362 00:11:29,730 --> 00:11:32,640 nó thực sự được sắp xếp cho bạn. 363 00:11:32,640 --> 00:11:35,380 Và bây giờ là mục tiêu trong tầm tay là để đánh số 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. Malan: Có gì thuật toán của bạn sẽ được? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Vâng, nếu nó sắp xếp, nó hoặc là đi 367 00:11:39,628 --> 00:11:42,710 để be-- nếu lớn nhất đến lớn nhất, giảm dần, nó sẽ là người đầu tiên, 368 00:11:42,710 --> 00:11:44,751 hoặc nếu nó là ngược lại, nó sẽ là người cuối cùng. 369 00:11:44,751 --> 00:11:48,897 Vì vậy, tôi sẽ chỉ cần gõ nhẹ cánh cửa này, và sau đó chỉ cần gõ nhẹ vào cánh cửa cuối cùng. 370 00:11:48,897 --> 00:11:49,980 DAVID J. Malan: Tuyệt vời. 371 00:11:49,980 --> 00:11:50,270 Được rồi. 372 00:11:50,270 --> 00:11:51,150 Vì vậy, chúng tôi nhận thấy số lượng 50. 373 00:11:51,150 --> 00:11:52,970 Vì vậy, ngay sau khi bạn biết họ đã được sắp xếp, chúng tôi 374 00:11:52,970 --> 00:11:55,040 đã có thể tận dụng giả định này. 375 00:11:55,040 --> 00:11:57,040 Vì vậy, họ quá giống ví dụ danh bạ điện thoại. 376 00:11:57,040 --> 00:11:59,540 Ngay khi bạn có, ngay cả với một vấn đề nhỏ như thế này, 377 00:11:59,540 --> 00:12:02,380 đầu vào của bạn trước khi sắp xếp, chúng ta có thể thực sự tìm ra giá trị cho là 378 00:12:02,380 --> 00:12:03,130 hiệu quả hơn. 379 00:12:03,130 --> 00:12:05,800 >> Và tôi đã không nói cho bạn nếu nó là sắp xếp nhỏ đến lớn, hoặc lớn đến nhỏ, 380 00:12:05,800 --> 00:12:08,080 và do đó, nó là rất hợp lý để bắt đầu ở một đầu hay khác 381 00:12:08,080 --> 00:12:09,750 để thực sự thấy rằng giá trị đích. 382 00:12:09,750 --> 00:12:11,400 Vì vậy, cảm ơn đến Trevor là tốt. 383 00:12:11,400 --> 00:12:13,260 Và tôi sẽ propose-- thực hiện độc đáo. 384 00:12:13,260 --> 00:12:16,960 Chúng tôi có một chút clip, thực sự, mà là một trong những khoảnh khắc yêu thích của chúng tôi trong CS50, 385 00:12:16,960 --> 00:12:19,700 nhờ đó mà đôi khi những bản demo không hoàn toàn đi theo kế hoạch. 386 00:12:19,700 --> 00:12:22,050 Và thực sự ngay bây giờ, tôi kéo lên các giao diện sai 387 00:12:22,050 --> 00:12:23,508 mà để sử dụng màn hình cảm ứng. 388 00:12:23,508 --> 00:12:24,660 Vì vậy, đó là lỗi của tôi ở đó. 389 00:12:24,660 --> 00:12:26,600 >> Vì vậy, điều này sẽ làm cho Clip năm tới như 390 00:12:26,600 --> 00:12:28,570 tại sao tôi đã nhấp vào màn hình của riêng tôi. 391 00:12:28,570 --> 00:12:31,390 Nhưng chúng ta hãy có một cái nhìn nhanh chóng vào những gì xảy ra năm ngoái 392 00:12:31,390 --> 00:12:34,770 với Jay, người đã đưa ra, nhiều như Trevor đây, tình nguyện, 393 00:12:34,770 --> 00:12:39,380 và trong đoạn clip ngắn này, bạn sẽ thấy như thế nào cùng một bản demo này không hoàn toàn 394 00:12:39,380 --> 00:12:41,074 tiết lộ những bài học cùng học. 395 00:12:41,074 --> 00:12:41,740 [VIDEO PLAYBACK] 396 00:12:41,740 --> 00:12:45,360 Tôi muốn -Tất cả các bạn phải làm bây giờ là để tìm cho tôi, và cho chúng ta, 397 00:12:45,360 --> 00:12:51,674 thực sự, số 50 một bước tại một thời điểm. 398 00:12:51,674 --> 00:12:52,450 >> -Các Số 50? 399 00:12:52,450 --> 00:12:53,190 >> -Các Số 50. 400 00:12:53,190 --> 00:12:55,356 Và bạn có thể tiết lộ những gì đằng sau mỗi cánh cửa 401 00:12:55,356 --> 00:12:58,540 chỉ đơn giản bằng cách chạm vào nó với một ngón tay. 402 00:12:58,540 --> 00:13:00,910 Chết tiệt. 403 00:13:00,910 --> 00:13:02,870 >> [Cười] 404 00:13:02,870 --> 00:13:03,806 >> [END PLAYBACK] 405 00:13:03,806 --> 00:13:05,430 DAVID J. Malan: Vì vậy mà đã đi rất tốt. 406 00:13:05,430 --> 00:13:06,796 Đó là những cánh cửa không được phân loại. 407 00:13:06,796 --> 00:13:08,670 Và Jay, tất nhiên, tìm thấy nó quá nhanh. 408 00:13:08,670 --> 00:13:12,910 Trevor đã làm một công việc tốt hơn nhiều về một thời điểm có thể dạy dỗ, 409 00:13:12,910 --> 00:13:15,850 có thể nói, năm nay ở mất nhiều thời gian để tìm thấy nó. 410 00:13:15,850 --> 00:13:17,950 Tất nhiên, sau đó chúng tôi đã cho Jay một cơ hội thứ hai, 411 00:13:17,950 --> 00:13:20,320 nhờ đó chúng ta sắp xếp các cửa ra vào, cũng như chúng ta đã làm cho Trevor, 412 00:13:20,320 --> 00:13:22,300 và Trevor đã làm siêu cũng thời gian này. 413 00:13:22,300 --> 00:13:26,124 Nhưng Jay đã làm nó một nửa là nhanh chóng. 414 00:13:26,124 --> 00:13:26,790 [VIDEO PLAYBACK] 415 00:13:26,790 --> 00:13:29,650 Mục tiêu -Các bây giờ là cũng tìm thấy chúng tôi số 50, 416 00:13:29,650 --> 00:13:33,030 nhưng làm điều đó thuật toán, và cho chúng tôi biết bạn đang đi về nó. 417 00:13:33,030 --> 00:13:33,660 >> -ĐƯỢC. 418 00:13:33,660 --> 00:13:35,604 >> -Và Nếu bạn tìm thấy nó, bạn giữ cho bộ phim. 419 00:13:35,604 --> 00:13:37,228 Nếu bạn không tìm thấy nó, bạn cho nó trở lại. 420 00:13:37,228 --> 00:13:38,044 >> -Man. 421 00:13:38,044 --> 00:13:38,860 >> -Oh! 422 00:13:38,860 --> 00:13:40,800 >> - [Không nghe thấy] OK. 423 00:13:40,800 --> 00:13:46,236 Vì vậy, tôi sẽ đến kiểm tra kết thúc đầu tiên để xác định nếu there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Vỗ tay] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [END PLAYBACK] 427 00:13:55,729 --> 00:13:56,520 DAVID J. Malan: OK. 428 00:13:56,520 --> 00:13:59,760 Vì vậy, phân loại rõ ràng cửa dẫn đến hiệu quả cao hơn. 429 00:13:59,760 --> 00:14:01,680 Và như vậy, nhanh gấp hai lần là những gì tôi có nghĩa là ở đó. 430 00:14:01,680 --> 00:14:03,270 Và do đó, Jay đã may mắn cả hai lần. 431 00:14:03,270 --> 00:14:06,685 Và anh cũng đã may mắn vì cuối cùng năm, tôi ra lệnh cho một số đĩa Blu-ray 432 00:14:06,685 --> 00:14:07,560 để thực sự đưa ra. 433 00:14:07,560 --> 00:14:09,768 Tôi xin lỗi năm nay, chúng tôi không có cùng, Trevor. 434 00:14:09,768 --> 00:14:11,540 Nhưng vẫn còn tốt hơn là một vài năm trở lại. 435 00:14:11,540 --> 00:14:14,820 Và một số bạn có thể biết điều này đồng, Sean, khi ông ở CS50, 436 00:14:14,820 --> 00:14:17,780 đã được thử thách với chính xác cùng một vấn đề, mặc dù trong SD, 437 00:14:17,780 --> 00:14:19,360 như bạn sẽ sớm thấy, trở lại trong ngày. 438 00:14:19,360 --> 00:14:22,622 Và bạn sẽ thấy rằng không chỉ anh lâu hơn một chút so với Jay, 439 00:14:22,622 --> 00:14:25,580 lâu hơn một chút so với Trevor, nó là thực sự có cơ hội tuyệt vời này 440 00:14:25,580 --> 00:14:29,820 để tham gia vào hầu như tất cả mọi người trong một đám đông la Price is Right, khuyến khích 441 00:14:29,820 --> 00:14:31,889 anh ta để tìm số chúng tôi đang tìm kiếm. 442 00:14:31,889 --> 00:14:32,930 Hãy. có một cái nhìn nhanh chóng. 443 00:14:32,930 --> 00:14:33,320 >> [VIDEO PLAYBACK] 444 00:14:33,320 --> 00:14:33,820 >> -ĐƯỢC. 445 00:14:33,820 --> 00:14:36,680 Vì vậy, nhiệm vụ của bạn ở đây, Sean, là sau đây. 446 00:14:36,680 --> 00:14:40,860 Tôi đã giấu đằng sau những cửa số bảy. 447 00:14:40,860 --> 00:14:45,120 Nhưng nằm khuất trong một số các cửa cũng như là những con số tiêu cực khác. 448 00:14:45,120 --> 00:14:47,500 Và mục tiêu của bạn là để suy nghĩ của hàng trên cùng của số 449 00:14:47,500 --> 00:14:50,390 như chỉ là một mảng, hoặc chỉ chuỗi các mẩu giấy 450 00:14:50,390 --> 00:14:51,510 với những con số phía sau họ. 451 00:14:51,510 --> 00:14:55,540 Và mục tiêu của bạn là, chỉ sử dụng đầu mảng ở đây, tìm thấy tôi số bảy. 452 00:14:55,540 --> 00:14:58,570 Và chúng tôi đang đi sau đó để phê phán làm thế nào bạn đi về làm việc đó. 453 00:14:58,570 --> 00:14:59,070 -Được rồi. 454 00:14:59,070 --> 00:15:00,850 -find Chúng tôi biết số bảy, xin vui lòng. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Không. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Năm, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Cười] 461 00:15:24,770 --> 00:15:25,910 >> Nó không phải là một câu hỏi trick. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 One. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Cười] 466 00:15:34,695 --> 00:15:37,861 Tại thời điểm này, điểm số của bạn không phải là rất tốt, vì vậy bạn cũng có thể tiếp tục đi. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Ba. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Cười] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Đi trên. 473 00:15:47,774 --> 00:15:50,690 Thành thật mà nói, tôi không thể không tự hỏi thậm chí những gì bạn đang suy nghĩ về, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Cười] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Chỉ có hàng hàng đầu, do bạn đã có ba trái. 477 00:15:55,020 --> 00:15:56,200 Vì vậy, tìm thấy tôi bảy. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Cười] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Bảy. 484 00:16:26,946 --> 00:16:28,780 >> [Vỗ tay] 485 00:16:28,780 --> 00:16:29,426 >> Được rồi. 486 00:16:29,426 --> 00:16:30,360 >> [END PLAYBACK] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. Malan: Vì vậy, chúng ta có thể xem các tất cả các ngày dài. 488 00:16:31,840 --> 00:16:34,090 Và tất nhiên, một số trình diễn năm nay có lẽ 489 00:16:34,090 --> 00:16:36,330 bây giờ sẽ kết thúc trong tiếp theo Video của năm là tốt. 490 00:16:36,330 --> 00:16:39,040 Vì vậy, bây giờ chúng ta thực sự tập trung vào các thuật toán 491 00:16:39,040 --> 00:16:42,140 ở đây, và xem nếu chúng ta không thể bây giờ bắt đầu để chính thức hóa 492 00:16:42,140 --> 00:16:46,650 làm thế nào chúng ta có thể đi về việc dữ liệu của chúng tôi vào trạng thái này mà nó được sắp xếp, 493 00:16:46,650 --> 00:16:50,054 vì vậy mà cuối cùng, chúng ta có thể thực sự tìm kiếm nó một cách hiệu quả hơn. 494 00:16:50,054 --> 00:16:52,470 Và mặc dù chúng ta đang đi sử dụng bộ dữ liệu tương đối nhỏ, 495 00:16:52,470 --> 00:16:54,511 như tám con số chúng tôi có ở đây trên bảng, 496 00:16:54,511 --> 00:16:58,230 cuối cùng những ý tưởng tương tự có thể được áp dụng 1.000 đầu vào, một triệu đầu vào, 497 00:16:58,230 --> 00:17:02,100 4 tỷ đầu vào, bởi vì các thuật toán đang có được về cơ bản giống nhau. 498 00:17:02,100 --> 00:17:05,359 >> Và do đó, đây là cuối cùng của chúng tôi cơ hội cho các tình nguyện viên ngày hôm nay, 499 00:17:05,359 --> 00:17:09,790 nhưng có lẽ là một trong tham gia nhiều nhất, mà chúng cần tám tình nguyện viên 500 00:17:09,790 --> 00:17:12,960 để đi lên và đi bộ với chúng tôi qua quá trình phân loại những gì sẽ sớm 501 00:17:12,960 --> 00:17:15,212 được các nhạc đứng ở đây. 502 00:17:15,212 --> 00:17:16,170 Hãy để tôi bắt đầu trở lại đây. 503 00:17:16,170 --> 00:17:19,692 >> Vì vậy, một trong các màu xanh lá cây turquoise-- là nó? 504 00:17:19,692 --> 00:17:21,130 Bạn đang cam kết? 505 00:17:21,130 --> 00:17:21,630 Hai. 506 00:17:21,630 --> 00:17:23,069 Come on xuống. 507 00:17:23,069 --> 00:17:23,569 ĐƯỢC. 508 00:17:23,569 --> 00:17:24,420 Ba. 509 00:17:24,420 --> 00:17:25,400 Bốn. 510 00:17:25,400 --> 00:17:27,247 Hãy me-- OK, năm. 511 00:17:27,247 --> 00:17:28,830 Bạn đang được đề cử bởi bạn bè của bạn. 512 00:17:28,830 --> 00:17:31,340 Sáu, bảy, tám người. 513 00:17:31,340 --> 00:17:32,130 Nào lên. 514 00:17:32,130 --> 00:17:32,630 Được rồi. 515 00:17:32,630 --> 00:17:33,190 Cam ơn rât nhiêu. 516 00:17:33,190 --> 00:17:33,689 Nào lên. 517 00:17:33,689 --> 00:17:34,790 Nào lên. 518 00:17:34,790 --> 00:17:35,330 >> Được rồi. 519 00:17:35,330 --> 00:17:38,890 Vì vậy, những gì chúng tôi có và here-- này là một trong số những người vụng về, 520 00:17:38,890 --> 00:17:42,390 vì điều này sẽ yêu cầu bạn hài hước tôi chỉ là một chút ít thời gian. 521 00:17:42,390 --> 00:17:43,442 Bạn phải là số một. 522 00:17:43,442 --> 00:17:44,150 Tên bạn là gì? 523 00:17:44,150 --> 00:17:44,610 >> Annan: Annan. 524 00:17:44,610 --> 00:17:45,526 >> DAVID J. Malan: Annan. 525 00:17:45,526 --> 00:17:46,092 David. 526 00:17:46,092 --> 00:17:46,800 Tên bạn là gì? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. Malan: Joseph, bạn là số hai. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, số ba. 530 00:17:52,260 --> 00:17:53,722 Stefan, số bốn. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. Malan: Cynthia, thứ năm. 533 00:17:57,548 --> 00:17:58,452 [Không nghe thấy] 534 00:17:58,452 --> 00:17:59,618 DAVID J. Malan: [Không nghe thấy]. 535 00:17:59,618 --> 00:18:00,391 David, số sáu. 536 00:18:00,391 --> 00:18:00,890 MATT: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. Malan: số Matt bảy. 538 00:18:02,160 --> 00:18:02,850 Và? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. Malan: Waverly, số tám. 541 00:18:04,470 --> 00:18:04,970 Được rồi. 542 00:18:04,970 --> 00:18:06,510 Nếu bạn could-- whoops. 543 00:18:06,510 --> 00:18:08,820 Nếu tất cả các bạn, như bạn Thách thức đầu tiên, có 544 00:18:08,820 --> 00:18:10,820 tám khán đài âm nhạc ở đây phải đối mặt với khán giả. 545 00:18:10,820 --> 00:18:14,200 Nếu bạn có thể đưa con số của bạn trên những nhạc đứng theo cách như vậy 546 00:18:14,200 --> 00:18:16,560 rằng họ lên đường với cùng một số trên bảng. 547 00:18:16,560 --> 00:18:19,560 Vì vậy, làm cho mình trông như thế bởi đưa con số của bạn bằng các nhạc 548 00:18:19,560 --> 00:18:21,960 đứng ở đây. 549 00:18:21,960 --> 00:18:25,980 Tuyệt vời cho đến nay. 550 00:18:25,980 --> 00:18:26,600 >> Tuyệt vời. 551 00:18:26,600 --> 00:18:26,890 ĐƯỢC. 552 00:18:26,890 --> 00:18:29,556 Vì vậy, bây giờ, chúng tôi sẽ yêu cầu các câu hỏi trong một vài cách khác nhau. 553 00:18:29,556 --> 00:18:31,610 Làm thế nào chúng ta có thể đi về phân loại những người này lên đây? 554 00:18:31,610 --> 00:18:34,500 Bởi vì chúng tôi đã có một vài phương pháp trước đó, nhờ đó mà chúng tôi đã 555 00:18:34,500 --> 00:18:36,360 loại làm hai xô nước khác nhau. 556 00:18:36,360 --> 00:18:38,842 Và sau đó chúng tôi đã thường vẽ ra những thứ cùng nhau. 557 00:18:38,842 --> 00:18:41,050 Ngay khi chúng tôi nhìn thấy hai con số mà thuộc về nhau, 558 00:18:41,050 --> 00:18:41,975 chúng tôi đặt chúng lại với nhau. 559 00:18:41,975 --> 00:18:43,350 Hai chữ cái thuộc về nhau. 560 00:18:43,350 --> 00:18:45,058 >> Nhưng chúng ta hãy xem chúng tôi không thể chính thức hóa này, 561 00:18:45,058 --> 00:18:48,044 vì vậy mà cuối cùng chúng ta có một số mã giả bạn sẽ, 562 00:18:48,044 --> 00:18:49,710 mà bạn có thể giải quyết những vấn đề này. 563 00:18:49,710 --> 00:18:51,870 Vì vậy, bây giờ, tôi nhìn ra ngoài ở những con số ở đây. 564 00:18:51,870 --> 00:18:55,030 Và tôi nhìn thấy một bó toàn bộ những sai lầm. 565 00:18:55,030 --> 00:18:57,750 Cuối cùng, tôi muốn một trên trái và tám trên bên phải. 566 00:18:57,750 --> 00:19:00,650 >> Và vì vậy tôi đang tìm kiếm tại hai, bốn và hai. 567 00:19:00,650 --> 00:19:02,930 Và vấn đề là gì, rõ ràng? 568 00:19:02,930 --> 00:19:04,261 Yeah. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Hai rõ ràng là đi trước bốn, vì vậy bạn có biết những gì? 571 00:19:07,160 --> 00:19:10,210 Hãy để chúng tôi có cách tiếp cận tham lam, nếu bạn sẽ, nhiều vấn đề như thế 572 00:19:10,210 --> 00:19:13,790 thiết one-- nếu bạn nhớ lại từ Standard Edition của Problem Set One, 573 00:19:13,790 --> 00:19:16,820 nơi mà tôi chỉ ở địa phương giải quyết vấn đề mà ở ngay tại đây trước mặt tôi 574 00:19:16,820 --> 00:19:17,690 và nhìn thấy nơi nó dẫn tôi. 575 00:19:17,690 --> 00:19:17,870 >> ĐƯỢC. 576 00:19:17,870 --> 00:19:20,161 Vì vậy, hai và bốn, để tôi đi trước và chỉ trao đổi hai bạn. 577 00:19:20,161 --> 00:19:22,400 Nếu bạn có thể chất có thể di chuyển mình và giấy của bạn, 578 00:19:22,400 --> 00:19:25,040 Tôi dường như đã nhận liệt kê trong một nhà nước tốt hơn. 579 00:19:25,040 --> 00:19:26,330 >> Bây giờ, họ đang tốt. 580 00:19:26,330 --> 00:19:28,480 Tôi sẽ di chuyển trên, bốn và sáu, có vẻ tốt. 581 00:19:28,480 --> 00:19:29,110 Không thành vấn đề. 582 00:19:29,110 --> 00:19:30,440 Sáu và tám, OK. 583 00:19:30,440 --> 00:19:31,860 Tám và một người, một vấn đề khác. 584 00:19:31,860 --> 00:19:34,750 Bởi vì những gì là sự thật về tám và một trong những? 585 00:19:34,750 --> 00:19:36,990 One đến trước tám, và vì vậy những gì chúng ta nên làm gì? 586 00:19:36,990 --> 00:19:38,090 Hãy trao đổi hai. 587 00:19:38,090 --> 00:19:39,316 Một tám người. 588 00:19:39,316 --> 00:19:40,690 Và bây giờ, tôi sẽ tiếp tục đi. 589 00:19:40,690 --> 00:19:42,030 Tôi sẽ tiếp tục tìm kiếm ở phía trước. 590 00:19:42,030 --> 00:19:42,840 Và chúng ta hãy xem những gì sẽ xảy ra. 591 00:19:42,840 --> 00:19:44,680 Tám và ba, của Tất nhiên, trong trật tự. 592 00:19:44,680 --> 00:19:45,815 Hãy trao đổi. 593 00:19:45,815 --> 00:19:46,940 Tám và bảy, tất nhiên. 594 00:19:46,940 --> 00:19:47,481 Trong trật tự. 595 00:19:47,481 --> 00:19:48,280 Hãy trao đổi. 596 00:19:48,280 --> 00:19:49,940 Tám và năm, tất nhiên, chúng ta hãy trao đổi. 597 00:19:49,940 --> 00:19:50,560 Được rồi. 598 00:19:50,560 --> 00:19:51,880 Danh sách được sắp xếp. 599 00:19:51,880 --> 00:19:53,060 yes? 600 00:19:53,060 --> 00:19:54,280 >> OK, rõ ràng là không. 601 00:19:54,280 --> 00:19:55,860 Nhưng nó là một chút tốt hơn, phải không? 602 00:19:55,860 --> 00:19:57,270 Bởi vì thông báo những gì đã xảy ra. 603 00:19:57,270 --> 00:20:01,749 Mỗi lần chúng tôi thực hiện một trao đổi, một nhỏ hơn số loại percolated theo cách đó, 604 00:20:01,749 --> 00:20:03,790 và một số lớn hơn percolated cách này, hoặc chúng tôi sẽ 605 00:20:03,790 --> 00:20:06,880 bắt đầu câu nói hởi đến trái hoặc bọt khí bên phải. 606 00:20:06,880 --> 00:20:10,080 >> Bây giờ, đó là không đủ, bởi vì lúc tốt nhất một số có thể 607 00:20:10,080 --> 00:20:11,990 đã di chuyển một chỗ về phía trước, hoặc ít nhất 608 00:20:11,990 --> 00:20:13,880 một số có thể có chuyển một chỗ xa hơn. 609 00:20:13,880 --> 00:20:16,369 Vì vậy, bạn biết những gì, loại này của làm việc khá tốt cho đến nay. 610 00:20:16,369 --> 00:20:17,410 Hãy để tôi chỉ cần thử nó một lần nữa. 611 00:20:17,410 --> 00:20:18,880 Hai và bốn, họ đang OK. 612 00:20:18,880 --> 00:20:20,180 Bốn và sáu, họ đang OK. 613 00:20:20,180 --> 00:20:21,790 Sáu và một, trong trật tự. 614 00:20:21,790 --> 00:20:23,007 Vì vậy, hãy trao đổi hai bạn. 615 00:20:23,007 --> 00:20:25,840 Và bây giờ, thấy ra vấn đề của bắt đầu để có được một chút tốt hơn nữa. 616 00:20:25,840 --> 00:20:27,006 Sáu và ba, trong trật tự. 617 00:20:27,006 --> 00:20:28,100 Hãy trao đổi hai bạn. 618 00:20:28,100 --> 00:20:29,730 Sáu và bảy, bạn tốt. 619 00:20:29,730 --> 00:20:32,230 Bảy năm và, tất nhiên, không theo thứ tự. 620 00:20:32,230 --> 00:20:33,920 Bảy và tám, theo thứ tự. 621 00:20:33,920 --> 00:20:36,470 Và bây giờ, tôi có thể cần đến làm điều này một vài lần nữa. 622 00:20:36,470 --> 00:20:39,830 Và trên thực tế, suy nghĩ cho mình có lẽ bao nhiêu lần tối đa 623 00:20:39,830 --> 00:20:41,330 Có lẽ tôi phải đi bộ qua lại? 624 00:20:41,330 --> 00:20:42,390 >> Chúng ta sẽ quay trở lại đó. 625 00:20:42,390 --> 00:20:43,700 Vì vậy, hai và bốn là vẫn OK. 626 00:20:43,700 --> 00:20:44,940 Bốn và một, nope. 627 00:20:44,940 --> 00:20:45,747 Vì vậy, chúng ta hãy trao đổi. 628 00:20:45,747 --> 00:20:47,830 Và một lần nữa, thông báo trực quan một là loại bọt 629 00:20:47,830 --> 00:20:49,163 bên trái, nơi mà nó nên được. 630 00:20:49,163 --> 00:20:50,010 Bốn và ba swap. 631 00:20:50,010 --> 00:20:51,330 Bốn và sáu. 632 00:20:51,330 --> 00:20:53,100 Sáu năm và trao đổi. 633 00:20:53,100 --> 00:20:53,959 Sáu và bảy. 634 00:20:53,959 --> 00:20:55,000 Bảy và tám là tốt. 635 00:20:55,000 --> 00:20:55,500 >> Tốt. 636 00:20:55,500 --> 00:20:58,460 Chúng tôi đang nhận được thậm chí còn tốt hơn. 637 00:20:58,460 --> 00:20:59,130 Vì vậy, chúng ta hãy xem. 638 00:20:59,130 --> 00:21:00,940 Bây giờ, chúng ta có hai và một. 639 00:21:00,940 --> 00:21:02,520 Tất nhiên, trao đổi. 640 00:21:02,520 --> 00:21:07,520 Hai và ba, ba và bốn, bốn và năm, sáu và bảy, bảy và tám. 641 00:21:07,520 --> 00:21:08,020 Tốt. 642 00:21:08,020 --> 00:21:08,730 Và bạn biết những gì? 643 00:21:08,730 --> 00:21:11,190 Bởi vì tôi đã thực hiện một sự thay đổi đó, hãy để tôi làm một kiểm tra sự tỉnh táo. 644 00:21:11,190 --> 00:21:13,023 Hãy để tôi đi tất cả các cách bắt đầu trở lại. 645 00:21:13,023 --> 00:21:13,680 ĐƯỢC. 646 00:21:13,680 --> 00:21:14,750 Một, two-- yup, thấy không? 647 00:21:14,750 --> 00:21:15,870 Một cái gì đó đã sai. 648 00:21:15,870 --> 00:21:18,420 Ba, bốn, năm, sáu, bảy, tám. 649 00:21:18,420 --> 00:21:21,920 Và trong đường chuyền cuối cùng này, là bạn cảm thấy thoải mái với bây giờ của tôi 650 00:21:21,920 --> 00:21:23,830 tuyên bố đây là sắp xếp? 651 00:21:23,830 --> 00:21:24,330 ĐƯỢC. 652 00:21:24,330 --> 00:21:25,880 Nhìn bề ngoài, điều đó hoàn toàn đúng. 653 00:21:25,880 --> 00:21:28,410 Nhưng chức năng, những gì đã làm cũng chỉ xảy ra 654 00:21:28,410 --> 00:21:31,870 trong đó đường chuyền cuối cùng cho phép bạn để xác nhận rằng danh sách này thực sự là 655 00:21:31,870 --> 00:21:32,660 sắp xếp? 656 00:21:32,660 --> 00:21:34,477 >> Tôi đã làm gì hoặc không làm vượt qua cuối cùng này? 657 00:21:34,477 --> 00:21:35,810 Đung Không có thay đổi. 658 00:21:35,810 --> 00:21:36,120 DAVID J. Malan: Xin lỗi? 659 00:21:36,120 --> 00:21:37,070 Đung Không có thay đổi. 660 00:21:37,070 --> 00:21:38,653 DAVID J. Malan: Không có thay đổi. 661 00:21:38,653 --> 00:21:41,947 Vì vậy, nó sẽ là ngu ngốc của tôi làm điều đó một lần nữa cùng một thuật toán 662 00:21:41,947 --> 00:21:43,780 nếu tôi không thực hiện bất kỳ thay đổi lần đầu tiên. 663 00:21:43,780 --> 00:21:45,160 Và nhà nước đã không thay đổi. 664 00:21:45,160 --> 00:21:47,576 Chắc chắn, tôi sẽ không làm cho bất kỳ thay đổi lần thứ hai. 665 00:21:47,576 --> 00:21:49,820 Và như vậy, nó an toàn hiện nay để nói, danh sách được sắp xếp. 666 00:21:49,820 --> 00:21:52,069 >> Và quả thực, đây là bây giờ một cái gì đó mà chúng ta sẽ thường 667 00:21:52,069 --> 00:21:56,900 gọi bong bóng sắp xếp, theo đó cặp, bạn sửa chữa sai lầm một lần nữa, 668 00:21:56,900 --> 00:22:00,210 và một lần nữa, và một lần nữa, và bạn tiếp tục đi qua lại, 669 00:22:00,210 --> 00:22:03,370 và qua lại, cho đến khi bạn làm cho không có giao dịch hoán đổi như vậy, tại thời điểm đó 670 00:22:03,370 --> 00:22:07,089 bạn có thể tự tin, yeah, tôi hoàn thành sửa chữa tất cả những sai lầm. 671 00:22:07,089 --> 00:22:08,630 Hãy thiết lập lại và cố gắng tiếp cận khác. 672 00:22:08,630 --> 00:22:11,590 Nếu các bạn có thể quay trở lại thứ tự mà bạn đã được một thời gian trước đây, 673 00:22:11,590 --> 00:22:13,780 mà nhìn như thế này. 674 00:22:13,780 --> 00:22:17,640 Bây giờ, chúng ta hãy một cách tiếp cận một ít nhiều giống như cuốn sách kỳ thi, 675 00:22:17,640 --> 00:22:21,122 nhờ đó mà chúng tôi đã không ngừng chọn mẫu tự của bảng chữ cái 676 00:22:21,122 --> 00:22:22,830 rằng chúng tôi loại muốn để đối phó với tới. 677 00:22:22,830 --> 00:22:26,420 Có lẽ đó là một lá thư cao, như A, hoặc một thư Z. thấp 678 00:22:26,420 --> 00:22:28,170 >> Vì vậy, tất cả mọi người trở lại theo thứ tự này. 679 00:22:28,170 --> 00:22:29,800 Và bây giờ hãy để tôi làm việc này. 680 00:22:29,800 --> 00:22:34,880 Hãy xem tôi biết tôi có tám số ở đây. 681 00:22:34,880 --> 00:22:37,410 Tôi sẽ đi trước và chỉ cố tình chọn 682 00:22:37,410 --> 00:22:38,520 các yếu tố nhỏ nhất. 683 00:22:38,520 --> 00:22:38,760 Phải không? 684 00:22:38,760 --> 00:22:39,801 Điều này có vẻ trực quan quá. 685 00:22:39,801 --> 00:22:42,560 Tại sao tôi không tìm nhỏ nhất phần tử, đặt nó nơi nó thuộc về, 686 00:22:42,560 --> 00:22:45,280 sau đó nhận được các phần tử nhỏ nhất tiếp theo, đặt nó, nơi nó thuộc về, và chỉ cần lặp lại. 687 00:22:45,280 --> 00:22:46,820 >> Bởi vì trực giác, mà nên làm việc quá. 688 00:22:46,820 --> 00:22:48,441 Vì vậy, bốn, đó là một con số khá nhỏ. 689 00:22:48,441 --> 00:22:49,940 Tôi sẽ nhớ nơi này là. 690 00:22:49,940 --> 00:22:50,523 Đợi một lát. 691 00:22:50,523 --> 00:22:51,577 Hai là nhỏ hơn. 692 00:22:51,577 --> 00:22:53,910 Bây giờ tôi nhớ nơi hai là, và quên đi bốn. 693 00:22:53,910 --> 00:22:55,050 Chúng tôi sẽ đối phó với điều đó sau này. 694 00:22:55,050 --> 00:22:56,460 Six, tôi không quan tâm. 695 00:22:56,460 --> 00:22:57,810 Tám, tôi không quan tâm. 696 00:22:57,810 --> 00:22:59,780 Một là số lượng nhỏ mới của tôi. 697 00:22:59,780 --> 00:23:01,470 Vì vậy, tôi sẽ nhớ nơi có một. 698 00:23:01,470 --> 00:23:02,534 Ba, không quan tâm. 699 00:23:02,534 --> 00:23:03,450 Bảy, không quan tâm. 700 00:23:03,450 --> 00:23:04,530 Năm, không quan tâm. 701 00:23:04,530 --> 00:23:07,390 >> Vì vậy mà không rơi khỏi các giai đoạn trong năm nay, 702 00:23:07,390 --> 00:23:09,890 Tôi sẽ lấy số one-- và là những gì tên của bạn một lần nữa? 703 00:23:09,890 --> 00:23:10,150 >> Annan: Annan. 704 00:23:10,150 --> 00:23:11,220 >> DAVID J. Malan: Annan. 705 00:23:11,220 --> 00:23:13,540 Và nếu bạn có thể tham gia cùng tôi tại đầu của danh sách, 706 00:23:13,540 --> 00:23:14,870 chúng ta hãy đưa bạn về nơi anh. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- tên của bạn là gì? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. Malan: Stefan là trong cách. 710 00:23:18,191 --> 00:23:23,490 Vì vậy, trước khi Stefan giải quyết điều này vấn đề, những gì chúng ta nên làm gì? 711 00:23:23,490 --> 00:23:25,412 Chúng ta làm gì với Stefan? 712 00:23:25,412 --> 00:23:27,269 >> Đung [không nghe được]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. Malan: OK. 714 00:23:28,060 --> 00:23:28,850 Vì vậy, chúng ta có thể làm điều đó. 715 00:23:28,850 --> 00:23:31,730 Chúng ta có thể loại mất Stefan và mình bốn, và chỉ cần đặt nó trong một biến 716 00:23:31,730 --> 00:23:33,530 và giữ nó cho một số lượng thời gian, 717 00:23:33,530 --> 00:23:35,220 do đó để có chỗ cho số một. 718 00:23:35,220 --> 00:23:36,280 Và đó không phải là xấu. 719 00:23:36,280 --> 00:23:39,270 Tôi có thể đề xuất, tại sao không chúng ta chỉ cần đặt Stefan ở đây? 720 00:23:39,270 --> 00:23:41,610 Tại sao điều này có thể vi phạm một của ý tưởng chúng tôi bắt đầu 721 00:23:41,610 --> 00:23:44,830 nói về thời gian trước, tuần qua? 722 00:23:44,830 --> 00:23:45,330 Yeah? 723 00:23:45,330 --> 00:23:45,740 >> Đung [không nghe được]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. Malan: Không có chỉ số cho nó. 725 00:23:46,860 --> 00:23:49,735 Nếu bạn nghĩ về điều này, thực sự, như một mảng, đây giống như một tiêu cực, 726 00:23:49,735 --> 00:23:52,900 vì vậy không có bộ nhớ thực sự ở đây nếu điều này thực sự là một mảng, 727 00:23:52,900 --> 00:23:55,090 như chúng ta tuyên bố tuần trước trong bài giảng. 728 00:23:55,090 --> 00:23:56,250 Vì vậy, chúng ta không nên làm điều này. 729 00:23:56,250 --> 00:23:57,340 Chúng ta có thể lưu trữ nó trong một biến. 730 00:23:57,340 --> 00:23:57,820 >> Hoặc bạn biết những gì? 731 00:23:57,820 --> 00:23:59,153 Tôi nghe ai đó khuyên nó. 732 00:23:59,153 --> 00:24:01,020 Những gì người khác chúng ta có thể làm gì với Stefan? 733 00:24:01,020 --> 00:24:03,770 Tại sao chúng ta không đuổi anh ta và đưa anh ta về nơi số một là. 734 00:24:03,770 --> 00:24:05,170 Vì vậy, nếu bạn muốn đi qua đó. 735 00:24:05,170 --> 00:24:07,300 Và quả thực, đây là một giải pháp khá tốt. 736 00:24:07,300 --> 00:24:10,480 Bây giờ trên một mặt, tôi đã loại của làm cho vấn đề tồi tệ hơn. 737 00:24:10,480 --> 00:24:13,650 Bốn giờ xa từ nơi nó nên được. 738 00:24:13,650 --> 00:24:14,900 Nó sẽ được hướng tới một nửa này. 739 00:24:14,900 --> 00:24:16,100 >> Nhưng bạn biết những gì? 740 00:24:16,100 --> 00:24:17,630 Có thể đã là may mắn. 741 00:24:17,630 --> 00:24:18,822 Có lẽ số tám đã ở đây. 742 00:24:18,822 --> 00:24:20,530 Và như vậy, có lẽ chúng ta sẽ đã nhận được may mắn, 743 00:24:20,530 --> 00:24:22,460 và đẩy tám gần hơn đến cùng. 744 00:24:22,460 --> 00:24:24,710 Vì vậy, vào cuối ngày, nó loại của tất cả các trung bình ra. 745 00:24:24,710 --> 00:24:26,085 Chúng ta không cần phải quan tâm đến bốn. 746 00:24:26,085 --> 00:24:29,400 Tất cả tôi quan tâm bây giờ là lựa chọn các phần tử nhỏ nhất. 747 00:24:29,400 --> 00:24:32,030 >> Và bây giờ, những gì tôi sẽ làm là quên về một số 748 00:24:32,030 --> 00:24:35,160 vĩnh viễn, bởi vì tôi biết danh sách phía sau tôi bây giờ được sắp xếp. 749 00:24:35,160 --> 00:24:36,720 Vì vậy, danh sách của tôi trước đây là kích thước tám. 750 00:24:36,720 --> 00:24:37,720 Bây giờ, nó có kích thước bảy. 751 00:24:37,720 --> 00:24:40,340 Vì vậy, vấn đề của tôi là nhận được nhỏ hơn, mặc dù tuyến tính. 752 00:24:40,340 --> 00:24:43,022 Vì vậy, bây giờ, tôi sẽ chọn phần tử nhỏ nhất hiện nay, hai. 753 00:24:43,022 --> 00:24:46,520 Sáu, tám, bốn, ba, bảy, năm. 754 00:24:46,520 --> 00:24:47,770 Đó là yếu tố nhỏ nhất. 755 00:24:47,770 --> 00:24:49,416 Vì vậy, những gì tôi sẽ làm gì with-- là những gì tên của bạn một lần nữa? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. Malan: Joseph? 758 00:24:50,085 --> 00:24:52,000 Chúng tôi đang đi để lại Joseph tại chỗ. 759 00:24:52,000 --> 00:24:54,842 Bây giờ, tôi sẽ giả vờ rằng những kẻ are-- tốt, 760 00:24:54,842 --> 00:24:56,550 Tôi biết rằng hai đã được sắp xếp. 761 00:24:56,550 --> 00:24:58,424 Bây giờ chúng ta tập trung vào các còn lại của danh sách. 762 00:24:58,424 --> 00:25:00,080 Sáu là nhỏ nhất hiện nay. 763 00:25:00,080 --> 00:25:01,190 Tám là lớn hơn. 764 00:25:01,190 --> 00:25:02,970 Bốn doanh nghiệp là nhỏ nhất hiện nay. 765 00:25:02,970 --> 00:25:04,762 Bây giờ ba là nhỏ nhất hiện nay. 766 00:25:04,762 --> 00:25:07,720 Và vì vậy bây giờ, tôi sẽ chọn ba, người is-- tên của bạn là gì nữa? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. Malan: Serena, nếu bạn có thể lấy số lượng và trao đổi của bạn with-- 769 00:25:10,620 --> 00:25:11,550 Kalsang: Kalsang. 770 00:25:11,550 --> 00:25:12,940 DAVID J. Malan: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Quay trở lại sau, và chúng tôi đi để trao đổi hai. 772 00:25:15,220 --> 00:25:17,360 Và bây giờ, chúng ta hãy đặt này trên máy lái tự động. 773 00:25:17,360 --> 00:25:21,589 Tôi sẽ đi và để nó đến với bạn để chọn các yếu tố nhỏ nhất tiếp theo. 774 00:25:21,589 --> 00:25:22,380 Dun, dun, dun, dun. 775 00:25:22,380 --> 00:25:24,560 Số bốn, những gì bạn nên làm gì? 776 00:25:24,560 --> 00:25:26,261 Tuyệt vời. 777 00:25:26,261 --> 00:25:27,760 Bây giờ, tôi sẽ làm cho đường chuyền khác. 778 00:25:27,760 --> 00:25:28,590 Dun, dun, dun, dun. 779 00:25:28,590 --> 00:25:31,465 Tôi thấy năm là nhỏ nhất tiếp theo. 780 00:25:31,465 --> 00:25:32,840 Bây giờ, tôi sẽ đi đường chuyền khác. 781 00:25:32,840 --> 00:25:33,631 Dun, dun, dun, dun. 782 00:25:33,631 --> 00:25:34,880 Sáu là nhỏ nhất. 783 00:25:34,880 --> 00:25:35,520 Tốt. 784 00:25:35,520 --> 00:25:36,585 Bảy là nhỏ nhất. 785 00:25:36,585 --> 00:25:37,085 Không thay đổi. 786 00:25:37,085 --> 00:25:38,630 Tám là nhỏ nhất. 787 00:25:38,630 --> 00:25:39,170 Xong. 788 00:25:39,170 --> 00:25:43,900 >> Vì vậy, những gì chúng ta vừa thực hiện bằng cách lặp đi lặp lại chọn một trong các yếu tố sau khi khác 789 00:25:43,900 --> 00:25:47,230 được thực hiện một cái gì đó mà chúng tôi sẽ chính thức hóa như sắp xếp chọn. 790 00:25:47,230 --> 00:25:49,120 Và nó có lẽ thậm chí đơn giản để giải thích, 791 00:25:49,120 --> 00:25:51,310 trong đó nghĩa là tất cả các bạn muốn làm là chỉ cần giữ 792 00:25:51,310 --> 00:25:54,700 đi lui trong danh sách lựa chọn, các phần tử nhỏ nhất tiếp theo, 793 00:25:54,700 --> 00:25:55,720 cho đến khi bạn thực hiện xong. 794 00:25:55,720 --> 00:25:58,650 >> Vì vậy, nó thậm chí còn đơn giản hơn, có lẽ trực giác, so với năm ngoái. 795 00:25:58,650 --> 00:26:00,020 Hãy thử một lần cuối cùng. 796 00:26:00,020 --> 00:26:03,060 Nếu các bạn có thể thiết lập lại chính mình vào các vị trí sau 797 00:26:03,060 --> 00:26:08,600 một lần cuối cùng, chúng ta hãy xem nếu chúng ta không thể Bây giờ chính thức hóa một cách tiếp cận khác. 798 00:26:08,600 --> 00:26:12,857 Trong thực tế, sẽ có ai đó ra có muốn đề nghị 799 00:26:12,857 --> 00:26:14,440 làm thế nào khác chúng ta có thể đi về việc này? 800 00:26:14,440 --> 00:26:17,439 Nếu không có tung ra từ thông dụng hoặc loại các câu trả lời đó đã được biết đến, 801 00:26:17,439 --> 00:26:19,689 chỉ bằng trực giác, những gì chúng ta có thể làm gì? 802 00:26:19,689 --> 00:26:21,635 >> Đung [không nghe được]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. Malan: Yeah. 804 00:26:22,510 --> 00:26:24,620 Vì vậy, có một số trực giác tuyệt vời đó. 805 00:26:24,620 --> 00:26:28,020 Những điều tốt đẹp dường như xảy ra vậy, đến nay khoa học máy tính khi chúng ta chia 806 00:26:28,020 --> 00:26:30,832 và chinh phục các vấn đề về phân chia nó trong một nửa và một nửa và một nửa. 807 00:26:30,832 --> 00:26:32,540 Và như vậy thực sự, chúng tôi có thể bắt đầu để làm điều đó. 808 00:26:32,540 --> 00:26:35,754 Và trên thực tế, đó là có được, chúng tôi sẽ thấy, một trong những giải pháp tốt nhất của chúng tôi nêu ra. 809 00:26:35,754 --> 00:26:37,420 Nhưng chúng ta hãy quay trở lại mà chẳng bao lâu. 810 00:26:37,420 --> 00:26:40,500 Trong thực tế, chúng tôi đang đi làm rằng một chút vào cuối tuần này. 811 00:26:40,500 --> 00:26:42,180 Những gì người khác chúng ta có thể làm gì để giải quyết này? 812 00:26:42,180 --> 00:26:44,647 Vì vậy, tất cả mọi người ở đây là trong Để dường như ngẫu nhiên. 813 00:26:44,647 --> 00:26:45,230 Bạn biết gì? 814 00:26:45,230 --> 00:26:48,320 Thay vì đi qua lại, qua lại, lui 815 00:26:48,320 --> 00:26:50,624 mỗi thời gian, điều này cảm thấy như Tôi đang làm rất nhiều đi bộ. 816 00:26:50,624 --> 00:26:52,790 Tại sao tôi không chỉ bắt đầu ở đầu của danh sách, 817 00:26:52,790 --> 00:26:54,960 và chỉ cần đặt bốn nơi mà nó thuộc? 818 00:26:54,960 --> 00:26:59,680 Vì vậy, hãy để tôi giả định cho thời điểm đó danh sách của tôi chỉ là yếu tố đầu tiên này. 819 00:26:59,680 --> 00:27:04,937 Được bốn phân loại tại thời điểm này trong thời gian, nếu tất cả tôi quan tâm là tất cả mọi thứ ở đây? 820 00:27:04,937 --> 00:27:06,520 Đây là loại tầm thường đúng, phải không? 821 00:27:06,520 --> 00:27:10,000 Giống như các danh sách có chứa một số, và rằng số bốn rõ ràng là sắp xếp. 822 00:27:10,000 --> 00:27:13,070 >> Vì vậy, hãy để tôi chỉ định là danh sách này được sắp xếp. 823 00:27:13,070 --> 00:27:15,090 Nhưng bây giờ tôi có phần còn lại của danh sách này. 824 00:27:15,090 --> 00:27:17,240 Vì vậy, bây giờ, tôi gặp hai. 825 00:27:17,240 --> 00:27:21,690 Trong trường hợp hai không rõ ràng thuộc đối với bốn với? 826 00:27:21,690 --> 00:27:22,580 Trước khi bốn. 827 00:27:22,580 --> 00:27:23,862 Vì vậy, những gì tôi có thể làm ở đây? 828 00:27:23,862 --> 00:27:24,820 Nhắc lại xem tên bạn là gì? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. Malan: Joseph, nếu bạn có thể bước trở lại 831 00:27:26,030 --> 00:27:27,790 chỉ trong một khoảnh khắc nào với số của bạn. 832 00:27:27,790 --> 00:27:31,130 Và bây giờ những gì Stefan nên làm ở đây? 833 00:27:31,130 --> 00:27:33,720 Hãy chuyển Stefan ở đây. 834 00:27:33,720 --> 00:27:35,520 Và bây giờ, chúng ta hãy Joseph vào đây. 835 00:27:35,520 --> 00:27:39,660 Và bây giờ, hãy để tôi cho rằng tất cả mọi thứ ở đây được sắp xếp. 836 00:27:39,660 --> 00:27:42,474 Vì vậy, kết quả tương tự, nhưng một cách tiếp cận cơ bản khác nhau. 837 00:27:42,474 --> 00:27:44,140 Tôi thậm chí còn không nhìn những gì ở dưới đó. 838 00:27:44,140 --> 00:27:46,310 Tôi chỉ tiếp tục dùng các yếu tố như họ đang giao cho tôi, 839 00:27:46,310 --> 00:27:47,240 và đối phó với chúng. 840 00:27:47,240 --> 00:27:48,330 >> Vì vậy, bây giờ, tôi thấy số sáu. 841 00:27:48,330 --> 00:27:51,110 Không số sáu thuộc về đâu? 842 00:27:51,110 --> 00:27:53,250 Chúng tôi có hai, bốn, sáu. 843 00:27:53,250 --> 00:27:54,800 Chính xác nơi cô là ngay bây giờ. 844 00:27:54,800 --> 00:27:57,750 Vì vậy, chúng ta hãy rời khỏi đó một mình, và bây giờ cho rằng điều này một phần của danh sách 845 00:27:57,750 --> 00:27:58,772 bây giờ được sắp xếp. 846 00:27:58,772 --> 00:28:01,230 Và như vậy, điều này cảm thấy cơ bản khác nhau trong đó tôi chỉ 847 00:28:01,230 --> 00:28:05,230 di chuyển qua danh sách ở đây tuyến tính, và tôi sẽ không bao giờ trở lại tăng gấp đôi. 848 00:28:05,230 --> 00:28:05,730 Vâng. 849 00:28:05,730 --> 00:28:06,230 Được rồi. 850 00:28:06,230 --> 00:28:08,190 Vì vậy, tám, nơi nào bạn thuộc về ai? 851 00:28:08,190 --> 00:28:08,730 Ngay tại đây. 852 00:28:08,730 --> 00:28:09,310 Perfect. 853 00:28:09,310 --> 00:28:10,210 Vì vậy, bây giờ, một. 854 00:28:10,210 --> 00:28:10,900 Uh-oh. 855 00:28:10,900 --> 00:28:13,010 Điều này dường như là sẽ rất tốn kém. 856 00:28:13,010 --> 00:28:15,690 Bây giờ, trong thuật toán trước đó, Tôi chỉ cần hoán đổi người. 857 00:28:15,690 --> 00:28:18,648 Vì vậy, tôi có thể đưa anh ta tất cả các con đường ở đầu, nhưng sau đó chuyển Joseph. 858 00:28:18,648 --> 00:28:21,450 Nhưng nếu tôi chuyển Joseph, bây giờ những gì sẽ là sai lầm? 859 00:28:21,450 --> 00:28:24,250 >> Bây giờ, tôi đã loại undone-- tôi đã thực hiện một bước về phía trước và sau đó 860 00:28:24,250 --> 00:28:26,300 một bước trở lại, bởi vì bây giờ Joseph sẽ được ra khỏi trật tự. 861 00:28:26,300 --> 00:28:26,830 Vì vậy, hãy làm điều này. 862 00:28:26,830 --> 00:28:29,150 Nếu bạn có thể mất một số và bước trở lại chỉ trong một khoảnh khắc. 863 00:28:29,150 --> 00:28:30,490 Làm thế nào chúng ta có thể put-- gì là tên của bạn một lần nữa? 864 00:28:30,490 --> 00:28:31,130 >> Annan: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. Malan: Annan tại chỗ? 866 00:28:32,610 --> 00:28:36,091 Những gì cần phải xảy ra đối với hai, bốn, sáu, tám? 867 00:28:36,091 --> 00:28:37,570 Tất cả họ cần phải thay đổi. 868 00:28:37,570 --> 00:28:42,590 Vì vậy, nếu tám muốn chuyển đầu tiên, sau đó sáu, sau đó bốn, sau đó hai. 869 00:28:42,590 --> 00:28:45,380 Và sau đó Annan, nếu bạn muốn muốn đến ở đây, tốt. 870 00:28:45,380 --> 00:28:47,760 Nhưng ở đây, chúng tôi đã chỉ loại đã phải trả giá 871 00:28:47,760 --> 00:28:49,510 tại một điểm khác nhau trong các thuật toán. 872 00:28:49,510 --> 00:28:52,550 Trong khi đó, lần cuối cùng với lựa chọn sắp xếp, và thậm chí bong bóng sắp xếp, 873 00:28:52,550 --> 00:28:54,700 Tôi đang đi đi lại ra, qua lại, 874 00:28:54,700 --> 00:28:58,360 đó là chắc chắn thêm lên thời gian khôn ngoan, và theo nghĩa đen từng bước. 875 00:28:58,360 --> 00:29:00,660 >> Sắp xếp chèn, lúc đầu Trong nháy mắt, có vẻ như nó là 876 00:29:00,660 --> 00:29:05,150 siêu thông minh hơn, trong đó tôi chỉ làm chậm, tiến bộ đáng kể, 877 00:29:05,150 --> 00:29:07,120 nhưng tôi sẽ không này lại. 878 00:29:07,120 --> 00:29:09,410 Nhưng nếu một người nào đó thực sự là trong trật tự, thông báo 879 00:29:09,410 --> 00:29:10,840 tất cả các công việc tôi phải làm như thế. 880 00:29:10,840 --> 00:29:14,750 Tôi đã phải di chuyển một nửa trong danh sách chỉ để nhường chỗ cho số một. 881 00:29:14,750 --> 00:29:16,790 Vì vậy, nó là cùng một lượng công việc như vậy, cho đến nay nó 882 00:29:16,790 --> 00:29:18,690 cảm thấy, chỉ là một loại công việc khác nhau. 883 00:29:18,690 --> 00:29:19,370 >> Tiếp tục đi. 884 00:29:19,370 --> 00:29:22,657 Vì vậy, bây giờ chúng ta biết rằng tất cả mọi người từ một đến tám đều được sắp xếp. 885 00:29:22,657 --> 00:29:23,740 Ở đây, tôi có số ba. 886 00:29:23,740 --> 00:29:25,864 Nếu bạn muốn đến lấy số ba, bước trở lại một. 887 00:29:25,864 --> 00:29:28,260 Và những gì các bạn cần phải làm gì? 888 00:29:28,260 --> 00:29:28,760 Yep. 889 00:29:28,760 --> 00:29:33,070 Vì vậy, đó là một trong một, hai, ba bước. 890 00:29:33,070 --> 00:29:36,010 Ba đơn vị thời gian mà chỉ có giá tôi, vì vậy mà ba có thể gắn vừa khít. 891 00:29:36,010 --> 00:29:37,460 Cuối cùng, bảy. 892 00:29:37,460 --> 00:29:39,730 >> Chúng ta hãy đi trước và có bạn hãy quay trở lại bước. 893 00:29:39,730 --> 00:29:42,780 Đây chỉ là sẽ chi phí cho chúng tôi một đơn vị thời gian, nhưng đó là OK. 894 00:29:42,780 --> 00:29:44,170 Và bây giờ, năm của đi có đắt hơn một chút. 895 00:29:44,170 --> 00:29:45,340 Nếu bạn muốn để bước trở lại. 896 00:29:45,340 --> 00:29:48,380 Chúng tôi cần phải di chuyển tám, và bảy, và sáu. 897 00:29:48,380 --> 00:29:50,749 Và sau đó tất cả mọi người hiện nay được sắp xếp. 898 00:29:50,749 --> 00:29:52,290 Vì vậy, một bàn tay lớn để các tình nguyện viên của chúng tôi ở đây. 899 00:29:52,290 --> 00:29:53,554 Cam ơn rât nhiêu. 900 00:29:53,554 --> 00:29:56,220 >> [Vỗ tay] 901 00:29:56,220 --> 00:29:56,860 >> Cảm ơn tất cả. 902 00:29:56,860 --> 00:29:57,520 Cảm ơn tất cả. 903 00:29:57,520 --> 00:30:02,940 Vì vậy, chúng ta hãy xem làm thế nào bây giờ chỉ tốn kém tất cả điều đó đã. 904 00:30:02,940 --> 00:30:06,210 Chúng ta hãy xem xét có lẽ đơn giản nhất trong số này, bong bóng sắp xếp. 905 00:30:06,210 --> 00:30:09,950 Và tôi nói đơn giản, chỉ vì bạn có thể giải quyết một cách thèm khát bởi chỉ 906 00:30:09,950 --> 00:30:11,660 sửa chữa các vấn đề cặp ở đây. 907 00:30:11,660 --> 00:30:13,720 Sửa chữa các vấn đề cặp ở đây, một lần nữa và một lần nữa 908 00:30:13,720 --> 00:30:17,680 và một lần nữa, lặp đi lặp lại nhiều lần như bạn thực sự cần. 909 00:30:17,680 --> 00:30:21,050 >> Vì vậy, nó chỉ ra rằng với một loại bong bóng, tốt, 910 00:30:21,050 --> 00:30:25,820 bao nhiêu bước để tôi phải mất trên đèo đầu tiên của thuật toán? 911 00:30:25,820 --> 00:30:30,850 Tôi có thể take-- hãy see-- một, hai, ba, bốn, năm, sáu, bảy. 912 00:30:30,850 --> 00:30:32,190 Và có tám yếu tố ở đây. 913 00:30:32,190 --> 00:30:35,280 Vì vậy, nó giống như n trừ đi 1 bước để nhận được từ sự khởi đầu của danh sách 914 00:30:35,280 --> 00:30:36,380 đến cuối danh sách. 915 00:30:36,380 --> 00:30:41,350 >> Nhưng với sắp xếp chọn, nhớ lại rằng tôi lựa chọn các yếu tố một lần nữa và một lần nữa 916 00:30:41,350 --> 00:30:44,590 và một lần nữa đó là nhỏ nhất, Tôi đang đặt nó tại chỗ, 917 00:30:44,590 --> 00:30:46,616 nhưng sau đó tôi không nhìn phía sau tôi một lần nữa. 918 00:30:46,616 --> 00:30:49,490 Vì vậy, tôi nghĩ rằng đó là một chút rõ ràng hơn sau đó lần đầu tiên, tôi có thể 919 00:30:49,490 --> 00:30:52,680 phải mất tất cả n trừ đi 1 bước để tìm các phần tử nhỏ nhất. 920 00:30:52,680 --> 00:30:55,920 Sau đó, tôi đặt chúng tại chỗ, và tôi đuổi bất cứ ai đã ở đây trước đó. 921 00:30:55,920 --> 00:30:57,500 >> Nhưng sau đó tôi không phải cứ nhìn vào yếu tố này, 922 00:30:57,500 --> 00:30:59,040 vì tôi biết nó đã là nhỏ nhất. 923 00:30:59,040 --> 00:31:01,581 Vì vậy, bây giờ, tôi có thể nhìn vào chỉ bảy yếu tố, sau đó sáu yếu tố, 924 00:31:01,581 --> 00:31:03,290 sau đó năm yếu tố, sau đó bốn yếu tố. 925 00:31:03,290 --> 00:31:06,900 Và do đó, về mặt toán học, nếu n là số phần tử hoặc số 926 00:31:06,900 --> 00:31:11,990 rằng chúng ta bắt đầu với, bạn có thể tưởng tượng rằng đây là giống như n trừ đi 1, 927 00:31:11,990 --> 00:31:14,250 cộng với n trừ đi 2 bước, cộng với n trừ đi 3 bước, 928 00:31:14,250 --> 00:31:16,780 cộng với n trừ đi 4 bước, tất cả các cách xuống chỉ còn một bước. 929 00:31:16,780 --> 00:31:18,160 Và tôi đang trên người cuối cùng của tôi. 930 00:31:18,160 --> 00:31:20,650 >> Và nếu bạn nhớ lại rằng rất nhiều các số liệu thống kê sách hoặc sách toán 931 00:31:20,650 --> 00:31:24,730 có những công thức trên bìa cứng lại hoặc mặt trước của họ, 932 00:31:24,730 --> 00:31:27,690 nó quay ra rằng loạt bài này có thể được thể hiện đơn giản hơn 933 00:31:27,690 --> 00:31:28,857 là n lần n trừ đi 1 trong 2. 934 00:31:28,857 --> 00:31:31,273 Và điều đó là tốt nếu đó là không đi đầu trong tâm trí của bạn. 935 00:31:31,273 --> 00:31:32,420 Nhưng điều này là thực sự đúng. 936 00:31:32,420 --> 00:31:34,449 Đó chỉ là một cách đơn giản của văn bản đó. 937 00:31:34,449 --> 00:31:36,240 Và sau đó nếu bạn nghĩ trở lại trường lớp, 938 00:31:36,240 --> 00:31:38,698 khi bạn chỉ cần bắt đầu nhân những điều trên, điều này tất nhiên, 939 00:31:38,698 --> 00:31:41,820 chỉ được n bình phương trừ đi n chia cho 2. 940 00:31:41,820 --> 00:31:44,772 Tất cả tôi đã làm là mở rộng các biểu thức đó. 941 00:31:44,772 --> 00:31:46,730 Và như vậy chúng ta hãy viết lại này một chút khác nhau. 942 00:31:46,730 --> 00:31:49,780 Đó là n bình phương chia cho 2 trừ đi n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Vì vậy, một lần nữa, tôi chỉ là loại áp dụng một số số học quy tắc đó. 944 00:31:53,270 --> 00:31:57,140 Nhưng nhận thấy bây giờ mà các hạn lớn nhất trong biểu thức này, có thể nói, 945 00:31:57,140 --> 00:31:58,540 là n bình phương. 946 00:31:58,540 --> 00:32:02,910 Vì vậy, có, đó là n bình phương chia cho 2, trừ đi n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Nhưng nói chung, nếu n là sẽ là một giá trị lớn, 948 00:32:05,080 --> 00:32:08,740 Tôi sẽ yêu cầu bồi thường n rằng bình phương sẽ là yếu tố chi phối. 949 00:32:08,740 --> 00:32:10,490 Nó chỉ có được một đóng góp lớn hơn 950 00:32:10,490 --> 00:32:12,877 với số lượng các bước hơn n / 2. 951 00:32:12,877 --> 00:32:13,960 Vì vậy, tôi có ý nghĩa gì bởi điều này? 952 00:32:13,960 --> 00:32:16,795 Hãy thử một ví dụ đơn giản, thậm chí mặc dù toán học được một chút lớn. 953 00:32:16,795 --> 00:32:20,210 >> Vì vậy, giả sử chúng ta đã có 1 triệu người trên sân khấu, hoặc 1 triệu thứ 954 00:32:20,210 --> 00:32:21,320 rằng chúng ta muốn sắp xếp. 955 00:32:21,320 --> 00:32:23,730 Hãy cắm một triệu vào chính xác công thức 956 00:32:23,730 --> 00:32:27,230 để xem có bao nhiêu bước cần phải mất tổng cộng để sắp xếp một triệu yếu tố sử dụng tiếng nói, 957 00:32:27,230 --> 00:32:28,560 sắp xếp chọn. 958 00:32:28,560 --> 00:32:30,760 >> Vì vậy, chúng tôi muốn có một công thức như trước. 959 00:32:30,760 --> 00:32:34,120 Tôi muốn cắm một triệu, vì vậy mà tôi nhận được một triệu bình phương chia cho 2, 960 00:32:34,120 --> 00:32:35,990 trừ đi một triệu chia cho 2. 961 00:32:35,990 --> 00:32:40,180 Nếu tôi làm toán mà trước ở đây, chúng tôi có 500 tỷ 962 00:32:40,180 --> 00:32:47,460 trừ đi 500.000, trong đó cho chúng ta 499.999.500.000, 963 00:32:47,460 --> 00:32:49,270 mà là khá darn lớn. 964 00:32:49,270 --> 00:32:54,370 >> Trong thực tế, nếu bạn so sánh với doanh nghiệp 499.000.000.000, 999 triệu, 965 00:32:54,370 --> 00:33:01,210 500.000 đối với giá trị ban đầu của chúng tôi, 500 tỷ, nó như vậy damn gần. 966 00:33:01,210 --> 00:33:06,850 Phải không? n bình phương chia cho 2 cho us-- hay đúng hơn, n bình phương chia cho 2 967 00:33:06,850 --> 00:33:08,370 đã cho chúng tôi 500 tỷ đồng. 968 00:33:08,370 --> 00:33:13,510 Đó là khá darn gần để 499.999.500.000, 969 00:33:13,510 --> 00:33:17,970 mà là để nói trừ ra 500.000, hay nói chung, trừ đi off 970 00:33:17,970 --> 00:33:20,010 n bình, không thực sự là một vấn đề lớn. 971 00:33:20,010 --> 00:33:22,490 Các n bình phương làm cho các số tăng trưởng rất nhanh. 972 00:33:22,490 --> 00:33:25,790 >> Bây giờ, đây chỉ là quan trọng trong chừng mực như chúng ta, như nhà khoa học máy tính, 973 00:33:25,790 --> 00:33:29,350 nói chung là sẽ không quan tâm quá nhiều về các sắc thái của các công thức 974 00:33:29,350 --> 00:33:31,400 và chính xác những gì câu trả lời chính xác được. 975 00:33:31,400 --> 00:33:33,390 Chúng tôi chăm sóc chỉ có vậy, bạn biết những gì? 976 00:33:33,390 --> 00:33:37,810 Vào cuối ngày, công thức này là vào thứ tự của n bình phương. 977 00:33:37,810 --> 00:33:39,350 >> Vâng, chúng tôi đang phân chia bởi 2 trong đó. 978 00:33:39,350 --> 00:33:41,360 Vâng, chúng tôi đã trừ đi n trừ đi 2. 979 00:33:41,360 --> 00:33:46,860 Nhưng vào cuối ngày, thuật ngữ rằng chúng tôi thực sự đau và tốn chúng tôi 980 00:33:46,860 --> 00:33:48,995 nhiều bước là hạn vuông. 981 00:33:48,995 --> 00:33:51,370 Và vì vậy những gì một nhà khoa học máy tính sẽ thường làm 982 00:33:51,370 --> 00:33:54,160 được bỏ qua tất cả những điều kiện bậc nhỏ hơn, 983 00:33:54,160 --> 00:33:56,900 và chỉ cần nhìn vào một trong đó đóng góp nhiều nhất cho các chi phí. 984 00:33:56,900 --> 00:34:00,530 >> Và điều này là tốt đẹp, bởi vì chúng ta có thể Bây giờ nói chuyện trong tính tổng quát hơn nhiều 985 00:34:00,530 --> 00:34:02,470 về các thuật toán, và có thể so sánh chúng. 986 00:34:02,470 --> 00:34:04,550 Và thực tế là tôi sử dụng O này là cố ý. 987 00:34:04,550 --> 00:34:06,680 Khi tôi nói về thứ tự của, Tôi đặc biệt 988 00:34:06,680 --> 00:34:09,560 đề cập đến một cái gì đó gọi là O. lớn Và lớn O 989 00:34:09,560 --> 00:34:14,090 là một ký hiệu mà một máy tính nhà khoa học sử dụng để mô tả 990 00:34:14,090 --> 00:34:16,710 một trên ràng buộc vào một cái gì đó. 991 00:34:16,710 --> 00:34:21,150 >> Vì vậy, nếu bạn nói rằng một thuật toán là trong O lớn của n bình phương, 992 00:34:21,150 --> 00:34:23,380 như tôi đã đề xuất chỉ là một thời điểm trước đây, phương tiện đó 993 00:34:23,380 --> 00:34:27,710 rằng trong điều khoản của nó đang chạy thời gian hay hiệu quả của nó, 994 00:34:27,710 --> 00:34:30,090 phải mất trên thứ tự của n bình bước. 995 00:34:30,090 --> 00:34:31,420 Có lẽ hơn, có thể ít hơn. 996 00:34:31,420 --> 00:34:33,435 Nhưng đó là vào thứ tự của n bình phương. 997 00:34:33,435 --> 00:34:34,560 Và đó là sự ràng buộc trên. 998 00:34:34,560 --> 00:34:36,530 Nó sẽ không được đau đớn hơn đó. 999 00:34:36,530 --> 00:34:40,800 Nó sẽ không phải là n cubed, hoặc 2 đến n, hoặc một cái gì đó lớn hơn nhiều. 1000 00:34:40,800 --> 00:34:43,800 Đây là một ràng buộc trên trên bất cứ chi phí đó là. 1001 00:34:43,800 --> 00:34:46,150 Vì vậy, cho rằng, chúng ta hãy xem xét một số ví dụ. 1002 00:34:46,150 --> 00:34:49,820 Và đây chỉ là một danh sách hữu hạn lần chạy của rất phổ biến 1003 00:34:49,820 --> 00:34:52,870 cho các thuật toán đó có nghĩa là phải minh họa của một số thứ chúng tôi đã 1004 00:34:52,870 --> 00:34:53,600 nhìn thấy đã. 1005 00:34:53,600 --> 00:34:58,060 >> Vì vậy, ví dụ, trong trường hợp sắp xếp chọn, những gì tôi đang tự xưng ở đây 1006 00:34:58,060 --> 00:35:02,250 là chạy mà sắp xếp chọn của thời gian là vào thứ tự của n bình phương. 1007 00:35:02,250 --> 00:35:06,260 Trong trường hợp xấu nhất, tôi sẽ có một bó toàn bộ các số ngẫu nhiên ở đây. 1008 00:35:06,260 --> 00:35:08,600 Và như chúng ta đã thấy toán học, nếu tôi tiếp tục đi bộ 1009 00:35:08,600 --> 00:35:11,310 thông qua danh sách, thông qua các danh sách, chọn nhỏ nhất tiếp theo 1010 00:35:11,310 --> 00:35:14,410 yếu tố một lần nữa và một lần nữa, nếu tôi thực sự viết xuống tất cả các bước 1011 00:35:14,410 --> 00:35:18,750 Tôi đang tham gia như tôi đã đề xuất formulaically trước đây, đó là vào thứ tự của n bình phương 1012 00:35:18,750 --> 00:35:20,370 bước mà tôi lựa chọn. 1013 00:35:20,370 --> 00:35:24,520 >> Và hóa ra bong bóng đó phân loại và sắp xếp chèn 1014 00:35:24,520 --> 00:35:27,370 chỉ là chậm trong trường hợp xấu nhất. 1015 00:35:27,370 --> 00:35:32,040 Xem xét, ví dụ, sắp xếp chèn, các thuật toán cuối cùng chúng tôi xử lý, 1016 00:35:32,040 --> 00:35:35,500 trong đó có chúng tôi xem xét các yếu tố, và sau đó chèn nó, nơi nó thuộc về. 1017 00:35:35,500 --> 00:35:38,720 Và sau đó chúng tôi nhìn vào các phần tử tiếp theo, và chèn nó, nơi nó thuộc về. 1018 00:35:38,720 --> 00:35:40,990 >> Vì vậy, xem xét các kịch bản tốt nhất có thể. 1019 00:35:40,990 --> 00:35:45,590 Giả sử tôi đã tình nguyện của tôi xếp hàng nghĩa đen như thế này, một đến tám, 1020 00:35:45,590 --> 00:35:47,440 đã được sắp xếp. 1021 00:35:47,440 --> 00:35:51,300 Có bao nhiêu bước là sắp xếp chèn sẽ đi để sắp xếp tám người, 1022 00:35:51,300 --> 00:35:55,640 nếu họ đến trên sân khấu nhìn như thế này? 1023 00:35:55,640 --> 00:35:57,410 >> Tám người đã được sắp xếp. 1024 00:35:57,410 --> 00:35:58,760 Và tôi sử dụng sắp xếp chèn. 1025 00:35:58,760 --> 00:36:02,180 Điều đó cuối cùng của thuật toán. 1026 00:36:02,180 --> 00:36:03,640 Vâng, chúng ta hãy diễn lại nhanh thật. 1027 00:36:03,640 --> 00:36:05,504 Vì vậy, nếu tôi bắt đầu ở đây, tôi thấy một. 1028 00:36:05,504 --> 00:36:06,420 Một thuộc về nơi nào? 1029 00:36:06,420 --> 00:36:07,730 Nó thuộc ngay tại đây. 1030 00:36:07,730 --> 00:36:08,330 Tôi thấy hai. 1031 00:36:08,330 --> 00:36:09,660 Không hai thuộc về đâu? 1032 00:36:09,660 --> 00:36:10,260 Ngay tại đây. 1033 00:36:10,260 --> 00:36:10,900 Tôi nhìn thấy ba. 1034 00:36:10,900 --> 00:36:11,920 Trường hợp nào ba thuộc về ai? 1035 00:36:11,920 --> 00:36:12,480 Ngay tại đây. 1036 00:36:12,480 --> 00:36:13,100 >> Tôi thấy bốn. 1037 00:36:13,100 --> 00:36:13,600 Ngay tại đây. 1038 00:36:13,600 --> 00:36:15,660 Năm, sáu, bảy, tám. 1039 00:36:15,660 --> 00:36:17,320 Không có lý do để lặp lại bản thân mình. 1040 00:36:17,320 --> 00:36:21,260 Và như vậy, có bao nhiêu bước là trong điều kiện của n? 1041 00:36:21,260 --> 00:36:23,870 Đó là vào thứ tự của n bước, phải không? n trừ đi 1. 1042 00:36:23,870 --> 00:36:27,567 Nhưng tôi lấy một số tuyến tính các bước, và bây giờ tôi đang làm. 1043 00:36:27,567 --> 00:36:28,900 Vì vậy, đó là trường hợp tốt nhất, mặc dù. 1044 00:36:28,900 --> 00:36:29,983 Những gì về trường hợp tồi tệ nhất? 1045 00:36:29,983 --> 00:36:32,730 Những gì là tám trên đó, và bảy là xuống đó, 1046 00:36:32,730 --> 00:36:35,840 và một và hai là ở đây, vì vậy rằng danh sách đã thực sự đảo ngược? 1047 00:36:35,840 --> 00:36:38,300 >> Vâng, những gì xảy ra thực sự nếu điều này là số? 1048 00:36:38,300 --> 00:36:41,300 Và chúng tôi sẽ làm chỉ là một vài ví dụ. 1049 00:36:41,300 --> 00:36:49,300 Nếu như, thực sự, số tám là ở đây, và whoops number--. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Vì vậy, những gì nếu quả thực, số tám là tất cả các cách trên đây, 1052 00:36:56,430 --> 00:36:57,790 và tôi đang sử dụng sắp xếp chèn? 1053 00:36:57,790 --> 00:36:58,290 >> ĐƯỢC. 1054 00:36:58,290 --> 00:37:00,280 Tôi khẳng định tại thời điểm đó là tại chỗ. 1055 00:37:00,280 --> 00:37:03,152 Nhưng bây giờ, seven-- nơi nào bảy đi? 1056 00:37:03,152 --> 00:37:04,360 Tất nhiên, nó đi qua đây. 1057 00:37:04,360 --> 00:37:06,760 Vì vậy, tôi phải di chuyển tám trên một nơi. 1058 00:37:06,760 --> 00:37:08,554 Bây giờ sáu, nơi nào nó đi? 1059 00:37:08,554 --> 00:37:09,220 Vâng, tất cả các quyền. 1060 00:37:09,220 --> 00:37:13,150 Bây giờ, tôi phải di chuyển tám trên một nơi, và bảy qua một nơi, 1061 00:37:13,150 --> 00:37:14,440 và sau đó tôi plop xuống sáu. 1062 00:37:14,440 --> 00:37:16,870 >> Vì vậy, lần đầu tiên, nó chi phí tôi một bước để khắc phục điều này, 1063 00:37:16,870 --> 00:37:18,570 sau đó chi phí cho tôi hai bước để sửa chữa mọi thứ. 1064 00:37:18,570 --> 00:37:20,370 Có bao nhiêu bước là nó sẽ đi để sửa chữa 1065 00:37:20,370 --> 00:37:22,720 điều cần đặt năm vào đúng chỗ? 1066 00:37:22,720 --> 00:37:23,340 Ba. 1067 00:37:23,340 --> 00:37:29,520 Bởi vì bây giờ tôi phải di chuyển một, hai, ba. 1068 00:37:29,520 --> 00:37:32,430 Có bao nhiêu bước là nó sẽ mất để đặt bốn ở đúng nơi? 1069 00:37:32,430 --> 00:37:36,040 4 và 5, cộng với 6, cộng với 7. 1070 00:37:36,040 --> 00:37:40,260 >> Và do đó, nó là toán học giống những gì chúng tôi đã mô tả cho sắp xếp chọn. 1071 00:37:40,260 --> 00:37:42,130 Chúng tôi có loạt bài này đó chỉ là tăng. 1072 00:37:42,130 --> 00:37:45,650 1 + 2 + 3 cộng với 4, hoặc ngược lại, 7 cộng với 6 1073 00:37:45,650 --> 00:37:52,610 cộng với 5 cộng với 4 thêm lên cho hôm nay mục đích để vào thứ tự của n bình phương. 1074 00:37:52,610 --> 00:37:57,640 >> Vì vậy, hãy để tôi định quá mà bong bóng sắp xếp cũng là trong n bình phương. 1075 00:37:57,640 --> 00:38:01,340 Bởi vì với bong bóng sắp xếp, mỗi lần tôi đi qua danh sách, 1076 00:38:01,340 --> 00:38:03,100 Tôi đang dùng khoảng bao nhiêu bước? 1077 00:38:03,100 --> 00:38:06,260 Mỗi lần tôi theo nghĩa đen đi bộ từ đó để có? 1078 00:38:06,260 --> 00:38:07,960 Khoảng n bước. 1079 00:38:07,960 --> 00:38:12,650 Nhưng bao nhiêu lần tôi có thể cần phải đi qua danh sách? 1080 00:38:12,650 --> 00:38:13,920 >> Vâng, khoảng thời gian n. 1081 00:38:13,920 --> 00:38:15,680 Có lẽ n trừ đi 1, nhưng khoảng n lần. 1082 00:38:15,680 --> 00:38:16,430 Vâng, tại sao vậy? 1083 00:38:16,430 --> 00:38:19,560 Vâng, với bong bóng sắp xếp, nếu chúng ta bắt đầu với bong bóng sắp xếp, 1084 00:38:19,560 --> 00:38:23,570 với danh sách trong tồi tệ nhất có thể tình hình, mà lại là hoàn toàn 1085 00:38:23,570 --> 00:38:25,550 trở về trước, điều gì sẽ xảy ra? 1086 00:38:25,550 --> 00:38:28,830 Tôi đi qua danh sách, và số ta thuộc về tất cả các cách trên đó. 1087 00:38:28,830 --> 00:38:33,280 >> Nhưng với bong bóng sắp xếp, làm thế nào đến nay không có một chuyển qua đầu tiên của tôi thông qua danh sách? 1088 00:38:33,280 --> 00:38:36,620 Làm thế nào nhiều điểm không có được anh gần gũi hơn với các địa điểm chính xác? 1089 00:38:36,620 --> 00:38:37,240 Chỉ một. 1090 00:38:37,240 --> 00:38:40,281 Vì vậy, nếu bạn loại lý do thông qua điều này, mỗi lần thông qua thuật toán này, 1091 00:38:40,281 --> 00:38:41,880 Lấy khoảng n bước của David. 1092 00:38:41,880 --> 00:38:44,940 Nhưng làm thế nào những đường chuyền thông qua danh sách là nó 1093 00:38:44,940 --> 00:38:49,060 sẽ mất một đến bong bóng bên trái nơi mà nó thuộc? 1094 00:38:49,060 --> 00:38:51,840 >> Ông ta sẽ di chuyển như thế, n không gian theo cách này. 1095 00:38:51,840 --> 00:38:57,960 Như vậy chỉ cần làm việc phân loại danh sách, Tôi phải đi bộ qua lại n lần. 1096 00:38:57,960 --> 00:39:01,540 Và mỗi lần, tôi nhìn vào n phần tử. 1097 00:39:01,540 --> 00:39:05,410 Vì vậy, làm n thứ n lần trên thứ tự của n bình phương. 1098 00:39:05,410 --> 00:39:07,220 >> Bây giờ, chúng ta sẽ thấy trong một số của quần short 1099 00:39:07,220 --> 00:39:10,440 được nhúng trong vấn đề tiếp theo của CS50 thiết lập, phương pháp tiếp cận khác tại các, 1100 00:39:10,440 --> 00:39:13,490 nhưng bây giờ, chúng ta hãy chỉ cần xem xét một số lần chạy khác, 1101 00:39:13,490 --> 00:39:16,840 đặc biệt là nếu những người sắp mất một chút ít thời gian để chìm trong. 1102 00:39:16,840 --> 00:39:21,790 Một thuật toán chúng ta đã nhìn thấy đã là gì mà mất vào thứ tự của n bước? 1103 00:39:21,790 --> 00:39:27,560 >> Điều gì nên mất một số tuyến tính các bước mà chúng tôi đã nhìn thấy cho đến nay? 1104 00:39:27,560 --> 00:39:29,350 Cái gì thế? 1105 00:39:29,350 --> 00:39:30,480 Các tìm kiếm danh bạ điện thoại. 1106 00:39:30,480 --> 00:39:31,390 Thuật toán đầu tiên. 1107 00:39:31,390 --> 00:39:31,560 Phải không? 1108 00:39:31,560 --> 00:39:33,650 Nơi chúng tôi tuyến tính tìm kiếm Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Thật. 1110 00:39:34,150 --> 00:39:37,180 Từ tuần không, khi tôi bắt đầu chuyển một trang tại một thời gian, 1111 00:39:37,180 --> 00:39:40,095 và tôi thậm chí còn nói rằng nó đã được loại của một thuật toán cảm giác tuyến tính, 1112 00:39:40,095 --> 00:39:42,720 và chúng tôi đã có hình ảnh trên hội đồng quản trị với các dòng màu đỏ thẳng 1113 00:39:42,720 --> 00:39:44,678 và màu vàng thẳng dòng, những người đã thực sự 1114 00:39:44,678 --> 00:39:46,810 các thuật toán đó là trong O lớn của n. 1115 00:39:46,810 --> 00:39:50,680 >> Bởi vì để tìm Mike Smith trong một điện thoại cuốn sách của các trang n, trong trường hợp xấu nhất, 1116 00:39:50,680 --> 00:39:52,422 có thể đưa tôi bước n. 1117 00:39:52,422 --> 00:39:53,630 Gì về việc tham dự? 1118 00:39:53,630 --> 00:39:55,790 Một hai ba bốn năm sáu. 1119 00:39:55,790 --> 00:39:59,420 Thời gian chạy là sao thuật toán cho việc tham dự? 1120 00:39:59,420 --> 00:40:03,070 Big O của n, bởi vì trong lý thuyết tôi có điểm tất cả mọi người trong phòng. 1121 00:40:03,070 --> 00:40:05,861 >> Bây giờ là một sang một bên, những gì về tối ưu hóa khác từ tuần không? 1122 00:40:05,861 --> 00:40:08,117 Hai, bốn, sáu, tám, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Một nhà khoa học máy tính sẽ nhận ra, chờ một phút, 1124 00:40:10,200 --> 00:40:12,320 đó là vào thứ tự của n chia hai bước. 1125 00:40:12,320 --> 00:40:12,820 Phải không? 1126 00:40:12,820 --> 00:40:14,444 Bởi vì tôi đang làm hai người tại một thời gian. 1127 00:40:14,444 --> 00:40:17,015 Nhưng chúng ta sẽ bỏ qua những điều kiện bậc thấp hơn, 1128 00:40:17,015 --> 00:40:19,140 và chúng tôi chỉ đi vứt chia cho 2, 1129 00:40:19,140 --> 00:40:21,830 và chỉ nói, O lớn của n cho các thuật toán đó là tốt. 1130 00:40:21,830 --> 00:40:22,760 >> Cái này thì sao? 1131 00:40:22,760 --> 00:40:26,170 Chúng tôi sẽ bỏ qua một số trong số này, nhưng những gì là một thuật toán mà là nhật ký của n? 1132 00:40:26,170 --> 00:40:29,900 Điều đó đã gần log n bước? 1133 00:40:29,900 --> 00:40:30,870 Sự phân chia và chinh phục. 1134 00:40:30,870 --> 00:40:31,369 Chính xác. 1135 00:40:31,369 --> 00:40:33,900 Cũng giống như các ví dụ trong cuốn sách điện thoại tuần không và trước ngày hôm nay, 1136 00:40:33,900 --> 00:40:36,191 nơi chúng ta chia các vấn đề một lần nữa và một lần nữa và một lần nữa. 1137 00:40:36,191 --> 00:40:39,070 Chúng tôi đã vẽ nó vào hội đồng quản trị trong tuần không như một dòng màu xanh lá cây cong, 1138 00:40:39,070 --> 00:40:41,460 và chúng tôi đã nói ngày hôm đó nó đã được một thuật toán logarit. 1139 00:40:41,460 --> 00:40:44,970 >> Và quả thực, số lượng các bước nó cần để thực hiện phân chia và chinh phục, 1140 00:40:44,970 --> 00:40:48,610 hoặc tìm kiếm nhị phân như chúng ta sẽ bắt đầu gọi nó, như trong các cuốn sách điện thoại, 1141 00:40:48,610 --> 00:40:50,680 là vào thứ tự của bản ghi và các bước. 1142 00:40:50,680 --> 00:40:52,470 Và đây là một chút của một kỳ lạ. 1143 00:40:52,470 --> 00:40:54,910 >> Mất gì một bước, hay cụ thể hơn 1144 00:40:54,910 --> 00:40:56,240 một hằng số của bước? 1145 00:40:56,240 --> 00:40:58,865 Có lẽ đó là hai, có lẽ đó là ba, nhưng một nhà khoa học máy tính chỉ 1146 00:40:58,865 --> 00:41:01,423 đơn giản hoá nó như O lớn của 1 một số hằng số của các bước. 1147 00:41:01,423 --> 00:41:04,256 Một cái gì đó bạn có thể làm điều đó là gì mất một hằng số của bước? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Thời gian chạy của vỗ tay là gì? 1150 00:41:10,930 --> 00:41:11,920 Thời gian liên tục. 1151 00:41:11,920 --> 00:41:12,420 Phải không? 1152 00:41:12,420 --> 00:41:15,490 Giống như, thời gian chạy của những gì làm bất cứ điều gì mà chỉ mất một 1153 00:41:15,490 --> 00:41:18,570 hoạt động, như in F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Đó có thể nói là thời gian liên tục, trừ trường hợp góc ít hơn với in F, 1155 00:41:24,110 --> 00:41:28,260 những gì có thể thời gian chạy in F thực sự được? 1156 00:41:28,260 --> 00:41:28,790 Và tại sao? 1157 00:41:28,790 --> 00:41:30,550 N đo trong trường hợp đó là gì? 1158 00:41:30,550 --> 00:41:32,251 >> Đung [không nghe được]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. Malan: Chính xác. 1160 00:41:33,250 --> 00:41:34,900 Số lượng ký tự chúng ta muốn in. 1161 00:41:34,900 --> 00:41:36,191 Vì vậy, nó rất bối cảnh nhạy cảm. 1162 00:41:36,191 --> 00:41:39,910 Hôm nay, chúng tôi đã tập trung rất nhiều vào chữ và số ở đây trên diễn đàn. 1163 00:41:39,910 --> 00:41:43,540 Nhưng nó cũng có thể là ký tự trong một chuỗi thực tế. 1164 00:41:43,540 --> 00:41:46,420 Vì vậy, nó quay ra có khác biện pháp đó sẽ bắt đầu quan tâm đến, 1165 00:41:46,420 --> 00:41:48,530 và đó là điều ngược lại của O lớn, do đó, để nói chuyện. 1166 00:41:48,530 --> 00:41:50,120 >> Đó là ký hiệu omega. 1167 00:41:50,120 --> 00:41:53,380 Trong khi đó O lớn có nghĩa là gì, các trên ràng buộc về thời gian chạy của bạn? 1168 00:41:53,380 --> 00:41:55,580 Tối đa, bao nhiêu thời gian một cái gì đó có thể mất? 1169 00:41:55,580 --> 00:41:59,250 Omega-- xin lỗi này tiếp tục trở up-- là đối diện đó, 1170 00:41:59,250 --> 00:42:02,960 nhờ đó mà nó là một ràng buộc thấp hơn trên lượng thời gian một cái gì đó có thể mất. 1171 00:42:02,960 --> 00:42:10,480 >> So. Ví dụ, một thuật toán là những gì đó tiến hành các bước luôn n bình? 1172 00:42:10,480 --> 00:42:15,600 Vâng, một trong những thuật toán, chúng tôi đã nhìn thấy ngày hôm nay, trong thực tế, có thể đó là tốt. 1173 00:42:15,600 --> 00:42:16,720 Loại lựa chọn. 1174 00:42:16,720 --> 00:42:18,270 Lựa chọn loại khá ngu ngốc. 1175 00:42:18,270 --> 00:42:21,760 Ngay cả khi xin lỗi algorithm--, thậm chí nếu mảng đã được sắp xếp, 1176 00:42:21,760 --> 00:42:24,150 sắp xếp chọn sẽ tiếp tục đi bộ qua danh sách 1177 00:42:24,150 --> 00:42:28,907 để chắc chắn rằng nó có nhỏ nhất yếu tố một lần nữa và một lần nữa và một lần nữa. 1178 00:42:28,907 --> 00:42:31,740 Và ngay cả khi bạn con người trong khán giả biết rằng, chờ một phút, 1179 00:42:31,740 --> 00:42:33,948 bạn đã được thông qua phần tử nhỏ nhất, máy tính 1180 00:42:33,948 --> 00:42:37,300 không biết rằng cho đến khi nó tất cả các cách thức thông qua danh sách. 1181 00:42:37,300 --> 00:42:40,240 Tương tự như vậy, một giới hạn thấp hơn mà cũng có thể được đưa vào tài khoản 1182 00:42:40,240 --> 00:42:42,000 có thể là thời gian tuyến tính. 1183 00:42:42,000 --> 00:42:48,260 >> Bao nhiêu thời gian hiện nó đi để yếu tố thứ n trong tốt nhất 1184 00:42:48,260 --> 00:42:52,420 trường hợp sử dụng một cái gì đó giống như bong bóng sắp xếp? 1185 00:42:52,420 --> 00:42:54,280 Giả danh sách của bạn đã được sắp xếp. 1186 00:42:54,280 --> 00:42:56,696 Chúng tôi nói bong bóng sắp xếp đưa vào thứ tự của n bình bước. 1187 00:42:56,696 --> 00:42:59,640 Nhưng nếu nó đã được sắp xếp? 1188 00:42:59,640 --> 00:43:02,310 Điều gì nếu bạn nhận ra sau một đi qua mảng 1189 00:43:02,310 --> 00:43:03,540 mà bạn đã thực hiện giao dịch hoán đổi không? 1190 00:43:03,540 --> 00:43:05,970 Bạn cần phải tiếp tục làm nhiều đèo? 1191 00:43:05,970 --> 00:43:06,470 >> Không. 1192 00:43:06,470 --> 00:43:10,340 Vì vậy, một giới hạn thấp hơn trên bong bóng sắp xếp có thể được cho là tuyến tính. 1193 00:43:10,340 --> 00:43:11,830 Omega của n. 1194 00:43:11,830 --> 00:43:14,450 Và chúng ta có thể nhìn vào những người khác trong số này là tốt. 1195 00:43:14,450 --> 00:43:17,990 Vì vậy, chúng ta hãy có một cái nhìn nhanh chóng lúc chỉ là một hình dung ở đây 1196 00:43:17,990 --> 00:43:20,790 để xem làm thế nào những phân biệt mình. 1197 00:43:20,790 --> 00:43:24,592 Tôi sẽ đi xuống đây vào đây trang đó là có sẵn trên trang web của C50, 1198 00:43:24,592 --> 00:43:27,550 nhưng nó sẽ là một nỗi đau để làm việc, vì nó sử dụng một công nghệ gọi là 1199 00:43:27,550 --> 00:43:30,560 Java applet, mà là một phần lớn không được hỗ trợ trong những ngày này, 1200 00:43:30,560 --> 00:43:32,730 ít nhất bằng Chrome và một số người khác. 1201 00:43:32,730 --> 00:43:37,070 >> Và hãy để tôi đi trước và tăng tốc độ này lên và giải thích những gì đang xảy ra. 1202 00:43:37,070 --> 00:43:40,840 Đây là một cuộc biểu tình của bong bóng sắp xếp, thuật toán đầu tiên chúng ta nhìn vào. 1203 00:43:40,840 --> 00:43:43,950 Và đó là một hình dung trong đó mỗi của các thanh này đại diện cho một số. 1204 00:43:43,950 --> 00:43:45,710 Lớn hơn các quán bar, lớn hơn số lượng. 1205 00:43:45,710 --> 00:43:47,520 Nhỏ hơn thanh, nhỏ hơn số lượng. 1206 00:43:47,520 --> 00:43:50,353 Và những gì bạn có thể nhìn thấy bằng mắt, thậm chí mặc dù điều này là siêu nhanh, 1207 00:43:50,353 --> 00:43:53,699 là thanh màu đỏ giống như tôi, đi đi lại lại sửa chữa vấn đề. 1208 00:43:53,699 --> 00:43:56,740 Bạn có thể thấy rằng các yếu tố lớn hơn đang thực sự sủi bọt lên bên phải, 1209 00:43:56,740 --> 00:43:59,650 và các yếu tố nhỏ hơn đang sủi bọt lên bên trái. 1210 00:43:59,650 --> 00:44:01,870 Và ở đây, nếu chúng ta thực sự xem xét chặt chẽ hơn, 1211 00:44:01,870 --> 00:44:04,330 chúng tôi thực sự có thể đếm số lượng so sánh và hoán đổi 1212 00:44:04,330 --> 00:44:05,350 mà đã được thực hiện. 1213 00:44:05,350 --> 00:44:07,360 >> Nhưng thay vào đó, chúng ta hãy nhìn tại các thuật toán thứ hai 1214 00:44:07,360 --> 00:44:11,240 chúng ta nhìn vào trước đó với chúng tôi tình nguyện viên, sắp xếp chọn. 1215 00:44:11,240 --> 00:44:13,500 Nhìn bề ngoài, nó có một hiệu ứng rất khác nhau. 1216 00:44:13,500 --> 00:44:16,820 Nhưng đó là, một lần nữa, rất trực quan, trong mà chúng tôi giữ lựa chọn nhỏ nhất tiếp theo 1217 00:44:16,820 --> 00:44:18,660 phần tử, và chúng tôi đã có một chút may mắn. 1218 00:44:18,660 --> 00:44:20,110 Đó là cảm nhận về cơ bản nhanh hơn. 1219 00:44:20,110 --> 00:44:22,840 Nhưng nếu chúng tôi chạy này một lần nữa và một lần nữa và một lần nữa với rất nhiều yếu tố đầu vào, 1220 00:44:22,840 --> 00:44:26,680 chúng ta sẽ thấy rằng nó thực sự vẫn còn trong O lớn của n bình phương. 1221 00:44:26,680 --> 00:44:29,920 >> Hãy làm một người cuối cùng ở đây, sắp xếp chèn, 1222 00:44:29,920 --> 00:44:33,180 đó là thuật toán thứ ba chúng ta nhìn vào, và thu hồi 1223 00:44:33,180 --> 00:44:36,700 rằng điều này giao dịch với các các yếu tố như nó gặp họ, 1224 00:44:36,700 --> 00:44:39,290 nhưng sau đó nó có thể thay đổi những điều trên để làm cho căn phòng, 1225 00:44:39,290 --> 00:44:41,660 chèn các yếu tố mà họ thuộc về. 1226 00:44:41,660 --> 00:44:45,330 >> Và điều này cũng kết thúc cho các kết quả cuối cùng. Bây giờ tất cả ba trong số những 1227 00:44:45,330 --> 00:44:46,490 cảm thấy khá nhanh. 1228 00:44:46,490 --> 00:44:48,740 Và quả thực, chúng tôi chạy tại một clip khá tốt. 1229 00:44:48,740 --> 00:44:52,510 Nhưng về cơ bản, họ đang tất cả khá khủng khiếp, phải trung thực. 1230 00:44:52,510 --> 00:44:56,960 Tất cả những thuật toán vậy, đến nay mà chạy trong O lớn của n bình 1231 00:44:56,960 --> 00:44:59,270 mất khá một chút thời gian để chạy cuối cùng. 1232 00:44:59,270 --> 00:45:01,920 >> Và quả thực, chúng ta có thể nhìn thấy và cảm thấy điều này cuối cùng 1233 00:45:01,920 --> 00:45:04,090 nếu tôi kéo lên bản demo thứ ba và cuối cùng này. 1234 00:45:04,090 --> 00:45:05,840 Đây là một hình dung rằng sẽ 1235 00:45:05,840 --> 00:45:08,500 để hiển thị bong bóng sắp xếp bên trái, sắp xếp chọn ở giữa, 1236 00:45:08,500 --> 00:45:13,410 và một cái gì đó, như là một trong chúng tôi Mặt tăng trước đó đề nghị, 1237 00:45:13,410 --> 00:45:15,020 hợp nhất phân loại bên phải. 1238 00:45:15,020 --> 00:45:16,937 Một phân chia và chinh phục chiến lược trên bên phải. 1239 00:45:16,937 --> 00:45:19,520 Và đó là, trên thực tế, những gì chúng tôi sẽ nhìn vào hôm thứ Tư. 1240 00:45:19,520 --> 00:45:21,990 Nhưng chúng ta hãy để thời gian này chạy song song. 1241 00:45:21,990 --> 00:45:26,765 Đó là khoảng cùng một số yếu tố, tất cả đều chạy cùng một lúc. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble sort vs lựa chọn loại vs sắp xếp hợp nhất. 1244 00:45:34,440 --> 00:45:36,760 >> Bây giờ, tất cả họ đang chạy trong lý thuyết cùng một lúc. 1245 00:45:36,760 --> 00:45:39,830 Các CPU đang chạy ở tốc độ như nhau, nhưng bạn 1246 00:45:39,830 --> 00:45:44,014 có thể cảm thấy như thế nào nhàm chán này là rất nhanh chóng sẽ trở thành, 1247 00:45:44,014 --> 00:45:45,930 và chỉ cần nhanh như thế nào khi chúng ta tiêm vào một chút trong tuần 1248 00:45:45,930 --> 00:45:49,330 các thuật toán số không thể chúng ta đẩy nhanh tốc độ. 1249 00:45:49,330 --> 00:45:51,760 >> Và bây giờ chúng ta hãy so sánh các trong một hình thức cuối cùng. 1250 00:45:51,760 --> 00:45:55,710 Tôi sẽ đi trước để website CS50, nơi 1251 00:45:55,710 --> 00:45:59,020 chúng tôi có liên kết cuối cùng này cho ngày hôm nay, nơi một người nào đó trên internet 1252 00:45:59,020 --> 00:46:03,960 vui lòng đặt cùng một video nắm bắt những gì phân loại khác nhau 1253 00:46:03,960 --> 00:46:07,510 thuật toán âm thanh như thế nào. 1254 00:46:07,510 --> 00:46:09,577 Đây là sắp xếp chèn. 1255 00:46:09,577 --> 00:46:12,072 >> [Bíp] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Nhờ đó mà bạn đang áp dụng một tần số dựa trên chiều cao của thanh bar. 1258 00:46:16,850 --> 00:46:19,826 Đây là bong bóng sắp xếp. 1259 00:46:19,826 --> 00:46:21,822 >> [Warped bíp] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Sắp tới tiếp theo is-- tới lên chọn tiếp theo của loại is--, 1262 00:46:45,774 --> 00:46:48,820 đó một lần nữa, chúng tôi đang chọn các phần tử nhỏ nhất tiếp theo, 1263 00:46:48,820 --> 00:46:51,820 và chúng ta có thể nhìn thấy nó ngày càng tăng từ trái sang phải. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Hợp nhất phân loại, người chiến thắng của chúng tôi cho đến nay ngày hôm nay. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Chú ý cách nó phân chia thứ vào [không nghe được] một nửa và quý. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Loại Gnome, mà chúng tôi có không nói về, và tạo ra thị 1270 00:47:21,660 --> 00:47:24,450 và audally một chút của một hình dạng và âm thanh khác nhau. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Đi lại, làm sạch mọi thứ lên. 1273 00:47:30,160 --> 00:47:32,230 Ngoài ra kiểm tra heapsort trên trang web của anh chàng này. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> Và đó là nó. 1276 00:47:36,810 --> 00:47:38,210 Chúng ta sẽ thấy bạn thời gian tới. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing AND MUSIC] 1279 00:47:48,334 --> 00:50:24,839