[Chơi nhạc] 

DAVID J. Malan: Được rồi. Vì vậy, chào đón trở lại. Đây là CS50, và là cuối tuần ba. 

Vì vậy, nhớ lại trong vài tuần qua, chúng tôi đã chi tiêu khá nhiều thời gian trên C, về lập trình, về cú pháp. Và nó khá bình thường, nếu bạn vẫn còn đấu tranh với vấn đề Set 2, để được đập đầu vào tường. Đó là thông báo lỗi khó hiểu, tìm kiếm và lỗi mà bạn không có thể khá đuổi theo. Bởi vì, yên tâm, mà chỉ trong thời gian vài tuần bạn sẽ nhìn lại những thứ như Caesar, và [? V-genair,?] thậm chí có thể Crack, và nhận ra như thế nào đến nay bạn đã đi trong một khoảng thời gian ngắn. Vì vậy, nếu có bất kỳ sự an ủi, treo ở đó cho bây giờ. 

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. 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 nhất là sự khởi đầu của rằng mức độ thoải mái. 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 hiệu quả. 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à nói chung giải quyết hơn vấn đề thú vị. 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ỳ trong những ví dụ chúng tôi có trong tâm trí. 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ã. Nó sẽ có mức độ cao hơn nhiều, và cuối cùng, về giải quyết vấn đề. 

Vì vậy, để có được đến thời điểm đó, hãy để tôi đề xuất rằng sau bảy 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ộ số, trong đó là số 50. Cho tôi dự án này trên này màn hình ở đây là tốt. 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 internet vào đây để xem. Lên đây, trong màu hồng. Được rồi. Tên của bạn là gì? 

Jennifer: [nghe được] 

DAVID J. Malan: Xin lỗi? 

Jennifer: Jennifer. 

DAVID J. Malan: Jennifer. Được rồi, Jennifer. Hân hạnh được gặp bạn. Lên đây. 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, ở 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. 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 trên một cánh cửa, và nó sẽ tiết lộ số lượng của nó. 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. 

15. 16. 50. Độc đáo được thực hiện. Được rồi. Tràng pháo tay cho Jennifer. 

[Vỗ tay] 

Được rồi. Vì vậy, là những gì chiến lược của bạn cho tìm kiếm các số, 50? 

Jennifer: Um, tôi nghĩ có lẽ nếu - [Nghe được] 

DAVID J. Malan: Oh. Cung cấp cho nó một giây. Vì vậy, là chiến thuật đầu tư tìm kiếm các số, 50? 

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 là, và sau đó tôi nghĩ, có lẽ nếu họ đang sắp xếp, tôi sẽ chỉ giữ khai thác cao hơn? 

DAVID J. Malan: OK. Và chúng ta dường như đã tìm thấy đó là trường hợp. 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 trước và tiết lộ những cánh cửa khác bạn có thể đã chọn? 

Jennifer: Oh, em yêu. 

DAVID J. Malan: Ah. 

Jennifer: Vì vậy, tôi chỉ có may mắn. 

DAVID J. Malan: Vì vậy, bạn có may mắn. Được rồi. Vì vậy, không xấu. Nhưng đó là một thú vị cái nhìn sâu sắc, phải không? Nếu bạn giả định, và bạn đã có được, thực sự, một chút may mắn đó. 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 như thế nào có ảnh hưởng đến hành vi của bạn? 

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. 

DAVID J. Malan: OK. 

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. 

DAVID J. Malan: OK. Vì vậy, lớn nhất đến nhỏ nhất, hoặc nhỏ nhất đến lớn nhất. 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ọ 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 sau đó trong trường hợp xấu nhất? 

Jennifer: Tất cả trong số họ. 

DAVID J. Malan: Tất cả trong số họ. Vì vậy, chúng ta hãy khái quát như n. 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 màn hình ở đây. 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. 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 thuật toán của các loại, ngay cả khi bạn đã được loại bỏ qua xung quanh. Là công bằng? 

Jennifer: Vâng. 

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 Ví dụ thứ hai của chúng tôi ở đây với 7 cánh cửa khác nhau. Cùng một số, nhưng điều này Hiện họ đều được sắp xếp. 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 số khác là - 

Jennifer: OK. 

DAVID J. Malan: - trước đó? 

Jennifer: Hãy bắt đầu với một trong những đầu tiên. 

DAVID J. Malan: Được rồi. Bắt đầu với các đầu tiên. 4. Bây giờ, nơi bạn sẽ đi, và tại sao? 

Jennifer: 4 thực sự là nhỏ. Vì vậy, nếu họ có thể loại nhỏ nhất đến lớn, cần được gấp đôi, và -. 

DAVID J. Malan: OK. Chúng ta hãy xem, mà bạn nghĩ? 

Jennifer: Hãy thử một trong những cuối cùng. Tốt đẹp. 

DAVID J. Malan: Rất độc đáo được thực hiện. Được rồi. 

[Vỗ tay] 

DAVID J. Malan: OK. Vì vậy, bạn đang thực sự làm này khủng khiếp, bởi vì bạn làm việc đó rất tốt. Khiến cho chúng tôi không thể thực hiện một số điểm. Vì vậy, hãy cố gắng quay trở lại đây. 

Jennifer: OK. 

DAVID J. Malan: Rất tốt thực hiện, dù sao. Vì vậy, bạn bắt đầu ngay từ đầu, bạn thấy điều đó là 4, sau đó bạn di chuyển đến cùng. Nhưng giả sử bạn đã không có được may mắn ở đó, và giả sử 50 là ở một nơi khác. Những gì bước thứ ba của bạn đã được? 

Jennifer: Trở lại để bắt đầu. 

DAVID J. Malan: Quay trở lại để bắt đầu. OK, vì vậy bạn có thể đã chạm vào cánh cửa này, đó là 8. Được rồi. Vì vậy, đó không phải là 50. Trong trường hợp bạn đã có thể nhìn tiếp theo? 

