1 00:00:00,000 --> 00:00:11,100 >> [Chơi nhạc] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. Malan: Được rồi. 3 00:00:11,490 --> 00:00:12,170 Vì vậy, chào đón trở lại. 4 00:00:12,170 --> 00:00:15,180 Đây là CS50, và là cuối tuần ba. 5 00:00:15,180 --> 00:00:17,770 >> Vì vậy, nhớ lại trong vài tuần qua, chúng tôi đã chi tiêu khá nhiều 6 00:00:17,770 --> 00:00:20,820 thời gian trên C, về lập trình, về cú pháp. 7 00:00:20,820 --> 00:00:24,680 Và nó khá bình thường, nếu bạn vẫn còn đấu tranh với vấn đề Set 2, để được 8 00:00:24,680 --> 00:00:25,950 đập đầu vào tường. 9 00:00:25,950 --> 00:00:28,310 Đó là thông báo lỗi khó hiểu, tìm kiếm và lỗi mà bạn 10 00:00:28,310 --> 00:00:29,220 không có thể khá đuổi theo. 11 00:00:29,220 --> 00:00:32,310 Bởi vì, yên tâm, mà chỉ trong thời gian vài tuần bạn sẽ nhìn lại 12 00:00:32,310 --> 00:00:35,930 những thứ như Caesar, và [? V-genair,?] thậm chí có thể Crack, và 13 00:00:35,930 --> 00:00:40,050 nhận ra như thế nào đến nay bạn đã đi trong một khoảng thời gian ngắn. 14 00:00:40,050 --> 00:00:43,670 Vì vậy, nếu có bất kỳ sự an ủi, treo ở đó cho bây giờ. 15 00:00:43,670 --> 00:00:46,610 >> Hôm nay, tuy nhiên, chúng ta bắt đầu quá trình chuyển đổi đến những thứ cao hơn. 16 00:00:46,610 --> 00:00:49,820 Và chúng ta bắt đầu đưa cho các cấp mà Các bạn có biết cách lập trình, hoặc 17 00:00:49,820 --> 00:00:52,090 nhất là sự khởi đầu của rằng mức độ thoải mái. 18 00:00:52,090 --> 00:00:56,520 Và chúng tôi sẽ bắt đầu xem xét như thế nào chúng ta có thể đi về các chương trình thiết kế hơn 19 00:00:56,520 --> 00:00:57,440 hiệu quả. 20 00:00:57,440 --> 00:01:01,090 Làm thế nào chúng ta có thể đi về tối ưu hóa hiệu quả của các thuật toán của chúng tôi, và 21 00:01:01,090 --> 00:01:03,110 nói chung giải quyết hơn vấn đề thú vị. 22 00:01:03,110 --> 00:01:06,850 Và bắt đầu đưa cho các cấp rằng, nếu chúng ta muốn, chúng ta có thể mã bất kỳ 23 00:01:06,850 --> 00:01:08,350 trong những ví dụ chúng tôi có trong tâm trí. 24 00:01:08,350 --> 00:01:11,430 Vì vậy, ngày hôm nay, chúng tôi không chạm vào bàn phím cho bất kỳ hình thức mã. 25 00:01:11,430 --> 00:01:15,150 Nó sẽ có mức độ cao hơn nhiều, và cuối cùng, về giải quyết vấn đề. 26 00:01:15,150 --> 00:01:20,490 >> Vì vậy, để có được đến thời điểm đó, hãy để tôi đề xuất rằng sau bảy 27 00:01:20,490 --> 00:01:24,290 hình chữ nhật đại diện cho bảy cửa ra vào, phía sau đó là một bó toàn bộ 28 00:01:24,290 --> 00:01:26,340 số, trong đó là số 50. 29 00:01:26,340 --> 00:01:30,470 Cho tôi dự án này trên này màn hình ở đây là tốt. 30 00:01:30,470 --> 00:01:36,770 Và đề xuất rằng chúng ta cần một tình nguyện giúp tìm cho tôi một số ở phía trước 31 00:01:36,770 --> 00:01:38,140 internet vào đây để xem. 32 00:01:38,140 --> 00:01:40,755 Lên đây, trong màu hồng. 33 00:01:40,755 --> 00:01:43,050 Được rồi. 34 00:01:43,050 --> 00:01:43,930 Tên của bạn là gì? 35 00:01:43,930 --> 00:01:44,850 >> Jennifer: [nghe được] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. Malan: Xin lỗi? 37 00:01:45,170 --> 00:01:45,860 >> Jennifer: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> DAVID J. Malan: Jennifer. 39 00:01:46,390 --> 00:01:46,980 Được rồi, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Hân hạnh được gặp bạn. 41 00:01:47,630 --> 00:01:48,370 Lên đây. 42 00:01:48,370 --> 00:01:52,430 Vì vậy, dưới đây là những cửa ra vào, và những gì Tôi muốn bạn để làm cho chúng ta đây, 43 00:01:52,430 --> 00:01:56,560 ở phía trước của tất cả các bạn cùng lớp của bạn, được tìm thấy chúng tôi số, 50. 44 00:01:56,560 --> 00:02:00,860 Tìm thấy một số, bạn có thể peek đằng sau bất kỳ của các cửa ra vào bằng cách khai thác 45 00:02:00,860 --> 00:02:03,030 trên một cánh cửa, và nó sẽ tiết lộ số lượng của nó. 46 00:02:03,030 --> 00:02:06,080 Và chúng ta hãy xem cách nhanh chóng bạn có thể tìm thấy chúng tôi biết số, 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Độc đáo được thực hiện. 54 00:02:17,350 --> 00:02:18,040 Được rồi. 55 00:02:18,040 --> 00:02:19,906 Tràng pháo tay cho Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Vỗ tay] 57 00:02:21,530 --> 00:02:22,320 >> Được rồi. 58 00:02:22,320 --> 00:02:25,254 Vì vậy, là những gì chiến lược của bạn cho tìm kiếm các số, 50? 59 00:02:25,254 --> 00:02:27,222 >> Jennifer: Um, tôi nghĩ có lẽ nếu - 60 00:02:27,222 --> 00:02:27,714 [Nghe được] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. Malan: Oh. 62 00:02:28,206 --> 00:02:29,630 Cung cấp cho nó một giây. 63 00:02:29,630 --> 00:02:32,420 Vì vậy, là chiến thuật đầu tư tìm kiếm các số, 50? 64 00:02:32,420 --> 00:02:34,760 >> Jennifer: Vì vậy, tôi chỉ bắt đầu tại bắt đầu nhìn thấy những gì số đầu tiên 65 00:02:34,760 --> 00:02:38,590 là, và sau đó tôi nghĩ, có lẽ nếu họ đang sắp xếp, tôi sẽ chỉ giữ 66 00:02:38,590 --> 00:02:39,970 khai thác cao hơn? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. Malan: OK. 68 00:02:40,140 --> 00:02:42,910 Và chúng ta dường như đã tìm thấy đó là trường hợp. 69 00:02:42,910 --> 00:02:45,670 Mặc dù, chúng ta hãy bóc các lớp chỉ cần một chút, và bạn muốn đi 70 00:02:45,670 --> 00:02:47,640 trước và tiết lộ những cánh cửa khác bạn có thể đã chọn? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> Jennifer: Oh, em yêu. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. Malan: Ah. 74 00:02:53,128 --> 00:02:54,280 >> Jennifer: Vì vậy, tôi chỉ có may mắn. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. Malan: Vì vậy, bạn có may mắn. 76 00:02:55,270 --> 00:02:55,710 Được rồi. 77 00:02:55,710 --> 00:02:56,795 Vì vậy, không xấu. 78 00:02:56,795 --> 00:02:58,750 Nhưng đó là một thú vị cái nhìn sâu sắc, phải không? 79 00:02:58,750 --> 00:03:01,870 Nếu bạn giả định, và bạn đã có được, thực sự, một chút may mắn đó. 80 00:03:01,870 --> 00:03:05,350 Nhưng nếu bạn cho rằng số lượng tham dự sắp xếp, bạn có thể được chính xác hơn 81 00:03:05,350 --> 00:03:08,750 như thế nào có ảnh hưởng đến hành vi của bạn? 82 00:03:08,750 --> 00:03:11,715 >> Jennifer: Vì vậy, nếu họ đã được sắp xếp, tôi nghĩ có lẽ nhỏ nhất đến lớn nhất. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. Malan: OK. 84 00:03:11,970 --> 00:03:15,260 >> Jennifer: Hoặc nếu điều này đã kết thúc được thực sự lớn, sau đó lớn nhất đến nhỏ nhất. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. Malan: OK. 86 00:03:15,540 --> 00:03:18,170 Vì vậy, lớn nhất đến nhỏ nhất, hoặc nhỏ nhất đến lớn nhất. 87 00:03:18,170 --> 00:03:21,990 Nhưng hãy để tôi đưa ra, giả sử bạn có nhận được may mắn, và giả sử rằng họ 88 00:03:21,990 --> 00:03:26,840 không được, trên thực tế, sắp xếp, bao nhiêu những cánh cửa có thể bạn đã nhìn trộm 89 00:03:26,840 --> 00:03:28,590 sau đó trong trường hợp xấu nhất? 90 00:03:28,590 --> 00:03:29,860 >> Jennifer: Tất cả trong số họ. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. Malan: Tất cả trong số họ. 92 00:03:30,420 --> 00:03:31,740 Vì vậy, chúng ta hãy khái quát như n. 93 00:03:31,740 --> 00:03:34,790 Có xảy ra là 7, nhưng chúng ta hãy là hơn thường nói rằng cánh cửa của n trên 94 00:03:34,790 --> 00:03:35,650 màn hình ở đây. 95 00:03:35,650 --> 00:03:40,110 Vì vậy, trong trường hợp xấu nhất, bạn sẽ có để xem sau 7 cửa ra vào, hoặc n cửa ra vào. 96 00:03:40,110 --> 00:03:44,140 Và vì vậy đây thực sự là, đó là một chút may mắn ngày hôm nay, nhưng nó thực sự là một tuyến tính 97 00:03:44,140 --> 00:03:46,440 thuật toán của các loại, ngay cả khi bạn đã được loại bỏ qua xung quanh. 98 00:03:46,440 --> 00:03:47,080 Là công bằng? 99 00:03:47,080 --> 00:03:47,500 >> Jennifer: Vâng. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. Malan: Vâng, hãy để tôi xem nếu bạn thay đổi chiến lược nếu tôi di chuyển chúng tôi 101 00:03:50,000 --> 00:03:52,190 Ví dụ thứ hai của chúng tôi ở đây với 7 cánh cửa khác nhau. 102 00:03:52,190 --> 00:03:55,240 Cùng một số, nhưng điều này Hiện họ đều được sắp xếp. 103 00:03:55,240 --> 00:03:58,350 Chiến lược của bạn ở đây sẽ là những gì, cố gắng để đưa ra khỏi tâm trí của bạn 104 00:03:58,350 --> 00:03:59,310 số khác là - 105 00:03:59,310 --> 00:03:59,930 >> Jennifer: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. Malan: - trước đó? 107 00:04:02,290 --> 00:04:03,180 >> Jennifer: Hãy bắt đầu với một trong những đầu tiên. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. Malan: Được rồi. 109 00:04:03,540 --> 00:04:05,190 Bắt đầu với các đầu tiên. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Bây giờ, nơi bạn sẽ đi, và tại sao? 112 00:04:08,810 --> 00:04:10,040 >> Jennifer: 4 thực sự là nhỏ. 113 00:04:10,040 --> 00:04:12,500 Vì vậy, nếu họ có thể loại nhỏ nhất đến lớn, cần 114 00:04:12,500 --> 00:04:13,290 được gấp đôi, và -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. Malan: OK. 116 00:04:13,670 --> 00:04:15,990 Chúng ta hãy xem, mà bạn nghĩ? 117 00:04:15,990 --> 00:04:19,050 >> Jennifer: Hãy thử một trong những cuối cùng. 118 00:04:19,050 --> 00:04:19,500 Tốt đẹp. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. Malan: Rất độc đáo được thực hiện. 120 00:04:20,880 --> 00:04:21,860 Được rồi. 121 00:04:21,860 --> 00:04:23,010 >> [Vỗ tay] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. Malan: OK. 123 00:04:24,310 --> 00:04:26,790 Vì vậy, bạn đang thực sự làm này khủng khiếp, bởi vì bạn 124 00:04:26,790 --> 00:04:27,700 làm việc đó rất tốt. 125 00:04:27,700 --> 00:04:31,150 Khiến cho chúng tôi không thể thực hiện một số điểm. 126 00:04:31,150 --> 00:04:32,565 Vì vậy, hãy cố gắng quay trở lại đây. 127 00:04:32,565 --> 00:04:34,560 >> Jennifer: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. Malan: Rất tốt thực hiện, dù sao. 129 00:04:35,980 --> 00:04:39,060 Vì vậy, bạn bắt đầu ngay từ đầu, bạn thấy điều đó là 4, sau đó bạn 130 00:04:39,060 --> 00:04:40,240 di chuyển đến cùng. 131 00:04:40,240 --> 00:04:42,320 Nhưng giả sử bạn đã không có được may mắn ở đó, và giả sử 50 132 00:04:42,320 --> 00:04:42,890 là ở một nơi khác. 133 00:04:42,890 --> 00:04:46,190 Những gì bước thứ ba của bạn đã được? 134 00:04:46,190 --> 00:04:47,680 >> Jennifer: Trở lại để bắt đầu. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. Malan: Quay trở lại để bắt đầu. 136 00:04:48,320 --> 00:04:51,320 OK, vì vậy bạn có thể đã chạm vào cánh cửa này, đó là 8. 137 00:04:51,320 --> 00:04:51,660 Được rồi. 138 00:04:51,660 --> 00:04:52,650 Vì vậy, đó không phải là 50. 139 00:04:52,650 --> 00:04:55,380 Trong trường hợp bạn đã có thể nhìn tiếp theo? 140 00:04:55,380 --> 00:04:56,720 >> Jennifer: Nếu tôi không biết họ sắp xếp. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. Malan: Đúng. 142 00:04:57,005 --> 00:04:58,490 Vâng, nếu bạn đã biết họ đã sắp xếp - 143 00:04:58,490 --> 00:04:58,700 >> Jennifer: Oh, có biết, đúng vậy. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. Malan: - nhưng bạn đã không biết là 50 chưa? 145 00:05:00,910 --> 00:05:01,785 >> Jennifer: Chỉ cần tiếp tục đi. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. Malan: Được rồi. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Tiếp tục đi. 149 00:05:03,800 --> 00:05:05,270 OK, tôi có thể làm việc với. 150 00:05:05,270 --> 00:05:05,610 >> Jennifer: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. Malan: Bây giờ, nếu bạn chỉ sẽ tiếp tục đi, những gì là của bạn 152 00:05:07,210 --> 00:05:09,680 thuật toán phân cấp sao lưu vào. 153 00:05:09,680 --> 00:05:10,740 >> Jennifer: Các tuyến tính -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. Malan: Đây là loại tuyến tính. 155 00:05:11,820 --> 00:05:13,480 Nhưng hãy để tôi đề xuất, cho phép tôi đặt ngay tại chỗ. 156 00:05:13,480 --> 00:05:14,900 Hãy để tôi làm mới trang. 157 00:05:14,900 --> 00:05:17,120 cùng một số, cùng một bố trí, cùng một cửa ra vào. 158 00:05:17,120 --> 00:05:21,350 Nhưng nghĩ lại cái ngày đầu tiên trong lớp khi chúng tôi xé một cuốn sách điện thoại trong 159 00:05:21,350 --> 00:05:25,480 một nửa, loại, và những gì đã được Chiến lược của chúng tôi không? 160 00:05:25,480 --> 00:05:26,450 >> Jennifer: Bắt đầu ở giữa. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. Malan: OK. 162 00:05:26,690 --> 00:05:27,610 Vì vậy, bắt đầu ở giữa. 163 00:05:27,610 --> 00:05:28,790 Vì vậy, chúng ta hãy đi trước và mô phỏng đó. 164 00:05:28,790 --> 00:05:30,720 Bắt đầu từ khu trung lộ của tiết lộ cánh cửa đó. 165 00:05:30,720 --> 00:05:31,660 Vì vậy, số 16. 166 00:05:31,660 --> 00:05:35,290 Vậy điều gì sẽ là chàng trai mạnh mẽ đã làm, ai xé danh bạ điện thoại trong một nửa, 167 00:05:35,290 --> 00:05:38,450 để có được đoán tiếp theo? 168 00:05:38,450 --> 00:05:39,400 >> Jennifer: Vào trong hiệp này. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. Malan: Và tại sao bên phải? 170 00:05:41,700 --> 00:05:43,900 >> Jennifer: Nếu họ là loại nhỏ nhất để lớn nhất, sau đó 50 nên 171 00:05:43,900 --> 00:05:44,720 ở cuối đó. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. Malan: Tốt. 173 00:05:44,920 --> 00:05:45,390 Hoàn toàn hợp lý. 174 00:05:45,390 --> 00:05:48,380 Vì vậy, như một cuốn sách điện thoại, bạn hãy vào đúng như trái ngược với bên trái, nhưng đây 175 00:05:48,380 --> 00:05:49,500 là Yếu tố chính. 176 00:05:49,500 --> 00:05:53,930 Bây giờ bạn có thể vứt bỏ, hoặc xé nhỏ, một nửa của vấn đề này, để lại cho bạn không 177 00:05:53,930 --> 00:05:55,970 với 7 cửa ra vào, nhưng thực sự chỉ với 3. 178 00:05:55,970 --> 00:05:57,870 Đó là khoảng một nửa số kích thước của vấn đề. 179 00:05:57,870 --> 00:05:58,350 Được rồi. 180 00:05:58,350 --> 00:06:01,890 Vì vậy, bây giờ những gì bạn sẽ phải thực hiện sau khi bạn đi phải không? 181 00:06:01,890 --> 00:06:05,870 >> Jennifer: Vì vậy, 16 vẫn còn khá nhỏ, so với 50, như vậy có lẽ tôi sẽ cố gắng, 182 00:06:05,870 --> 00:06:06,700 như, này. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. Malan: Được rồi. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Được rồi, bây giờ những gì là của bạn bản năng nói cho bạn? 186 00:06:10,830 --> 00:06:12,100 >> Jennifer: Tôi có thể vứt bỏ và điều này sau đó chỉ cần - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. Malan: OK. 188 00:06:12,360 --> 00:06:14,212 Tốt, bạn có thể vứt bỏ nửa bên trái đó. 189 00:06:14,212 --> 00:06:14,890 >> Jennifer: - chọn một này. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. Malan: Và bên phải. 191 00:06:15,530 --> 00:06:15,760 >> Jennifer: Vâng. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. Malan: Vì vậy, mặc dù nó khó để xem có lẽ, khi chỉ có 193 00:06:17,820 --> 00:06:21,320 7 cửa ra vào, suy nghĩ, bây giờ, sự phù hợp của 194 00:06:21,320 --> 00:06:22,620 Thuật toán bạn chỉ cần áp dụng. 195 00:06:22,620 --> 00:06:24,510 Trong trường hợp trước, bạn đã làm nhận được may mắn, mà là tuyệt vời. 196 00:06:24,510 --> 00:06:26,540 Nhưng bạn đã sử dụng để phân tích, Tôi sẽ nói. 197 00:06:26,540 --> 00:06:29,150 Bạn sử dụng loại bản năng của bạn, và biết nó sắp xếp, nếu nó đẹp 198 00:06:29,150 --> 00:06:31,600 nhỏ ngay từ đầu, rõ ràng, chúng tôi đã phải đi hơn bên phải. 199 00:06:31,600 --> 00:06:34,990 Nhưng trong một nghĩa nào đó, bạn có may mắn, bởi vì có lẽ đây là số 100, 200 00:06:34,990 --> 00:06:36,220 và có thể 50 là hơn ở giữa. 201 00:06:36,220 --> 00:06:37,910 Có lẽ 50 thậm chí còn hơn ở đây. 202 00:06:37,910 --> 00:06:40,960 >> Nhưng những gì bạn đã làm một chút khác nhau thời gian này là, bạn đã làm điều tương tự 203 00:06:40,960 --> 00:06:42,150 một lần nữa và một lần nữa. 204 00:06:42,150 --> 00:06:45,310 Và tôi sẽ cho rằng những gì bạn vừa đã làm, mặc dù chịu ảnh hưởng của điện thoại 205 00:06:45,310 --> 00:06:48,100 cuốn sách chẳng hạn, là một cái gì đó nhiều thuật toán nhiều hơn, và nhiều 206 00:06:48,100 --> 00:06:49,930 ít đặc biệt hoa chữ cái đầu. 207 00:06:49,930 --> 00:06:51,620 Ít hơn nhiều theo bản năng. 208 00:06:51,620 --> 00:06:57,160 Vì vậy, vào cuối ngày, làm thế nào có bạn mô tả hiệu quả của 209 00:06:57,160 --> 00:07:00,530 Thuật toán đầu tiên, nơi mà bạn đã đi trái sang phải, so với 210 00:07:00,530 --> 00:07:03,430 thuật toán thứ hai đây? 211 00:07:03,430 --> 00:07:06,460 >> Jennifer: Điều này nên, như, có thể giảm một nửa thời gian, hoặc thậm chí hơn, yeah. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. Malan: OK, thậm chí có thể hơn. 213 00:07:07,320 --> 00:07:10,150 Chúng ta đẩy một chút khó khăn hơn về điều đó. 214 00:07:10,150 --> 00:07:13,030 Điều gì thực sự, nếu chúng ta tiếp tục này logic, chúng tôi chắc chắn giảm đi một nửa 215 00:07:13,030 --> 00:07:15,830 thời gian chạy với các thuật toán thứ hai này bằng cách ném đi một nửa 216 00:07:15,830 --> 00:07:18,470 số, nhưng những gì chúng tôi đã làm về sau lặp đi lặp lại, khi Jennifer tiết lộ 217 00:07:18,470 --> 00:07:20,615 số thứ hai? 218 00:07:20,615 --> 00:07:22,830 >> Chúng tôi giảm một nửa số lượng các cửa một lần nữa. 219 00:07:22,830 --> 00:07:25,270 Và sau đó chúng tôi đã làm gì sau đó, nếu có nhiều cửa ra vào để chơi với? 220 00:07:25,270 --> 00:07:27,520 Chúng tôi sẽ giảm một nửa họ, và một lần nữa, và một lần nữa, và một lần nữa. 221 00:07:27,520 --> 00:07:30,420 Và điều này cũng giống như các bạn tất cả đứng ở tuần đầu tiên của 222 00:07:30,420 --> 00:07:33,000 lớp, một nửa của bạn ngồi xuống, một nửa các bạn ngồi xuống, một nửa của bạn 223 00:07:33,000 --> 00:07:35,440 ngồi xuống, cho đến khi một đơn độc linh hồn đang đứng. 224 00:07:35,440 --> 00:07:39,050 Và chúng tôi cho rằng thời gian chạy của rằng, số lượng các bước nó đã là 225 00:07:39,050 --> 00:07:40,430 về trình tự của những gì? 226 00:07:40,430 --> 00:07:41,230 >> SPEAKER 1: [nghe được] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. Malan: Vì vậy, căn cứ đăng nhập 2 của n, hoặc chỉ đơn giản hơn, đăng nhập n. 228 00:07:43,970 --> 00:07:45,060 Vì vậy, một cái gì đó logarit. 229 00:07:45,060 --> 00:07:48,380 Và đồ thị không phải là một đường thẳng mà chỉ có tồi tệ hơn và tồi tệ hơn, đó là 230 00:07:48,380 --> 00:07:52,490 đường cong này thú vị mà không nhận được quá xấu theo thời gian. 231 00:07:52,490 --> 00:07:53,910 Vì vậy, hãy giữ cho ý tưởng này. 232 00:07:53,910 --> 00:07:54,690 Chúng ta hãy cảm ơn Jennifer. 233 00:07:54,690 --> 00:07:56,150 Cảm ơn rất nhiều vì đã đến trên lên. 234 00:07:56,150 --> 00:07:57,400 Và, một giây. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Không có đèn bàn ngày hôm nay, nhưng chúng tôi không có CS50 quả bóng căng thẳng. 237 00:08:02,925 --> 00:08:03,420 >> Jennifer: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. Malan: Được rồi, đây. 239 00:08:04,410 --> 00:08:06,545 Cảm ơn bạn đã phải gánh chịu sự căng thẳng lên đây. 240 00:08:06,545 --> 00:08:07,350 Được rồi. 241 00:08:07,350 --> 00:08:10,620 Vì vậy, chúng ta hãy xem nếu chúng ta có thể không phải bây giờ chính thức hóa này nhiều hơn một chút. 242 00:08:10,620 --> 00:08:14,820 Vì vậy, một lần nữa, những gì chúng ta đã làm được về cơ bản giống như chúng tôi đã làm 243 00:08:14,820 --> 00:08:16,660 trong đó tuần đầu tiên. 244 00:08:16,660 --> 00:08:23,780 Nhưng thay vì kết thúc chỉ với một tuyến tính thuật toán, mà chúng tôi mô tả 245 00:08:23,780 --> 00:08:27,210 trước đây là đường thẳng này, theo đó, nếu chúng ta đặt một cửa hơn trên 246 00:08:27,210 --> 00:08:29,610 màn hình, sau đó Jennifer sẽ đã phải bất lực nhìn, có khả năng, 247 00:08:29,610 --> 00:08:30,600 đằng sau một cửa hơn. 248 00:08:30,600 --> 00:08:33,490 Nếu chúng ta đặt hai cánh cửa nữa, cô ấy có thể có nhìn đằng sau hai cánh cửa nữa. 249 00:08:33,490 --> 00:08:35,990 >> Và do đó, có này tuyến tính mối quan hệ giữa kích thước của 250 00:08:35,990 --> 00:08:39,059 vấn đề trên, nói rằng, các trục x, và số lượng thời gian cần thiết để 251 00:08:39,059 --> 00:08:40,440 giải quyết trên y. 252 00:08:40,440 --> 00:08:43,330 Nhưng hình ảnh tôi đã được ám chỉ đến trước đó là dòng màu xanh lá cây này. 253 00:08:43,330 --> 00:08:45,970 Xanh cố tình, bởi vì nó chỉ cảm thấy tốt hơn. 254 00:08:45,970 --> 00:08:49,790 Về lý thuyết, thuật toán, khi chúng tôi đã làm nó với danh bạ điện thoại, khi chúng tôi đã làm nó 255 00:08:49,790 --> 00:08:52,420 với các bạn, kể cho nhau, và trong trường hợp thứ hai, khi Jennifer chỉ 256 00:08:52,420 --> 00:08:55,250 đã làm nó lên đây, nó đã được sắp xếp của cơ bản tốt hơn. 257 00:08:55,250 --> 00:08:57,180 Bởi vì nó không chỉ là nhanh gấp hai lần. 258 00:08:57,180 --> 00:08:58,870 Đó không phải là thậm chí bốn lần nhanh. 259 00:08:58,870 --> 00:09:03,290 Đó là hoàn toàn phụ thuộc vào những gì kích thước của đầu vào là, như thế nào nhiều 260 00:09:03,290 --> 00:09:05,220 bước cuối cùng nó mất. 261 00:09:05,220 --> 00:09:08,040 >> Và do đó ý tưởng đơn giản này mà tất cả chúng ta mất cho các cấp với danh bạ điện thoại, 262 00:09:08,040 --> 00:09:10,200 tương tự có thể được áp dụng một cái gì đó như thế này. 263 00:09:10,200 --> 00:09:12,380 Và điều này có thể là tình cờ hơn được gọi là, như bạn có thể 264 00:09:12,380 --> 00:09:13,940 tưởng tượng, phân chia và chinh phục. 265 00:09:13,940 --> 00:09:16,390 Không giống như những gì chúng tôi đã làm, tất nhiên, với danh bạ điện thoại. 266 00:09:16,390 --> 00:09:18,300 >> Nhưng mã giả, thu hồi, là này. 267 00:09:18,300 --> 00:09:21,800 Vì vậy, chúng tôi sẽ không làm điều này một lần nữa, nhưng nhớ lại trong tuần đầu tiên, tất cả chúng ta đứng dậy 268 00:09:21,800 --> 00:09:25,140 và sau đó một nửa của bạn ngồi xuống, một nửa bạn ngồi xuống, một nửa của bạn ngồi xuống. 269 00:09:25,140 --> 00:09:29,280 Rằng thuật toán được thực hiện trong một chút một cách gian lận, trong đó, 270 00:09:29,280 --> 00:09:32,870 không chỉ là một trong tôi đếm, về cơ bản, hiệu quả hơn. 271 00:09:32,870 --> 00:09:35,830 Trong trường hợp đó, tôi đã được tận dụng một nguồn thứ cấp. 272 00:09:35,830 --> 00:09:39,470 Loại, nhiều CPU, bộ não nhiều, nhiều người thông minh trong 273 00:09:39,470 --> 00:09:42,740 phòng đã giúp tôi có được từ một cái gì đó tuyến tính với một cái gì đó 274 00:09:42,740 --> 00:09:45,190 logarit, từ một cái gì đó màu đỏ để một cái gì đó màu xanh lá cây. 275 00:09:45,190 --> 00:09:48,650 >> Nhưng trong trường hợp này, Jennifer một mình có thể nâng cao hiệu trên 276 00:09:48,650 --> 00:09:52,370 thực hiện các thuật toán đầu tiên của mình bằng cách, một lần nữa, chỉ cần suy nghĩ một chút khó khăn hơn. 277 00:09:52,370 --> 00:09:56,650 Và bây giờ, khi nói đến thời gian để thực hiện những điều này, để tìm ra 278 00:09:56,650 --> 00:10:00,670 những gì dòng mã bạn có thể viết như vậy mà bạn có thể lặp lại chúng một lần nữa, và 279 00:10:00,670 --> 00:10:03,350 một lần nữa, và một lần nữa, loại trong một thời trang vòng lặp. 280 00:10:03,350 --> 00:10:06,370 Bởi vì bạn sẽ không có sang trọng, như Jennifer đã làm lúc đầu, để 281 00:10:06,370 --> 00:10:10,460 chỉ có một bó toàn bộ của IFS và nói, hmm, nếu số đầu tiên này là 4, 282 00:10:10,460 --> 00:10:11,800 hãy để tôi nhảy tất cả các cách để kết thúc. 283 00:10:11,800 --> 00:10:14,180 Ồ, nếu con số này là quá lớn, hãy để tôi tự ý di chuyển trở lại 284 00:10:14,180 --> 00:10:15,220 đến yếu tố thứ hai. 285 00:10:15,220 --> 00:10:18,210 Bạn sẽ thấy rằng nó sẽ có rất nhiều khó khăn hơn để chính thức hóa những gì con người chúng ta 286 00:10:18,210 --> 00:10:21,270 đưa cho các cấp như rất hợp lý công nghệ tự động, nhưng một máy tính duy nhất là 287 00:10:21,270 --> 00:10:23,260 sẽ làm những gì bạn nói với nó để làm. 288 00:10:23,260 --> 00:10:25,280 >> Bây giờ điều này có rất thú vị ý nghĩa. 289 00:10:25,280 --> 00:10:29,950 Biểu đồ này là loại có nghĩa là để sắp xếp của áp đảo trực quan, nhưng thông báo, nơi 290 00:10:29,950 --> 00:10:32,230 là đường thẳng trong biểu đồ này? 291 00:10:32,230 --> 00:10:35,330 Mà là đồ thị tuyến tính mà chúng ta gọi n? 292 00:10:35,330 --> 00:10:37,580 Vâng, đó là loại xuống dưới cùng của hình ảnh này, phải không? 293 00:10:37,580 --> 00:10:40,500 Vì vậy, tất cả chúng tôi đã làm là chúng tôi đã loại thu nhỏ để trục x và 294 00:10:40,500 --> 00:10:44,780 trục y để cố gắng để có được một cảm giác về những gì các loại đường cong như thế nào. 295 00:10:44,780 --> 00:10:47,760 >> Và các chi tiết cụ thể của toán học biểu ngày hôm nay sẽ không có vấn đề như vậy 296 00:10:47,760 --> 00:10:52,440 nhiều, nhưng nhận thấy rằng có rất nhiều các thuật toán mà còn tồi tệ hơn 297 00:10:52,440 --> 00:10:53,470 cái gì đó là tuyến tính. 298 00:10:53,470 --> 00:10:55,410 Thật vậy, n cubed trông khá xấu. 299 00:10:55,410 --> 00:10:58,400 2 đến n trông khá xấu. n bình phương trông khá xấu. 300 00:10:58,400 --> 00:11:01,630 Và chúng tôi sẽ xem những gì một số người có thể là trong thực tế hôm nay. 301 00:11:01,630 --> 00:11:05,430 Và log n không cảm thấy là xấu, nhưng tốt hơn so với n là đăng nhập cơ sở 2 của n. 302 00:11:05,430 --> 00:11:08,080 Nhưng bạn đã biết, nó đã có thậm chí tuyệt vời hơn nếu Jennifer, hoặc nếu chúng tôi, 303 00:11:08,080 --> 00:11:12,910 trong tuần đầu tiên, đã đưa ra cái gì đó là nhật ký của nhật ký của n. 304 00:11:12,910 --> 00:11:15,880 >> Vì vậy, nói cách khác, đó là toàn bộ này loạt các giải pháp có thể 305 00:11:15,880 --> 00:11:18,570 vấn đề, nhưng ngay cả ở đây, thông báo những gì sẽ xảy ra. 306 00:11:18,570 --> 00:11:22,910 Khi tôi thu nhỏ, mà của những đường cong sẽ chứng minh là tuyệt đối 307 00:11:22,910 --> 00:11:26,630 tồi tệ nhất trong những cái trên màn hình bây giờ? 308 00:11:26,630 --> 00:11:28,680 Vì vậy, n cắt hạt lựu trông khá xấu vào lúc này. 309 00:11:28,680 --> 00:11:32,470 Nhưng nếu chúng ta thu nhỏ và xem chi tiết của x và trục y, ai sẽ 310 00:11:32,470 --> 00:11:34,550 thống trị cuối cùng? 311 00:11:34,550 --> 00:11:37,120 Vì vậy, nó thực sự chỉ ra rằng 2 đến n, và bạn có thể con số này ra chỉ bằng cách 312 00:11:37,120 --> 00:11:39,990 cắm vào một số ngày càng lớn số, và bạn sẽ thấy rằng 2 đến 313 00:11:39,990 --> 00:11:42,070 n, thực sự, trở nên lớn nhanh hơn nhiều. 314 00:11:42,070 --> 00:11:45,530 Nếu chúng ta thực sự thu nhỏ, 2 đến thuật toán n hoàn toàn hút. 315 00:11:45,530 --> 00:11:48,170 Tôi có ý nghĩa này sẽ mất khá nhiều thời gian cho các 316 00:11:48,170 --> 00:11:49,460 máy tính để khuấy qua. 317 00:11:49,460 --> 00:11:52,500 >> Nhưng bạn sẽ thấy theo thời gian, đặc biệt là với bộ vấn đề tương lai và thậm chí 318 00:11:52,500 --> 00:11:55,600 dự án cuối cùng, là dữ liệu của bạn thiết bị lớn, tất cả phải không? 319 00:11:55,600 --> 00:11:58,300 Thậm chí trong phiên bản đầu tiên của Facebook, như số lượng bạn bè, và 320 00:11:58,300 --> 00:12:01,840 số lượng người dùng đăng ký có lớn, bạn có thể sắp xếp của điện thoại vào và 321 00:12:01,840 --> 00:12:05,530 thực hiện một cái gì đó với tìm kiếm tuyến tính, hoặc một phân loại rất đơn giản 322 00:12:05,530 --> 00:12:07,030 thuật toán, như chúng ta sẽ thấy ngày hôm nay. 323 00:12:07,030 --> 00:12:09,280 Bạn phải bắt đầu suy nghĩ khó khăn hơn và khó khăn hơn về những vấn đề này. 324 00:12:09,280 --> 00:12:12,070 Và các loại của các vấn đề địa điểm như Facebook, Google, và Microsoft, 325 00:12:12,070 --> 00:12:16,350 và những người khác làm việc trên là chính xác những loại dữ liệu lớn loại câu hỏi 326 00:12:16,350 --> 00:12:18,530 càng những ngày này. 327 00:12:18,530 --> 00:12:18,900 >> Được rồi. 328 00:12:18,900 --> 00:12:23,800 Vì vậy, thành công của Jennifer trong đó thứ hai thuật toán, thẳng thắn, cô ấy đã làm ngạc nhiên 329 00:12:23,800 --> 00:12:26,110 cũng lần đầu tiên, nhưng chúng ta hãy viết nó như là may mắn cho chúng tôi 330 00:12:26,110 --> 00:12:27,000 có thể làm cho thời điểm này. 331 00:12:27,000 --> 00:12:30,970 Trong trường hợp thứ hai, cô thừa hưởng một thuật toán lặp đi lặp lại một lần nữa và 332 00:12:30,970 --> 00:12:34,670 một lần nữa, nhưng cô đã cho cấp giả định chắc chắn rằng chúng tôi cho phép 333 00:12:34,670 --> 00:12:39,370 cô, nhưng cô khai thác một số chi tiết lần thứ hai là cô ấy không có 334 00:12:39,370 --> 00:12:39,840 lần đầu tiên. 335 00:12:39,840 --> 00:12:41,800 Đó là những gì? 336 00:12:41,800 --> 00:12:43,050 >> Rằng danh sách đã được sắp xếp. 337 00:12:43,050 --> 00:12:46,350 Vì vậy, ngay sau khi danh sách đã được sắp xếp, chúng tôi cho rằng Jennifer đã có thể làm 338 00:12:46,350 --> 00:12:47,480 về cơ bản tốt hơn. 339 00:12:47,480 --> 00:12:51,450 7 cửa ra vào, có, mà không phải là thú vị, nhưng giả sử nó chúng ta 7 triệu cửa ra vào. 340 00:12:51,450 --> 00:12:54,080 Nhật ký của n chắc chắn là sẽ để thực hiện nhiều, nhiều 341 00:12:54,080 --> 00:12:55,610 nhanh hơn trong thời gian dài. 342 00:12:55,610 --> 00:12:58,880 Nhưng cô đã phải có cửa sắp xếp cho cô ấy. 343 00:12:58,880 --> 00:13:02,320 Bây giờ, tôi đã tự làm điều đó trước trên màn hình máy tính 344 00:13:02,320 --> 00:13:05,160 ở đây, nhưng giả sử rằng Jennifer đã phải làm điều đó bản thân? 345 00:13:05,160 --> 00:13:10,120 Giả sử rằng các cánh cửa trong câu hỏi dữ liệu đại diện trong một cơ sở dữ liệu, hoặc 346 00:13:10,120 --> 00:13:14,260 bạn bè đăng ký cho Facebook, hoặc bất kỳ trang web trên mạng Internet 347 00:13:14,260 --> 00:13:16,880 các trang web khác nhau có thể cần chỉ số hoặc tìm kiếm trên. 348 00:13:16,880 --> 00:13:20,940 >> Giả sử rằng bạn chỉ có một dữ liệu thô thiết lập và nó đã để lại cho bạn, hoặc để 349 00:13:20,940 --> 00:13:23,010 Jennifer để làm phân loại đó? 350 00:13:23,010 --> 00:13:26,950 Mà đúng hơn, đòi hỏi chúng ta trả lời các câu hỏi, tốt, bao nhiêu thời gian 351 00:13:26,950 --> 00:13:31,080 đã có thể lấy Jennifer, hoặc thậm chí tôi, để sắp xếp những con số trước để 352 00:13:31,080 --> 00:13:32,680 rằng cô có thể tận dụng điều đó? 353 00:13:32,680 --> 00:13:32,880 Phải không? 354 00:13:32,880 --> 00:13:36,620 Bởi vì ý nghĩa, tất nhiên, là nếu tôi phải mất nhiều thời gian để sắp xếp 355 00:13:36,620 --> 00:13:40,800 những con số, những người có hề quan tâm rằng bạn có thể tìm thấy một số như 50 quá nhanh, 356 00:13:40,800 --> 00:13:44,850 như trong trường hợp của Jennifer, nếu chúng ta hơn áp đảo số lượng tổng thời gian 357 00:13:44,850 --> 00:13:46,920 mất bằng cách phân loại những điều trước? 358 00:13:46,920 --> 00:13:49,320 >> Vì vậy, chúng ta hãy xem nếu chúng ta không có thể các vẽ lên bức tranh ở đây. 359 00:13:49,320 --> 00:13:51,370 Tôi có căng thẳng một bó toàn bộ hơn quả bóng, nếu giúp 360 00:13:51,370 --> 00:13:52,270 phá vỡ lớp băng ở đây. 361 00:13:52,270 --> 00:13:55,690 Và nếu bạn không phiền, chúng tôi cần bảy tình nguyện viên - 362 00:13:55,690 --> 00:13:57,060 trên, OK. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Vì vậy, chúng tôi không cần phải chi tiêu trên đèn bàn, có vẻ như. 365 00:13:59,250 --> 00:13:59,690 Được rồi. 366 00:13:59,690 --> 00:14:01,530 Vì vậy, làm thế nào về bạn hai ở phía trước. 367 00:14:01,530 --> 00:14:04,160 Làm thế nào về hai người bạn trong trở lại. 368 00:14:04,160 --> 00:14:04,870 Vì vậy, đó là bốn. 369 00:14:04,870 --> 00:14:09,890 Làm thế nào về bạn ở phía trước năm, sáu và bảy. 370 00:14:09,890 --> 00:14:10,320 Ngay tại đó. 371 00:14:10,320 --> 00:14:13,260 Bạn của bạn của bạn chỉ ra, để bạn có được giải thưởng. 372 00:14:13,260 --> 00:14:13,700 >> Được rồi. 373 00:14:13,700 --> 00:14:14,410 Lên đây. 374 00:14:14,410 --> 00:14:17,120 Và lý do tại sao chúng ta không có bạn kẻ đi trên trên đây. 375 00:14:17,120 --> 00:14:18,960 Tôi sẽ cung cấp cho bạn mỗi một con số. 376 00:14:18,960 --> 00:14:22,150 Và đi trước và sắp xếp mình giống hệt với những gì 377 00:14:22,150 --> 00:14:25,180 mô tả trên màn hình. 378 00:14:25,180 --> 00:14:26,530 >> [Interposing GIỌNG NÓI] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. Malan: OOP, xin lỗi. 380 00:14:28,160 --> 00:14:30,210 Lỗi. 381 00:14:30,210 --> 00:14:32,180 Được rồi. 382 00:14:32,180 --> 00:14:32,750 Vâng, ở đây chúng tôi đi. 383 00:14:32,750 --> 00:14:34,180 Thứ năm. 384 00:14:34,180 --> 00:14:35,136 Số sáu. 385 00:14:35,136 --> 00:14:37,770 Một, hai, ba, bốn, năm, sáu, bảy. 386 00:14:37,770 --> 00:14:39,410 Oh, đây là khó xử. 387 00:14:39,410 --> 00:14:41,210 >> SPEAKER 2: Tôi sẽ chỉ nhận được một -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. Malan: Tốt thỏa thuận. 389 00:14:41,900 --> 00:14:43,130 Được rồi. 390 00:14:43,130 --> 00:14:44,611 Cảm ơn bạn đã tham gia. 391 00:14:44,611 --> 00:14:47,200 >> [Vỗ tay] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Được rồi. 394 00:14:48,860 --> 00:14:51,970 Vì vậy, chúng tôi có bốn, hai, sáu, một, ba, bảy, năm. 395 00:14:51,970 --> 00:14:56,010 Hoàn thiện vì vậy chúng tôi có bảy tình nguyện viên ở đây người đều bình đẳng trong chiều rộng đến 396 00:14:56,010 --> 00:14:57,430 mảng mà chúng ta đang chơi với trước đó. 397 00:14:57,430 --> 00:14:59,470 Và tôi đã chọn bảy cho lý do sẽ được chỉ 398 00:14:59,470 --> 00:15:00,840 thuận tiện trong một chút. 399 00:15:00,840 --> 00:15:04,400 Và tôi sẽ đề xuất đầu tiên chúng tôi sắp xếp bảy tình nguyện viên. 400 00:15:04,400 --> 00:15:06,786 Nếu bạn muốn, đầu tiên, để chào hỏi mặc dù. 401 00:15:06,786 --> 00:15:08,970 Vì đây là có được một lúng túng trong vài phút. 402 00:15:08,970 --> 00:15:10,370 Giới thiệu bản thân. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Xin chào, tôi là Grace. 404 00:15:10,980 --> 00:15:14,190 Tôi là một sinh viên năm hai trong Leverett nhà. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Hi. 406 00:15:14,620 --> 00:15:15,620 Tôi Branson. 407 00:15:15,620 --> 00:15:16,920 Tôi là một sinh viên năm nhất trong mối hàn. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> Gabe: Hi. 410 00:15:20,230 --> 00:15:21,040 Tôi Gabe. 411 00:15:21,040 --> 00:15:22,300 Tôi là một cơ sở trong Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Tôi là Neil. 414 00:15:25,980 --> 00:15:29,090 Tôi là một sinh viên năm nhất trong Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Tôi là Jason. 416 00:15:29,550 --> 00:15:32,816 Tôi là một sinh viên năm nhất trong Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Tôi là Mike. 418 00:15:33,700 --> 00:15:37,360 Tôi là một sinh viên năm nhất trong Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Tôi là Jess. 420 00:15:37,990 --> 00:15:40,313 Tôi là một sinh viên năm hai trong Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. Malan: Tuyệt vời. 422 00:15:41,300 --> 00:15:41,850 Được rồi. 423 00:15:41,850 --> 00:15:44,190 Vâng, cảm ơn bạn cho tất cả các của chúng tôi tình nguyện viên ở đây cho đến nay. 424 00:15:44,190 --> 00:15:47,110 Và thách thức trong tay bây giờ sẽ được sắp xếp của những chàng trai, nhưng sau đó 425 00:15:47,110 --> 00:15:50,250 chúng ta sẽ phải suy nghĩ một chút khó khăn về tính hiệu quả của chúng tôi thực sự 426 00:15:50,250 --> 00:15:51,110 sắp xếp chúng. 427 00:15:51,110 --> 00:15:52,580 Vì vậy, trước tiên hãy thử này. 428 00:15:52,580 --> 00:15:55,970 Các bạn có thể nhìn thấy số của nhau chỉ bằng cách đặt xung quanh các góc. 429 00:15:55,970 --> 00:15:59,380 Đi trước và mất một vài giây, và loại mình từ nhỏ nhất trên 430 00:15:59,380 --> 00:16:01,240 trái sang lớn nhất ở bên phải. 431 00:16:01,240 --> 00:16:02,490 Đi. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> OK. 434 00:16:07,530 --> 00:16:08,030 Tốt. 435 00:16:08,030 --> 00:16:09,370 Đó là thực sự darn nhanh. 436 00:16:09,370 --> 00:16:14,040 Bây giờ ai đó ở đây, là những gì các thuật toán mà những kẻ áp dụng? 437 00:16:14,040 --> 00:16:14,900 >> SPEAKER 1: Ít nhất. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. Malan: OK. 439 00:16:15,000 --> 00:16:18,070 Ít nhất đến lớn nhất thực sự là sắp xếp của mục tiêu, nhưng tôi không chắc chắn đó là 440 00:16:18,070 --> 00:16:18,890 thực sự là một thuật toán. 441 00:16:18,890 --> 00:16:21,810 Ít nhất đến lớn nhất không nói tôi bước theo các bước phải làm gì. 442 00:16:21,810 --> 00:16:22,833 Yeah? 443 00:16:22,833 --> 00:16:24,083 >> SPEAKER 1: [nghe được] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> DAVID J. Malan: OK. 446 00:16:26,280 --> 00:16:28,920 Vì vậy, nếu bạn nhìn thấy một người nhỏ hơn số của bạn, sau đó di chuyển đến 447 00:16:28,920 --> 00:16:29,680 quyền của họ. 448 00:16:29,680 --> 00:16:32,800 Vì vậy mà hiện nay đã nhận được nhiều ý nghĩa, giống như một thuật toán, bởi vì bạn 449 00:16:32,800 --> 00:16:35,410 có thể nói, nếu điều này, sau đó. 450 00:16:35,410 --> 00:16:37,050 Vì vậy, chúng tôi có một số loại xây dựng có điều kiện. 451 00:16:37,050 --> 00:16:39,700 Và những kẻ dường như để làm điều đó một vài lần, bởi vì một số bạn di chuyển một chút 452 00:16:39,700 --> 00:16:40,420 một khoảng cách. 453 00:16:40,420 --> 00:16:43,410 Vì vậy, có lẽ một số loại vòng lặp xảy ra trong tâm trí của họ. 454 00:16:43,410 --> 00:16:44,610 >> Nhưng hãy cố gắng để chính thức hóa đó. 455 00:16:44,610 --> 00:16:47,540 Nếu các bạn có thể thiết lập lại trở lại để sắp xếp này. 456 00:16:47,540 --> 00:16:50,650 Chúng ta hãy xem nếu chúng ta không có thể chính thức hóa này bit, và sau đó đặt câu hỏi, chỉ cần 457 00:16:50,650 --> 00:16:51,580 cách hiệu quả là điều này? 458 00:16:51,580 --> 00:16:54,220 Tất nhiên, khi chúng tôi làm điều này chậm hơn, nó sẽ cảm thấy như tốt 459 00:16:54,220 --> 00:16:57,210 một thuật toán, nhưng chúng ta hãy xem nếu chúng ta có thể đặt ngón tay của chúng tôi về các bước chính xác. 460 00:16:57,210 --> 00:16:58,670 >> Vì vậy, bạn hai chàng trai bốn và hai. 461 00:16:58,670 --> 00:17:01,020 Hoặc bạn đặt hàng đúng hay sai? 462 00:17:01,020 --> 00:17:01,900 Rõ ràng là không chính xác. 463 00:17:01,900 --> 00:17:02,710 Vì vậy, chúng tôi đổi chỗ. 464 00:17:02,710 --> 00:17:05,170 Bây giờ tôi sẽ di chuyển sang một bên ở đây và nói, 4-6. 465 00:17:05,170 --> 00:17:06,240 Là bạn đúng hay sai? 466 00:17:06,240 --> 00:17:06,599 >> Gabe: Đúng. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. Malan: Đúng. 468 00:17:07,180 --> 00:17:08,300 Sáu và một? 469 00:17:08,300 --> 00:17:08,609 Không. 470 00:17:08,609 --> 00:17:09,630 Trao đổi. 471 00:17:09,630 --> 00:17:10,490 Vì vậy, đó là hai giao dịch hoán đổi. 472 00:17:10,490 --> 00:17:11,710 Sáu và ba? 473 00:17:11,710 --> 00:17:11,980 Không. 474 00:17:11,980 --> 00:17:13,000 Trao đổi. 475 00:17:13,000 --> 00:17:13,930 Sáu và bảy? 476 00:17:13,930 --> 00:17:14,630 Có vẻ tốt. 477 00:17:14,630 --> 00:17:15,396 Bảy và năm? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [nghe được] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. Malan: OK, trao đổi. 480 00:17:17,089 --> 00:17:19,770 Và sắp xếp. 481 00:17:19,770 --> 00:17:19,980 Được rồi. 482 00:17:19,980 --> 00:17:21,440 Vì vậy, rõ ràng là không, phải không? 483 00:17:21,440 --> 00:17:22,470 Vì vậy, có được nhiều đang xảy ra. 484 00:17:22,470 --> 00:17:24,920 Nhưng, trên thực tế, những kẻ, thậm chí chỉ theo bản năng. 485 00:17:24,920 --> 00:17:25,450 tiếp tục di chuyển. 486 00:17:25,450 --> 00:17:27,710 Họ không chỉ dừng lại, khi họ sửa chữa một vấn đề. 487 00:17:27,710 --> 00:17:27,839 Như vậy. 488 00:17:27,839 --> 00:17:29,390 Thật vậy, tôi sẽ có để làm điều tương tự. 489 00:17:29,390 --> 00:17:32,720 Tôi sẽ phải sắp xếp các tua trở lại đến đầu của vấn đề này, 490 00:17:32,720 --> 00:17:35,630 hoặc bắt đầu của mảng này người, chúng ta hãy bắt đầu gọi điện cho họ. 491 00:17:35,630 --> 00:17:38,366 >> Và bây giờ những gì nên thuật toán của tôi trên đèo thứ hai được? 492 00:17:38,366 --> 00:17:39,220 >> SPEAKER 1: Cùng một điều. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. Malan: Cùng một điều. 494 00:17:39,940 --> 00:17:41,460 Và điều này, tôi bắt đầu thích, phải không? 495 00:17:41,460 --> 00:17:44,720 Ngay sau khi bạn có thể thấy mình đang làm điều tương tự một lần nữa và một lần nữa, đó là 496 00:17:44,720 --> 00:17:47,890 trở nên giống như một thuật toán, và ít bản năng của con người. 497 00:17:47,890 --> 00:17:48,680 >> Vì vậy, bây giờ, ở đây chúng tôi đi một lần nữa. 498 00:17:48,680 --> 00:17:49,870 Hai và bốn? 499 00:17:49,870 --> 00:17:50,220 Không. 500 00:17:50,220 --> 00:17:51,050 Bốn và một? 501 00:17:51,050 --> 00:17:53,380 Ah, có thực sự một số làm việc vẫn được thực hiện. 502 00:17:53,380 --> 00:17:53,620 Cho và ba? 503 00:17:53,620 --> 00:17:54,572 Tốt. 504 00:17:54,572 --> 00:17:56,000 Bốn và sáu? 505 00:17:56,000 --> 00:17:58,380 Sáu và năm? 506 00:17:58,380 --> 00:17:59,470 Sáu và bảy? 507 00:17:59,470 --> 00:18:00,970 OK, bây giờ, thực hiện. 508 00:18:00,970 --> 00:18:01,550 OK, không. 509 00:18:01,550 --> 00:18:02,710 Tôi phải quay trở lại. 510 00:18:02,710 --> 00:18:05,130 >> Vì vậy, bây giờ, một lần nữa, chúng tôi đang làm điều này một chút cố tình hơn. 511 00:18:05,130 --> 00:18:08,700 Và bây giờ, đó chỉ là một bộ não thực hiện thuật toán này. 512 00:18:08,700 --> 00:18:10,290 Một CPU, nếu bạn sẽ. 513 00:18:10,290 --> 00:18:13,090 Và thẳng thắn, đó là tài nguyên duy nhất chúng ta sẽ có thể truy cập. 514 00:18:13,090 --> 00:18:16,280 Và một khi chúng tôi quay trở lại với một bàn phím và có một cái gì đó như C của chúng tôi 515 00:18:16,280 --> 00:18:19,600 xử lý, chúng ta chỉ viết một chương trình có thể làm một việc tại một thời điểm. 516 00:18:19,600 --> 00:18:22,900 Trong khi đó, những kẻ một thời điểm trước đây, chúng tôi thừa hưởng trí tuệ tập thể của họ 517 00:18:22,900 --> 00:18:24,180 như các bạn đã làm trong tuần không. 518 00:18:24,180 --> 00:18:24,980 Vì vậy, hãy tiếp tục làm điều này. 519 00:18:24,980 --> 00:18:26,260 >> Hai và một. 520 00:18:26,260 --> 00:18:26,945 Hai và ba. 521 00:18:26,945 --> 00:18:27,460 Ba và bốn. 522 00:18:27,460 --> 00:18:28,310 Bốn và năm. 523 00:18:28,310 --> 00:18:28,620 Năm và sáu. 524 00:18:28,620 --> 00:18:30,510 Sáu và bảy. 525 00:18:30,510 --> 00:18:31,880 Thực hiện? 526 00:18:31,880 --> 00:18:34,560 Vì vậy, tôi, nhưng hãy để tôi chơi ủng hộ của ma quỷ. 527 00:18:34,560 --> 00:18:37,950 Làm tôi, các loại máy tính người chỉ đã vượt qua thông qua mảng này 528 00:18:37,950 --> 00:18:40,225 người, biết rằng tôi đang thực hiện? 529 00:18:40,225 --> 00:18:40,670 >> SPEAKER 1: Không. 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. Malan: Vậy tại sao? 531 00:18:41,050 --> 00:18:46,900 Những gì tôi phải làm để kết luận dứt khoát rằng tôi đang thực hiện? 532 00:18:46,900 --> 00:18:48,230 Có lẽ hơn một vượt qua. 533 00:18:48,230 --> 00:18:48,430 Phải không? 534 00:18:48,430 --> 00:18:51,760 Bởi vì tất cả tôi biết rằng từ trước vượt qua là tôi sửa chữa một sai lầm. 535 00:18:51,760 --> 00:18:53,920 Và đó có nghĩa là, có thể có vẫn còn một sai lầm 536 00:18:53,920 --> 00:18:54,840 mà tôi cần phải sửa chữa. 537 00:18:54,840 --> 00:18:58,680 Vì vậy, tôi chỉ có thể chắc chắn bởi tua, và sau đó kiểm tra, 1-2, hai và 538 00:18:58,680 --> 00:19:00,940 ba, ba và bốn, bốn và năm, năm và sáu, sáu và bảy. 539 00:19:00,940 --> 00:19:02,510 OK, bây giờ tôi đã không làm việc. 540 00:19:02,510 --> 00:19:05,990 >> Tôi chắc chắn có thể nhớ rằng tôi đã không làm việc với một cái gì đó giống như một biến, 541 00:19:05,990 --> 00:19:06,975 như một int. 542 00:19:06,975 --> 00:19:12,490 Gọi nó là giao dịch hoán đổi, và nếu giao dịch hoán đổi là 0 một lần tôi được đây, và nó bắt đầu từ 0, sau đó 543 00:19:12,490 --> 00:19:15,520 Tôi sẽ chỉ được ngu ngốc để tiếp tục đi qua lại, kiểm tra một lần nữa, và 544 00:19:15,520 --> 00:19:16,450 một lần nữa, và một lần nữa, phải không? 545 00:19:16,450 --> 00:19:18,450 Bởi vì bạn gặp khó khăn trong một số loại vòng lặp vô hạn. 546 00:19:18,450 --> 00:19:21,250 Vì vậy, ngay sau khi có 0 giao dịch hoán đổi, chúng ta có thể cho rằng điều này 547 00:19:21,250 --> 00:19:23,810 Thuật toán là thực sự hoàn chỉnh. 548 00:19:23,810 --> 00:19:25,400 >> Bây giờ, chúng ta hãy đặt một tên trên này. 549 00:19:25,400 --> 00:19:28,930 Các thuật toán mà tôi đề nghị chúng ta chỉ thực hiện được một cái gì đó gọi là bong bóng 550 00:19:28,930 --> 00:19:32,800 loại, được gọi như vậy trong ý nghĩa rằng những con số mà là loại lớn hơn 551 00:19:32,800 --> 00:19:37,990 bong bóng theo cách của họ lên đến đỉnh, hoặc lên đến cuối của dãy số. 552 00:19:37,990 --> 00:19:40,270 Nhưng làm thế nào hiệu quả là thuật toán này? 553 00:19:40,270 --> 00:19:44,600 Bao nhiêu bước này tôi phải thể chất thực hiện, ví dụ, để sắp xếp những 554 00:19:44,600 --> 00:19:45,850 bảy con người? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Bốn đến năm? 557 00:19:49,550 --> 00:19:51,420 OK, quá nhiều là cuối cùng sẽ là câu trả lời. 558 00:19:51,420 --> 00:19:54,960 Nhưng thậm chí sau đó, số lượng cụ thể không phải là quá thú vị. 559 00:19:54,960 --> 00:19:56,670 Chúng ta hãy khái quát nó như n. 560 00:19:56,670 --> 00:20:00,520 Vì vậy, nếu tôi đã n người lên đây, và họ là, loại, trong thứ tự ngẫu nhiên tại 561 00:20:00,520 --> 00:20:02,180 bắt đầu, theo thứ tự ban đầu. 562 00:20:02,180 --> 00:20:04,910 Vâng, bao nhiêu bước này tôi có để trên đèo đầu tiên? 563 00:20:04,910 --> 00:20:09,810 Đó là một, hai, ba, bốn, năm, sáu, và họ bảy người, vì vậy 564 00:20:09,810 --> 00:20:13,670 đó là bảy, sáu -, vì vậy đó là n trừ một bước lần đầu tiên. 565 00:20:13,670 --> 00:20:16,280 >> Bây giờ, bao nhiêu bước này tôi có phải thực hiện khi tôi rewound? 566 00:20:16,280 --> 00:20:19,310 Vâng, chúng tôi thực sự có thể tăng gấp đôi nếu chúng tôi thực sự muốn, nhưng bây giờ, tôi 567 00:20:19,310 --> 00:20:22,300 chỉ cần đi để nói, tất cả các bên phải, khác n trừ đi 1. 568 00:20:22,300 --> 00:20:25,240 Vì vậy, các n trừ đi 1 là sẽ nhận được gây phiền nhiễu để theo dõi, vì vậy hãy 569 00:20:25,240 --> 00:20:26,400 chỉ tròn một chút. 570 00:20:26,400 --> 00:20:27,770 Vì vậy, 2n bước. 571 00:20:27,770 --> 00:20:29,310 Vì vậy, 14 bước, cho hay phải mất. 572 00:20:29,310 --> 00:20:31,930 >> Bao nhiêu lần tôi đi một bước thời gian tới? 573 00:20:31,930 --> 00:20:33,740 Vâng, đó là 3n. 574 00:20:33,740 --> 00:20:34,510 thực sự. 575 00:20:34,510 --> 00:20:37,920 Và bây giờ, trong trường hợp xấu nhất, cho Ví dụ, bao nhiêu lần tôi đã có 576 00:20:37,920 --> 00:20:41,730 đi qua lại, qua lại, thực hiện thuật toán này, trao đổi 577 00:20:41,730 --> 00:20:44,620 người từng vượt qua, khoảng? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Nó thực sự n bình phương, phải không? 580 00:20:50,010 --> 00:20:53,000 >> Bởi vì trong trường hợp xấu nhất, bạn có thể loại của suy nghĩ về điều này bằng trực giác, 581 00:20:53,000 --> 00:20:54,800 mặc dù nó có thể mất một chút chút thời gian để chìm in 582 00:20:54,800 --> 00:20:57,590 Trong trường hợp xấu nhất, những gì sẽ những Bảy người đã trông giống như, trong 583 00:20:57,590 --> 00:21:00,230 các điều khoản của thỏa thuận các con số của họ? 584 00:21:00,230 --> 00:21:01,460 Hoàn toàn ngược lại, phải không? 585 00:21:01,460 --> 00:21:02,815 Và chỉ để mô phỏng mà, là những gì tên của bạn một lần nữa? 586 00:21:02,815 --> 00:21:03,360 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> DAVID J. Malan: Mike? 588 00:21:03,640 --> 00:21:08,100 OK, Mike, có thể bạn chỉ cần tham gia tôi trên đây chỉ một giây? 589 00:21:08,100 --> 00:21:08,880 Trên thực tế, không. 590 00:21:08,880 --> 00:21:10,150 Mike xin lỗi, chúng ta hãy quay lại. 591 00:21:10,150 --> 00:21:10,910 Tên của bạn là gì nữa? 592 00:21:10,910 --> 00:21:11,180 >> NEIL: Neil. 593 00:21:11,180 --> 00:21:11,640 >> DAVID J. Malan: Neil. 594 00:21:11,640 --> 00:21:13,750 OK, Neil, bạn đến với tôi, nếu bạn không nhớ. 595 00:21:13,750 --> 00:21:17,150 Vì vậy, tôi sẽ đề xuất, chỉ cần cho đơn giản, rằng Neil hiện đang ở của mình 596 00:21:17,150 --> 00:21:18,510 trường hợp xấu nhất có thể. 597 00:21:18,510 --> 00:21:20,720 Nhưng nhớ lại làm thế nào tôi thực hiện thuật toán của tôi. 598 00:21:20,720 --> 00:21:24,530 Tôi so sánh, so sánh, so sánh, so sánh, so sánh, oh. 599 00:21:24,530 --> 00:21:26,640 Bây giờ những kẻ đang ra trật tự, vì vậy tôi sửa chữa. 600 00:21:26,640 --> 00:21:27,980 Vì vậy, các bạn trao đổi. 601 00:21:27,980 --> 00:21:31,630 Nhưng xem xét bây giờ, bao nhiêu xa hơn Neil không phải đi đâu? 602 00:21:31,630 --> 00:21:32,690 Nó khoảng n. 603 00:21:32,690 --> 00:21:33,570 Bạn biết đấy, nó không thực sự n. 604 00:21:33,570 --> 00:21:36,040 Nó giống như, n trừ đi 1, nhưng tôi nhận được khó chịu theo dõi lưu giữ ít 605 00:21:36,040 --> 00:21:37,550 số lượng, vì vậy chúng ta hãy gọi nó là n. 606 00:21:37,550 --> 00:21:42,860 >> Vì vậy, nếu Neil di chuyển một bước tối đa mỗi thời gian, và để di chuyển Neil một bước, 607 00:21:42,860 --> 00:21:46,580 Tôi phải làm qua thực sự tẻ nhạt này qua lại, đây là khoảng 608 00:21:46,580 --> 00:21:52,080 làm điều này, bước n, tổng cộng n lần, bởi vì nó sẽ đưa tôi 609 00:21:52,080 --> 00:21:55,820 nhiều bước để có được Neil tất cả đường đến nơi anh thuộc về. 610 00:21:55,820 --> 00:21:58,620 Hãy để một mình tất cả mọi người khác nếu các bạn tất cả đều sai lệnh là tốt. 611 00:21:58,620 --> 00:22:01,100 >> Vì vậy, chúng ta hãy gọi bong bóng sắp xếp n bình phương. 612 00:22:01,100 --> 00:22:04,860 Thời gian chạy của thuật toán này, thực hiện các thuật toán này, 613 00:22:04,860 --> 00:22:07,120 hiệu quả của thuật toán này, chúng ta sẽ chỉ mô tả hơn 614 00:22:07,120 --> 00:22:08,800 nói chung là n bình phương. 615 00:22:08,800 --> 00:22:11,650 Đó là tốt đẹp, bởi vì tôi có thể làm cùng một ví dụ với tám người, chín 616 00:22:11,650 --> 00:22:15,450 người, một triệu người, và Câu trả lời là sẽ không thay đổi. 617 00:22:15,450 --> 00:22:18,870 >> Vì vậy, nếu các bạn không phiền, chúng ta hãy thiết lập lại bạn đến nơi mà bạn bắt đầu. 618 00:22:18,870 --> 00:22:22,510 Và chúng ta hãy thử hai cách tiếp cận khác và xem nếu chúng ta không có thể làm cơ bản 619 00:22:22,510 --> 00:22:23,820 tốt hơn thế này. 620 00:22:23,820 --> 00:22:27,130 Vì vậy, thời gian này, tôi sẽ đề xuất một loại thuật toán khác nhau. 621 00:22:27,130 --> 00:22:29,950 Đó là rất thông minh của chúng tôi thời gian qua, và các bạn đã đúng khi có 622 00:22:29,950 --> 00:22:32,470 bản năng phải chỉ loại trao đổi của cặp. 623 00:22:32,470 --> 00:22:36,500 Nhưng nếu tôi thực sự muốn tiếp cận này đơn giản, và mục tiêu của tôi là để di chuyển 624 00:22:36,500 --> 00:22:39,800 tất cả các số ít theo cách này, và đẩy tất cả các số lớn 625 00:22:39,800 --> 00:22:43,030 cách, tại sao tôi không chỉ làm điều đó trong ngây thơ nhất cách có thể và xem nếu tôi 626 00:22:43,030 --> 00:22:45,730 có thể làm tốt hơn những gì đã được một khá thuật toán phức tạp? 627 00:22:45,730 --> 00:22:46,620 >> Vì vậy, chúng ta hãy xem. 628 00:22:46,620 --> 00:22:48,940 Bốn là một con số khá nhỏ, vì vậy tôi sẽ để lại cho bạn có thời điểm. 629 00:22:48,940 --> 00:22:50,610 Ooh, số hai là tốt hơn. 630 00:22:50,610 --> 00:22:52,230 Vì vậy, có thể bạn chỉ cần bước về phía trước cho một thời điểm? 631 00:22:52,230 --> 00:22:55,670 Này hiện đang được đánh số nhỏ nhất của tôi ứng cử viên, và tôi sẽ nhớ 632 00:22:55,670 --> 00:22:57,000 rằng với, như, một biến. 633 00:22:57,000 --> 00:22:57,930 Nhưng tôi sẽ tiếp tục kiểm tra. 634 00:22:57,930 --> 00:22:59,890 Có một người nào đó mà số là nhỏ hơn? 635 00:22:59,890 --> 00:23:00,460 Sáu, không. 636 00:23:00,460 --> 00:23:01,390 Oh, có một lần nữa là Neil. 637 00:23:01,390 --> 00:23:04,050 >> Vì vậy, tôi sẽ đẩy bạn trở lại loại khái niệm. 638 00:23:04,050 --> 00:23:05,120 Neil sẽ đi về phía trước. 639 00:23:05,120 --> 00:23:08,440 Và bây giờ, biến mà tôi đang sử dụng để theo dõi những người có nhỏ nhất 640 00:23:08,440 --> 00:23:11,390 số được cập nhật để chứa Vị trí của Neil. 641 00:23:11,390 --> 00:23:12,110 Vâng, chúng ta hãy xem. 642 00:23:12,110 --> 00:23:13,960 Ba, bảy, năm. 643 00:23:13,960 --> 00:23:15,590 OK, tôi biết Neil là nhỏ nhất. 644 00:23:15,590 --> 00:23:18,110 Điều đơn giản nhất là những gì cho tôi để làm gì bây giờ? 645 00:23:18,110 --> 00:23:21,410 Tôi sẽ không lãng phí thời gian của tôi bằng cách chỉ sủi bọt Neil một vị trí bên trái. 646 00:23:21,410 --> 00:23:25,350 Tại sao tôi không chỉ cần đặt nơi ông Neil thuộc, đó là tất nhiên ở đâu? 647 00:23:25,350 --> 00:23:26,160 >> Tất cả các con đường ở đầu. 648 00:23:26,160 --> 00:23:27,720 Vì vậy, Neil, đi với tôi. 649 00:23:27,720 --> 00:23:28,910 Và là tên bạn một lần nữa những gì? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Grace. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. Malan: Grace. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Vì vậy, Grace, không may, bạn loại theo cách này. 654 00:23:32,490 --> 00:23:34,290 Vì vậy, làm thế nào để chúng ta giải quyết vấn đề này? 655 00:23:34,290 --> 00:23:34,490 Phải không? 656 00:23:34,490 --> 00:23:37,500 Nếu đây là một mảng, có chỉ có bảy địa điểm. 657 00:23:37,500 --> 00:23:40,830 Nhớ lại rằng, với Rob, chúng tôi nói chuyện về tuyên bố lứa tuổi, và chúng tôi chỉ có một 658 00:23:40,830 --> 00:23:41,740 số hữu hạn các lứa tuổi? 659 00:23:41,740 --> 00:23:42,535 Cùng một ý tưởng ở đây. 660 00:23:42,535 --> 00:23:44,300 Chúng tôi chỉ có một số hữu hạn các số nguyên. 661 00:23:44,300 --> 00:23:47,590 Grace là loại trong của chúng tôi cách, vì vậy làm thế nào để chúng tôi sửa chữa? 662 00:23:47,590 --> 00:23:49,555 >> Cách đơn giản nhất là như thế, Ơn, xin lỗi. 663 00:23:49,555 --> 00:23:51,870 Bạn sẽ phải đi qua có như vậy chúng ta có thể làm cho căn phòng. 664 00:23:51,870 --> 00:23:55,290 Bây giờ, nếu bạn nghĩ về điều này, có thể chúng tôi chỉ làm cho vấn đề tồi tệ hơn. 665 00:23:55,290 --> 00:23:58,510 Và có lẽ chúng ta đã làm, bởi vì những gì nếu Grace được đặt ở bên phải? 666 00:23:58,510 --> 00:24:01,730 Nhưng chúng tôi biết cô ấy không, bởi vì nếu không, cô sẽ được 667 00:24:01,730 --> 00:24:03,980 đứng về phía trước thay vì Neil vào thời điểm này, phải không? 668 00:24:03,980 --> 00:24:05,550 Chúng tôi đã kiểm tra số cô ấy. 669 00:24:05,550 --> 00:24:05,770 >> Được rồi. 670 00:24:05,770 --> 00:24:09,110 Vì vậy, bây giờ, Neil là đặt ở bên phải, và Tôi có thể làm tối ưu hóa nhẹ. 671 00:24:09,110 --> 00:24:11,740 Đối với những phút tiếp theo, tôi sẽ bỏ qua Neil tất cả cùng nhau, như vậy là không 672 00:24:11,740 --> 00:24:15,280 lãng phí thời gian của mình, hoặc vô tình trao đổi anh ấy đến chỗ sai. 673 00:24:15,280 --> 00:24:17,805 Vì vậy, bây giờ, làm thế nào để tìm kế tiếp yếu tố đó là nhỏ nhất? 674 00:24:17,805 --> 00:24:18,480 Hai. 675 00:24:18,480 --> 00:24:20,225 Đó là một con số khá tốt, nếu bạn muốn bước về phía trước và 676 00:24:20,225 --> 00:24:21,100 Tôi sẽ nhớ đến bạn. 677 00:24:21,100 --> 00:24:21,980 Sáu, không tốt. 678 00:24:21,980 --> 00:24:24,820 Bốn, ba, bảy, năm, không tốt. 679 00:24:24,820 --> 00:24:26,800 Vì vậy, hãy để tôi di chuyển bạn đúng nơi của bạn. 680 00:24:26,800 --> 00:24:28,470 Và chúng tôi chỉ có may mắn lần này. 681 00:24:28,470 --> 00:24:31,350 >> Bây giờ, tôi sẽ bỏ qua những hai người, và bây giờ làm thêm một 682 00:24:31,350 --> 00:24:32,260 đi qua này. 683 00:24:32,260 --> 00:24:33,490 Sáu, rằng một số lượng khá nhỏ. 684 00:24:33,490 --> 00:24:34,300 Đi về phía trước. 685 00:24:34,300 --> 00:24:35,220 Oh, xin lỗi. 686 00:24:35,220 --> 00:24:37,640 Số ân sủng là tốt hơn, để bước về phía trước. 687 00:24:37,640 --> 00:24:38,260 Bốn. 688 00:24:38,260 --> 00:24:39,120 Xin lỗi, Grace. 689 00:24:39,120 --> 00:24:39,950 Quay trở lại một lần nữa. 690 00:24:39,950 --> 00:24:41,550 Thứ ba là tốt hơn. 691 00:24:41,550 --> 00:24:42,290 Bảy. 692 00:24:42,290 --> 00:24:42,720 Năm. 693 00:24:42,720 --> 00:24:43,550 Và bây giờ tên của bạn là gì nữa? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> DAVID J. Malan: Jason. 696 00:24:44,420 --> 00:24:47,050 Vì vậy, Jason hiện đang là nhỏ nhất yếu tố tôi đã chọn. 697 00:24:47,050 --> 00:24:49,160 Mà là ông sẽ đi đâu? 698 00:24:49,160 --> 00:24:50,380 Vì vậy, nơi sáu là. 699 00:24:50,380 --> 00:24:51,210 Và tên của bạn là một lần nữa? 700 00:24:51,210 --> 00:24:51,710 >> Gabe: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> DAVID J. Malan: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe là trong cách. 703 00:24:53,220 --> 00:24:54,640 Điều dễ nhất để làm gì? 704 00:24:54,640 --> 00:24:58,390 Trao đổi hai chàng trai và tiếp tục. 705 00:24:58,390 --> 00:24:59,020 Vì vậy, bây giờ chúng ta hãy xem. 706 00:24:59,020 --> 00:25:00,170 Ai là nhỏ nhất? 707 00:25:00,170 --> 00:25:01,030 Bốn. 708 00:25:01,030 --> 00:25:01,990 Hãy để tôi chỉ cần loại gian lận. 709 00:25:01,990 --> 00:25:03,090 Năm sẽ là nhỏ nhất. 710 00:25:03,090 --> 00:25:05,220 Tôi tìm tới, nếu bạn muốn bước về phía trước, những gì tôi phải làm gì với 711 00:25:05,220 --> 00:25:06,820 những người này, với Gabe? 712 00:25:06,820 --> 00:25:08,450 Trao đổi một lần nữa. 713 00:25:08,450 --> 00:25:10,740 Vì vậy, bây giờ, vẫn còn hơi ra khỏi trật tự. 714 00:25:10,740 --> 00:25:14,140 Tôi tìm thấy Gabe là nhỏ nhất, vì vậy Tôi bật anh ta ra, di chuyển các bạn hơn. 715 00:25:14,140 --> 00:25:15,190 Và thực hiện. 716 00:25:15,190 --> 00:25:17,200 >> Vì vậy, câu trả lời là như nhau. 717 00:25:17,200 --> 00:25:18,600 Kết quả cuối cùng là như nhau. 718 00:25:18,600 --> 00:25:22,730 Mà của hai thuật toán này là tốt hơn? 719 00:25:22,730 --> 00:25:23,500 Điều thứ hai, tôi nghe. 720 00:25:23,500 --> 00:25:24,252 Tại sao? 721 00:25:24,252 --> 00:25:25,900 >> SPEAKER 3: Đó là bước n [không nghe được]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. Malan: Đó là n bậc nhất. 723 00:25:27,600 --> 00:25:28,490 Thú vị. 724 00:25:28,490 --> 00:25:30,610 Như vậy là nó mặc dù? 725 00:25:30,610 --> 00:25:33,630 Vì vậy, làm thế nào tôi tìm thấy phần tử nhỏ nhất? 726 00:25:33,630 --> 00:25:37,060 Bao nhiêu bước này tôi phải mất các tìm các phần tử nhỏ nhất? 727 00:25:37,060 --> 00:25:39,220 Tôi đã có một nhìn tất cả các cách ở cuối, phải không? 728 00:25:39,220 --> 00:25:41,530 Bởi vì trong đó trường hợp xấu nhất, những gì nếu Neil đã ở đây? 729 00:25:41,530 --> 00:25:45,700 Vì vậy, chỉ tìm kiếm các phần tử nhỏ nhất tôi phải mất n bước, hoặc n trừ đi 1. 730 00:25:45,700 --> 00:25:46,100 Nhưng, OK. 731 00:25:46,100 --> 00:25:46,980 Vì vậy, sửa chữa Neil. 732 00:25:46,980 --> 00:25:48,740 Hãy nhớ rằng, một phút hoặc lâu hơn trước đây. 733 00:25:48,740 --> 00:25:51,680 >> Nhưng làm thế nào tôi tìm kế tiếp phần tử nhỏ nhất? 734 00:25:51,680 --> 00:25:54,830 Đó là n trừ đi 1, hoặc n trừ đi 2 thực sự, từ số bước. 735 00:25:54,830 --> 00:25:55,440 Vì vậy, OK. 736 00:25:55,440 --> 00:25:57,390 Vì vậy, tôi đã n trừ đi 2. 737 00:25:57,390 --> 00:25:57,600 Được rồi. 738 00:25:57,600 --> 00:25:59,130 Để cảm thấy tốt hơn một chút. 739 00:25:59,130 --> 00:25:59,730 Được rồi. 740 00:25:59,730 --> 00:26:03,270 Bao nhiêu bước trong thời gian tới để tìm số ba? 741 00:26:03,270 --> 00:26:04,420 Vì vậy, n trừ đi 4. 742 00:26:04,420 --> 00:26:07,670 Vì vậy, nó giảm, một ít bước trên mỗi lần lặp. 743 00:26:07,670 --> 00:26:08,740 Vì vậy, điều này không cảm thấy tốt hơn, phải không? 744 00:26:08,740 --> 00:26:13,450 Nếu thời gian trước là khoảng n lần n, Lần này là n trừ đi 1, cộng với n trừ 745 00:26:13,450 --> 00:26:16,500 2, cộng với n trừ đi 3, cộng với n trừ 4, dấu chấm, dấu chấm, dấu chấm. 746 00:26:16,500 --> 00:26:18,750 Nhưng nếu bạn nhớ lại từ trường trung học của bạn sách giáo khoa, ăn gian ít 747 00:26:18,750 --> 00:26:24,380 tấm ở mặt sau có công thức, nếu bạn thêm hàng loạt các con số, 748 00:26:24,380 --> 00:26:31,280 tổng số bước là những gì sẽ được rằng tôi có ở đây? 749 00:26:31,280 --> 00:26:36,580 >> Đây là một trong những, thích, n trừ 1, lần n, chia cho 2. 750 00:26:36,580 --> 00:26:39,040 Vì vậy, hãy để tôi xem nếu tôi có thể kéo lên này chỉ là một thời điểm. 751 00:26:39,040 --> 00:26:42,230 Và một lần nữa, tôi là loại làm tròn số số chỉ để giữ cho cuộc sống của chúng tôi đơn giản, 752 00:26:42,230 --> 00:26:47,830 nhưng khi tôi gọi lại, nó là một cái gì đó như thế nào nếu Tôi làm n trừ đi 1 điều gì đó, sau đó trừ đi n 753 00:26:47,830 --> 00:26:53,570 2, sau đó n trừ đi 3, đó là khoảng một cái gì đó như thế này hơn 2, và nếu tôi 754 00:26:53,570 --> 00:26:55,510 nhân này ra, đó là thực sự n vuông. 755 00:26:55,510 --> 00:26:58,940 Đó không phải là cảm giác quá tốt. n trừ đi n hơn 2. 756 00:26:58,940 --> 00:27:00,350 >> Nhưng đây là vấn đề. 757 00:27:00,350 --> 00:27:03,720 Khoa học máy tính, khi các vấn đề bắt đầu để có được thú vị là khi n 758 00:27:03,720 --> 00:27:04,700 được thực sự lớn. 759 00:27:04,700 --> 00:27:08,110 Và khi n được thực sự lớn, trong đó các giá trị là sẽ thống trị tất cả 760 00:27:08,110 --> 00:27:09,750 của những người khác? 761 00:27:09,750 --> 00:27:10,990 Đó là loại n bình phương, phải không? 762 00:27:10,990 --> 00:27:13,340 Có, chia cho 2 là khá tốt. 763 00:27:13,340 --> 00:27:16,740 Nhưng nếu bạn đang nói về tỷ các mẩu dữ liệu, hoặc hàng nghìn tỷ 764 00:27:16,740 --> 00:27:18,700 mẩu dữ liệu, OK, vì vậy bạn nhanh gấp hai lần. 765 00:27:18,700 --> 00:27:22,440 Nhưng những người thực sự quan tâm nếu có số lượng lớn, nếu yếu tố này là những gì được 766 00:27:22,440 --> 00:27:23,040 lớn hơn và lớn hơn. 767 00:27:23,040 --> 00:27:25,990 Và chắc chắn, nó làm cho hơn một sự khác biệt so với anh chàng này. 768 00:27:25,990 --> 00:27:29,120 Vì vậy, mặc dù các bạn là đúng, thuật toán thứ hai, chúng tôi sẽ gọi nó là 769 00:27:29,120 --> 00:27:32,970 lựa chọn loại, là, trong thế giới thực, một bit nhanh hơn khả năng, bởi vì tôi 770 00:27:32,970 --> 00:27:35,360 tham gia ngày càng ít bước mỗi lần. 771 00:27:35,360 --> 00:27:37,340 >> Nó không thực sự nhanh hơn cơ bản. 772 00:27:37,340 --> 00:27:41,430 Bởi vì nếu chúng ta thực sự chơi này ra cho giá trị lớn của n, vào cuối 773 00:27:41,430 --> 00:27:44,750 ngày, với n đủ lớn, nó vẫn còn sẽ cảm thấy khá chậm. 774 00:27:44,750 --> 00:27:46,770 Vâng, hãy để tôi lấy một vượt qua cuối cùng ở đó. 775 00:27:46,770 --> 00:27:48,920 Đó là những gì tôi sẽ gọi lựa chọn loại. 776 00:27:48,920 --> 00:27:51,040 Các bạn có thể thiết lập lại chính mình một lần cuối cùng? 777 00:27:51,040 --> 00:27:53,550 Và trong trường hợp cuối cùng này, tôi sẽ đề xuất một cái gì đó 778 00:27:53,550 --> 00:27:54,970 gọi là sắp xếp chèn. 779 00:27:54,970 --> 00:27:57,470 Sắp xếp chèn là, khái niệm, một chút khác nhau. 780 00:27:57,470 --> 00:28:00,980 >> Thay vì đi lại và chọn phần tử nhỏ nhất, tôi 781 00:28:00,980 --> 00:28:05,030 chỉ cần đi để đối phó với mỗi kẻ như tôi gặp họ, và chèn 782 00:28:05,030 --> 00:28:06,850 chúng vào vị trí chính xác của họ. 783 00:28:06,850 --> 00:28:10,160 Vì vậy, tôi chỉ cần đi để bắt đầu với Grace, và tôi thấy rằng cô ấy là số bốn. 784 00:28:10,160 --> 00:28:11,720 Trường hợp không thứ tư thuộc về ai? 785 00:28:11,720 --> 00:28:14,940 Tôi đã không bắt đầu sắp xếp bất cứ điều gì, Grace để được ở lại ngay tại đó. 786 00:28:14,940 --> 00:28:18,355 Và bây giờ tôi sẽ yêu cầu bồi thường, nếu bạn có thể có một bước bên phải của bạn, điều này 787 00:28:18,355 --> 00:28:21,650 danh sách được sắp xếp của tôi, đây là của tôi Danh sách còn lại chưa được phân loại. 788 00:28:21,650 --> 00:28:23,260 Vì vậy, bây giờ tôi sẽ tiến hành tiếp theo, và tên của bạn là gì nữa? 789 00:28:23,260 --> 00:28:23,700 >> BRANSON: Branson. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. Malan: Branson. 791 00:28:24,150 --> 00:28:25,375 Vì vậy, Branson là số hai. 792 00:28:25,375 --> 00:28:27,490 Vì vậy, tôi sẽ đưa các bạn ra trong một khoảnh khắc. 793 00:28:27,490 --> 00:28:30,940 Và bây giờ, nơi nào bạn thuộc trong mảng này? 794 00:28:30,940 --> 00:28:32,360 Vì vậy, ở bên phải của Grace. 795 00:28:32,360 --> 00:28:35,670 Vì vậy, một lần nữa, chúng ta đang loại làm Grace làm rất nhiều công việc ở đây. 796 00:28:35,670 --> 00:28:37,290 Nơi nào chúng ta đưa bạn? 797 00:28:37,290 --> 00:28:40,120 Vì vậy, chúng ta sẽ trượt bạn đến trái, và chèn Branson có. 798 00:28:40,120 --> 00:28:41,680 Nhưng bây giờ tôi cho rằng các bạn đã làm xong. 799 00:28:41,680 --> 00:28:43,240 Nhưng thông báo, tôi không sử dụng không gian thêm. 800 00:28:43,240 --> 00:28:45,130 Nó vẫn còn 2 yếu tố ở đây, 5 trên đây. 801 00:28:45,130 --> 00:28:47,910 Tổng số kích thước mảng là 7, vì vậy tôi không gian lận, tất cả phải không? 802 00:28:47,910 --> 00:28:51,950 >> Vì vậy, bây giờ chúng tôi có, với Gabe ở đây, thứ sáu, nơi nào bạn thuộc về ai? 803 00:28:51,950 --> 00:28:52,650 Bạn có may mắn một lần nữa. 804 00:28:52,650 --> 00:28:53,820 Vì vậy, bạn có thể ở ngay tại đó. 805 00:28:53,820 --> 00:28:57,210 Chỉ cần đi một bước nhỏ ở bên phải chỉ để làm cho rõ ràng rằng bạn đang sắp xếp. 806 00:28:57,210 --> 00:29:00,520 Và bây giờ chúng tôi có Neil một lần nữa, số một, nơi nào bạn đi? 807 00:29:00,520 --> 00:29:03,540 Và bây giờ là nơi mà chúng ta sẽ bắt đầu thấy rằng thuật toán này, mặc dù trên đầu tiên 808 00:29:03,540 --> 00:29:05,950 Trong nháy mắt, cảm thấy khá thông minh, xem những gì sắp xảy ra. 809 00:29:05,950 --> 00:29:07,370 Nếu bạn có thể bước về phía trước. 810 00:29:07,370 --> 00:29:09,260 >> Nơi nào chúng ta muốn đặt Neil? 811 00:29:09,260 --> 00:29:11,830 Vì vậy, rõ ràng là ở đây, vậy làm thế nào chúng tôi nhận được Neil có? 812 00:29:11,830 --> 00:29:12,970 Chúng ta hãy làm điều này từng bước. 813 00:29:12,970 --> 00:29:15,620 Gabe, nơi nào bạn cần phải đi? 814 00:29:15,620 --> 00:29:19,590 Vâng, do đó, có một bước tiến lớn, hoặc hai nửa bước để làm cho 815 00:29:19,590 --> 00:29:20,820 một bước ở đó. 816 00:29:20,820 --> 00:29:21,750 Grace, nơi bạn đi? 817 00:29:21,750 --> 00:29:22,510 Tốt. 818 00:29:22,510 --> 00:29:23,500 Vì vậy, một bước. 819 00:29:23,500 --> 00:29:24,960 Và cuối cùng, Branson? 820 00:29:24,960 --> 00:29:25,460 Một bước. 821 00:29:25,460 --> 00:29:27,190 Và bây giờ chúng ta có thể đưa Neil vào vị trí. 822 00:29:27,190 --> 00:29:28,440 >> Vì vậy, bây giờ, tiếp tục logic này. 823 00:29:28,440 --> 00:29:32,420 Mặc dù chúng tôi không thay đổi Neil hơn, và hơn và hơn, để đưa anh ta 824 00:29:32,420 --> 00:29:36,420 nơi anh đi, trong trường hợp xấu nhất, các số tiếp theo chúng tôi có thể gặp phải có thể 825 00:29:36,420 --> 00:29:42,220 là số, nói rằng, có một số bằng không, thì chúng ta sẽ phải thay đổi tất cả 826 00:29:42,220 --> 00:29:42,730 những người này. 827 00:29:42,730 --> 00:29:44,950 Giả sử rằng có một số, tiêu cực một, sau đó chúng ta phải thay đổi 828 00:29:44,950 --> 00:29:46,080 tất cả các sinh vật này. 829 00:29:46,080 --> 00:29:48,500 Vì vậy, chúng tôi thực sự chỉ là loại lật các vấn đề xung quanh, như vậy mà chúng tôi 830 00:29:48,500 --> 00:29:52,620 chuyển các chi phí từ quá trình lựa chọn để chèn 831 00:29:52,620 --> 00:29:56,930 quá trình, như vậy mà các bạn chỉ có để di chuyển khoảng n trừ đi một cái gì đó 832 00:29:56,930 --> 00:29:57,940 số bước. 833 00:29:57,940 --> 00:30:01,200 Và số lượng các bước chỉ đi tăng như tôi chọn số lượng nhiều hơn, 834 00:30:01,200 --> 00:30:04,730 nếu tôi phải tiếp tục đẩy các bạn trở lại, và trở lại, và ngược lại. 835 00:30:04,730 --> 00:30:08,320 >> Vì vậy, điều đáng buồn hiện nay là tất cả các thuật toán là n bình phương. 836 00:30:08,320 --> 00:30:10,570 Chúng ta hãy đi trước và nhờ vào những chàng trai, và hình dung những một chút 837 00:30:10,570 --> 00:30:11,090 khác nhau. 838 00:30:11,090 --> 00:30:12,312 Thực hiện rất tốt. 839 00:30:12,312 --> 00:30:14,120 >> [Vỗ tay] 840 00:30:14,120 --> 00:30:15,030 >> Được rồi. 841 00:30:15,030 --> 00:30:16,280 Có bạn đi. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Cảm ơn - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [nghe được] giữ các con số. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. Malan: Không, bạn có thể giữ số là tốt. 846 00:30:21,990 --> 00:30:23,440 Được rồi. 847 00:30:23,440 --> 00:30:24,100 Độc đáo được thực hiện. 848 00:30:24,100 --> 00:30:25,300 Được rồi. 849 00:30:25,300 --> 00:30:30,510 Vì vậy, chúng ta hãy xem nếu chúng ta không có thể bây giờ tóm tắt nhanh hơn và trực quan hơn, 850 00:30:30,510 --> 00:30:33,410 chính xác những gì vừa xảy ra đây như sau. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Tôi sẽ đi trước và kéo lên Firefox. 853 00:30:38,770 --> 00:30:41,310 Chúng tôi sẽ liên kết trình diễn này trên trang web của khóa học. 854 00:30:41,310 --> 00:30:43,870 Java là một chút khó chịu để làm việc trong một số trình duyệt những ngày này. 855 00:30:43,870 --> 00:30:46,760 Vì vậy, nếu bạn không chơi với điều này ở nhà, nhận ra bạn có thể cần phải sử dụng trình duyệt Firefox 856 00:30:46,760 --> 00:30:47,990 để có được nó làm việc. 857 00:30:47,990 --> 00:30:50,440 Và những gì tôi sẽ làm gì với điều này trình diễn như sau. 858 00:30:50,440 --> 00:30:54,875 >> Ở phía dưới, tôi có một bó toàn bộ tùy chọn trình đơn, trong đó có một sự khởi đầu và một 859 00:30:54,875 --> 00:30:55,840 nút dừng lại. 860 00:30:55,840 --> 00:30:59,450 Ngoài ra, như một sang một bên, có vẻ là một lỗi trong các chương trình này, nhờ đó mà bạn 861 00:30:59,450 --> 00:31:03,720 có thể không thực sự thấy bắt đầu hoặc dừng lại nút trừ khi bạn giữ lệnh hoặc Alt 862 00:31:03,720 --> 00:31:06,560 cộng và phóng to thu nhỏ, mà tò mò cho bạn thấy các nút hơn. 863 00:31:06,560 --> 00:31:09,090 Vì vậy, chỉ FYI nếu bạn chơi với điều này ở nhà. 864 00:31:09,090 --> 00:31:12,870 Bây giờ tôi sẽ phải bấm Start trong chỉ một thời điểm, sau khi xác định một sự chậm trễ, 865 00:31:12,870 --> 00:31:16,810 như, 200 mili giây ở đây, chỉ cần vì vậy chúng tôi có thể xem những gì sẽ xảy ra. 866 00:31:16,810 --> 00:31:20,180 >> Vì vậy, tôi cho rằng đây là một hình dung của thuật toán đầu tiên 867 00:31:20,180 --> 00:31:23,730 những kẻ đã làm, bong bóng sắp xếp, theo đó chúng tôi trao đổi người cặp-khôn ngoan. 868 00:31:23,730 --> 00:31:27,490 Cái nhìn sâu sắc quan trọng để hình dung này là chiều cao của thanh 869 00:31:27,490 --> 00:31:30,510 đại diện cho kích thước của số. 870 00:31:30,510 --> 00:31:32,210 Vì vậy, các cao thanh, lớn hơn số lượng. 871 00:31:32,210 --> 00:31:33,680 Ngắn hơn thanh, nhỏ hơn số lượng. 872 00:31:33,680 --> 00:31:38,630 Và nếu bạn nhận thấy, chúng ta đang trải qua phiên đầu tiên của thuật toán này, 873 00:31:38,630 --> 00:31:42,620 trao đổi số lớn và nhỏ, do đó, số lượng nhỏ đến trước và 874 00:31:42,620 --> 00:31:44,280 số lượng lớn đi bên phải. 875 00:31:44,280 --> 00:31:48,770 >> Và ngay sau khi chúng tôi nhận được vào cuối mảng nhiều hơn con số hơn bảy, chúng tôi 876 00:31:48,770 --> 00:31:49,900 sẽ quay trở lại để bắt đầu. 877 00:31:49,900 --> 00:31:51,140 Và dự đoán này. 878 00:31:51,140 --> 00:31:54,860 Trên cùng phía trái, anh chàng ít sẽ để trao đổi về một bên, và điều này 879 00:31:54,860 --> 00:31:56,010 quá trình lặp đi lặp lại. 880 00:31:56,010 --> 00:31:59,450 Bây giờ hình dung này một cách nhanh chóng được nhàm chán, vì vậy hãy để tôi đi trước và dừng lại 881 00:31:59,450 --> 00:32:04,170 nó, thay đổi chậm trễ một cái gì đó nhiều nhanh hơn chỉ để có được bây giờ, một cảm giác về 882 00:32:04,170 --> 00:32:05,060 thuật toán này. 883 00:32:05,060 --> 00:32:07,840 >> Vì vậy, mặc dù tôi đã tăng tốc nó lên, đây là như nâng cấp bộ vi xử lý của tôi, mua 884 00:32:07,840 --> 00:32:08,580 một máy tính mới. 885 00:32:08,580 --> 00:32:12,980 Tôi đã không thay đổi cơ bản của tôi thuật toán, nhưng bạn thực sự có thể xem chi tiết 886 00:32:12,980 --> 00:32:16,800 rõ ràng hơn với con người, mà lớn con số này đang nổi lên đến đỉnh, 887 00:32:16,800 --> 00:32:20,900 và những con số nhỏ sủi bọt xuống phía dưới. 888 00:32:20,900 --> 00:32:22,390 Và bây giờ điều này ở đây được sắp xếp. 889 00:32:22,390 --> 00:32:25,260 Và như một sang một bên, trong các hình vuông, có chỉ một số sổ sách kế toán để có 890 00:32:25,260 --> 00:32:28,010 giúp bạn đếm bao nhiêu so sánh, hoặc có bao nhiêu giao dịch hoán đổi có 891 00:32:28,010 --> 00:32:28,950 thực sự được thực hiện. 892 00:32:28,950 --> 00:32:30,750 >> Vâng, chúng ta hãy thử một trong những người khác chúng ta đã thấy. 893 00:32:30,750 --> 00:32:37,116 Hãy để tôi bấm vào bong bóng sắp xếp ở đây, và hãy để tôi lựa chọn, và toàn bộ trang web này 894 00:32:37,116 --> 00:32:38,936 là một lỗi nhỏ. 895 00:32:38,936 --> 00:32:41,155 Chúng ta hãy chấp nhận rủi ro và chạy nó một lần nữa. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Có chúng tôi đi. 898 00:32:45,030 --> 00:32:47,180 Vì vậy, chúng ta hãy làm lựa chọn sắp xếp. 899 00:32:47,180 --> 00:32:49,140 Tôi không biết lý do tại sao trình đơn xuất hiện ở đó. 900 00:32:49,140 --> 00:32:54,070 Chúng ta hãy phóng to để khắc phục điều đó lỗi, thay đổi này đến 50. 901 00:32:54,070 --> 00:32:56,020 Ah, chúng ta hãy thực sự làm mà nhanh hơn nhiều. 902 00:32:56,020 --> 00:32:59,160 Năm mili giây hoặc lâu hơn, và bắt đầu. 903 00:32:59,160 --> 00:33:00,470 >> Vì vậy, đây là lựa chọn sắp xếp. 904 00:33:00,470 --> 00:33:03,070 Vì vậy, một lần nữa, suy nghĩ về những gì chúng tôi đã làm với những con người ở đây. 905 00:33:03,070 --> 00:33:08,490 Chúng tôi đã đi qua mảng và chọn phần tử nhỏ nhất một lần nữa, 906 00:33:08,490 --> 00:33:09,250 và một lần nữa, và một lần nữa. 907 00:33:09,250 --> 00:33:11,110 Bây giờ tôi cho rằng vẫn còn khá xấu. 908 00:33:11,110 --> 00:33:15,010 Nó vẫn còn n bình phương, cho hay phải mất, nhưng nó là, trong thế giới thực, một chút 909 00:33:15,010 --> 00:33:18,280 nhanh hơn, bởi vì tôi đã thực sự tham gia ít hơn một chút bước trên mỗi lần. 910 00:33:18,280 --> 00:33:19,800 Nhưng chúng ta chỉ nói những gì? 911 00:33:19,800 --> 00:33:21,830 Có lẽ 40 hoặc hơn thanh đây? 912 00:33:21,830 --> 00:33:23,200 Chúng tôi không nói 40 triệu USD. 913 00:33:23,200 --> 00:33:27,430 Vì vậy, nó không hoàn toàn rõ ràng với tôi rằng thực sự là một lợi đáng kể. 914 00:33:27,430 --> 00:33:32,530 >> Cho tôi bây giờ quay trở lại và thay đổi của chúng tôi thuật toán thứ ba, được chọn 915 00:33:32,530 --> 00:33:33,180 sắp xếp chèn. 916 00:33:33,180 --> 00:33:36,380 Và bây giờ nó thực sự lỗi vì đơn thực sự không phải ở dưới đó. 917 00:33:36,380 --> 00:33:40,840 Vì vậy, bây giờ chúng tôi sẽ di chuyển trở lại đây và bắt đầu thuật toán này. 918 00:33:40,840 --> 00:33:43,270 Reo, bắt đầu và dừng lại. 919 00:33:43,270 --> 00:33:47,160 Vì vậy, đây là một loại có một mô hình khá với nó, nhờ đó mà chúng tôi một lần nữa 920 00:33:47,160 --> 00:33:50,240 chèn con người, hoặc trong trường hợp này, các quán bar vào 921 00:33:50,240 --> 00:33:52,620 vị trí thích hợp của họ. 922 00:33:52,620 --> 00:33:55,430 Và nó đã được thực hiện trước khi Tôi quay lại. 923 00:33:55,430 --> 00:33:58,940 Nhưng điều này cũng vậy, trên lý thuyết, vẫn còn n bình phương. 924 00:33:58,940 --> 00:34:01,430 >> Vì vậy, chúng ta hãy xem nếu chúng ta không có thể tóm tắt này như sau. 925 00:34:01,430 --> 00:34:04,750 Tôi sẽ đi trước và chỉ để cung cấp chúng tôi loại một cách phổ biến nói chuyện 926 00:34:04,750 --> 00:34:08,489 về những điều này, chúng tôi giới thiệu chỉ là một chút ký hiệu ở đây. 927 00:34:08,489 --> 00:34:12,480 Bạn đang về để nhìn thấy một cái gì đó gọi là lớn O, bởi vì nó có nghĩa là một lớn 928 00:34:12,480 --> 00:34:16,320 O. Và đây là một cách mà một máy tính nhà khoa học hay một nhà toán học thậm chí sử dụng 929 00:34:16,320 --> 00:34:19,230 để mô tả thời gian chạy của một số thuật toán. 930 00:34:19,230 --> 00:34:21,400 Bao nhiêu bước nó thực sự mất? 931 00:34:21,400 --> 00:34:25,080 >> Bây giờ tôi sẽ để gây rắc rối cho bản thân mình với chữ viết tay của tôi ở đây chỉ trong một thời điểm. 932 00:34:25,080 --> 00:34:29,020 Nhưng hãy để tôi đi trước và nói rằng đây sẽ là O lớn hơn ở đây. 933 00:34:29,020 --> 00:34:33,610 Và cho tôi giới thiệu một khác biểu tượng, một omega vốn. 934 00:34:33,610 --> 00:34:37,080 Omega là có được điều ngược lại, về cơ bản, các lớn O. Trong khi O lớn 935 00:34:37,080 --> 00:34:40,790 có nghĩa là, trong trường hợp xấu nhất, bao nhiêu thời gian có thể một số thuật toán thực hiện, trong 936 00:34:40,790 --> 00:34:43,480 theo n, omega sẽ được bao nhiêu thời gian có thể nó 937 00:34:43,480 --> 00:34:45,409 mất trong trường hợp tốt nhất. 938 00:34:45,409 --> 00:34:48,090 Và chúng tôi sẽ xem những gì chúng tôi có ý nghĩa bởi trường hợp tốt nhất chỉ trong một khoảnh khắc. 939 00:34:48,090 --> 00:34:49,940 >> Vì vậy, chúng ta hãy bắt đầu một cái gì đó đơn giản. 940 00:34:49,940 --> 00:34:54,719 Hãy để tôi bắt đầu với một tìm kiếm tuyến tính. 941 00:34:54,719 --> 00:34:55,679 Vì vậy, không phân loại. 942 00:34:55,679 --> 00:34:58,000 Chúng tôi sẽ gọi tìm kiếm tuyến tính này. 943 00:34:58,000 --> 00:35:01,140 Và bây giờ, làm cho một ít bảng trong số này. 944 00:35:01,140 --> 00:35:06,600 Và bây giờ, trong trường hợp tìm kiếm tuyến tính, trong trường hợp xấu nhất, có bao nhiêu bước là 945 00:35:06,600 --> 00:35:11,770 nó sẽ đưa tôi để tìm một số sự lựa chọn tùy ý? 946 00:35:11,770 --> 00:35:14,540 Và có n tổng số cửa hoặc n tổng số. 947 00:35:14,540 --> 00:35:15,940 Trường hợp tồi tệ nhất. 948 00:35:15,940 --> 00:35:18,800 Bao nhiêu bước tôi sẽ phải thực hiện để tìm số 50 trong một mảng 949 00:35:18,800 --> 00:35:20,830 n cửa? 950 00:35:20,830 --> 00:35:21,410 Và tại sao? 951 00:35:21,410 --> 00:35:23,680 Bởi vì nó có thể là tất cả các cách hơn vào cuối. 952 00:35:23,680 --> 00:35:27,120 Vì vậy, nhiều như Jennifer gặp phải, số 50 là tất cả các cách trên, vì vậy trong 953 00:35:27,120 --> 00:35:30,760 trường hợp tìm kiếm tuyến tính tồi tệ nhất là O lớn của n, chúng tôi sẽ nói. 954 00:35:30,760 --> 00:35:33,430 >> Những gì về trường hợp tốt nhất, nếu bạn thực sự may mắn? 955 00:35:33,430 --> 00:35:36,200 Nó chỉ là sẽ đi trước một bước, hoặc một hằng số của các bước. 956 00:35:36,200 --> 00:35:37,830 Vì vậy, chúng tôi sẽ mô tả đó như 1. 957 00:35:37,830 --> 00:35:39,010 Vì vậy, điều này là khá tốt. 958 00:35:39,010 --> 00:35:41,210 Bây giờ những gì nếu chúng tôi làm gì thích tìm kiếm nhị phân? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Vì vậy, tìm kiếm nhị phân, trong điều tồi tệ nhất trường hợp, mất bao nhiêu thời gian? 961 00:35:47,846 --> 00:35:49,250 >> [Interposing GIỌNG NÓI] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. Malan: Vì vậy, trên thực tế, tôi nghe nó trong một vài nơi. 963 00:35:51,310 --> 00:35:56,390 Vì vậy, nó thực sự đăng nhập n, cho hay phải mất, bởi vì như chúng ta phân chia danh sách trong nửa 964 00:35:56,390 --> 00:36:00,730 một lần nữa, và một lần nữa, và một lần nữa, chúng tôi có thể để tìm kiếm, cuối cùng, giá trị, 965 00:36:00,730 --> 00:36:04,750 nếu nó có, nhưng có một nhược điểm. 966 00:36:04,750 --> 00:36:08,590 Giả định rằng chúng ta phải là những gì đưa cho các cấp để tìm kiếm nhị phân? 967 00:36:08,590 --> 00:36:09,700 Nó phải được sắp xếp. 968 00:36:09,700 --> 00:36:12,770 Nó không sắp xếp, bạn có thể chia nhỏ các điều lại lần nữa và một lần nữa, và bạn 969 00:36:12,770 --> 00:36:15,490 có thể đi lại, và bạn có thể đi ngay, và bạn có thể đi bên trái và bên phải, nhưng bạn 970 00:36:15,490 --> 00:36:18,070 sẽ không tìm thấy các yếu tố nếu danh sách không được sắp xếp, bởi vì 971 00:36:18,070 --> 00:36:18,790 bạn có thể bỏ lỡ nó. 972 00:36:18,790 --> 00:36:22,120 Bởi vì theo kinh nghiệm của bạn, cho đi trái hoặc phải sẽ là thiếu sót nếu nó 973 00:36:22,120 --> 00:36:23,420 thực sự không được sắp xếp. 974 00:36:23,420 --> 00:36:26,110 Do đó, có loại một chi phí ẩn để sử dụng một cái gì đó như thế này. 975 00:36:26,110 --> 00:36:29,250 >> Bây giờ, chúng ta hãy đi vào phân loại của chúng tôi các thuật toán tìm kiếm không - 976 00:36:29,250 --> 00:36:31,140 oh, thực sự chúng ta hãy đi vào ô này. 977 00:36:31,140 --> 00:36:33,190 Tìm kiếm nhị phân trong trường hợp tốt nhất? 978 00:36:33,190 --> 00:36:36,290 Nó cũng là 1 nếu nó chỉ xảy ra được ở chính giữa của mảng, hoặc 979 00:36:36,290 --> 00:36:37,810 giữa danh bạ điện thoại. 980 00:36:37,810 --> 00:36:39,710 Bây giờ chúng ta hãy làm bong bóng sắp xếp. 981 00:36:39,710 --> 00:36:42,570 Vì vậy, một lần nữa, bây giờ chúng ta đang bước vào các loại, không phải là tìm kiếm. 982 00:36:42,570 --> 00:36:47,220 >> Trong trường hợp xấu nhất, có bao nhiêu bước đã làm chúng tôi khẳng định bong bóng sắp xếp sẽ mất? 983 00:36:47,220 --> 00:36:48,410 n bình phương. 984 00:36:48,410 --> 00:36:49,200 Vì vậy, tôi sẽ vẽ đó. 985 00:36:49,200 --> 00:36:51,710 Ooh, chữ viết tay của tôi trông còn tệ hơn khi nó dự kiến ​​là lớn. 986 00:36:51,710 --> 00:36:52,510 Được rồi. 987 00:36:52,510 --> 00:36:53,570 Vì vậy, đó là n bình phương. 988 00:36:53,570 --> 00:36:59,460 Và trong trường hợp tốt nhất của bong bóng sắp xếp, bao nhiêu bước là nó sẽ mất? 989 00:36:59,460 --> 00:37:00,980 1, tôi nghe. 990 00:37:00,980 --> 00:37:01,760 >> SPEAKER 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. Malan: n, tôi nghe. 992 00:37:03,286 --> 00:37:04,200 >> SPEAKER 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. Malan: 2, tôi nghe. 994 00:37:05,010 --> 00:37:06,670 Tôi nghe 3? 995 00:37:06,670 --> 00:37:07,080 Được rồi. 996 00:37:07,080 --> 00:37:11,390 Vì vậy, tôi đã nghe 1, n, 2, nhưng chúng ta hãy chọn ngoài ít nhất là đầu tiên của những 997 00:37:11,390 --> 00:37:12,330 đề nghị, 1. 998 00:37:12,330 --> 00:37:15,370 Nó không phải là một bản năng xấu, bởi vì nó loại sau một mô hình ở đây. 999 00:37:15,370 --> 00:37:19,670 Nhưng nếu nó chỉ mất 1 bước, làm thế nào trong thế giới tôi có thể khẳng định rằng danh sách 1000 00:37:19,670 --> 00:37:22,900 được sắp xếp, bởi vì nếu tôi chỉ cho phép để có 1 bước, bao nhiêu yếu tố 1001 00:37:22,900 --> 00:37:25,230 có thể tôi thực sự kiểm tra để chắc chắn? 1002 00:37:25,230 --> 00:37:28,270 Vâng, chỉ cần 1, có nghĩa là có n trừ 1 yếu tố có thể được ra khỏi 1003 00:37:28,270 --> 00:37:31,310 trật tự, và tôi chỉ cần đi trên đức tin sau khi nhìn vào 1 yếu tố mà các 1004 00:37:31,310 --> 00:37:31,850 điều được sắp xếp. 1005 00:37:31,850 --> 00:37:33,930 Vì vậy, 1 không đúng ở đây. 1006 00:37:33,930 --> 00:37:35,710 Vì vậy, tối thiểu, bao nhiêu Tôi phải nhìn vào? 1007 00:37:35,710 --> 00:37:36,680 >> [Interposing GIỌNG NÓI] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. Malan: n trừ đi 1, hoặc thực sự, n, bởi vì tôi cần phải nhìn vào mỗi 1009 00:37:40,160 --> 00:37:42,190 yếu tố để đảm bảo rằng nó không phải là ra lệnh. 1010 00:37:42,190 --> 00:37:44,750 Nhưng một lần nữa, chúng tôi sẽ sắp xếp của làn sóng của chúng tôi tay vào những con số nhỏ hơn và 1011 00:37:44,750 --> 00:37:47,100 cho rằng, như n được lớn, họ không thú nào. 1012 00:37:47,100 --> 00:37:48,380 Vì vậy, đó là bong bóng sắp xếp. 1013 00:37:48,380 --> 00:37:49,830 Và bây giờ, chúng ta hãy làm những hai năm. 1014 00:37:49,830 --> 00:37:53,520 Lựa chọn sắp xếp, và sau đó chúng tôi sẽ làm sắp xếp chèn. 1015 00:37:53,520 --> 00:37:57,160 Và sau đó chúng tôi sẽ thổi của bạn tâm trí với một cái gì đó nhiều 1016 00:37:57,160 --> 00:37:58,926 tốt hơn so với tất cả các. 1017 00:37:58,926 --> 00:38:00,410 Được rồi. 1018 00:38:00,410 --> 00:38:04,700 >> Trường hợp xấu nhất chạy là gì thời gian lựa chọn loại? 1019 00:38:04,700 --> 00:38:05,680 >> SPEAKER 4: n bình phương. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. Malan: n vuông, tôi nghe. 1021 00:38:06,710 --> 00:38:09,790 Nhưng tại sao n bình phương, trực giác? 1022 00:38:09,790 --> 00:38:11,170 >> SPEAKER 4: Bởi vì chúng ta chỉ cần làm điều đó. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. Malan: Bởi vì chúng ta chỉ cần làm điều đó. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Tốt câu trả lời. 1026 00:38:13,380 --> 00:38:16,660 Nhưng trực giác, tại sao lựa chọn loại n bình phương? 1027 00:38:16,660 --> 00:38:18,980 Chúng tôi đã làm những gì phải làm một lần nữa và một lần nữa? 1028 00:38:18,980 --> 00:38:22,570 Chúng tôi phải giữ quét qua, là bạn nhỏ nhất, là bạn 1029 00:38:22,570 --> 00:38:24,020 nhỏ nhất, là bạn nhỏ. 1030 00:38:24,020 --> 00:38:27,480 Và cấp, chúng tôi đã có thể mang n bước, sau đó n trừ đi 1, sau đó n trừ đi 2. 1031 00:38:27,480 --> 00:38:30,700 Nhưng nếu bạn loại thêm những tất cả lên, hoặc mang nó về niềm tin mà tôi đã thêm 1032 00:38:30,700 --> 00:38:34,810 họ lên trước, chúng tôi nhận khoảng n phương trừ một số con số nhỏ hơn. 1033 00:38:34,810 --> 00:38:36,730 Vì vậy, tôi sẽ gọi n này bình phương. 1034 00:38:36,730 --> 00:38:39,530 Nhưng với lựa chọn sắp xếp tốt nhất trường hợp, bao nhiêu bước là nó 1035 00:38:39,530 --> 00:38:40,632 sẽ đưa tôi? 1036 00:38:40,632 --> 00:38:41,840 >> SPEAKER 5: [nghe được] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. Malan: Đó là không may vẫn n bình phương, phải không? 1038 00:38:44,350 --> 00:38:49,590 Bởi vì nếu tôi lựa chọn nhỏ nhất yếu tố, và chúng tôi có bảy người dân ở đây, 1039 00:38:49,590 --> 00:38:53,280 Tôi chỉ biết, một khi tôi nhận được đến rất kết thúc, tôi đã tìm thấy nhỏ nhất 1040 00:38:53,280 --> 00:38:55,670 số, bất cứ nơi nào người cô ấy có thể có được. 1041 00:38:55,670 --> 00:38:58,820 Nhưng làm thế nào để tìm kế tiếp số lượng nhỏ nhất? 1042 00:38:58,820 --> 00:39:00,160 Tôi phải làm vượt qua khác. 1043 00:39:00,160 --> 00:39:04,810 Vì vậy, trong trường hợp tốt nhất, những gì là đầu vào để lựa chọn loại? 1044 00:39:04,810 --> 00:39:07,830 Đây là một danh sách đã được loại, số một, số hai, số ba, số bốn. 1045 00:39:07,830 --> 00:39:08,600 Nhưng tôi là một máy tính. 1046 00:39:08,600 --> 00:39:10,190 Tôi chỉ có thể nhìn vào một điều tại một thời điểm. 1047 00:39:10,190 --> 00:39:12,465 Tôi không thể sắp xếp của một bước trở lại như một con người và nói, 1048 00:39:12,465 --> 00:39:14,030 ooh, điều này có vẻ đúng. 1049 00:39:14,030 --> 00:39:17,580 >> Tôi chỉ có thể xét xử đúng đắn trong lựa chọn loại bằng cách chọn 1050 00:39:17,580 --> 00:39:18,370 số nhỏ nhất. 1051 00:39:18,370 --> 00:39:21,390 Nhưng ngay cả khi tôi tìm thấy một số đầu tiên, nếu tôi không biết bất cứ điều gì khác về 1052 00:39:21,390 --> 00:39:24,460 những con số khác, mà tôi không biết, tất cả tôi biết rằng tôi đã được giao một mảng 1053 00:39:24,460 --> 00:39:27,930 hoặc một bộ cửa đằng sau đó là số, cách duy nhất tôi biết rằng một 1054 00:39:27,930 --> 00:39:28,680 là nhỏ nhất? 1055 00:39:28,680 --> 00:39:32,440 Nếu tôi nhận được tất cả các cách ở đây và nhận ra, chết tiệt, ai thực sự là nhỏ nhất. 1056 00:39:32,440 --> 00:39:34,870 >> Nhưng làm thế nào để sau đó xác định rằng hai là nhỏ nhất tiếp theo? 1057 00:39:34,870 --> 00:39:38,350 Bằng cách làm việc thiếu hiệu quả như nhau một lần nữa và một lần nữa. 1058 00:39:38,350 --> 00:39:42,210 Vì vậy, cuối cùng, với sắp xếp chèn, như thế nào, trong trường hợp xấu nhất, 1059 00:39:42,210 --> 00:39:44,990 chúng ta đã nói nó thực hiện? 1060 00:39:44,990 --> 00:39:49,100 Nó cũng là n bình phương. 1061 00:39:49,100 --> 00:39:53,020 Và làm thế nào về với trường hợp tốt nhất? 1062 00:39:53,020 --> 00:39:56,282 Chúng tôi sẽ rời khỏi đó như một cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Chúng tôi sẽ điền vào đó trống thời gian tới, nhưng trước tiên hãy để tôi đề nghị chúng ta 1064 00:40:00,090 --> 00:40:02,620 về cơ bản làm tốt hơn tất cả các, tất cả phải không? 1065 00:40:02,620 --> 00:40:05,220 >> Vì vậy, suy nghĩ cho mình những gì chèn loại sẽ là. 1066 00:40:05,220 --> 00:40:06,910 Vâng, đó là không phải là rất ấn tượng, bởi vì tôi là người duy nhất 1067 00:40:06,910 --> 00:40:08,970 mà nhìn thấy sự thay đổi. 1068 00:40:08,970 --> 00:40:09,620 Wow. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 Vì vậy, ở đây chúng ta có một phần nào trình diễn khác nhau. 1071 00:40:12,615 --> 00:40:16,580 Nếu tôi phóng to ở đây, bạn sẽ thấy rằng trên bên trái chúng ta có bong bóng sắp xếp, trong 1072 00:40:16,580 --> 00:40:20,740 giữa chúng tôi đã lựa chọn sắp xếp, và trên bên phải, chúng ta có một cái gì đó chúng tôi 1073 00:40:20,740 --> 00:40:23,380 đã không nhìn nhưng được gọi là hợp nhất phân loại. 1074 00:40:23,380 --> 00:40:26,080 Nhưng xem xét những gì chúng tôi đã làm gì ở đây vậy, đến nay ngày hôm nay. 1075 00:40:26,080 --> 00:40:29,200 Khi Jennifer lần đầu tiên đứng trên sân khấu, chúng tôi đã đi qua các mảng của các số 1076 00:40:29,200 --> 00:40:33,750 một lần nữa, và một lần nữa, với tìm kiếm tuyến tính, và chúng tôi có tuyến tính thời gian hoạt động, lớn O 1077 00:40:33,750 --> 00:40:35,100 n, vậy để nói chuyện. 1078 00:40:35,100 --> 00:40:41,000 >> Khi chúng tôi bây giờ xem xét trong tuần đầu tiên của lớp học, khi chúng tôi đã phân chia và chinh phục, 1079 00:40:41,000 --> 00:40:43,740 và chúng tôi đã điện thoại cuốn sách rách, và Jennifer, và chúng tôi chung 1080 00:40:43,740 --> 00:40:47,500 thừa hưởng mà cái nhìn sâu sắc quan trọng, đó là lặp lại chính mình một lần nữa và một lần nữa bằng 1081 00:40:47,500 --> 00:40:50,930 bằng cách nào đó vứt đi, vứt đi, vứt đi, một nửa của vấn đề, hoặc 1082 00:40:50,930 --> 00:40:55,320 nói chung, phân chia một vấn đề trong một nửa, và sau đó xử lý các mảnh nhỏ hơn 1083 00:40:55,320 --> 00:40:59,630 các vấn đề như khái niệm tương đương đến khác, chúng tôi bằng cách nào đó đã làm 1084 00:40:59,630 --> 00:41:00,910 về cơ bản tốt hơn. 1085 00:41:00,910 --> 00:41:04,720 Nhưng với bong bóng sắp xếp, với lựa chọn sắp xếp, với sắp xếp chèn, chúng tôi đã có thể 1086 00:41:04,720 --> 00:41:06,560 không hiểu biết như vậy mà Jennifer đã làm. 1087 00:41:06,560 --> 00:41:10,220 Chúng tôi khá nhiều chỉ đi tới đi ra một bó toàn bộ thời gian, và chúng tôi 1088 00:41:10,220 --> 00:41:12,650 việc tinh chỉnh một chút, trao đổi theo thứ tự này, có thể 1089 00:41:12,650 --> 00:41:13,730 chèn hoặc chọn. 1090 00:41:13,730 --> 00:41:16,950 Nhưng vào cuối ngày, tôi đã làm rất nhiều đi bộ lúng túng lại. 1091 00:41:16,950 --> 00:41:21,160 Chúng tôi đã không thực sự tận dụng một cái gì đó thông minh như Jennifer đã làm như chia 1092 00:41:21,160 --> 00:41:22,040 và chinh phục. 1093 00:41:22,040 --> 00:41:25,620 >> Vì vậy, hợp nhất phân loại, ngược lại, mà chúng tôi sẽ không nhìn thấy cho đến tuần tới, nó sẽ 1094 00:41:25,620 --> 00:41:29,540 để tận dụng ý tưởng quan trọng bằng cách chia đầu vào, và sau đó giảm một nửa, và sau đó 1095 00:41:29,540 --> 00:41:30,580 giảm một nửa, và sau đó giảm một nửa. 1096 00:41:30,580 --> 00:41:34,590 Và trên mỗi lần lặp của vòng lặp, sắp xếp nửa bên trái, và bên phải 1097 00:41:34,590 --> 00:41:38,200 một nửa, sau đó nửa bên trái của nửa bên trái, và nửa bên phải của bên trái, sau đó 1098 00:41:38,200 --> 00:41:40,990 nửa bên trái của nửa bên phải, và nửa bên phải của nửa bên phải. 1099 00:41:40,990 --> 00:41:42,840 Và lặp đi lặp lại một lần nữa và một lần nữa. 1100 00:41:42,840 --> 00:41:46,170 >> Vì vậy, bạn sẽ thấy điều này trực quan, nhưng điều này là những gì chờ đợi chúng ta trong tuần tới. 1101 00:41:46,170 --> 00:41:49,760 Và nói chung, khi chúng ta suy nghĩ một chút chút khó khăn hơn về bất kỳ vấn đề như vậy. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Chúng tôi có n phương trên bên trái, n vuông ở giữa, và n 1104 00:41:57,970 --> 00:41:59,400 đăng nhập n bên phải. 1105 00:41:59,400 --> 00:42:00,590 Do đó, có cliffhanger thực sự của bạn. 1106 00:42:00,590 --> 00:42:02,040 Chúng ta sẽ thấy bạn vào thứ hai. 1107 00:42:02,040 --> 00:42:05,163 >> [Vỗ tay]