1 00:00:00,000 --> 00:00:11,904 >> [MUSIC CHƠI] 2 00:00:11,904 --> 00:00:12,910 >> GIÁO SƯ: Tất cả các quyền. 3 00:00:12,910 --> 00:00:16,730 Đây là CS50 và điều này là cuối tuần ba. 4 00:00:16,730 --> 00:00:20,230 Vì vậy, chúng tôi ở đây ngày hôm nay, không phải trong Sanders Nhà hát, thay vì trong Weidner Library. 5 00:00:20,230 --> 00:00:23,170 Bên trong đó là một phòng thu được gọi là Hauser Studio, 6 00:00:23,170 --> 00:00:28,310 hoặc chúng ta sẽ nói Studio H, hoặc có trách nhiệm chúng tôi say-- nếu bạn rất thích câu nói đùa rằng, 7 00:00:28,310 --> 00:00:30,540 nó thực sự từ bạn cùng lớp, Mark, trực tuyến, 8 00:00:30,540 --> 00:00:32,420 những người đề nghị càng nhiều thông qua Twitter. 9 00:00:32,420 --> 00:00:34,270 Bây giờ những gì là thú vị về được ở đây trong một phòng thu 10 00:00:34,270 --> 00:00:38,410 là tôi đang được bao quanh bởi những màu xanh lá cây bức tường, một màn hình màu xanh lá cây hoặc chromakey, 11 00:00:38,410 --> 00:00:43,290 vậy để nói chuyện, có nghĩa là CS50 của Đội ngũ sản xuất, unbeknownst với tôi 12 00:00:43,290 --> 00:00:47,380 ngay bây giờ, có thể được đặt tôi bất cứ nơi nào nhất trên thế giới, 13 00:00:47,380 --> 00:00:48,660 cho tốt hơn hoặc tồi tệ hơn. 14 00:00:48,660 --> 00:00:51,800 >> Bây giờ những gì nằm phía trước, vấn đề đặt hai là trong tay của bạn trong tuần này, 15 00:00:51,800 --> 00:00:53,830 nhưng với vấn đề đặt ba này trong tuần tới, 16 00:00:53,830 --> 00:00:56,600 bạn sẽ được thử thách với các trò chơi được gọi là 15, 17 00:00:56,600 --> 00:00:58,960 một lợi đảng cũ bạn có thể gọi lại nhận 18 00:00:58,960 --> 00:01:02,030 như một đứa trẻ mà có cả một bó con số đó có thể trượt lên, xuống, 19 00:01:02,030 --> 00:01:05,790 trái và phải, và có một khoảng cách trong câu đố, nơi mà bạn 20 00:01:05,790 --> 00:01:07,840 thực sự có thể trượt những mảnh ghép. 21 00:01:07,840 --> 00:01:11,150 Cuối cùng bạn nhận được điều này lúng túng trong một số lệnh bán ngẫu nhiên, 22 00:01:11,150 --> 00:01:12,940 và mục tiêu là để sắp xếp nó, trên xuống dưới, 23 00:01:12,940 --> 00:01:16,310 trái sang phải, từ một tất cả các con đường lên đến 15. 24 00:01:16,310 --> 00:01:19,360 >> Thật không may, việc thực hiện bạn sẽ có trong tay 25 00:01:19,360 --> 00:01:21,590 là có được phần mềm dựa, không thể chất. 26 00:01:21,590 --> 00:01:25,280 Bạn đang thực sự sẽ phải viết mã với đó là sinh viên hoặc người dùng can 27 00:01:25,280 --> 00:01:26,760 chơi các trò chơi của 15. 28 00:01:26,760 --> 00:01:29,030 Và trên thực tế, trong các hacker phiên bản của trò chơi của 15, 29 00:01:29,030 --> 00:01:32,155 bạn sẽ là một thách thức để thực hiện, không chỉ là sân chơi của trường học cũ này 30 00:01:32,155 --> 00:01:35,010 trò chơi, mà là việc giải quyết của nó, thực hiện chế độ thần, 31 00:01:35,010 --> 00:01:38,280 có thể nói, đó thực sự giải quyết các câu đố cho con người, 32 00:01:38,280 --> 00:01:41,080 bằng cách cung cấp cho họ với các gợi ý, sau khi gợi ý, sau khi gợi ý. 33 00:01:41,080 --> 00:01:42,280 Vì vậy, thêm vào đó vào tuần tới. 34 00:01:42,280 --> 00:01:43,720 Nhưng đó là những gì ở phía trước. 35 00:01:43,720 --> 00:01:47,610 >> Để bây giờ nhớ lại rằng hồi đầu tuần này chúng tôi đã có cliffhanger này, nếu bạn muốn, 36 00:01:47,610 --> 00:01:52,560 nhờ đó mà tốt nhất chúng tôi đã làm phân loại khôn ngoan là một giới hạn trên của o lớn của n 37 00:01:52,560 --> 00:01:53,210 bình phương. 38 00:01:53,210 --> 00:01:56,520 Nói cách khác, bong bóng sắp xếp, sắp xếp chọn, sắp xếp chèn, 39 00:01:56,520 --> 00:01:59,120 tất cả trong số họ, trong khi khác nhau trong việc thực hiện của họ, 40 00:01:59,120 --> 00:02:03,480 thoái hóa thành một n bình chạy thời gian trong trường hợp xấu nhất. 41 00:02:03,480 --> 00:02:06,010 Và chúng ta thường cho rằng trường hợp rất tồi tệ nhất để phân loại 42 00:02:06,010 --> 00:02:08,814 là một trong những yếu tố đầu vào của bạn là hoàn toàn ngược lại. 43 00:02:08,814 --> 00:02:11,980 Và quả thực, nó mất khá một vài bước để thực hiện mỗi người trong những thuật toán. 44 00:02:11,980 --> 00:02:15,110 >> Bây giờ, ở cuối của lớp thu hồi, chúng tôi so sánh bong bóng sắp xếp 45 00:02:15,110 --> 00:02:19,390 chống lựa chọn loại chống lại một khác mà chúng ta gọi là sắp xếp hợp nhất vào thời điểm đó, 46 00:02:19,390 --> 00:02:22,120 và tôi đề xuất rằng nó lấy lợi thế của một bài học từ tuần 47 00:02:22,120 --> 00:02:24,060 bằng không, phân chia và chinh phục. 48 00:02:24,060 --> 00:02:28,810 Và bằng cách nào đó đạt được một số loại logarit chạy lần cuối cùng, 49 00:02:28,810 --> 00:02:31,024 thay vì một cái gì đó mà hoàn toàn là bậc hai. 50 00:02:31,024 --> 00:02:33,440 Và nó không hoàn toàn logarit, nó là nhiều hơn một chút so với điều đó. 51 00:02:33,440 --> 00:02:36,520 Nhưng nếu bạn gọi lại từ trường, nó đã được nhiều hơn, nhanh hơn nhiều. 52 00:02:36,520 --> 00:02:38,210 Chúng ta hãy nhìn vào nơi chúng tôi rời đi. 53 00:02:38,210 --> 00:02:41,880 54 00:02:41,880 --> 00:02:45,370 >> Bubble sort so với lựa chọn loại so với sắp xếp hợp nhất. 55 00:02:45,370 --> 00:02:47,700 Bây giờ tất cả chúng đang chạy, trong Về lý thuyết, cùng một lúc. 56 00:02:47,700 --> 00:02:50,510 Các CPU đang chạy ở tốc độ như nhau. 57 00:02:50,510 --> 00:02:54,990 Nhưng bạn có thể cảm thấy như thế nào nhàm chán này rất nhanh chóng sẽ trở thành, 58 00:02:54,990 --> 00:02:58,790 và chỉ cần nhanh như thế nào, khi chúng ta tiêm một chút về thuật toán tuần số không, 59 00:02:58,790 --> 00:03:00,080 chúng ta có thể đẩy nhanh tốc độ. 60 00:03:00,080 --> 00:03:01,630 >> Vì vậy, loại nhãn trông tuyệt vời. 61 00:03:01,630 --> 00:03:05,220 Làm thế nào chúng ta có thể tận dụng nó, để để sắp xếp các số một cách nhanh chóng hơn. 62 00:03:05,220 --> 00:03:07,140 Vâng chúng ta hãy nghĩ lại để một thành phần mà chúng ta 63 00:03:07,140 --> 00:03:10,380 đã trở lại trong tuần không, mà của tìm kiếm một người nào đó trong một cuốn sách điện thoại, 64 00:03:10,380 --> 00:03:12,380 và nhớ lại rằng giả mà chúng tôi đề xuất, 65 00:03:12,380 --> 00:03:14,560 thông qua đó chúng ta có thể tìm thấy một người như Mike Smith, 66 00:03:14,560 --> 00:03:16,310 nhìn một chút gì đó như thế này. 67 00:03:16,310 --> 00:03:20,820 >> Bây giờ có một cái nhìn đặc biệt ở dòng 7 và 8, và 10 và 11, 68 00:03:20,820 --> 00:03:25,240 mà gây ra vòng lặp đó, nhờ đó chúng ta giữ đi lại cho dòng 3 một lần nữa, và một lần nữa, 69 00:03:25,240 --> 00:03:26,520 Và một lần nữa. 70 00:03:26,520 --> 00:03:31,790 Nhưng nó chỉ ra rằng chúng ta có thể xem thuật toán này, ở đây trong giả, 71 00:03:31,790 --> 00:03:33,620 một chút một cách toàn diện hơn. 72 00:03:33,620 --> 00:03:35,960 Trong thực tế, những gì tôi đang tìm kiếm ở đây trên màn hình, 73 00:03:35,960 --> 00:03:41,180 là một thuật toán để tìm kiếm Mike Smith trong một số bộ trang. 74 00:03:41,180 --> 00:03:45,520 Và quả thực, chúng ta có thể đơn giản hóa này thuật toán trong những dòng 7 và 8, 75 00:03:45,520 --> 00:03:49,860 và 10 và 11 để chỉ nói điều này, mà tôi đã trình bày ở đây trong màu vàng. 76 00:03:49,860 --> 00:03:52,210 Nói cách khác, nếu Mike Smith là trước đó trong cuốn sách, 77 00:03:52,210 --> 00:03:55,004 chúng ta không cần phải xác định bước bước giờ làm thế nào để đi tìm anh ta. 78 00:03:55,004 --> 00:03:56,920 Chúng tôi không có chỉ định để quay lại dòng 3, 79 00:03:56,920 --> 00:03:58,960 tại sao chúng ta không chỉ thay vào đó, nói rằng, nói chung, 80 00:03:58,960 --> 00:04:01,500 tìm kiếm cho Mike trong nửa bên trái của cuốn sách. 81 00:04:01,500 --> 00:04:03,960 >> Ngược lại, nếu Mike là thực sự sau này trong các cuốn sách, 82 00:04:03,960 --> 00:04:07,540 tại sao chúng ta không chỉ trích dẫn tìm kiếm unquote cho Mike ở nửa bên phải của cuốn sách. 83 00:04:07,540 --> 00:04:11,030 Nói cách khác, tại sao chúng ta không chỉ loại đá trái banh để mình nói, 84 00:04:11,030 --> 00:04:13,130 tìm kiếm cho Mike ở đây tập hợp con của cuốn sách, 85 00:04:13,130 --> 00:04:16,279 và để nó tồn tại của chúng tôi thuật toán để cho chúng tôi 86 00:04:16,279 --> 00:04:18,750 làm thế nào để tìm kiếm cho Mike ở rằng một nửa bên trái của cuốn sách. 87 00:04:18,750 --> 00:04:20,750 Nói cách khác, chúng tôi thuật toán hoạt động cho dù nó 88 00:04:20,750 --> 00:04:24,670 một cuốn sách điện thoại của độ dày này, điều này độ dày, hoặc bất kỳ độ dày nào. 89 00:04:24,670 --> 00:04:27,826 Vì vậy, chúng ta có thể đệ quy xác định thuật toán này. 90 00:04:27,826 --> 00:04:29,950 Nói cách khác, trên màn hình ở đây, là một thuật toán 91 00:04:29,950 --> 00:04:33,130 để tìm kiếm cho Mike Smith trong số các trang của một cuốn sách điện thoại. 92 00:04:33,130 --> 00:04:37,410 Vì vậy, trong dòng 7 và 10, chúng ta hãy chỉ cần nói chính xác điều đó. 93 00:04:37,410 --> 00:04:40,250 Và tôi sử dụng thuật ngữ này một thời điểm trước đây, và quả thật, đệ quy 94 00:04:40,250 --> 00:04:42,450 là từ thông dụng hiện nay, và đó là quá trình này 95 00:04:42,450 --> 00:04:47,210 làm điều gì đó mang tính chu kỳ bằng cách nào đó sử dụng mã mà bạn đã có, 96 00:04:47,210 --> 00:04:49,722 và gọi đó là một lần nữa, và một lần nữa, và một lần nữa. 97 00:04:49,722 --> 00:04:51,930 Bây giờ nó sẽ là quan trọng rằng chúng tôi bằng cách nào đó dưới 98 00:04:51,930 --> 00:04:53,821 ra, và không làm điều đó vô cùng dài. 99 00:04:53,821 --> 00:04:56,070 Nếu không chúng ta sẽ có thực sự là một vòng lặp vô hạn. 100 00:04:56,070 --> 00:04:59,810 Nhưng chúng ta hãy xem liệu chúng ta có thể mượn ý tưởng này của một đệ quy, làm cái gì nữa 101 00:04:59,810 --> 00:05:03,600 và một lần nữa và một lần nữa, để giải quyết vấn đề phân loại thông qua hợp nhất 102 00:05:03,600 --> 00:05:05,900 sắp xếp, hiệu quả tất cả các chi tiết. 103 00:05:05,900 --> 00:05:06,970 >> Vì vậy, tôi cung cấp cho bạn hợp nhất phân loại. 104 00:05:06,970 --> 00:05:07,920 Hãy nhìn xem. 105 00:05:07,920 --> 00:05:10,850 Vì vậy, đây là giả, với mà chúng tôi có thể thực hiện phân loại, 106 00:05:10,850 --> 00:05:12,640 sử dụng thuật toán này được gọi là sắp xếp hợp nhất. 107 00:05:12,640 --> 00:05:13,880 Và nó khá đơn giản này. 108 00:05:13,880 --> 00:05:15,940 Trên đầu vào của n phần tử, nói cách khác, nếu bạn 109 00:05:15,940 --> 00:05:18,830 cho n phần tử và các con số và chữ hoặc bất cứ điều gì các đầu vào là, 110 00:05:18,830 --> 00:05:22,430 nếu bạn đang đưa ra các yếu tố n, nếu n là nhỏ hơn 2, chỉ cần trả lại. 111 00:05:22,430 --> 00:05:22,930 Phải không? 112 00:05:22,930 --> 00:05:26,430 Bởi vì nếu n là nhỏ hơn 2, mà có nghĩa là danh sách các yếu tố 113 00:05:26,430 --> 00:05:30,446 là một trong hai kích thước 0 hoặc 1, và trong cả hai trường hợp tầm thường, 114 00:05:30,446 --> 00:05:31,570 danh sách đã được sắp xếp. 115 00:05:31,570 --> 00:05:32,810 Nếu không có danh sách, nó được sắp xếp. 116 00:05:32,810 --> 00:05:35,185 Và nếu có một danh sách dài 1, nó rõ ràng là sắp xếp. 117 00:05:35,185 --> 00:05:38,280 Vì vậy, các thuật toán chỉ cần thực sự làm điều gì đó thú vị, 118 00:05:38,280 --> 00:05:40,870 nếu chúng ta có hai hoặc nhiều hơn các yếu tố ban cho chúng ta. 119 00:05:40,870 --> 00:05:42,440 Vì vậy, chúng ta hãy nhìn vào sự kỳ diệu đó. 120 00:05:42,440 --> 00:05:47,500 Khác sắp xếp một nửa trái của các yếu tố, sau đó sắp xếp một nửa bên phải của các yếu tố, 121 00:05:47,500 --> 00:05:49,640 sau đó hợp nhất hai nửa được sắp xếp. 122 00:05:49,640 --> 00:05:52,440 Và loại tâm uốn là gì ở đây, là tôi không thực sự 123 00:05:52,440 --> 00:05:56,190 dường như đã nói với bạn bất cứ điều gì chỉ được nêu ra, phải không? 124 00:05:56,190 --> 00:05:59,560 Tất cả tôi đã nói được, đưa ra một danh sách các n phần tử, sắp xếp lại một nửa, 125 00:05:59,560 --> 00:06:01,800 sau đó nửa bên phải, sau đó hợp nhất hai nửa sắp xếp, 126 00:06:01,800 --> 00:06:03,840 nhưng mà là nước sốt bí mật thực tế? 127 00:06:03,840 --> 00:06:05,260 Trường hợp là thuật toán? 128 00:06:05,260 --> 00:06:09,150 Vâng nó chỉ ra rằng những người hai dòng đầu tiên, một nửa loại bỏ các yếu tố, 129 00:06:09,150 --> 00:06:13,970 và sắp xếp đúng một nửa của các yếu tố, những cuộc gọi đệ quy, do đó, để nói chuyện. 130 00:06:13,970 --> 00:06:16,120 >> Sau khi tất cả, lúc này điểm trong thời gian, tôi có 131 00:06:16,120 --> 00:06:18,950 một thuật toán nào đó để sắp xếp một bó toàn bộ các yếu tố? 132 00:06:18,950 --> 00:06:19,450 Vâng. 133 00:06:19,450 --> 00:06:20,620 Nó ở ngay đây. 134 00:06:20,620 --> 00:06:25,180 Nó ở ngay trên màn hình, và vì vậy tôi có thể sử dụng cùng một tập hợp các bước 135 00:06:25,180 --> 00:06:28,500 để sắp xếp một nửa trái, như tôi có thể nửa bên phải. 136 00:06:28,500 --> 00:06:30,420 Và quả thực, một lần nữa, và một lần nữa. 137 00:06:30,420 --> 00:06:34,210 Vì vậy, bằng cách này hay khác, và chúng tôi sẽ sớm thấy điều này, sự kỳ diệu của sắp xếp hợp nhất 138 00:06:34,210 --> 00:06:37,967 được nhúng vào trong đó rất thức dòng, việc sáp nhập hai nửa được sắp xếp. 139 00:06:37,967 --> 00:06:39,300 Và điều đó có vẻ khá trực quan. 140 00:06:39,300 --> 00:06:41,050 Bạn lấy hai nửa, và bạn, bằng cách nào đó, kết hợp chúng lại với nhau, 141 00:06:41,050 --> 00:06:43,260 và chúng ta sẽ thấy điều này cụ thể trong một khoảnh khắc. 142 00:06:43,260 --> 00:06:45,080 >> Nhưng đây là một thuật toán hoàn chỉnh. 143 00:06:45,080 --> 00:06:46,640 Và chúng ta hãy xem chính xác lý do tại sao. 144 00:06:46,640 --> 00:06:50,912 Cũng giả sử rằng chúng ta đang đưa ra những giống tám yếu tố ở đây trên màn hình, một 145 00:06:50,912 --> 00:06:53,120 thông qua tám, nhưng chúng nhằm dường như ngẫu nhiên. 146 00:06:53,120 --> 00:06:55,320 Và mục tiêu trước mắt là để sắp xếp các yếu tố này. 147 00:06:55,320 --> 00:06:58,280 Vâng làm thế nào tôi có thể đi về làm việc đó bằng cách sử dụng, một lần nữa, 148 00:06:58,280 --> 00:07:00,407 hợp nhất phân loại, theo giả này? 149 00:07:00,407 --> 00:07:02,740 Và một lần nữa, làm biến đổi màu sắc này trong tâm trí của bạn, chỉ trong một khoảnh khắc. 150 00:07:02,740 --> 00:07:05,270 Trường hợp đầu tiên là khá tầm thường, nếu nó nhỏ hơn 2, 151 00:07:05,270 --> 00:07:07,060 chỉ cần trả lại, không có việc phải làm. 152 00:07:07,060 --> 00:07:09,290 Vì vậy, thực sự đó chỉ là ba các bước để thực sự giữ trong tâm trí. 153 00:07:09,290 --> 00:07:11,081 Một lần nữa, và một lần nữa, tôi sẽ muốn có 154 00:07:11,081 --> 00:07:13,980 để sắp xếp một nửa trái, sắp xếp một nửa bên phải, 155 00:07:13,980 --> 00:07:15,890 và sau đó một lần họ hai nửa đều được sắp xếp, 156 00:07:15,890 --> 00:07:18,710 Tôi muốn kết hợp chúng lại với nhau vào một danh sách được sắp xếp. 157 00:07:18,710 --> 00:07:19,940 Vì vậy, giữ cho rằng trong tâm trí. 158 00:07:19,940 --> 00:07:21,310 >> Vì vậy, đây là danh sách ban đầu. 159 00:07:21,310 --> 00:07:23,510 Hãy coi đây là một mảng, như chúng ta bắt đầu 160 00:07:23,510 --> 00:07:25,800 trong tuần thứ hai, đó là một khối liên tục của bộ nhớ. 161 00:07:25,800 --> 00:07:28,480 Trong trường hợp này, có chứa tám số, trở lại trở lại để trở lại. 162 00:07:28,480 --> 00:07:30,700 Và bây giờ chúng ta áp dụng sắp xếp hợp nhất. 163 00:07:30,700 --> 00:07:33,300 Vì vậy, lần đầu tiên tôi muốn sắp xếp nửa bên trái của danh sách này, 164 00:07:33,300 --> 00:07:37,370 và chúng ta, do đó, tập trung vào 4, 8, 6, và 2. 165 00:07:37,370 --> 00:07:41,000 >> Bây giờ làm thế nào để tôi đi về sắp xếp một danh sách các kích thước 4? 166 00:07:41,000 --> 00:07:45,990 Vâng tôi phải bây giờ xem xét sắp xếp bên trái của một nửa trái. 167 00:07:45,990 --> 00:07:47,720 Một lần nữa, chúng ta hãy quay lại với chỉ một khoảnh khắc. 168 00:07:47,720 --> 00:07:51,010 Nếu giả là điều này, và tôi cho tám yếu tố, 169 00:07:51,010 --> 00:07:53,230 8 rõ ràng là lớn hơn hơn hoặc bằng 2. 170 00:07:53,230 --> 00:07:54,980 Vì vậy, với những trường hợp đầu tiên không áp dụng. 171 00:07:54,980 --> 00:07:58,120 Vì vậy, để sắp xếp tám yếu tố, tôi lần đầu tiên sắp xếp một nửa trái của các yếu tố, 172 00:07:58,120 --> 00:08:01,930 sau đó tôi sắp xếp một nửa bên phải, sau đó tôi hợp nhất hai nửa được sắp xếp, mỗi kích thước 4. 173 00:08:01,930 --> 00:08:02,470 ĐƯỢC. 174 00:08:02,470 --> 00:08:07,480 >> Nhưng nếu bạn vừa nói với tôi, sắp xếp các nửa bên trái, mà bây giờ có kích thước 4, 175 00:08:07,480 --> 00:08:09,350 làm thế nào để sắp xếp các nửa còn lại? 176 00:08:09,350 --> 00:08:11,430 Vâng, nếu tôi có một đầu vào của bốn yếu tố, 177 00:08:11,430 --> 00:08:14,590 Lần đầu tiên tôi sắp xếp bên trái hai, sau đó quyền hai, 178 00:08:14,590 --> 00:08:16,210 và sau đó tôi kết hợp chúng lại với nhau. 179 00:08:16,210 --> 00:08:18,700 Vì vậy, một lần nữa, nó sẽ trở thành một chút của một tâm uốn trò chơi ở đây, 180 00:08:18,700 --> 00:08:21,450 bởi vì bạn, loại, phải nhớ bạn đang ở đâu trong câu chuyện, 181 00:08:21,450 --> 00:08:23,620 nhưng vào cuối ngày, đưa ra bất kỳ số lượng các yếu tố, 182 00:08:23,620 --> 00:08:25,620 đầu tiên bạn muốn sắp xếp nửa bên trái, sau đó nửa bên phải, 183 00:08:25,620 --> 00:08:26,661 sau đó kết hợp chúng lại với nhau. 184 00:08:26,661 --> 00:08:28,630 Hãy bắt đầu làm chính xác điều đó. 185 00:08:28,630 --> 00:08:30,170 Dưới đây là các đầu vào của tám yếu tố. 186 00:08:30,170 --> 00:08:31,910 Bây giờ chúng tôi đang tìm kiếm một nửa trái ở đây. 187 00:08:31,910 --> 00:08:33,720 Làm thế nào để sắp xếp bốn yếu tố? 188 00:08:33,720 --> 00:08:35,610 Cũng lần đầu tiên tôi sắp xếp một nửa còn lại. 189 00:08:35,610 --> 00:08:37,720 Bây giờ làm thế nào để sắp xếp các nửa còn lại? 190 00:08:37,720 --> 00:08:39,419 Vâng tôi đã được trao hai yếu tố. 191 00:08:39,419 --> 00:08:41,240 Vì vậy, hãy sắp xếp hai yếu tố này. 192 00:08:41,240 --> 00:08:44,540 2 là lớn hơn hoặc bằng 2, tất nhiên. 193 00:08:44,540 --> 00:08:46,170 Vì vậy, trường hợp đầu tiên mà không áp dụng. 194 00:08:46,170 --> 00:08:49,010 >> Vì vậy, bây giờ tôi phải sắp xếp bên trái một nửa của hai yếu tố này. 195 00:08:49,010 --> 00:08:50,870 Nửa bên trái, tất nhiên, chỉ 4 là. 196 00:08:50,870 --> 00:08:54,020 Vậy làm thế nào để sắp xếp một danh sách của một phần tử? 197 00:08:54,020 --> 00:08:57,960 Vâng bây giờ, mà trường hợp cơ sở đặc biệt lên hàng đầu, do đó, để nói chuyện, được áp dụng. 198 00:08:57,960 --> 00:09:01,470 1 là ít hơn 2, và tôi danh sách thực sự có kích thước 1 là. 199 00:09:01,470 --> 00:09:02,747 Vì vậy, tôi chỉ trả lại. 200 00:09:02,747 --> 00:09:03,580 Tôi không làm bất cứ điều gì. 201 00:09:03,580 --> 00:09:06,770 Và quả thực, nhìn vào những gì tôi đã thực hiện, 4 đã được sắp xếp. 202 00:09:06,770 --> 00:09:09,220 Giống như tôi đã phần nào thành công ở đây. 203 00:09:09,220 --> 00:09:11,750 >> Bây giờ có vẻ ngu ngốc yêu cầu bồi thường, nhưng đó là sự thật. 204 00:09:11,750 --> 00:09:13,700 4 là một danh sách có kích thước 1. 205 00:09:13,700 --> 00:09:15,090 Nó đã được sắp xếp. 206 00:09:15,090 --> 00:09:16,270 Đó là một nửa trái. 207 00:09:16,270 --> 00:09:18,010 Bây giờ tôi sắp xếp một nửa bên phải. 208 00:09:18,010 --> 00:09:22,310 Đầu vào của tôi là một yếu tố, 8 tương tự, đã được sắp xếp. 209 00:09:22,310 --> 00:09:25,170 Ngu ngốc, quá, nhưng một lần nữa, nguyên tắc cơ bản này 210 00:09:25,170 --> 00:09:28,310 sẽ cho phép chúng ta bây giờ xây dựng trên đầu trang này thành công. 211 00:09:28,310 --> 00:09:32,260 4 sắp xếp, 8 được sắp xếp, bây giờ bước cuối cùng là gì? 212 00:09:32,260 --> 00:09:35,330 Vì vậy, bước thứ ba và cuối cùng, bất kỳ Hiện bạn đang sắp xếp một danh sách, thu hồi, 213 00:09:35,330 --> 00:09:38,310 là để hợp nhất hai nửa, bên trái và bên phải. 214 00:09:38,310 --> 00:09:39,900 Vì vậy, chúng ta hãy làm chính xác điều đó. 215 00:09:39,900 --> 00:09:41,940 Nửa bên trái của tôi là, tất nhiên, 4. 216 00:09:41,940 --> 00:09:43,310 Nửa bên phải của tôi là 8. 217 00:09:43,310 --> 00:09:44,100 >> Vì vậy, hãy làm điều này. 218 00:09:44,100 --> 00:09:46,410 Đầu tiên tôi sẽ phân bổ một số bộ nhớ bổ sung, 219 00:09:46,410 --> 00:09:48,680 rằng tôi sẽ đại diện ở đây, như chỉ là một mảng thứ cấp, 220 00:09:48,680 --> 00:09:49,660 đó là đủ lớn để phù hợp này. 221 00:09:49,660 --> 00:09:52,243 Nhưng bạn có thể tưởng tượng được mở rộng rằng hình chữ nhật toàn bộ chiều dài, 222 00:09:52,243 --> 00:09:53,290 nếu chúng ta cần nhiều hơn sau này. 223 00:09:53,290 --> 00:09:58,440 Làm thế nào để tôi mất 4 và 8, và hợp nhất hai danh sách có kích thước 1 với nhau? 224 00:09:58,440 --> 00:10:00,270 Cũng ở đây, khá đơn giản. 225 00:10:00,270 --> 00:10:03,300 4 đến trước, sau đó đến 8. 226 00:10:03,300 --> 00:10:07,130 Bởi vì nếu tôi muốn sắp xếp nửa bên trái, sau đó nửa bên phải, 227 00:10:07,130 --> 00:10:09,900 và sau đó hợp nhất hai nửa với nhau, trong thứ tự sắp xếp, 228 00:10:09,900 --> 00:10:11,940 4 đến trước, sau đó đến 8. 229 00:10:11,940 --> 00:10:15,810 >> Vì vậy, chúng tôi dường như có tiến bộ, thậm chí mặc dù tôi đã không thực hiện bất kỳ công việc thực tế. 230 00:10:15,810 --> 00:10:17,800 Nhưng hãy nhớ rằng chúng ta ở đâu trong câu chuyện. 231 00:10:17,800 --> 00:10:19,360 Chúng tôi ban đầu mất tám yếu tố. 232 00:10:19,360 --> 00:10:21,480 Chúng tôi sắp xếp một nửa trái, đó là 4. 233 00:10:21,480 --> 00:10:24,450 Sau đó, chúng tôi sắp xếp một nửa trái của một nửa trái, đó là 2. 234 00:10:24,450 --> 00:10:25,270 Và ở đây chúng tôi đi. 235 00:10:25,270 --> 00:10:26,920 Chúng tôi đang thực hiện với bước đó. 236 00:10:26,920 --> 00:10:29,930 >> Vì vậy, nếu chúng ta đã sắp xếp các còn lại một nửa số 2, bây giờ chúng tôi 237 00:10:29,930 --> 00:10:32,130 phải sắp xếp một nửa bên phải của 2. 238 00:10:32,130 --> 00:10:35,710 Vì vậy, nửa bên phải của 2 hai giá trị ở đây, 6 và 2. 239 00:10:35,710 --> 00:10:40,620 Vì vậy, bây giờ chúng ta có một đầu vào kích thước 2, và sắp xếp lại một nửa, và sau đó 240 00:10:40,620 --> 00:10:42,610 nửa bên phải, và sau đó kết hợp chúng lại với nhau. 241 00:10:42,610 --> 00:10:45,722 Vâng làm thế nào để sắp xếp một danh sách các kích thước 1, có chứa chỉ số 6? 242 00:10:45,722 --> 00:10:46,430 Tôi đã thực hiện. 243 00:10:46,430 --> 00:10:48,680 Danh sách đó có kích thước 1 được sắp xếp. 244 00:10:48,680 --> 00:10:52,140 >> Làm thế nào để sắp xếp một danh sách kích thước 1, cái gọi là một nửa bên phải. 245 00:10:52,140 --> 00:10:54,690 Vâng nó cũng đã được sắp xếp. 246 00:10:54,690 --> 00:10:56,190 Số 2 là một mình. 247 00:10:56,190 --> 00:11:00,160 Vì vậy, bây giờ tôi có hai nửa, bên trái và Đúng vậy, tôi cần phải hợp nhất chúng lại với nhau. 248 00:11:00,160 --> 00:11:01,800 Hãy để tôi cung cấp cho bản thân mình một số không gian thêm. 249 00:11:01,800 --> 00:11:05,580 Và đặt 2 trong đó, sau đó 6 trong đó, do đó 250 00:11:05,580 --> 00:11:10,740 phân loại danh sách đó, trái và phải, và sáp nhập nó với nhau, cuối cùng. 251 00:11:10,740 --> 00:11:12,160 Vì vậy, tôi đang ở trong hình dạng tốt hơn một chút. 252 00:11:12,160 --> 00:11:16,250 Tôi làm không phải, bởi vì rõ ràng 4, 8, 2, 6 không phải là sự sắp đặt cuối cùng mà tôi muốn. 253 00:11:16,250 --> 00:11:20,640 Nhưng bây giờ tôi có hai danh sách kích thước 2, mà có cả hai, tương ứng, được sắp xếp. 254 00:11:20,640 --> 00:11:24,580 Vì vậy, bây giờ nếu bạn tua lại trong tâm trí của bạn mắt, đâu đó lại cho chúng tôi? 255 00:11:24,580 --> 00:11:28,520 Tôi bắt đầu với tám yếu tố, sau đó tôi đẽo nó xuống một nửa trái của 4, 256 00:11:28,520 --> 00:11:31,386 sau đó nửa bên trái là 2, và sau đó nửa bên phải của 2, 257 00:11:31,386 --> 00:11:34,510 Tôi đã hoàn thành, do đó, phân loại trái một nửa số 2, và nửa bên phải của 2, 258 00:11:34,510 --> 00:11:37,800 do đó, bước thứ ba và cuối cùng là những gì ở đây? 259 00:11:37,800 --> 00:11:41,290 Tôi phải kết hợp với nhau hai danh sách kích thước 2. 260 00:11:41,290 --> 00:11:42,040 Vì vậy, chúng ta hãy đi trước. 261 00:11:42,040 --> 00:11:43,940 Và trên màn hình ở đây, cung cấp cho tôi một số bộ nhớ bổ sung, 262 00:11:43,940 --> 00:11:47,170 mặc dù về mặt kỹ thuật, nhận thấy rằng tôi đã có một bó toàn bộ các không gian trống lên đầu 263 00:11:47,170 --> 00:11:47,670 có. 264 00:11:47,670 --> 00:11:50,044 Nếu tôi muốn đặc biệt không gian hiệu quả khôn ngoan, 265 00:11:50,044 --> 00:11:52,960 Tôi chỉ có thể bắt đầu di chuyển các yếu tố qua lại, trên và dưới. 266 00:11:52,960 --> 00:11:55,460 Nhưng chỉ cho hình ảnh rõ nét, Tôi sẽ đặt nó xuống bên dưới, 267 00:11:55,460 --> 00:11:56,800 để giữ cho mọi thứ tốt đẹp và sạch sẽ. 268 00:11:56,800 --> 00:11:58,150 >> Vì vậy, tôi đã có hai danh sách kích thước 2. 269 00:11:58,150 --> 00:11:59,770 Danh sách đầu tiên có 4 và 8. 270 00:11:59,770 --> 00:12:01,500 Danh sách thứ hai có 2 và 6. 271 00:12:01,500 --> 00:12:03,950 Hãy kết hợp những cùng trong thứ tự sắp xếp. 272 00:12:03,950 --> 00:12:09,910 2, tất nhiên, đến trước, sau đó 4, sau đó 6, sau đó 8. 273 00:12:09,910 --> 00:12:12,560 Và bây giờ chúng ta dường như nhận được một nơi nào đó thú vị. 274 00:12:12,560 --> 00:12:15,720 Nửa bây giờ tôi đã sắp xếp của liệt, và tình cờ, đó là 275 00:12:15,720 --> 00:12:18,650 tất cả các số chẵn, nhưng đó là, thực sự, chỉ là một sự trùng hợp. 276 00:12:18,650 --> 00:12:22,220 Và bây giờ tôi đã sắp xếp bên trái một nửa, vì vậy mà nó là 2, 4, 6, và 8. 277 00:12:22,220 --> 00:12:23,430 Không có gì là không theo thứ tự. 278 00:12:23,430 --> 00:12:24,620 Mà cảm thấy như tiến độ. 279 00:12:24,620 --> 00:12:26,650 >> Bây giờ nó cảm thấy như tôi đã được nói chuyện mãi mãi bây giờ, 280 00:12:26,650 --> 00:12:29,850 vì vậy những gì vẫn còn để được nhìn thấy nếu điều này Thuật toán là, thực sự, hiệu quả hơn. 281 00:12:29,850 --> 00:12:31,766 Nhưng chúng ta đang trải qua nó siêu có phương pháp. 282 00:12:31,766 --> 00:12:34,060 Một máy tính, tất nhiên, sẽ làm điều đó như thế. 283 00:12:34,060 --> 00:12:34,840 Vì vậy, nơi là chúng tôi? 284 00:12:34,840 --> 00:12:36,180 Chúng tôi bắt đầu với tám yếu tố. 285 00:12:36,180 --> 00:12:37,840 Tôi sắp xếp một nửa trái của 4. 286 00:12:37,840 --> 00:12:39,290 Tôi dường như được thực hiện với điều đó. 287 00:12:39,290 --> 00:12:42,535 Vì vậy, bây giờ các bước tiếp theo là sắp xếp một nửa bên phải của 4. 288 00:12:42,535 --> 00:12:44,410 Và phần này chúng ta có thể đi thông qua nhiều hơn một chút 289 00:12:44,410 --> 00:12:47,140 nhanh chóng, mặc dù bạn chào đón để tua lại hoặc tạm dừng, chỉ 290 00:12:47,140 --> 00:12:49,910 nghĩ qua nó ở tốc độ của riêng của bạn, nhưng những gì 291 00:12:49,910 --> 00:12:53,290 chúng tôi có bây giờ là một cơ hội để làm các thuật toán chính xác cùng trên bốn 292 00:12:53,290 --> 00:12:54,380 số khác nhau. 293 00:12:54,380 --> 00:12:57,740 >> Vì vậy, chúng ta hãy đi trước, và tập trung vào nửa bên phải, mà chúng tôi đang ở đây. 294 00:12:57,740 --> 00:13:01,260 Nửa trái mà nửa bên phải, và bây giờ 295 00:13:01,260 --> 00:13:04,560 nửa bên trái của trái một nửa số đó một nửa bên phải, 296 00:13:04,560 --> 00:13:08,030 và làm thế nào để sắp xếp một danh sách các kích thước 1 chỉ chứa các số 1? 297 00:13:08,030 --> 00:13:09,030 Nó đã được thực hiện. 298 00:13:09,030 --> 00:13:11,830 Làm thế nào để tôi làm điều tương tự cho một danh sách có kích thước 1 chỉ chứa 7? 299 00:13:11,830 --> 00:13:12,840 Nó đã được thực hiện. 300 00:13:12,840 --> 00:13:16,790 Bước thứ ba hiệp này sau đó được kết hợp hai yếu tố này 301 00:13:16,790 --> 00:13:20,889 vào một danh sách mới có kích thước 2, 1 và 7. 302 00:13:20,889 --> 00:13:23,180 Không có vẻ đã làm tất cả công việc thú vị mà nhiều. 303 00:13:23,180 --> 00:13:24,346 Hãy xem những gì sẽ xảy ra tiếp theo. 304 00:13:24,346 --> 00:13:29,210 Tôi chỉ cần sắp xếp một nửa bên trái của nửa bên phải của đầu vào ban đầu của tôi. 305 00:13:29,210 --> 00:13:32,360 Bây giờ chúng ta hãy sắp xếp đúng các một nửa, trong đó có 5 và 3. 306 00:13:32,360 --> 00:13:35,740 Chúng ta hãy nhìn lại bên trái một nửa, sắp xếp, nửa bên phải, sắp xếp, 307 00:13:35,740 --> 00:13:39,120 và kết hợp hai với nhau, vào một số không gian bổ sung, 308 00:13:39,120 --> 00:13:41,670 3 đến trước, sau đó đến 5. 309 00:13:41,670 --> 00:13:46,190 Và vì vậy bây giờ, chúng tôi đã sắp xếp các nửa bên trái của nửa bên phải 310 00:13:46,190 --> 00:13:49,420 của vấn đề ban đầu, và nửa bên phải của nửa bên phải 311 00:13:49,420 --> 00:13:50,800 của vấn đề ban đầu. 312 00:13:50,800 --> 00:13:52,480 Bước thứ ba và cuối cùng là gì? 313 00:13:52,480 --> 00:13:54,854 Cũng kết hợp hai nửa lại với nhau. 314 00:13:54,854 --> 00:13:57,020 Vì vậy, hãy để tôi có được bản thân mình một số thêm không gian, nhưng, một lần nữa, tôi 315 00:13:57,020 --> 00:13:58,699 có thể được sử dụng mà không gian lên top tùng. 316 00:13:58,699 --> 00:14:00,490 Nhưng chúng tôi sẽ tiếp tục nó đơn giản trực quan. 317 00:14:00,490 --> 00:14:07,070 Hãy để tôi kết hợp trong doanh nghiệp 1, và sau đó 3, và sau đó 5, và sau đó 7. 318 00:14:07,070 --> 00:14:10,740 Qua đó để lại cho tôi bây giờ với nửa bên phải của vấn đề gốc 319 00:14:10,740 --> 00:14:12,840 đó là hoàn toàn được sắp xếp. 320 00:14:12,840 --> 00:14:13,662 >> Vì vậy, những gì còn lại? 321 00:14:13,662 --> 00:14:16,120 Tôi cảm thấy như tôi luôn nói sự những điều tương tự một lần nữa, và một lần nữa, 322 00:14:16,120 --> 00:14:18,700 nhưng đó là phản xạ của thực tế mà chúng ta đang sử dụng đệ quy. 323 00:14:18,700 --> 00:14:21,050 Quá trình sử dụng một Thuật toán một lần nữa, và một lần nữa, 324 00:14:21,050 --> 00:14:23,940 trên tập con nhỏ hơn của các vấn đề ban đầu. 325 00:14:23,940 --> 00:14:27,580 Vì vậy, bây giờ tôi đã sắp xếp một trái một nửa của vấn đề ban đầu. 326 00:14:27,580 --> 00:14:30,847 Tôi có một nửa được sắp xếp đúng của vấn đề ban đầu. 327 00:14:30,847 --> 00:14:32,180 Bước thứ ba và cuối cùng là gì? 328 00:14:32,180 --> 00:14:33,590 Oh, đó là sáp nhập. 329 00:14:33,590 --> 00:14:34,480 Vì vậy, hãy làm điều đó. 330 00:14:34,480 --> 00:14:36,420 Hãy phân bổ một số bổ sung bộ nhớ, nhưng thần của tôi, chúng tôi 331 00:14:36,420 --> 00:14:37,503 có thể đặt nó ở bất cứ đâu bây giờ. 332 00:14:37,503 --> 00:14:40,356 Chúng tôi có rất nhiều không gian có sẵn cho chúng tôi, nhưng chúng tôi sẽ giữ nó đơn giản. 333 00:14:40,356 --> 00:14:42,730 Thay vì đi lại và ra với bộ nhớ ban đầu của chúng tôi, 334 00:14:42,730 --> 00:14:44,480 chúng ta hãy làm điều đó thị xuống dưới đây, 335 00:14:44,480 --> 00:14:47,240 để hoàn tất việc sáp nhập nửa bên trái và nửa bên phải. 336 00:14:47,240 --> 00:14:49,279 >> Vì vậy, bằng việc sáp nhập, những gì tôi cần phải làm gì? 337 00:14:49,279 --> 00:14:50,820 Tôi muốn sử dụng yếu tố theo thứ tự. 338 00:14:50,820 --> 00:14:53,230 Vì vậy, nhìn vào nửa trái, Tôi thấy số đầu tiên là 2. 339 00:14:53,230 --> 00:14:55,230 Tôi nhìn vào nửa bên phải, Tôi thấy số đầu tiên 340 00:14:55,230 --> 00:14:58,290 là 1, như vậy rõ ràng mà số làm tôi muốn nhổ ra, 341 00:14:58,290 --> 00:15:00,430 và đưa lên đầu tiên trong danh sách cuối cùng của tôi? 342 00:15:00,430 --> 00:15:01,449 Tất nhiên, 1. 343 00:15:01,449 --> 00:15:02,990 Bây giờ tôi muốn hỏi rằng cùng một câu hỏi. 344 00:15:02,990 --> 00:15:05,040 Trên một nửa trái, tôi đã vẫn có số lượng 2. 345 00:15:05,040 --> 00:15:07,490 Trên nửa bên phải, Tôi đã có số lượng 3. 346 00:15:07,490 --> 00:15:08,930 Mà một trong những tôi muốn để lựa chọn? 347 00:15:08,930 --> 00:15:11,760 Tất nhiên, số 2 và bây giờ thấy các ứng cử viên 348 00:15:11,760 --> 00:15:13,620 4 trên bên trái, 3 ở bên phải. 349 00:15:13,620 --> 00:15:15,020 Hãy, tất nhiên, chọn 3. 350 00:15:15,020 --> 00:15:18,020 Bây giờ các ứng cử viên trên 4 bên trái, 5 bên phải. 351 00:15:18,020 --> 00:15:19,460 Chúng tôi, tất nhiên, chọn 4. 352 00:15:19,460 --> 00:15:21,240 6 trên bên trái, 5 bên phải. 353 00:15:21,240 --> 00:15:22,730 Chúng tôi, tất nhiên, chọn 5. 354 00:15:22,730 --> 00:15:25,020 6 trên bên trái, 7 bên phải. 355 00:15:25,020 --> 00:15:29,320 Chúng tôi lựa chọn 6, và sau đó chúng tôi chọn 7, và sau đó chúng tôi chọn 8. 356 00:15:29,320 --> 00:15:30,100 Thì đấy. 357 00:15:30,100 --> 00:15:34,370 >> Vì vậy, một số lượng lớn các từ ngữ sau, chúng tôi đã sắp xếp danh sách này trong tám yếu tố 358 00:15:34,370 --> 00:15:38,450 vào một danh sách của một đến tám, đó là tăng theo mỗi bước đi, 359 00:15:38,450 --> 00:15:40,850 nhưng bao nhiêu thời gian đã làm nó đưa chúng ta để làm điều đó. 360 00:15:40,850 --> 00:15:43,190 Vâng, tôi đã cố tình điều đặt ra những bức tranh 361 00:15:43,190 --> 00:15:46,330 ở đây, để chúng ta có thể loại thấy hay đánh giá cao các bộ phận 362 00:15:46,330 --> 00:15:49,060 trong chinh phục đó đang diễn ra. 363 00:15:49,060 --> 00:15:52,830 >> Thật vậy, nếu bạn nhìn lại sự trỗi dậy, Tôi đã để lại tất cả các đường chấm 364 00:15:52,830 --> 00:15:55,660 trong giữ chỗ, bạn có thể, loại, xem, theo thứ tự ngược, 365 00:15:55,660 --> 00:15:58,800 nếu bạn loại nhìn lại lịch sử bây giờ, danh sách ban đầu của tôi 366 00:15:58,800 --> 00:16:00,250 là, tất nhiên, có kích thước 8. 367 00:16:00,250 --> 00:16:03,480 Và sau đó trước đây, tôi đã đối phó với hai danh sách kích thước 4, 368 00:16:03,480 --> 00:16:08,400 và sau đó bốn danh sách kích thước 2, và sau đó tám danh sách có kích thước 1. 369 00:16:08,400 --> 00:16:10,151 >> Vì vậy, những gì thực hiện điều này, loại, nhắc nhở bạn về? 370 00:16:10,151 --> 00:16:11,858 Vâng, thực sự, bất kỳ các thuật toán chúng tôi đã 371 00:16:11,858 --> 00:16:14,430 nhìn vậy, đến nay, nơi chúng tôi chia và phân chia, và phân chia, 372 00:16:14,430 --> 00:16:19,500 tiếp tục có điều một lần nữa, và một lần nữa, kết quả trong ý tưởng chung này. 373 00:16:19,500 --> 00:16:23,100 Và do đó, có một cái gì đó logarit xảy ra ở đây. 374 00:16:23,100 --> 00:16:26,790 Và nó không hoàn toàn log của n, nhưng có một thành phần logarit 375 00:16:26,790 --> 00:16:28,280 những gì chúng ta vừa làm. 376 00:16:28,280 --> 00:16:31,570 >> Bây giờ hãy xem xét làm thế nào mà là thực sự. 377 00:16:31,570 --> 00:16:34,481 Vì vậy, đăng nhập của n, một lần nữa là một thời gian chạy tuyệt vời, 378 00:16:34,481 --> 00:16:36,980 khi chúng tôi đã làm một cái gì đó như tìm kiếm nhị phân, cũng như bây giờ chúng ta gọi nó, 379 00:16:36,980 --> 00:16:40,090 các chiến lược chia và chinh phục qua đó, chúng tôi thấy Mike Smith. 380 00:16:40,090 --> 00:16:41,020 Bây giờ về mặt kỹ thuật. 381 00:16:41,020 --> 00:16:43,640 Đó là log cơ số 2 của n, thậm chí mặc dù trong hầu hết các lớp học toán, 382 00:16:43,640 --> 00:16:45,770 10 thường là các cơ sở mà bạn giả định. 383 00:16:45,770 --> 00:16:48,940 Nhưng các nhà khoa học máy tính hầu như luôn luôn suy nghĩ và nói về cơ sở 2, 384 00:16:48,940 --> 00:16:52,569 vì vậy chúng tôi thường chỉ nói log của n, thay vì log cơ số 2 của n, 385 00:16:52,569 --> 00:16:55,110 nhưng chúng một cách chính xác và cùng trong thế giới của máy tính 386 00:16:55,110 --> 00:16:57,234 khoa học, và là một sang một bên, có một yếu tố không đổi 387 00:16:57,234 --> 00:17:01,070 Sự khác biệt giữa hai người, vì vậy nó Moot anyway, vì lý do chính thức hơn. 388 00:17:01,070 --> 00:17:04,520 >> Nhưng bây giờ, những gì chúng tôi quan tâm về là ví dụ này. 389 00:17:04,520 --> 00:17:08,520 Vì vậy, chúng ta không chứng minh bằng ví dụ, nhưng tại ít nhất là sử dụng một ví dụ về những con số 390 00:17:08,520 --> 00:17:10,730 ở bàn tay như một kiểm tra sự tỉnh táo, nếu bạn sẽ. 391 00:17:10,730 --> 00:17:14,510 Vì vậy, trước đây công thức là cơ sở log 2 của n, nhưng là những gì n trong trường hợp này. 392 00:17:14,510 --> 00:17:18,526 Tôi đã có con số n ban đầu, hoặc 8 của số lượng ban đầu cụ thể. 393 00:17:18,526 --> 00:17:20,359 Bây giờ nó được một chút trong khi, nhưng tôi khá 394 00:17:20,359 --> 00:17:25,300 chắc chắn rằng bản ghi cơ sở 2 giá trị 8 là 3, 395 00:17:25,300 --> 00:17:29,630 và quả thật, những gì là tốt đẹp về điều đó rằng 3 là chính xác số lần 396 00:17:29,630 --> 00:17:33,320 mà bạn có thể chia một danh sách chiều dài 8 một lần nữa, và một lần nữa, 397 00:17:33,320 --> 00:17:36,160 và một lần nữa, cho đến khi bạn đang trái với danh sách các chỉ 1 kích thước. 398 00:17:36,160 --> 00:17:36,660 Phải không? 399 00:17:36,660 --> 00:17:40,790 8 đi đến 4, đi vào 2, đi đến 1, và đó là 400 00:17:40,790 --> 00:17:43,470 phản ánh chính xác điều đó hình ảnh, chúng tôi chỉ vừa mới đây. 401 00:17:43,470 --> 00:17:47,160 Vì vậy, một chút tỉnh táo kiểm tra khi đến nơi logarit được thực sự tham gia. 402 00:17:47,160 --> 00:17:50,180 >> Vì vậy, bây giờ, những gì người khác đang tham gia ở đây? n. 403 00:17:50,180 --> 00:17:53,440 Vì vậy, nhận thấy rằng mỗi thời gian tôi chia danh sách, 404 00:17:53,440 --> 00:17:58,260 mặc dù trong thứ tự ngược lại trong lịch sử ở đây, tôi vẫn đang làm điều n. 405 00:17:58,260 --> 00:18:02,320 Đó là biện pháp sáp nhập đòi hỏi Tôi chạm vào mỗi một trong số các con số, 406 00:18:02,320 --> 00:18:05,060 để trượt nó vào vị trí thích hợp của nó. 407 00:18:05,060 --> 00:18:10,760 Vì vậy, mặc dù chiều cao của này sơ đồ có kích thước log n của n hoặc 3, 408 00:18:10,760 --> 00:18:13,860 Cụ thể, nói cách khác, Tôi đã làm ba sư đoàn ở đây. 409 00:18:13,860 --> 00:18:18,800 Bao nhiêu công việc tôi làm theo chiều ngang cùng biểu đồ này mỗi lần? 410 00:18:18,800 --> 00:18:21,110 >> Vâng, tôi đã làm n bước làm việc, bởi vì nếu tôi đã 411 00:18:21,110 --> 00:18:24,080 có bốn yếu tố và bốn yếu tố, và tôi cần phải hợp nhất chúng lại với nhau. 412 00:18:24,080 --> 00:18:26,040 Tôi cần phải đi qua bốn và bốn, 413 00:18:26,040 --> 00:18:28,123 cuối cùng để hợp nhất chúng trở thành tám yếu tố. 414 00:18:28,123 --> 00:18:32,182 Nếu ngược lại tôi đã có tám ngón tay ở đây, mà tôi thì không, và tám 415 00:18:32,182 --> 00:18:34,390 fingers-- sorry-- Nếu tôi đã có bốn ngón tay trên đây, 416 00:18:34,390 --> 00:18:37,380 mà tôi làm, bốn ngón tay ở đây, mà tôi làm, 417 00:18:37,380 --> 00:18:40,590 thì đó là cùng Ví dụ như trước đây, nếu tôi làm 418 00:18:40,590 --> 00:18:44,010 có tám ngón tay mặc dù trong Tổng cộng, mà tôi có thể, loại, làm. 419 00:18:44,010 --> 00:18:47,950 Tôi chính xác có thể làm ở đây, sau đó tôi có thể chắc chắn 420 00:18:47,950 --> 00:18:50,370 hợp nhất tất cả các danh sách này có kích thước 1 với nhau. 421 00:18:50,370 --> 00:18:54,050 Nhưng tôi chắc chắn phải nhìn tại mỗi phần tử đúng một lần. 422 00:18:54,050 --> 00:18:59,640 Vì vậy, chiều cao của quá trình này là log n, chiều rộng của quá trình này, có thể nói, 423 00:18:59,640 --> 00:19:02,490 là n, vì vậy những gì chúng ta dường như có, cuối cùng, là 424 00:19:02,490 --> 00:19:06,470 một thời gian chạy của kích thước n lần log n. 425 00:19:06,470 --> 00:19:08,977 >> Nói cách khác, chúng ta chia danh sách, log n lần, 426 00:19:08,977 --> 00:19:11,810 nhưng mỗi lần chúng tôi đã làm điều đó, chúng tôi đã có chạm vào mỗi một trong những yếu tố 427 00:19:11,810 --> 00:19:13,560 để hợp nhất chúng tất cả cùng nhau, mà 428 00:19:13,560 --> 00:19:18,120 được n bước, vì vậy chúng tôi có n lần log n, hoặc như một nhà khoa học máy tính sẽ nói, 429 00:19:18,120 --> 00:19:20,380 tiệm cận, mà sẽ là từ lớn 430 00:19:20,380 --> 00:19:22,810 để mô tả trên bị ràng buộc vào một thời gian chạy, 431 00:19:22,810 --> 00:19:28,010 chúng tôi đang chạy trong một o lớn các log n thời gian, do đó, để nói chuyện. 432 00:19:28,010 --> 00:19:31,510 >> Bây giờ điều này là quan trọng, bởi vì nhớ lại những gì lần chạy là 433 00:19:31,510 --> 00:19:34,120 với bong bóng sắp xếp, và lựa chọn sắp xếp, và sắp xếp chèn, 434 00:19:34,120 --> 00:19:38,200 và thậm chí một vài người khác đang tồn tại, n bình phương là nơi mà chúng tôi đang ở. 435 00:19:38,200 --> 00:19:39,990 Và bạn có thể, loại, thấy điều này ở đây. 436 00:19:39,990 --> 00:19:45,720 Nếu n bình phương rõ ràng là n lần n, nhưng ở đây chúng tôi có n lần log n, 437 00:19:45,720 --> 00:19:48,770 và chúng ta đã biết từ tuần bằng không, mà log n, logarit, 438 00:19:48,770 --> 00:19:50,550 là tốt hơn so với một cái gì đó tuyến tính. 439 00:19:50,550 --> 00:19:52,930 Sau khi tất cả, nhớ lại những hình ảnh với màu đỏ và màu vàng 440 00:19:52,930 --> 00:19:56,500 và các đường màu xanh lá cây mà chúng tôi đã thu hút, các dòng logarit xanh là thấp hơn nhiều. 441 00:19:56,500 --> 00:20:00,920 Và do đó, tốt hơn nhiều và nhanh hơn hơn so với các dòng màu vàng và đỏ trực tiếp, 442 00:20:00,920 --> 00:20:05,900 n lần đăng nhập n là, thực sự, tốt hơn hơn n lần n, hoặc n bình phương. 443 00:20:05,900 --> 00:20:09,110 >> Vì vậy, chúng tôi dường như có xác định một thuật toán hợp nhất 444 00:20:09,110 --> 00:20:11,870 loại chạy trong nhiều thời gian nhanh hơn, và quả thật, 445 00:20:11,870 --> 00:20:16,560 đó là lý do tại sao, hồi đầu tuần này, khi chúng ta thấy rằng cuộc thi giữa bong bóng 446 00:20:16,560 --> 00:20:20,750 phân loại, sắp xếp chọn, và hợp nhất sắp xếp, hợp nhất phân loại thực sự, thực sự chiến thắng. 447 00:20:20,750 --> 00:20:23,660 Và quả thực, chúng tôi thậm chí còn không chờ đợi cho bong bóng sắp xếp và lựa chọn loại 448 00:20:23,660 --> 00:20:24,790 kêt thuc. 449 00:20:24,790 --> 00:20:27,410 >> Bây giờ chúng ta hãy một pass khác lúc này, từ một hơi hơn 450 00:20:27,410 --> 00:20:31,030 quan điểm chính thức, chỉ trong trường hợp, điều này tạo ra tiếng vang tốt hơn 451 00:20:31,030 --> 00:20:33,380 hơn so với cuộc thảo luận cấp cao hơn. 452 00:20:33,380 --> 00:20:34,880 Vì vậy, đây là thuật toán nữa. 453 00:20:34,880 --> 00:20:36,770 Hãy tự hỏi mình, những gì thời gian chạy 454 00:20:36,770 --> 00:20:39,287 là các thuật toán này bước khác nhau? 455 00:20:39,287 --> 00:20:41,620 Chúng ta hãy chia nó thành người đầu tiên trường hợp và trường hợp thứ hai. 456 00:20:41,620 --> 00:20:46,280 IF và ELSE Trong trường hợp IF, NẾU n là nhỏ hơn 2, chỉ cần trả lại. 457 00:20:46,280 --> 00:20:47,580 Cảm thấy như thời gian liên tục. 458 00:20:47,580 --> 00:20:50,970 Đó là, loại, giống như hai bước, NẾU n là nhỏ hơn 2, sau đó quay trở lại. 459 00:20:50,970 --> 00:20:54,580 Nhưng như chúng tôi đã nói hôm thứ Hai, thời gian liên tục, hoặc lớn o 1, 460 00:20:54,580 --> 00:20:57,130 có thể được hai bước, ba bước, thậm chí 1.000 bước. 461 00:20:57,130 --> 00:20:59,870 Điều quan trọng là nó một hằng số của các bước. 462 00:20:59,870 --> 00:21:03,240 Vì vậy, màu vàng đánh dấu giả ở đây chạy trong, chúng tôi sẽ gọi nó, 463 00:21:03,240 --> 00:21:04,490 thời gian liên tục. 464 00:21:04,490 --> 00:21:06,780 Vì vậy, nhiều chính thức, và chúng ta sẽ đối với: này 465 00:21:06,780 --> 00:21:09,910 sẽ là mức độ mà chúng ta chính thức hóa quyền này now-- T n, 466 00:21:09,910 --> 00:21:15,030 thời gian chạy của một vấn đề mà phải mất n somethings như đầu vào, 467 00:21:15,030 --> 00:21:19,150 bằng lớn o của một, NẾU n là ít hơn 2. 468 00:21:19,150 --> 00:21:20,640 Vì vậy, nó có điều kiện về điều đó. 469 00:21:20,640 --> 00:21:24,150 Vì vậy, để được rõ ràng, IF n là ít hơn 2, chúng tôi có một danh sách rất ngắn, sau đó 470 00:21:24,150 --> 00:21:29,151 thời gian chạy, T n, trong đó n là 1 hoặc 0, trong trường hợp này rất cụ thể, 471 00:21:29,151 --> 00:21:30,650 nó chỉ sẽ là thời gian liên tục. 472 00:21:30,650 --> 00:21:32,691 Nó sẽ mất một bước, hai bước, bất cứ điều gì. 473 00:21:32,691 --> 00:21:33,950 Đó là một số cố định của các bước. 474 00:21:33,950 --> 00:21:38,840 >> Vì vậy, phần ngon ngọt chắc chắn phải có trong các trường hợp khác trong mã giả. 475 00:21:38,840 --> 00:21:40,220 Các trường hợp ELSE. 476 00:21:40,220 --> 00:21:44,870 Sắp xếp một nửa bên trái của các yếu tố, sắp xếp đúng một nửa của các nguyên tố, hợp nhất hai nửa được sắp xếp. 477 00:21:44,870 --> 00:21:46,800 Không mỗi người trong những bước đi trong bao lâu? 478 00:21:46,800 --> 00:21:49,780 Vâng, nếu chạy thời gian để sắp xếp n phần tử 479 00:21:49,780 --> 00:21:53,010 là, chúng ta hãy gọi nó rất quát, T n, 480 00:21:53,010 --> 00:21:55,500 sau đó phân loại trái nửa các nguyên tố 481 00:21:55,500 --> 00:21:59,720 là, loại, giống như nói rằng, T của n khi chia cho 2, 482 00:21:59,720 --> 00:22:03,000 và tương tự như phân loại nửa bên phải của các nguyên tố là, loại, giống như nói rằng, 483 00:22:03,000 --> 00:22:06,974 T n chia 2, và sau đó sáp nhập hai nửa được sắp xếp. 484 00:22:06,974 --> 00:22:08,890 Vâng, nếu tôi đã có một số số phần tử ở đây, 485 00:22:08,890 --> 00:22:11,230 như bốn, và một số số các yếu tố ở đây, giống như bốn, 486 00:22:11,230 --> 00:22:14,650 và tôi phải hợp nhất mỗi trong bốn trong, và mỗi bốn năm, một 487 00:22:14,650 --> 00:22:17,160 sau khi khác, do đó cuối cùng tôi có tám yếu tố. 488 00:22:17,160 --> 00:22:20,230 Nó cảm thấy như đó là lớn o n bậc? 489 00:22:20,230 --> 00:22:23,500 Nếu tôi đã có n ngón tay và mỗi chúng phải được sáp nhập vào vị trí, 490 00:22:23,500 --> 00:22:25,270 đó là giống như một bước n. 491 00:22:25,270 --> 00:22:27,360 >> Vì vậy, thực sự formulaically, chúng ta có thể thể hiện điều này, 492 00:22:27,360 --> 00:22:29,960 mặc dù là một chút đáng sợ lúc đầu Trong nháy mắt, nhưng nó là cái gì 493 00:22:29,960 --> 00:22:31,600 mà bắt chính xác logic. 494 00:22:31,600 --> 00:22:35,710 Thời gian chạy, T n, IF n là lớn hơn hoặc bằng 2. 495 00:22:35,710 --> 00:22:42,500 Trong trường hợp này, các trường hợp ELSE, là T của n chia 2, cộng với T của N chia hết cho 2, 496 00:22:42,500 --> 00:22:45,320 cộng lớn o n, một số số tuyến tính của các bước, 497 00:22:45,320 --> 00:22:51,630 có lẽ chính xác n, có thể 2 lần n, nhưng đó là khoảng, thứ tự của n. 498 00:22:51,630 --> 00:22:54,060 Vì vậy, điều đó cũng là cách chúng ta có thể thể hiện điều này formulaically. 499 00:22:54,060 --> 00:22:56,809 Bây giờ bạn sẽ không biết điều này trừ khi bạn đã ghi nó trong tâm trí của bạn, 500 00:22:56,809 --> 00:22:58,710 hoặc nhìn nó trong các trở lại của một cuốn sách giáo khoa, mà 501 00:22:58,710 --> 00:23:00,501 có thể có một chút cheat sheet ở cuối, 502 00:23:00,501 --> 00:23:03,940 nhưng điều này là, thực sự, sẽ cho chúng ta một o n log n lớn, 503 00:23:03,940 --> 00:23:06,620 bởi vì việc lặp lại bạn nhìn thấy ở đây trên màn hình, 504 00:23:06,620 --> 00:23:09,550 nếu bạn thực sự đã làm nó ra, với một số lượng vô hạn các ví dụ, 505 00:23:09,550 --> 00:23:13,000 hoặc bạn đã làm nó formulaically, bạn sẽ thấy rằng điều này, bởi vì công thức này 506 00:23:13,000 --> 00:23:17,100 chính nó là đệ quy, với t của n trên một cái gì đó ở bên phải, 507 00:23:17,100 --> 00:23:21,680 và t trong n qua bên trái, điều này có thể thực sự được thể hiện, cuối cùng, 508 00:23:21,680 --> 00:23:24,339 đi như là lớn của n log n. 509 00:23:24,339 --> 00:23:26,130 Nếu không thuyết phục, đó là tốt cho bây giờ, chỉ cần 510 00:23:26,130 --> 00:23:28,960 mất trên đức tin, mà đó là, thực sự, những gì tái phát dẫn đến, 511 00:23:28,960 --> 00:23:31,780 nhưng đây chỉ là một chút của một Phương pháp toán học để tìm kiếm 512 00:23:31,780 --> 00:23:36,520 tại thời gian chạy của sắp xếp hợp nhất dựa trên giả của nó một mình. 513 00:23:36,520 --> 00:23:39,030 >> Bây giờ chúng ta hãy xem một chút của một tạm nghỉ từ tất cả điều đó, 514 00:23:39,030 --> 00:23:41,710 và có một cái nhìn tại một một số cựu thượng nghị sĩ, người 515 00:23:41,710 --> 00:23:44,260 có thể nhìn một chút quen thuộc, người ngồi xuống với Eric của Google 516 00:23:44,260 --> 00:23:48,410 Schmidt, một số thời gian trước đây, cho một cuộc phỏng vấn trên sân khấu, trước mặt cả một bó 517 00:23:48,410 --> 00:23:53,710 người, nói chuyện cuối cùng về một chủ đề, đó là khá quen thuộc. 518 00:23:53,710 --> 00:23:54,575 Hãy nhìn xem. 519 00:23:54,575 --> 00:24:01,020 520 00:24:01,020 --> 00:24:03,890 >> ERIC Schmidt: Bây giờ Thượng nghị sĩ, bạn đang ở đây tại Google, 521 00:24:03,890 --> 00:24:09,490 và tôi thích suy nghĩ của các tổng thống như một cuộc phỏng vấn việc làm. 522 00:24:09,490 --> 00:24:11,712 Bây giờ thật khó để có được một công việc làm chủ tịch. 523 00:24:11,712 --> 00:24:12,670 TỔNG THỐNG OBAMA: Đúng vậy. 524 00:24:12,670 --> 00:24:13,940 ERIC Schmidt: Và bạn sẽ làm [Không nghe thấy] bây giờ. 525 00:24:13,940 --> 00:24:15,523 Nó cũng khó để có được một công việc tại Google. 526 00:24:15,523 --> 00:24:17,700 TỔNG THỐNG OBAMA: Đúng vậy. 527 00:24:17,700 --> 00:24:21,330 >> ERIC Schmidt: Chúng tôi có câu hỏi, và chúng tôi đặt câu hỏi các ứng cử viên của chúng tôi, 528 00:24:21,330 --> 00:24:24,310 và điều này là từ Larry Schwimmer. 529 00:24:24,310 --> 00:24:25,890 >> TỔNG THỐNG OBAMA: OK. 530 00:24:25,890 --> 00:24:27,005 >> ERIC Schmidt: Cái gì? 531 00:24:27,005 --> 00:24:28,130 Bạn có nghĩ rằng tôi đang đùa đấy à? 532 00:24:28,130 --> 00:24:30,590 Nó ở ngay đây. 533 00:24:30,590 --> 00:24:33,490 Cách hiệu quả nhất để là gì sắp xếp một số nguyên triệu 32 bit? 534 00:24:33,490 --> 00:24:37,560 535 00:24:37,560 --> 00:24:38,979 >> TỔNG THỐNG OBAMA: Well-- 536 00:24:38,979 --> 00:24:41,020 ERIC Schmidt: Đôi khi, có lẽ tôi xin lỗi, maybe-- 537 00:24:41,020 --> 00:24:42,750 TỔNG THỐNG OBAMA: Không, không, không, không, không, tôi think-- 538 00:24:42,750 --> 00:24:43,240 ERIC Schmidt: Đó không phải là it-- 539 00:24:43,240 --> 00:24:45,430 TỔNG THỐNG OBAMA: Tôi nghĩ, tôi nghĩ rằng các bong bóng 540 00:24:45,430 --> 00:24:46,875 loại sẽ là con đường sai để đi. 541 00:24:46,875 --> 00:24:49,619 542 00:24:49,619 --> 00:24:50,535 ERIC Schmidt: Thôi nào. 543 00:24:50,535 --> 00:24:52,200 Ai nói với anh điều này? 544 00:24:52,200 --> 00:24:54,020 ĐƯỢC. 545 00:24:54,020 --> 00:24:55,590 Tôi đã làm không phải là khoa học máy tính on-- 546 00:24:55,590 --> 00:24:58,986 >> TỔNG THỐNG OBAMA: Chúng tôi đã có điệp viên của chúng tôi trong đó. 547 00:24:58,986 --> 00:24:59,860 GIÁO SƯ: Tất cả các quyền. 548 00:24:59,860 --> 00:25:03,370 Hãy để lại phía sau chúng tôi bây giờ thế giới lý thuyết của thuật toán 549 00:25:03,370 --> 00:25:06,520 trong phân tích tiệm cận của chúng, và trở về một số chủ đề 550 00:25:06,520 --> 00:25:09,940 từ tuần không và một, và khởi động để loại bỏ một số bánh xe đào tạo, 551 00:25:09,940 --> 00:25:10,450 nếu bạn sẽ. 552 00:25:10,450 --> 00:25:13,241 Vì vậy mà bạn thực sự hiểu cuối cùng từ mặt đất lên, có chuyện gì 553 00:25:13,241 --> 00:25:16,805 xảy ra dưới mui xe, khi bạn viết, biên dịch và thực thi chương trình. 554 00:25:16,805 --> 00:25:19,680 Nhớ lại đặc biệt, rằng đây là Chương trình C đầu tiên chúng ta nhìn vào, 555 00:25:19,680 --> 00:25:22,840 một chương trình đơn giản kinh điển của các loại, tương đối nói, 556 00:25:22,840 --> 00:25:24,620 trong đó, nó in, Hello World. 557 00:25:24,620 --> 00:25:27,610 Và nhớ lại rằng tôi đã nói, quá trình rằng mã nguồn đi qua 558 00:25:27,610 --> 00:25:28,430 là chính xác này. 559 00:25:28,430 --> 00:25:31,180 Bạn lấy mã nguồn của bạn, vượt qua nó thông qua một trình biên dịch, như Clang, 560 00:25:31,180 --> 00:25:34,650 và đi ra mã đối tượng, mà có thể trông như thế này, số không và những người thân 561 00:25:34,650 --> 00:25:37,880 rằng CPU của máy tính, trung tâm đơn vị xử lý hoặc não, 562 00:25:37,880 --> 00:25:39,760 cuối cùng hiểu. 563 00:25:39,760 --> 00:25:42,460 >> Nó chỉ ra rằng đó là một bit của một sự đơn giản, 564 00:25:42,460 --> 00:25:44,480 rằng chúng tôi bây giờ trong một vị trí để trêu chọc nhau 565 00:25:44,480 --> 00:25:46,720 để hiểu những gì đang thực sự được xảy ra dưới mui xe 566 00:25:46,720 --> 00:25:48,600 mỗi khi bạn chạy Clang, hay rộng hơn, 567 00:25:48,600 --> 00:25:53,040 mỗi khi bạn thực hiện một chương trình, Hãy sử dụng và CF 50 IDE. 568 00:25:53,040 --> 00:25:56,760 Đặc biệt, công cụ như này là lần đầu tiên tạo ra, 569 00:25:56,760 --> 00:25:58,684 khi lần đầu tiên bạn biên dịch chương trình của bạn. 570 00:25:58,684 --> 00:26:00,600 Nói cách khác, khi bạn lấy mã nguồn của bạn 571 00:26:00,600 --> 00:26:04,390 và biên dịch nó, những gì đầu tiên được xuất ra bởi Clang 572 00:26:04,390 --> 00:26:06,370 là một cái gì đó gọi là mã lắp ráp. 573 00:26:06,370 --> 00:26:08,990 Và trên thực tế, nó trông giống hệt như thế này. 574 00:26:08,990 --> 00:26:11,170 >> Tôi chạy một lệnh tại dòng lệnh trước đó. 575 00:26:11,170 --> 00:26:16,260 Hello.c Clang vốn dash s, và điều này tạo ra một tập tin 576 00:26:16,260 --> 00:26:19,490 cho tôi gọi hello.s, trong số đó là chính xác 577 00:26:19,490 --> 00:26:22,290 những nội dung này, và nhiều hơn một chút ở trên và một chút dưới hơn, 578 00:26:22,290 --> 00:26:25,080 nhưng tôi đã đặt juiciest thông tin ở đây trên màn hình. 579 00:26:25,080 --> 00:26:29,190 Và nếu bạn nhìn kỹ, bạn sẽ thấy ít nhất là một vài từ khóa quen thuộc. 580 00:26:29,190 --> 00:26:31,330 Chúng tôi có chính ở đầu trang. 581 00:26:31,330 --> 00:26:35,140 Chúng tôi đã printf xuống ở giữa. 582 00:26:35,140 --> 00:26:38,670 Và chúng tôi cũng có hello world backslash n trong dấu ngoặc kép xuống dưới đây. 583 00:26:38,670 --> 00:26:42,450 >> Và mọi thứ khác ở đây là hướng dẫn mức rất thấp 584 00:26:42,450 --> 00:26:45,500 rằng CPU của máy tính hiểu được. 585 00:26:45,500 --> 00:26:50,090 Hướng dẫn CPU di chuyển bộ nhớ xung quanh, rằng dây tải từ bộ nhớ, 586 00:26:50,090 --> 00:26:52,750 và cuối cùng, in thứ trên màn hình. 587 00:26:52,750 --> 00:26:56,780 Bây giờ những gì xảy ra mặc dù sau mã lắp ráp này được tạo ra? 588 00:26:56,780 --> 00:26:59,964 Cuối cùng, bạn làm gì, thực sự, vẫn tạo ra mã đối tượng. 589 00:26:59,964 --> 00:27:02,630 Nhưng những bước mà có thực sự được diễn ra dưới mui xe 590 00:27:02,630 --> 00:27:04,180 nhìn nhiều hơn một chút như thế này. 591 00:27:04,180 --> 00:27:08,390 Mã nguồn trở thành mã lắp ráp, mà sau đó trở thành mã đối tượng, 592 00:27:08,390 --> 00:27:11,930 và những lời tác ở đây là rằng, khi bạn biên dịch mã nguồn của bạn, 593 00:27:11,930 --> 00:27:16,300 đi ra mã lắp ráp, và sau đó khi bạn lắp ráp mã lắp ráp của bạn, 594 00:27:16,300 --> 00:27:17,800 đi ra mã đối tượng. 595 00:27:17,800 --> 00:27:20,360 >> Bây giờ Clang là siêu tinh vi, giống như rất nhiều các trình biên dịch, 596 00:27:20,360 --> 00:27:23,151 và nó hiện tất cả các bước với nhau, và nó không nhất thiết 597 00:27:23,151 --> 00:27:25,360 đầu ra bất kỳ trung gian tập tin mà bạn thậm chí có thể nhìn thấy. 598 00:27:25,360 --> 00:27:28,400 Nó chỉ biên dịch mọi thứ, đó là thuật ngữ chung 599 00:27:28,400 --> 00:27:30,000 mô tả toàn bộ quá trình này. 600 00:27:30,000 --> 00:27:32,000 Nhưng nếu bạn thực sự muốn để được cụ thể, có 601 00:27:32,000 --> 00:27:34,330 rất nhiều nhiều đang xảy ra ở đó là tốt. 602 00:27:34,330 --> 00:27:38,860 >> Nhưng chúng ta hãy cũng xem xét bây giờ mà thậm chí mà chương trình siêu đơn giản, hello.c, 603 00:27:38,860 --> 00:27:40,540 được gọi là một hàm. 604 00:27:40,540 --> 00:27:41,870 Nó được gọi là printf. 605 00:27:41,870 --> 00:27:46,900 Nhưng tôi đã không viết printf, thực sự, mà đi kèm với c, vậy để nói chuyện. 606 00:27:46,900 --> 00:27:51,139 Đó là một hồi chức năng mà khai báo trong io.h tiêu chuẩn, mà 607 00:27:51,139 --> 00:27:53,180 là một tập tin tiêu đề, mà là một chủ đề chúng ta sẽ thực sự 608 00:27:53,180 --> 00:27:55,780 lặn xuống sâu hơn trước khi dài. 609 00:27:55,780 --> 00:27:58,000 Nhưng một tập tin tiêu đề là thường đi kèm 610 00:27:58,000 --> 00:28:02,920 bởi một tập tin mã, tập tin mã nguồn, vì vậy giống như có tồn tại io.h. chuẩn 611 00:28:02,920 --> 00:28:05,930 >> Đôi khi trước đây, một người nào đó, hoặc ai đó, cũng đã viết 612 00:28:05,930 --> 00:28:11,040 một tập tin gọi là io.c tiêu chuẩn, trong đó các định nghĩa thực tế, 613 00:28:11,040 --> 00:28:15,220 hoặc triển khai của printf, và chùm của các chức năng khác, 614 00:28:15,220 --> 00:28:16,870 đang thực sự được viết. 615 00:28:16,870 --> 00:28:22,140 Vì vậy, cho rằng, nếu chúng ta xem xét việc có đây trên bên trái, hello.c, rằng khi 616 00:28:22,140 --> 00:28:26,250 biên soạn, cho chúng ta hello.s, ngay cả khi Clang không bận tâm tiết kiệm ở một nơi 617 00:28:26,250 --> 00:28:31,360 chúng ta có thể nhìn thấy nó, và rằng mã lắp ráp được lắp ráp thành hello.o, mà 618 00:28:31,360 --> 00:28:34,630 là, thực sự, tên mặc định đưa ra bất cứ khi nào bạn biên dịch mã nguồn 619 00:28:34,630 --> 00:28:39,350 mã vào mã đối tượng, nhưng không phải là hoàn toàn sẵn sàng để thực hiện nó chưa, 620 00:28:39,350 --> 00:28:41,460 bởi vì một bước đã xảy ra, và có 621 00:28:41,460 --> 00:28:44,440 đã xảy ra trong vài quá khứ tuần, có lẽ unbeknownst cho bạn. 622 00:28:44,440 --> 00:28:47,290 >> Cụ thể ở đâu đó trong CS50 IDE, và điều này, 623 00:28:47,290 --> 00:28:49,870 quá, sẽ là một chút của một sự đơn giản trong một khoảnh khắc, 624 00:28:49,870 --> 00:28:54,670 có, hoặc là có một thời gian, một tập tin gọi là io.c tiêu chuẩn, 625 00:28:54,670 --> 00:28:58,440 rằng ai đó biên dịch vào io.s tiêu chuẩn hoặc tương đương, 626 00:28:58,440 --> 00:29:02,010 rằng một người nào đó sau đó lắp ráp vào io.o tiêu chuẩn, 627 00:29:02,010 --> 00:29:04,600 hoặc nó biến ra thành một tập hơi khác nhau 628 00:29:04,600 --> 00:29:07,220 định dạng mà có thể có một khác nhau tập tin mở rộng hoàn toàn, 629 00:29:07,220 --> 00:29:11,720 nhưng trong lý thuyết và khái niệm, chính xác những bước đã phải xảy ra trong một số hình thức. 630 00:29:11,720 --> 00:29:14,060 Mà là để nói, mà bây giờ khi tôi đang viết một chương trình, 631 00:29:14,060 --> 00:29:17,870 hello.c, mà chỉ nói rằng, xin chào thế giới, và tôi đang sử dụng mã của người khác 632 00:29:17,870 --> 00:29:22,480 như printf, mà là một lần khi một thời gian, trong một tập tin gọi là io.c tiêu chuẩn, 633 00:29:22,480 --> 00:29:26,390 sau đó bằng cách nào đó tôi đã để mất tôi mã đối tượng, số không và những người thân của tôi, 634 00:29:26,390 --> 00:29:29,260 và đối tượng của người đó code, hay số không và những người thân, 635 00:29:29,260 --> 00:29:34,970 và bằng cách nào đó liên kết chúng lại với nhau thành một tập tin cuối cùng, gọi là hello, mà 636 00:29:34,970 --> 00:29:38,070 có tất cả các số không và những người từ chức năng chính của tôi, 637 00:29:38,070 --> 00:29:40,830 và tất cả các số không và những người cho printf. 638 00:29:40,830 --> 00:29:44,900 >> Và quả thực, đó là quá trình cuối cùng gọi là, liên kết mã đối tượng của bạn. 639 00:29:44,900 --> 00:29:47,490 Đầu ra của mà là một tập tin thực thi. 640 00:29:47,490 --> 00:29:49,780 Vì vậy, trong công bằng, tại cuối ngày, không có gì 641 00:29:49,780 --> 00:29:52,660 đã thay đổi kể từ tuần thứ nhất, khi chúng ta đầu tiên bắt đầu biên soạn chương trình. 642 00:29:52,660 --> 00:29:55,200 Thật vậy, tất cả những điều này đã được xảy ra dưới mui xe, 643 00:29:55,200 --> 00:29:57,241 nhưng bây giờ chúng tôi đang ở trong một vị trí nơi chúng ta có thể thực sự 644 00:29:57,241 --> 00:29:58,794 trêu chọc nhau những bước khác nhau. 645 00:29:58,794 --> 00:30:00,710 Và quả thực, ở cuối trong ngày, chúng tôi vẫn 646 00:30:00,710 --> 00:30:04,480 trái với số không và những người thân, mà thực sự là một segue tuyệt vời bây giờ 647 00:30:04,480 --> 00:30:08,620 đến một khả năng của C, mà chúng tôi đã không có để tận dụng khả năng nhất 648 00:30:08,620 --> 00:30:11,250 cho đến nay, được gọi là toán tử trên bit. 649 00:30:11,250 --> 00:30:15,220 Nói cách khác, cho đến nay, bất cứ lúc nào chúng tôi đã xử lý dữ liệu trong C hoặc các biến trong C, 650 00:30:15,220 --> 00:30:17,660 chúng tôi đã có những thứ như chars và phao nổi và các ins 651 00:30:17,660 --> 00:30:21,990 và chờ đợi và đôi và như thế, nhưng tất cả những người đang có ít nhất tám bit. 652 00:30:21,990 --> 00:30:25,550 Chúng tôi chưa bao giờ được thể thao tác bit riêng lẻ, 653 00:30:25,550 --> 00:30:28,970 mặc dù một chút cá nhân, chúng tôi biết, có thể đại diện cho một 0 và 1. 654 00:30:28,970 --> 00:30:32,640 Bây giờ nó chỉ ra rằng trong C, bạn có thể có được quyền truy cập vào các bit riêng lẻ, 655 00:30:32,640 --> 00:30:35,530 nếu bạn biết cú pháp, mà để có được ở họ. 656 00:30:35,530 --> 00:30:38,010 >> Vì vậy, chúng ta hãy có một cái nhìn tại toán tử trên bit. 657 00:30:38,010 --> 00:30:41,700 Vì vậy, trong hình ở đây là một vài biểu tượng chúng tôi, loại, loại, nhìn thấy trước. 658 00:30:41,700 --> 00:30:45,580 Tôi nhìn thấy một dấu, một dọc thanh, và một số người khác là tốt, 659 00:30:45,580 --> 00:30:49,430 và nhớ lại rằng dấu và ký hiệu là một cái gì đó chúng ta đã thấy trước đây. 660 00:30:49,430 --> 00:30:54,060 Các toán tử logic AND, nơi bạn có hai trong số chúng lại với nhau, hoặc logic OR 661 00:30:54,060 --> 00:30:56,300 điều hành, nơi bạn có hai thanh dọc. 662 00:30:56,300 --> 00:31:00,550 Toán tử trên bit, mà chúng tôi sẽ thấy hoạt động trên bit riêng lẻ, 663 00:31:00,550 --> 00:31:03,810 chỉ cần sử dụng một ký hiệu duy nhất, một đơn thanh dọc, các biểu tượng caret 664 00:31:03,810 --> 00:31:06,620 đến tiếp theo, ít dấu ngã, và sau đó còn lại 665 00:31:06,620 --> 00:31:08,990 khung bên trái khung, hoặc khung bên phải khung bên phải. 666 00:31:08,990 --> 00:31:10,770 Mỗi trong số này có ý nghĩa khác nhau. 667 00:31:10,770 --> 00:31:11,950 >> Trong thực tế, chúng ta hãy có một cái nhìn. 668 00:31:11,950 --> 00:31:16,560 Hãy đi học cũ ngày hôm nay, và sử dụng một màn hình cảm ứng từ năm qua, 669 00:31:16,560 --> 00:31:18,002 được biết đến như một bảng trắng. 670 00:31:18,002 --> 00:31:19,710 Và bảng trắng này sẽ cho phép chúng tôi 671 00:31:19,710 --> 00:31:27,360 để bày tỏ một số biểu tượng khá đơn giản, hay đúng hơn là một số công thức khá đơn giản, 672 00:31:27,360 --> 00:31:29,560 rằng chúng ta có thể sau đó cuối cùng đòn bẩy, để 673 00:31:29,560 --> 00:31:33,230 để truy cập cá nhân bit trong một chương trình C. 674 00:31:33,230 --> 00:31:34,480 Nói cách khác, chúng ta hãy làm điều này. 675 00:31:34,480 --> 00:31:37,080 Hãy nói chuyện đầu tiên cho một lúc về ký hiệu, 676 00:31:37,080 --> 00:31:39,560 đó là các phép toán AND điều hành. 677 00:31:39,560 --> 00:31:42,130 Nói cách khác, đây là một nhà điều hành, cho phép 678 00:31:42,130 --> 00:31:45,930 tôi phải có một biến trái tay thường, và một biến cánh tay phải, 679 00:31:45,930 --> 00:31:50,640 hoặc một giá trị cá nhân, rằng nếu chúng VÀ chúng lại với nhau, mang lại cho tôi một kết quả cuối cùng. 680 00:31:50,640 --> 00:31:51,560 Vì vậy, tôi có nghĩa là gì? 681 00:31:51,560 --> 00:31:54,840 Nếu trong một chương trình, bạn có một biến mà các cửa hàng một trong những giá trị, 682 00:31:54,840 --> 00:31:58,000 hoặc chúng ta hãy giữ cho nó đơn giản, và chỉ viết ra số không và những cá nhân, 683 00:31:58,000 --> 00:32:00,940 đây là cách các nhà điều hành dấu và làm việc. 684 00:32:00,940 --> 00:32:06,400 0 ký hiệu 0 được sẽ bằng 0. 685 00:32:06,400 --> 00:32:07,210 Bây giờ tại sao vậy? 686 00:32:07,210 --> 00:32:09,291 >> Nó rất giống với Biểu thức Boolean, 687 00:32:09,291 --> 00:32:10,540 mà chúng ta đã thảo luận tới. 688 00:32:10,540 --> 00:32:15,800 Nếu bạn nghĩ rằng sau khi tất cả, 0 là sai, 0 là sai, sai và sai 689 00:32:15,800 --> 00:32:18,720 là, như chúng ta đã thảo luận một cách hợp lý, cũng sai. 690 00:32:18,720 --> 00:32:20,270 Vì vậy, chúng tôi nhận được 0 ở đây là tốt. 691 00:32:20,270 --> 00:32:24,390 Nếu bạn lấy dấu và 0 1, cũng vậy, quá, 692 00:32:24,390 --> 00:32:29,890 sẽ là 0, vì cho điều này biểu hiện bên tay trái là đúng hay 1, 693 00:32:29,890 --> 00:32:32,360 nó sẽ cần phải là sự thật và đúng sự thật. 694 00:32:32,360 --> 00:32:36,320 Nhưng ở đây chúng tôi có sai và sự thật, hoặc 0 và 1. 695 00:32:36,320 --> 00:32:42,000 Bây giờ một lần nữa, nếu chúng ta có 1 ký hiệu 0, điều đó cũng sẽ là 0, 696 00:32:42,000 --> 00:32:47,240 và nếu chúng tôi có 1 ký hiệu 1, cuối cùng chúng ta có một chút 1. 697 00:32:47,240 --> 00:32:50,340 Vì vậy, nói cách khác, chúng ta không làm bất cứ điều gì thú vị với nhà điều hành này 698 00:32:50,340 --> 00:32:51,850 chỉ được nêu ra, nhà điều hành ký hiệu này. 699 00:32:51,850 --> 00:32:53,780 Đó là bitwise AND. 700 00:32:53,780 --> 00:32:57,290 Nhưng đó là những thành phần thông qua đó chúng ta có thể làm 701 00:32:57,290 --> 00:32:59,240 những điều thú vị, như chúng ta sẽ sớm thấy. 702 00:32:59,240 --> 00:33:02,790 >> Bây giờ chúng ta hãy nhìn vào chỉ duy nhất thanh dọc ở đây ở bên phải. 703 00:33:02,790 --> 00:33:06,710 Nếu tôi có một bit 0 và tôi Hoặc nó có, các phép toán 704 00:33:06,710 --> 00:33:11,030 OR, một bit 0, đó là sẽ cho tôi 0. 705 00:33:11,030 --> 00:33:17,540 Nếu tôi mất một chút và OR nó với 0 một bit 1, sau đó tôi sẽ có được 1. 706 00:33:17,540 --> 00:33:19,830 Và trên thực tế, chỉ cần cho sự rõ ràng, để tôi đi lại, 707 00:33:19,830 --> 00:33:23,380 để thanh dọc của tôi không được nhầm lẫn với 1. 708 00:33:23,380 --> 00:33:26,560 Hãy để tôi viết lại tất cả 1 của tôi là nhiều hơn một chút 709 00:33:26,560 --> 00:33:32,700 rõ ràng, vì vậy mà chúng tôi tới xem, nếu tôi đã 1 OR 0, đó sẽ là một 1, 710 00:33:32,700 --> 00:33:39,060 và nếu tôi có một 1 OR 1 mà, quá, là có được một 1. 711 00:33:39,060 --> 00:33:42,900 Vì vậy, bạn có thể nhìn thấy một cách logic rằng OR điều hành hoạt động rất khác nhau. 712 00:33:42,900 --> 00:33:48,070 Điều này mang lại cho tôi 0 OR 0 mang lại cho tôi 0, nhưng mọi sự kết hợp khác mang lại cho tôi 1. 713 00:33:48,070 --> 00:33:52,480 Vì vậy, miễn là tôi có một 1 trong công thức, kết quả là có được 1. 714 00:33:52,480 --> 00:33:55,580 >> Ngược lại với AND điều hành, các ký hiệu, 715 00:33:55,580 --> 00:34:00,940 chỉ khi tôi có hai 1 trong việc phương trình, tôi thực sự có được một 1 ra. 716 00:34:00,940 --> 00:34:02,850 Bây giờ có một vài khác nhà khai thác là tốt. 717 00:34:02,850 --> 00:34:04,810 Một trong số đó là một chút liên quan hơn. 718 00:34:04,810 --> 00:34:07,980 Vì vậy, hãy để tôi đi trước và xóa này để giải phóng một số không gian. 719 00:34:07,980 --> 00:34:13,020 720 00:34:13,020 --> 00:34:16,460 Và chúng ta hãy nhìn vào biểu tượng dấu nháy, chỉ trong một khoảnh khắc. 721 00:34:16,460 --> 00:34:18,210 Đây thường là một nhân vật bạn có thể gõ 722 00:34:18,210 --> 00:34:21,420 trên bàn phím của bạn phím Shift và giữ sau đó một trong những con số trên đỉnh Hoa Kỳ của bạn 723 00:34:21,420 --> 00:34:22,250 bàn phím. 724 00:34:22,250 --> 00:34:26,190 >> Vì vậy, đây là độc quyền OR, độc quyền OR. 725 00:34:26,190 --> 00:34:27,790 Vì vậy, chúng tôi chỉ thấy các nhà điều hành OR. 726 00:34:27,790 --> 00:34:29,348 Đây là độc quyền OR. 727 00:34:29,348 --> 00:34:30,639 Những gì là sự khác biệt thực sự? 728 00:34:30,639 --> 00:34:34,570 Vâng chúng ta hãy nhìn vào công thức, và sử dụng như là thành phần cuối cùng. 729 00:34:34,570 --> 00:34:37,690 0 0 XOR. 730 00:34:37,690 --> 00:34:39,650 Tôi sẽ nói luôn là 0. 731 00:34:39,650 --> 00:34:41,400 Đó là định nghĩa của XOR. 732 00:34:41,400 --> 00:34:47,104 0 XOR 1 là có được 1. 733 00:34:47,104 --> 00:34:58,810 1 XOR 0 là có được 1, và 1 XOR 1 là có được? 734 00:34:58,810 --> 00:34:59,890 Sai rồi? 735 00:34:59,890 --> 00:35:00,520 Hoặc đúng? 736 00:35:00,520 --> 00:35:01,860 Tôi không biết. 737 00:35:01,860 --> 00:35:02,810 0. 738 00:35:02,810 --> 00:35:04,700 Bây giờ những gì đang xảy ra ở đây? 739 00:35:04,700 --> 00:35:06,630 Cũng suy nghĩ về tên của nhà điều hành này. 740 00:35:06,630 --> 00:35:09,980 Exclusive OR, vì vậy, khi tên, loại, cho thấy, 741 00:35:09,980 --> 00:35:13,940 câu trả lời là chỉ có được 1 nếu đầu vào là độc quyền, 742 00:35:13,940 --> 00:35:15,560 độc quyền khác nhau. 743 00:35:15,560 --> 00:35:18,170 Vì vậy, đây là những yếu tố đầu vào tương tự, do đầu ra là 0. 744 00:35:18,170 --> 00:35:20,700 Dưới đây là những yếu tố đầu vào tương tự, do đầu ra là 0. 745 00:35:20,700 --> 00:35:25,640 Sau đây là các kết quả đầu ra là khác nhau, họ là độc quyền, và như vậy đầu ra là 1. 746 00:35:25,640 --> 00:35:28,190 Vì vậy, nó rất giống với AND, nó rất giống, 747 00:35:28,190 --> 00:35:32,760 hay đúng hơn là nó rất giống với OR, nhưng chỉ trong một cách độc quyền. 748 00:35:32,760 --> 00:35:36,210 Điều này không còn là 1, bởi vì chúng tôi có hai 1 của, 749 00:35:36,210 --> 00:35:38,621 và không độc quyền, chỉ một trong số họ. 750 00:35:38,621 --> 00:35:39,120 Được rồi. 751 00:35:39,120 --> 00:35:40,080 Còn những người khác? 752 00:35:40,080 --> 00:35:44,220 Vâng dấu ngã, trong khi đó, thực sự đẹp và đơn giản, may mắn. 753 00:35:44,220 --> 00:35:46,410 Và đây là một unary điều hành, có nghĩa là 754 00:35:46,410 --> 00:35:50,400 nó được áp dụng để chỉ có một đầu vào, một toán hạng, vậy để nói chuyện. 755 00:35:50,400 --> 00:35:51,800 Không để một bên trái và một bên phải. 756 00:35:51,800 --> 00:35:56,050 Nói cách khác, nếu bạn có dấu ngã của 0, câu trả lời sẽ là ngược lại. 757 00:35:56,050 --> 00:35:59,710 Và nếu bạn có dấu ngã của 1, Câu trả lời sẽ có điều ngược lại. 758 00:35:59,710 --> 00:36:02,570 Vì vậy, các nhà điều hành là dấu ngã một cách phủ một chút, 759 00:36:02,570 --> 00:36:06,000 hoặc lật một chút từ 0-1, hoặc 1-0. 760 00:36:06,000 --> 00:36:09,820 >> Và đó lại cho chúng ta cuối cùng chỉ với hai nhà khai thác cuối cùng, 761 00:36:09,820 --> 00:36:13,840 cái gọi là sự chuyển đổi trái, và cái gọi là dịch phải. 762 00:36:13,840 --> 00:36:16,620 Chúng ta hãy xem làm thế nào những người làm việc. 763 00:36:16,620 --> 00:36:20,780 Các nhà điều hành dịch trái, bằng văn bản với hai dấu ngoặc nhọn như thế, 764 00:36:20,780 --> 00:36:22,110 hoạt động như sau. 765 00:36:22,110 --> 00:36:27,390 Nếu đầu vào của tôi, hoặc toán hạng của tôi, bên trái điều hành dịch chuyển là khá đơn giản chỉ là 1. 766 00:36:27,390 --> 00:36:33,750 Và sau đó tôi nói với các máy tính để lại sự thay đổi đó 1, nói bảy bậc, 767 00:36:33,750 --> 00:36:37,150 kết quả là như thể tôi đi mà 1, và di chuyển nó 768 00:36:37,150 --> 00:36:40,160 bảy bậc so với trái, và theo mặc định, 769 00:36:40,160 --> 00:36:42,270 chúng ta giả sử rằng các không gian bên phải 770 00:36:42,270 --> 00:36:44,080 sẽ được đệm bằng số không. 771 00:36:44,080 --> 00:36:50,316 Nói cách khác, 1 trái shift 7 sẽ để cung cấp cho tôi rằng 1, tiếp theo là 1, 2, 3, 772 00:36:50,316 --> 00:36:54,060 4, 5, 6, 7 số không. 773 00:36:54,060 --> 00:36:57,380 Vì vậy, trong một cách, nó cho phép bạn mất một số nhỏ như 1, 774 00:36:57,380 --> 00:37:00,740 và rõ ràng làm cho nó nhiều nhiều, lớn hơn nhiều trong cách này, 775 00:37:00,740 --> 00:37:06,460 nhưng chúng tôi đang thực sự đi vào xem cách tiếp cận thông minh hơn cho nó 776 00:37:06,460 --> 00:37:08,080 thay vào đó, là tốt, 777 00:37:08,080 --> 00:37:08,720 >> Được rồi. 778 00:37:08,720 --> 00:37:10,060 Đó là nó cho tuần ba. 779 00:37:10,060 --> 00:37:11,400 Chúng ta sẽ thấy bạn thời gian tới. 780 00:37:11,400 --> 00:37:12,770 Đây là CS50. 781 00:37:12,770 --> 00:37:17,270 782 00:37:17,270 --> 00:37:22,243 >> [MUSIC CHƠI] 783 00:37:22,243 --> 00:37:25,766 >> SPEAKER 1: Ông được tại các bữa ăn nhẹ bar ăn một fudge sundae nóng. 784 00:37:25,766 --> 00:37:28,090 Ông đã có tất cả trên khuôn mặt của mình. 785 00:37:28,090 --> 00:37:30,506 Anh ta mặc rằng sô cô la như một bộ râu 786 00:37:30,506 --> 00:37:31,756 SPEAKER 2: Bạn đang làm gì? 787 00:37:31,756 --> 00:37:32,422 SPEAKER 3: Hmmm? 788 00:37:32,422 --> 00:37:33,500 Cái gì? 789 00:37:33,500 --> 00:37:36,800 >> SPEAKER 2: Bạn chỉ cần suy thoái kép? 790 00:37:36,800 --> 00:37:38,585 Bạn đôi nhúng chip. 791 00:37:38,585 --> 00:37:39,460 SPEAKER 3: Xin lỗi. 792 00:37:39,460 --> 00:37:44,440 SPEAKER 2: Bạn nhúng chip, bạn cắn một miếng, và bạn nhúng một lần nữa. 793 00:37:44,440 --> 00:37:44,940 SPEAKER 3: 794 00:37:44,940 --> 00:37:48,440 SPEAKER 2: Vì vậy, đó là giống như đặt toàn bộ miệng bên phải của bạn trong dip. 795 00:37:48,440 --> 00:37:52,400 Tiếp theo thời gian bạn có một chip, chỉ nhúng nó một lần, và kết thúc nó. 796 00:37:52,400 --> 00:37:53,890 >> SPEAKER 3: Bạn biết những gì, Dan? 797 00:37:53,890 --> 00:37:58,006 Bạn nhúng theo cách mà bạn muốn nhúng. 798 00:37:58,006 --> 00:38:01,900 Tôi sẽ nhúng các cách mà tôi muốn để nhúng. 799 00:38:01,900 --> 00:38:03,194