Jennifer: Nếu tôi không biết họ sắp xếp. 

DAVID J. Malan: Đúng. Vâng, nếu bạn đã biết họ đã sắp xếp - 

Jennifer: Oh, có biết, đúng vậy. 

DAVID J. Malan: - nhưng bạn đã không biết là 50 chưa? 

Jennifer: Chỉ cần tiếp tục đi. 

DAVID J. Malan: Được rồi. OK. Tiếp tục đi. OK, tôi có thể làm việc với. 

Jennifer: OK. 

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 thuật toán phân cấp sao lưu vào. 

Jennifer: Các tuyến tính -. 

DAVID J. Malan: Đây là loại tuyến tính. Nhưng hãy để tôi đề xuất, cho phép tôi đặt ngay tại chỗ. Hãy để tôi làm mới trang. cùng một số, cùng một bố trí, cùng một cửa ra vào. 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 một nửa, loại, và những gì đã được Chiến lược của chúng tôi không? 

Jennifer: Bắt đầu ở giữa. 

DAVID J. Malan: OK. Vì vậy, bắt đầu ở giữa. Vì vậy, chúng ta hãy đi trước và mô phỏng đó. Bắt đầu từ khu trung lộ của tiết lộ cánh cửa đó. Vì vậy, số 16. 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, để có được đoán tiếp theo? 

Jennifer: Vào trong hiệp này. 

DAVID J. Malan: Và tại sao bên phải? 

Jennifer: Nếu họ là loại nhỏ nhất để lớn nhất, sau đó 50 nên ở cuối đó. 

DAVID J. Malan: Tốt. Hoàn toàn hợp lý. 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 là Yếu tố chính. 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 với 7 cửa ra vào, nhưng thực sự chỉ với 3. Đó là khoảng một nửa số kích thước của vấn đề. Được rồi. 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? 

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, như, này. 

DAVID J. Malan: Được rồi. 42. Được rồi, bây giờ những gì là của bạn bản năng nói cho bạn? 

Jennifer: Tôi có thể vứt bỏ và điều này sau đó chỉ cần - 

DAVID J. Malan: OK. Tốt, bạn có thể vứt bỏ nửa bên trái đó. 

Jennifer: - chọn một này. 

DAVID J. Malan: Và bên phải. 

Jennifer: Vâng. 

DAVID J. Malan: Vì vậy, mặc dù nó khó để xem có lẽ, khi chỉ có 7 cửa ra vào, suy nghĩ, bây giờ, sự phù hợp của Thuật toán bạn chỉ cần áp dụng. Trong trường hợp trước, bạn đã làm nhận được may mắn, mà là tuyệt vời. Nhưng bạn đã sử dụng để phân tích, Tôi sẽ nói. 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 nhỏ ngay từ đầu, rõ ràng, chúng tôi đã phải đi hơn bên phải. Nhưng trong một nghĩa nào đó, bạn có may mắn, bởi vì có lẽ đây là số 100, và có thể 50 là hơn ở giữa. Có lẽ 50 thậm chí còn hơn ở đây. 

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ự một lần nữa và một lần nữa. 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 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 ít đặc biệt hoa chữ cái đầu. Ít hơn nhiều theo bản năng. Vì vậy, vào cuối ngày, làm thế nào có bạn mô tả hiệu quả của Thuật toán đầu tiên, nơi mà bạn đã đi trái sang phải, so với thuật toán thứ hai đây? 

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. 

DAVID J. Malan: OK, thậm chí có thể hơn. Chúng ta đẩy một chút khó khăn hơn về điều đó. Đ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 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 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ộ số thứ hai? 

Chúng tôi giảm một nửa số lượng các cửa một lần nữa. Và sau đó chúng tôi đã làm gì sau đó, nếu có nhiều cửa ra vào để chơi với? 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. 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 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 ngồi xuống, cho đến khi một đơn độc linh hồn đang đứng. 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à về trình tự của những gì? 

SPEAKER 1: [nghe được] 

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. Vì vậy, một cái gì đó logarit. 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à đường cong này thú vị mà không nhận được quá xấu theo thời gian. Vì vậy, hãy giữ cho ý tưởng này. Chúng ta hãy cảm ơn Jennifer. Cảm ơn rất nhiều vì đã đến trên lên. Và, một giây. 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. 

Jennifer: Yay. 

DAVID J. Malan: Được rồi, đây. Cảm ơn bạn đã phải gánh chịu sự căng thẳng lên đây. Được rồi. 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. 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 trong đó tuần đầu tiên. 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ả trước đây là đường thẳng này, theo đó, nếu chúng ta đặt một cửa hơn trên màn hình, sau đó Jennifer sẽ đã phải bất lực nhìn, có khả năng, đằng sau một cửa hơn. 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. 

Và do đó, có này tuyến tính mối quan hệ giữa kích thước của vấn đề trên, nói rằng, các trục x, và số lượng thời gian cần thiết để giải quyết trên y. Nhưng hình ảnh tôi đã được ám chỉ đến trước đó là dòng màu xanh lá cây này. Xanh cố tình, bởi vì nó chỉ cảm thấy tốt hơn. 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ó với các bạn, kể cho nhau, và trong trường hợp thứ hai, khi Jennifer chỉ đã làm nó lên đây, nó đã được sắp xếp của cơ bản tốt hơn. Bởi vì nó không chỉ là nhanh gấp hai lần. Đó không phải là thậm chí bốn lần nhanh. Đó 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 bước cuối cùng nó mất. 

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, tương tự có thể được áp dụng một cái gì đó như thế này. Và điều này có thể là tình cờ hơn được gọi là, như bạn có thể tưởng tượng, phân chia và chinh phục. 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. 

Nhưng mã giả, thu hồi, là này. 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 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. Rằng thuật toán được thực hiện trong một chút một cách gian lận, trong đó, không chỉ là một trong tôi đếm, về cơ bản, hiệu quả hơn. Trong trường hợp đó, tôi đã được tận dụng một nguồn thứ cấp. Loại, nhiều CPU, bộ não nhiều, nhiều người thông minh trong 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ì đó logarit, từ một cái gì đó màu đỏ để một cái gì đó màu xanh lá cây. 

Nhưng trong trường hợp này, Jennifer một mình có thể nâng cao hiệu trên 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. Và bây giờ, khi nói đến thời gian để thực hiện những điều này, để tìm ra 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à 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. Bởi vì bạn sẽ không có sang trọng, như Jennifer đã làm lúc đầu, để 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, hãy để tôi nhảy tất cả các cách để kết thúc. Ồ, nếu con số này là quá lớn, hãy để tôi tự ý di chuyển trở lại đến yếu tố thứ hai. 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 đư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à sẽ làm những gì bạn nói với nó để làm. 

Bây giờ điều này có rất thú vị ý nghĩa. 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 là đường thẳng trong biểu đồ này? Mà là đồ thị tuyến tính mà chúng ta gọi n? Vâng, đó là loại xuống dưới cùng của hình ảnh này, phải không? 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à 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. 

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 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 cái gì đó là tuyến tính. Thật vậy, n cubed trông khá xấu. 2 đến n trông khá xấu. n bình phương trông khá xấu. 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. 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. 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, trong tuần đầu tiên, đã đưa ra cái gì đó là nhật ký của nhật ký của n. 

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ể vấn đề, nhưng ngay cả ở đây, thông báo những gì sẽ xảy ra. Khi tôi thu nhỏ, mà của những đường cong sẽ chứng minh là tuyệt đối tồi tệ nhất trong những cái trên màn hình bây giờ? Vì vậy, n cắt hạt lựu trông khá xấu vào lúc này. Nhưng nếu chúng ta thu nhỏ và xem chi tiết của x và trục y, ai sẽ thống trị cuối cùng? 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 cắm vào một số ngày càng lớn số, và bạn sẽ thấy rằng 2 đến n, thực sự, trở nên lớn nhanh hơn nhiều. Nếu chúng ta thực sự thu nhỏ, 2 đến thuật toán n hoàn toàn hút. Tôi có ý nghĩa này sẽ mất khá nhiều thời gian cho các máy tính để khuấy qua. 

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í 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? Thậm chí trong phiên bản đầu tiên của Facebook, như số lượng bạn bè, và 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à 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 thuật toán, như chúng ta sẽ thấy ngày hôm nay. 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. Và các loại của các vấn đề địa điểm như Facebook, Google, và Microsoft, 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 càng những ngày này. 

Được rồi. 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 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 có thể làm cho thời điểm này. 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à 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 cô, nhưng cô khai thác một số chi tiết lần thứ hai là cô ấy không có lần đầu tiên. Đó là những gì? 

Rằng danh sách đã được sắp xếp. 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 về cơ bản tốt hơn. 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. Nhật ký của n chắc chắn là sẽ để thực hiện nhiều, nhiều nhanh hơn trong thời gian dài. Nhưng cô đã phải có cửa sắp xếp cho cô ấy. Bây giờ, tôi đã tự làm điều đó trước trên màn hình máy tính ở đây, nhưng giả sử rằng Jennifer đã phải làm điều đó bản thân? 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 bạn bè đăng ký cho Facebook, hoặc bất kỳ trang web trên mạng Internet các trang web khác nhau có thể cần chỉ số hoặc tìm kiếm trên. 

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 để Jennifer để làm phân loại đó? 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 đã có thể lấy Jennifer, hoặc thậm chí tôi, để sắp xếp những con số trước để rằng cô có thể tận dụng điều đó? Phải không? 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 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, 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 mất bằng cách phân loại những điều trước? 

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. Tôi có căng thẳng một bó toàn bộ hơn quả bóng, nếu giúp phá vỡ lớp băng ở đây. Và nếu bạn không phiền, chúng tôi cần bảy tình nguyện viên - trên, OK. Wow. Vì vậy, chúng tôi không cần phải chi tiêu trên đèn bàn, có vẻ như. Được rồi. Vì vậy, làm thế nào về bạn hai ở phía trước. Làm thế nào về hai người bạn trong trở lại. Vì vậy, đó là bốn. Làm thế nào về bạn ở phía trước năm, sáu và bảy. Ngay tại đó. Bạn của bạn của bạn chỉ ra, để bạn có được giải thưởng. 

Được rồi. Lên đây. Và lý do tại sao chúng ta không có bạn kẻ đi trên trên đây. Tôi sẽ cung cấp cho bạn mỗi một con số. Và đi trước và sắp xếp mình giống hệt với những gì mô tả trên màn hình. 

[Interposing GIỌNG NÓI] 

DAVID J. Malan: OOP, xin lỗi. Lỗi. Được rồi. Vâng, ở đây chúng tôi đi. Thứ năm. Số sáu. Một, hai, ba, bốn, năm, sáu, bảy. Oh, đây là khó xử. 

SPEAKER 2: Tôi sẽ chỉ nhận được một -. 

DAVID J. Malan: Tốt thỏa thuận. Được rồi. Cảm ơn bạn đã tham gia. 

[Vỗ tay] 

OK. Được rồi. Vì vậy, chúng tôi có bốn, hai, sáu, một, ba, bảy, năm. 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 mảng mà chúng ta đang chơi với trước đó. Và tôi đã chọn bảy cho lý do sẽ được chỉ thuận tiện trong một chút. 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. Nếu bạn muốn, đầu tiên, để chào hỏi mặc dù. Vì đây là có được một lúng túng trong vài phút. Giới thiệu bản thân. 

GRACE: Xin chào, tôi là Grace. Tôi là một sinh viên năm hai trong Leverett nhà. 

BRANSON: Hi. Tôi Branson. Tôi là một sinh viên năm nhất trong mối hàn. 

Gabe: Hi. Tôi Gabe. Tôi là một cơ sở trong Cabot. 

NEIL: Tôi là Neil. Tôi là một sinh viên năm nhất trong Matthews. 

JASON: Tôi là Jason. Tôi là một sinh viên năm nhất trong Greenough. 

MIKE: Tôi là Mike. Tôi là một sinh viên năm nhất trong Grays. 

JESS: Tôi là Jess. Tôi là một sinh viên năm hai trong Leverett. 

DAVID J. Malan: Tuyệt vời. Được rồi. 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. 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 đó 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ự sắp xếp chúng. Vì vậy, trước tiên hãy thử này. 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. Đi trước và mất một vài giây, và loại mình từ nhỏ nhất trên trái sang lớn nhất ở bên phải. Đi. 

OK. Tốt. Đó là thực sự darn nhanh. Bây giờ ai đó ở đây, là những gì các thuật toán mà những kẻ áp dụng? 

SPEAKER 1: Ít nhất. 

DAVID J. Malan: OK. Í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à thực sự là một thuật toán. Í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ì. Yeah? 

SPEAKER 1: [nghe được] 

DAVID J. Malan: OK. 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 quyền của họ. 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 có thể nói, nếu điều này, sau đó. Vì vậy, chúng tôi có một số loại xây dựng có điều kiện. 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 một khoảng cách. Vì vậy, có lẽ một số loại vòng lặp xảy ra trong tâm trí của họ. 

Nhưng hãy cố gắng để chính thức hóa đó. Nếu các bạn có thể thiết lập lại trở lại để sắp xếp này. 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 cách hiệu quả là điều này? 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 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. 

Vì vậy, bạn hai chàng trai bốn và hai. Hoặc bạn đặt hàng đúng hay sai? Rõ ràng là không chính xác. Vì vậy, chúng tôi đổi chỗ. Bây giờ tôi sẽ di chuyển sang một bên ở đây và nói, 4-6. Là bạn đúng hay sai? 

Gabe: Đúng. 

DAVID J. Malan: Đúng. Sáu và một? Không. Trao đổi. Vì vậy, đó là hai giao dịch hoán đổi. Sáu và ba? Không. Trao đổi. Sáu và bảy? Có vẻ tốt. Bảy và năm? 

JESS: [nghe được] 

DAVID J. Malan: OK, trao đổi. Và sắp xếp. Được rồi. Vì vậy, rõ ràng là không, phải không? Vì vậy, có được nhiều đang xảy ra. Nhưng, trên thực tế, những kẻ, thậm chí chỉ theo bản năng. tiếp tục di chuyển. Họ không chỉ dừng lại, khi họ sửa chữa một vấn đề. Như vậy. Thật vậy, tôi sẽ có để làm điều tương tự. Tôi sẽ phải sắp xếp các tua trở lại đến đầu của vấn đề này, 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ọ. 

Và bây giờ những gì nên thuật toán của tôi trên đèo thứ hai được? 

SPEAKER 1: Cùng một điều. 

DAVID J. Malan: Cùng một điều. Và điều này, tôi bắt đầu thích, phải không? 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à trở nên giống như một thuật toán, và ít bản năng của con người. 

Vì vậy, bây giờ, ở đây chúng tôi đi một lần nữa. Hai và bốn? Không. Bốn và một? Ah, có thực sự một số làm việc vẫn được thực hiện. Cho và ba? Tốt. Bốn và sáu? Sáu và năm? Sáu và bảy? OK, bây giờ, thực hiện. OK, không. Tôi phải quay trở lại. 

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. Và bây giờ, đó chỉ là một bộ não thực hiện thuật toán này. Một CPU, nếu bạn sẽ. Và thẳng thắn, đó là tài nguyên duy nhất chúng ta sẽ có thể truy cập. 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 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. 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ọ như các bạn đã làm trong tuần không. Vì vậy, hãy tiếp tục làm điều này. 

Hai và một. Hai và ba. Ba và bốn. Bốn và năm. Năm và sáu. Sáu và bảy. Thực hiện? Vì vậy, tôi, nhưng hãy để tôi chơi ủng hộ của ma quỷ. 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 người, biết rằng tôi đang thực hiện? 

SPEAKER 1: Không. 

DAVID J. Malan: Vậy tại sao? 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? Có lẽ hơn một vượt qua. Phải không? 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. Và đó có nghĩa là, có thể có vẫn còn một sai lầm mà tôi cần phải sửa chữa. Vì vậy, tôi chỉ có thể chắc chắn bởi tua, và sau đó kiểm tra, 1-2, hai và ba, ba và bốn, bốn và năm, năm và sáu, sáu và bảy. OK, bây giờ tôi đã không làm việc. 

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, như một int. 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 đó 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à một lần nữa, và một lần nữa, phải không? Bởi vì bạn gặp khó khăn trong một số loại vòng lặp vô hạn. 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 Thuật toán là thực sự hoàn chỉnh. 

Bây giờ, chúng ta hãy đặt một tên trên này. 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 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 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ố. Nhưng làm thế nào hiệu quả là thuật toán này? 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 bảy con người? 

Bốn đến năm? OK, quá nhiều là cuối cùng sẽ là câu trả lời. Nhưng thậm chí sau đó, số lượng cụ thể không phải là quá thú vị. Chúng ta hãy khái quát nó như n. 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 bắt đầu, theo thứ tự ban đầu. Vâng, bao nhiêu bước này tôi có để trên đèo đầu tiên? Đó là một, hai, ba, bốn, năm, sáu, và họ bảy người, vì vậy đó là bảy, sáu -, vì vậy đó là n trừ một bước lần đầu tiên. 

Bây giờ, bao nhiêu bước này tôi có phải thực hiện khi tôi rewound? 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 chỉ cần đi để nói, tất cả các bên phải, khác n trừ đi 1. 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 chỉ tròn một chút. Vì vậy, 2n bước. Vì vậy, 14 bước, cho hay phải mất. 

Bao nhiêu lần tôi đi một bước thời gian tới? Vâng, đó là 3n. thực sự. Và bây giờ, trong trường hợp xấu nhất, cho Ví dụ, bao nhiêu lần tôi đã có đi qua lại, qua lại, thực hiện thuật toán này, trao đổi người từng vượt qua, khoảng? Nó thực sự n bình phương, phải không? 

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, mặc dù nó có thể mất một chút chút thời gian để chìm in 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 các điều khoản của thỏa thuận các con số của họ? Hoàn toàn ngược lại, phải không? Và chỉ để mô phỏng mà, là những gì tên của bạn một lần nữa? 

MIKE: Mike. 

DAVID J. Malan: Mike? OK, Mike, có thể bạn chỉ cần tham gia tôi trên đây chỉ một giây? Trên thực tế, không. Mike xin lỗi, chúng ta hãy quay lại. Tên của bạn là gì nữa? 

NEIL: Neil. 

DAVID J. Malan: Neil. OK, Neil, bạn đến với tôi, nếu bạn không nhớ. 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 trường hợp xấu nhất có thể. Nhưng nhớ lại làm thế nào tôi thực hiện thuật toán của tôi. Tôi so sánh, so sánh, so sánh, so sánh, so sánh, oh. Bây giờ những kẻ đang ra trật tự, vì vậy tôi sửa chữa. Vì vậy, các bạn trao đổi. Nhưng xem xét bây giờ, bao nhiêu xa hơn Neil không phải đi đâu? Nó khoảng n. Bạn biết đấy, nó không thực sự n. 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 số lượng, vì vậy chúng ta hãy gọi nó là n. 

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, Tôi phải làm qua thực sự tẻ nhạt này qua lại, đây là khoảng làm điều này, bước n, tổng cộng n lần, bởi vì nó sẽ đưa tôi nhiều bước để có được Neil tất cả đường đến nơi anh thuộc về. 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. 

Vì vậy, chúng ta hãy gọi bong bóng sắp xếp n bình phương. 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, hiệu quả của thuật toán này, chúng ta sẽ chỉ mô tả hơn nói chung là n bình phương. Đó 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 người, một triệu người, và Câu trả lời là sẽ không thay đổi. 

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. 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 tốt hơn thế này. Vì vậy, thời gian này, tôi sẽ đề xuất một loại thuật toán khác nhau. Đó là rất thông minh của chúng tôi thời gian qua, và các bạn đã đúng khi có bản năng phải chỉ loại trao đổi của cặp. 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 tất cả các số ít theo cách này, và đẩy tất cả các số lớn 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 có thể làm tốt hơn những gì đã được một khá thuật toán phức tạp? 

Vì vậy, chúng ta hãy xem. 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. Ooh, số hai là tốt hơn. Vì vậy, có thể bạn chỉ cần bước về phía trước cho một thời điểm? Này hiện đang được đánh số nhỏ nhất của tôi ứng cử viên, và tôi sẽ nhớ rằng với, như, một biến. Nhưng tôi sẽ tiếp tục kiểm tra. Có một người nào đó mà số là nhỏ hơn? Sáu, không. Oh, có một lần nữa là Neil. 

Vì vậy, tôi sẽ đẩy bạn trở lại loại khái niệm. Neil sẽ đi về phía trước. Và bây giờ, biến mà tôi đang sử dụng để theo dõi những người có nhỏ nhất số được cập nhật để chứa Vị trí của Neil. Vâng, chúng ta hãy xem. Ba, bảy, năm. OK, tôi biết Neil là nhỏ nhất. Điều đơn giản nhất là những gì cho tôi để làm gì bây giờ? 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. Tại sao tôi không chỉ cần đặt nơi ông Neil thuộc, đó là tất nhiên ở đâu? 

Tất cả các con đường ở đầu. Vì vậy, Neil, đi với tôi. Và là tên bạn một lần nữa những gì? 

GRACE: Grace. 

DAVID J. Malan: Grace. OK. Vì vậy, Grace, không may, bạn loại theo cách này. Vì vậy, làm thế nào để chúng ta giải quyết vấn đề này? Phải không? Nếu đây là một mảng, có chỉ có bảy địa điểm. 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 số hữu hạn các lứa tuổi? Cùng một ý tưởng ở đây. Chúng tôi chỉ có một số hữu hạn các số nguyên. 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? 

Cách đơn giản nhất là như thế, Ơn, xin lỗi. Bạn sẽ phải đi qua có như vậy chúng ta có thể làm cho căn phòng. 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. Và có lẽ chúng ta đã làm, bởi vì những gì nếu Grace được đặt ở bên phải? Nhưng chúng tôi biết cô ấy không, bởi vì nếu không, cô sẽ được đứng về phía trước thay vì Neil vào thời điểm này, phải không? Chúng tôi đã kiểm tra số cô ấy. 

Được rồi. 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ẹ. Đố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 lãng phí thời gian của mình, hoặc vô tình trao đổi anh ấy đến chỗ sai. Vì vậy, bây giờ, làm thế nào để tìm kế tiếp yếu tố đó là nhỏ nhất? Hai. Đó là một con số khá tốt, nếu bạn muốn bước về phía trước và Tôi sẽ nhớ đến bạn. Sáu, không tốt. Bốn, ba, bảy, năm, không tốt. Vì vậy, hãy để tôi di chuyển bạn đúng nơi của bạn. Và chúng tôi chỉ có may mắn lần này. 

Bây giờ, tôi sẽ bỏ qua những hai người, và bây giờ làm thêm một đi qua này. Sáu, rằng một số lượng khá nhỏ. Đi về phía trước. Oh, xin lỗi. Số ân sủng là tốt hơn, để bước về phía trước. Bốn. Xin lỗi, Grace. Quay trở lại một lần nữa. Thứ ba là tốt hơn. Bảy. Năm. Và bây giờ tên của bạn là gì nữa? 

JASON: Jason. 

DAVID J. Malan: Jason. Vì vậy, Jason hiện đang là nhỏ nhất yếu tố tôi đã chọn. Mà là ông sẽ đi đâu? Vì vậy, nơi sáu là. Và tên của bạn là một lần nữa? 

Gabe: Gabe. 

DAVID J. Malan: Gabe. Gabe là trong cách. Điều dễ nhất để làm gì? Trao đổi hai chàng trai và tiếp tục. Vì vậy, bây giờ chúng ta hãy xem. Ai là nhỏ nhất? Bốn. Hãy để tôi chỉ cần loại gian lận. Năm sẽ là nhỏ nhất. 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 những người này, với Gabe? Trao đổi một lần nữa. Vì vậy, bây giờ, vẫn còn hơi ra khỏi trật tự. 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. Và thực hiện. 

Vì vậy, câu trả lời là như nhau. Kết quả cuối cùng là như nhau. Mà của hai thuật toán này là tốt hơn? Điều thứ hai, tôi nghe. Tại sao? 

SPEAKER 3: Đó là bước n [không nghe được]. 

DAVID J. Malan: Đó là n bậc nhất. Thú vị. Như vậy là nó mặc dù? Vì vậy, làm thế nào tôi tìm thấy phần tử nhỏ nhất? 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? Tôi đã có một nhìn tất cả các cách ở cuối, phải không? Bởi vì trong đó trường hợp xấu nhất, những gì nếu Neil đã ở đây? 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. Nhưng, OK. Vì vậy, sửa chữa Neil. Hãy nhớ rằng, một phút hoặc lâu hơn trước đây. 

Nhưng làm thế nào tôi tìm kế tiếp phần tử nhỏ nhất? Đó là n trừ đi 1, hoặc n trừ đi 2 thực sự, từ số bước. Vì vậy, OK. Vì vậy, tôi đã n trừ đi 2. Được rồi. Để cảm thấy tốt hơn một chút. Được rồi. Bao nhiêu bước trong thời gian tới để tìm số ba? Vì vậy, n trừ đi 4. Vì vậy, nó giảm, một ít bước trên mỗi lần lặp. Vì vậy, điều này không cảm thấy tốt hơn, phải không? 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ừ 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. 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 tấm ở mặt sau có công thức, nếu bạn thêm hàng loạt các con số, tổng số bước là những gì sẽ được rằng tôi có ở đây? 

Đây là một trong những, thích, n trừ 1, lần n, chia cho 2. 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. 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, 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 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 nhân này ra, đó là thực sự n vuông. Đó không phải là cảm giác quá tốt. n trừ đi n hơn 2. 

Nhưng đây là vấn đề. Khoa học máy tính, khi các vấn đề bắt đầu để có được thú vị là khi n được thực sự lớn. Và khi n được thực sự lớn, trong đó các giá trị là sẽ thống trị tất cả của những người khác? Đó là loại n bình phương, phải không? Có, chia cho 2 là khá tốt. 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ỷ mẩu dữ liệu, OK, vì vậy bạn nhanh gấp hai lần. 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 lớn hơn và lớn hơn. 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. 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à 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 tham gia ngày càng ít bước mỗi lần. 

Nó không thực sự nhanh hơn cơ bản. 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 ngày, với n đủ lớn, nó vẫn còn sẽ cảm thấy khá chậm. Vâng, hãy để tôi lấy một vượt qua cuối cùng ở đó. Đó là những gì tôi sẽ gọi lựa chọn loại. Các bạn có thể thiết lập lại chính mình một lần cuối cùng? Và trong trường hợp cuối cùng này, tôi sẽ đề xuất một cái gì đó gọi là sắp xếp chèn. Sắp xếp chèn là, khái niệm, một chút khác nhau. 

Thay vì đi lại và chọn phần tử nhỏ nhất, tôi chỉ cần đi để đối phó với mỗi kẻ như tôi gặp họ, và chèn chúng vào vị trí chính xác của họ. 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. Trường hợp không thứ tư thuộc về ai? Tôi đã không bắt đầu sắp xếp bất cứ điều gì, Grace để được ở lại ngay tại đó. 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 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. 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? 

BRANSON: Branson. 

DAVID J. Malan: Branson. Vì vậy, Branson là số hai. Vì vậy, tôi sẽ đưa các bạn ra trong một khoảnh khắc. Và bây giờ, nơi nào bạn thuộc trong mảng này? Vì vậy, ở bên phải của Grace. 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. Nơi nào chúng ta đưa bạn? Vì vậy, chúng ta sẽ trượt bạn đến trái, và chèn Branson có. Nhưng bây giờ tôi cho rằng các bạn đã làm xong. Nhưng thông báo, tôi không sử dụng không gian thêm. Nó vẫn còn 2 yếu tố ở đây, 5 trên đây. 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? 

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? Bạn có may mắn một lần nữa. Vì vậy, bạn có thể ở ngay tại đó. 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. 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? 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 Trong nháy mắt, cảm thấy khá thông minh, xem những gì sắp xảy ra. Nếu bạn có thể bước về phía trước. 

Nơi nào chúng ta muốn đặt Neil? Vì vậy, rõ ràng là ở đây, vậy làm thế nào chúng tôi nhận được Neil có? Chúng ta hãy làm điều này từng bước. Gabe, nơi nào bạn cần phải đi? Vâng, do đó, có một bước tiến lớn, hoặc hai nửa bước để làm cho một bước ở đó. Grace, nơi bạn đi? Tốt. Vì vậy, một bước. Và cuối cùng, Branson? Một bước. Và bây giờ chúng ta có thể đưa Neil vào vị trí. 

Vì vậy, bây giờ, tiếp tục logic này. Mặc dù chúng tôi không thay đổi Neil hơn, và hơn và hơn, để đưa anh ta 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ể 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ả những người này. Giả sử rằng có một số, tiêu cực một, sau đó chúng ta phải thay đổi tất cả các sinh vật này. 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 chuyển các chi phí từ quá trình lựa chọn để chèn 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ì đó số bước. Và số lượng các bước chỉ đi tăng như tôi chọn số lượng nhiều hơn, 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. 

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. 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 khác nhau. Thực hiện rất tốt. 

[Vỗ tay] 

Được rồi. Có bạn đi. Cảm ơn - 

BRANSON: [nghe được] giữ các con số. 

DAVID J. Malan: Không, bạn có thể giữ số là tốt. Được rồi. Độc đáo được thực hiện. Được rồi. 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, chính xác những gì vừa xảy ra đây như sau. Tôi sẽ đi trước và kéo lên Firefox. 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. 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. 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 để có được nó làm việc. Và những gì tôi sẽ làm gì với điều này trình diễn như sau. 

Ở 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 nút dừng lại. 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 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 cộng và phóng to thu nhỏ, mà tò mò cho bạn thấy các nút hơn. Vì vậy, chỉ FYI nếu bạn chơi với điều này ở nhà. 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ễ, 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. 

Vì vậy, tôi cho rằng đây là một hình dung của thuật toán đầu tiên 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. Cái nhìn sâu sắc quan trọng để hình dung này là chiều cao của thanh đại diện cho kích thước của số. Vì vậy, các cao thanh, lớn hơn số lượng. Ngắn hơn thanh, nhỏ hơn số lượng. 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, trao đổi số lớn và nhỏ, do đó, số lượng nhỏ đến trước và số lượng lớn đi bên phải. 

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 sẽ quay trở lại để bắt đầu. Và dự đoán này. 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 quá trình lặp đi lặp lại. 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 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ề thuật toán này. 

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 một máy tính mới. 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 rõ ràng hơn với con người, mà lớn con số này đang nổi lên đến đỉnh, và những con số nhỏ sủi bọt xuống phía dưới. Và bây giờ điều này ở đây được sắp xếp. 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ó giúp bạn đếm bao nhiêu so sánh, hoặc có bao nhiêu giao dịch hoán đổi có thực sự được thực hiện. 

Vâng, chúng ta hãy thử một trong những người khác chúng ta đã thấy. 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 là một lỗi nhỏ. Chúng ta hãy chấp nhận rủi ro và chạy nó một lần nữa. Có chúng tôi đi. Vì vậy, chúng ta hãy làm lựa chọn sắp xếp. Tôi không biết lý do tại sao trình đơn xuất hiện ở đó. Chúng ta hãy phóng to để khắc phục điều đó lỗi, thay đổi này đến 50. Ah, chúng ta hãy thực sự làm mà nhanh hơn nhiều. Năm mili giây hoặc lâu hơn, và bắt đầu. 

Vì vậy, đây là lựa chọn sắp xếp. 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. Chúng tôi đã đi qua mảng và chọn phần tử nhỏ nhất một lần nữa, và một lần nữa, và một lần nữa. Bây giờ tôi cho rằng vẫn còn khá xấu. 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 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. Nhưng chúng ta chỉ nói những gì? Có lẽ 40 hoặc hơn thanh đây? Chúng tôi không nói 40 triệu USD. 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ể. 

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 sắp xếp chèn. Và bây giờ nó thực sự lỗi vì đơn thực sự không phải ở dưới đó. 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. Reo, bắt đầu và dừng lại. 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 chèn con người, hoặc trong trường hợp này, các quán bar vào vị trí thích hợp của họ. Và nó đã được thực hiện trước khi Tôi quay lại. Nhưng điều này cũng vậy, trên lý thuyết, vẫn còn n bình phương. 

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. 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 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. 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 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 để mô tả thời gian chạy của một số thuật toán. Bao nhiêu bước nó thực sự mất? 

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. Nhưng hãy để tôi đi trước và nói rằng đây sẽ là O lớn hơn ở đây. Và cho tôi giới thiệu một khác biểu tượng, một omega vốn. Omega là có được điều ngược lại, về cơ bản, các lớn O. Trong khi O lớn 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 theo n, omega sẽ được bao nhiêu thời gian có thể nó mất trong trường hợp tốt nhất. 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. 

Vì vậy, chúng ta hãy bắt đầu một cái gì đó đơn giản. Hãy để tôi bắt đầu với một tìm kiếm tuyến tính. Vì vậy, không phân loại. Chúng tôi sẽ gọi tìm kiếm tuyến tính này. Và bây giờ, làm cho một ít bảng trong số này. 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à nó sẽ đưa tôi để tìm một số sự lựa chọn tùy ý? Và có n tổng số cửa hoặc n tổng số. Trường hợp tồi tệ nhất. Bao nhiêu bước tôi sẽ phải thực hiện để tìm số 50 trong một mảng n cửa? Và tại sao? Bởi vì nó có thể là tất cả các cách hơn vào cuối. 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 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. 

Những gì về trường hợp tốt nhất, nếu bạn thực sự may mắn? Nó chỉ là sẽ đi trước một bước, hoặc một hằng số của các bước. Vì vậy, chúng tôi sẽ mô tả đó như 1. Vì vậy, điều này là khá tốt. Bây giờ những gì nếu chúng tôi làm gì thích tìm kiếm nhị phân? 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? 

[Interposing GIỌNG NÓI] 

DAVID J. Malan: Vì vậy, trên thực tế, tôi nghe nó trong một vài nơi. 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 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ị, nếu nó có, nhưng có một nhược điểm. 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? Nó phải được sắp xếp. 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 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 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ì bạn có thể bỏ lỡ nó. 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ó thực sự không được sắp xếp. Do đó, có loại một chi phí ẩn để sử dụng một cái gì đó như thế này. 

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 - oh, thực sự chúng ta hãy đi vào ô này. Tìm kiếm nhị phân trong trường hợp tốt nhất? Nó cũng là 1 nếu nó chỉ xảy ra được ở chính giữa của mảng, hoặc giữa danh bạ điện thoại. Bây giờ chúng ta hãy làm bong bóng sắp xếp. 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. 

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? n bình phương. Vì vậy, tôi sẽ vẽ đó. Ooh, chữ viết tay của tôi trông còn tệ hơn khi nó dự kiến ​​là lớn. Được rồi. Vì vậy, đó là n bình phương. 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? 1, tôi nghe. 

SPEAKER 1: n. 

DAVID J. Malan: n, tôi nghe. 

SPEAKER 1: 2. 

DAVID J. Malan: 2, tôi nghe. Tôi nghe 3? Được rồi. 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 đề nghị, 1. 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. 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 đượ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ố có thể tôi thực sự kiểm tra để chắc chắn? Vâng, chỉ cần 1, có nghĩa là có n trừ 1 yếu tố có thể được ra khỏi 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 điều được sắp xếp. Vì vậy, 1 không đúng ở đây. Vì vậy, tối thiểu, bao nhiêu Tôi phải nhìn vào? 

[Interposing GIỌNG NÓI] 

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 yếu tố để đảm bảo rằng nó không phải là ra lệnh. 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à cho rằng, như n được lớn, họ không thú nào. Vì vậy, đó là bong bóng sắp xếp. Và bây giờ, chúng ta hãy làm những hai năm. Lựa chọn sắp xếp, và sau đó chúng tôi sẽ làm sắp xếp chèn. 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 tốt hơn so với tất cả các. Được rồi. 

Trường hợp xấu nhất chạy là gì thời gian lựa chọn loại? 

SPEAKER 4: n bình phương. 

DAVID J. Malan: n vuông, tôi nghe. Nhưng tại sao n bình phương, trực giác? 

SPEAKER 4: Bởi vì chúng ta chỉ cần làm điều đó. 

DAVID J. Malan: Bởi vì chúng ta chỉ cần làm điều đó. OK. Tốt câu trả lời. Nhưng trực giác, tại sao lựa chọn loại n bình phương? 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? Chúng tôi phải giữ quét qua, là bạn nhỏ nhất, là bạn nhỏ nhất, là bạn nhỏ. Và cấp, chúng tôi đã có thể mang n bước, sau đó n trừ đi 1, sau đó n trừ đi 2. 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 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. Vì vậy, tôi sẽ gọi n này bình phương. 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ó sẽ đưa tôi? 

SPEAKER 5: [nghe được] 

DAVID J. Malan: Đó là không may vẫn n bình phương, phải không? 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, 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 số, bất cứ nơi nào người cô ấy có thể có được. Nhưng làm thế nào để tìm kế tiếp số lượng nhỏ nhất? Tôi phải làm vượt qua khác. 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? Đây là một danh sách đã được loại, số một, số hai, số ba, số bốn. Nhưng tôi là một máy tính. Tôi chỉ có thể nhìn vào một điều tại một thời điểm. 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, ooh, điều này có vẻ đúng. 

Tôi chỉ có thể xét xử đúng đắn trong lựa chọn loại bằng cách chọn số nhỏ nhất. 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ề 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 hoặc một bộ cửa đằng sau đó là số, cách duy nhất tôi biết rằng một là nhỏ nhất? 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. 

Nhưng làm thế nào để sau đó xác định rằng hai là nhỏ nhất tiếp theo? 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. 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, chúng ta đã nói nó thực hiện? Nó cũng là n bình phương. Và làm thế nào về với trường hợp tốt nhất? Chúng tôi sẽ rời khỏi đó như một cliffhanger. 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 về cơ bản làm tốt hơn tất cả các, tất cả phải không? 

Vì vậy, suy nghĩ cho mình những gì chèn loại sẽ là. Vâng, đó là không phải là rất ấn tượng, bởi vì tôi là người duy nhất mà nhìn thấy sự thay đổi. Wow. OK. Vì vậy, ở đây chúng ta có một phần nào trình diễn khác nhau. 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 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 đã không nhìn nhưng được gọi là hợp nhất phân loại. 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. 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ố 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 n, vậy để nói chuyện. 

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, và chúng tôi đã điện thoại cuốn sách rách, và Jennifer, và chúng tôi chung 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 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 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 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 về cơ bản tốt hơn. 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ể không hiểu biết như vậy mà Jennifer đã làm. 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 việc tinh chỉnh một chút, trao đổi theo thứ tự này, có thể chèn hoặc chọn. Nhưng vào cuối ngày, tôi đã làm rất nhiều đi bộ lúng túng lại. 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 và chinh phục. 

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ẽ để 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 đó giảm một nửa, và sau đó giảm một nửa. 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 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 đó 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. Và lặp đi lặp lại một lần nữa và một lần nữa. 

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. 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. Chúng tôi có n phương trên bên trái, n vuông ở giữa, và n đăng nhập n bên phải. Do đó, có cliffhanger thực sự của bạn. Chúng ta sẽ thấy bạn vào thứ hai. 

[Vỗ tay]