SPEAKER: Được rồi, đây là CS50. Đây là cuối tuần ba, và nếu bạn chưa tận dụng đã có, biết rằng sẽ có bữa ăn trưa thứ sáu này như thường lệ, nơi bạn có thể thưởng thức cuộc trò chuyện tốt và thực phẩm tại Lửa và Băng với một số CS50 của nhân viên và các bạn cùng lớp. Đi đến URL này ở đây. 

Bây giờ bạn có thể nhớ lại, hoặc bạn có thể sớm được làm quen với, những điều này ở đây, mà được đưa ra ở cuối của học kỳ cho nhiều lớp học. Cuốn sách màu xanh được gọi là kỳ thi, trong đó bạn viết câu trả lời cho các kỳ thi. Bây giờ tôi có ở đây 26 chẳng hạn cuốn sách màu xanh, trên mỗi người được viết bằng một cái tên, từ A đến Z. Và thực sự những cái tên đơn giản, A thông qua Z. Và một trong các mục tiêu trong tầm tay hôm nay là có được để tiếp tục những gì chúng tôi bắt đầu vào thứ hai, mà không phải là rất nhiều nhìn vào mã, nhưng thực sự nhìn vào những ý tưởng và giải quyết vấn đề. Một trong những mục tiêu và lời hứa của khóa học này là để dạy cho bạn để suy nghĩ nhiều hơn cẩn thận, có phương pháp hơn, và để giải quyết vấn đề hiệu quả hơn. Và quả thực, chúng ta có thể làm điều đó thực sự mà không cần chạm vào một dòng mã. Vì vậy, tôi có một vài con voi ở đây ngày hôm nay, màu cam và màu xanh, nếu chúng ta có thể có được một tình nguyện viên, có thể từ xa trở lại hơn bình thường. Làm thế nào về ngay, nhanh lên xuống. Mục tiêu trong số đó là có được để giúp đỡ cộng với quản lý kỳ thi này ở đây. Tên của bạn là gì? 

TƯỢNG: Mary Beth. SPEAKER: Mary Beth, đi lên trên. Hãy để tôi có được microphone ở bên em. Rất vui được gặp bạn. 

TƯỢNG: Rất vui được gặp bạn. SPEAKER: Được rồi, vì vậy tôi có ở đây cuốn sách màu xanh từ A đến Z, và tôi sẽ giả vờ rằng Tôi có một trong các sinh viên, và họ đang đến trong hơi ngẫu nhiên ở phần cuối của một khối thi ba giờ, vì vậy họ kết thúc trong một số để bán ngẫu nhiên như thế này. Bây giờ công việc của bạn chỉ trong một thời điểm sẽ để be-- này thực sự là như thế nào họ nhận được lại vào cuối năm lớp, có khả năng nhất. Công việc của bạn bây giờ là có được, khá đơn giản, để sắp xếp những cuốn sách màu xanh cho chúng tôi từ A đến Z. 

TƯỢNG: Ồ, đây là sẽ mất mãi mãi. 

SPEAKER: Và chúng ta sẽ xem khi bạn làm điều này, không có áp lực. TƯỢNG: Không, không có áp lực hay bất cứ điều gì. 

SPEAKER: Và cho vui, chúng ta hãy đưa ra một bộ đếm thời gian. 

TƯỢNG: Vì vậy, nhiều niềm vui, rất nhiều niềm vui. 

SPEAKER: Tôi có thể giữ mic cho bạn. Được rồi, chúng tôi đã chỉ tăng gấp đôi tốc độ của chúng tôi. Vì vậy, trong khi chờ đợi, hãy để tôi đặt ra những gì sẽ là câu hỏi dành cho Mary Beth là những gì cô ấy làm, làm thế nào là cô đi về giải quyết này? Và trong thực tế, bạn có thể không có bao giờ nghĩ về một cái gì đó rất đơn giản như khi bạn chọn tăng 26 cuốn sách như thế này, mà không có một tự nhiên ra lệnh cho họ. Quá trình này là gì mà bạn thực sự sử dụng không? Có khá ngẫu nhiên chỉ chọn một trong những đầu tiên bạn thấy và đặt nó trong vị trí của nó? Đừng đầu tiên bạn di chuyển bàn tay của bạn xung quanh tìm kiếm A sau đó tìm kiếm B? Bạn hãy nhìn vào một cặp chúng cạnh nhau và chỉ nói, chờ một phút, điều này là không đúng, và sau đó trao đổi thứ tự? Chúng tôi đã nhìn thấy vào hôm thứ Hai rằng có một số cách trong đó chúng ta có thể làm điều này, và thực sự là chúng tôi gần kết thúc ở đây, Tôi sẽ để ý có lẽ những gì Mary Beth đang làm. Chúng tôi có một vài cọc có vẻ như, một lớn hơn một, ba nhỏ hơn. 

TƯỢNG: Tôi ra lệnh cho họ khi tôi tìm thấy hai chữ cái mà tôi biết ở bên nhau trong một chuỗi, Tôi đặt chúng lại với nhau vì vậy mà tôi không phải lo lắng về việc giữ gìn theo dõi của một hàng toàn bộ cuốn sách. Nó chỉ là, oh, A là lần đầu tiên, Tôi đã có chồng này ở đây. SPEAKER: Vì vậy, gần như một mảnh ghép mà có hình dạng quyền phù hợp với nhau. TƯỢNG: Khá nhiều, yeah. SPEAKER: OK, tuyệt vời. Và bây giờ mỗi cọc có lẽ đó là sắp xếp? 

TƯỢNG: Vâng. 

SPEAKER: Được rồi, từ A đến Z. Tất cả đúng, xin chúc mừng, bạn đã làm nó. Bạn có sự lựa chọn của bạn. Màu xanh? Được rồi, cảm ơn bạn vì điều đó. Vì vậy, Mary Beth đã đề xuất những cách tiếp cận cô, nhưng cách tiếp cận khác là những gì làm thế nào bạn có thể đi về sắp xếp những việc này? Những gì bạn sẽ làm gì? Biên bản để đánh bại sẽ có được một phút và 50 giây hoặc lâu hơn, cộng với những cái tôi quên đếm. Những gì bạn sẽ làm gì? Vâng? TƯỢNG: Lấy chồng. Bắt đầu từ đầu. Kiểm tra giấy tờ của bạn. Và nếu một trong những đầu cao hơn, có thể, họ đang có, một trong những chốt là cao hơn, sau đó chuyển đổi chúng. 

SPEAKER: OK, vì vậy bắt đầu ở phía trên và phía dưới, và sau đó làm việc theo cách của bạn hướng nội như vậy, trao đổi chúng? OK, vì vậy một chút tương tự với tinh thần bong bóng sắp xếp, nhưng việc lựa chọn những thái cực không phải là cặp liền kề. Nhưng ngắn của nó là có chắc chắn là một loạt các cách khác nhau chúng ta có thể làm điều này, và thẳng thắn, tôi nghĩ rằng bạn loại áp dụng một vài phương pháp tiếp cận, phải không? Bạn đã thực hiện sắp xếp của bốn cọc được sắp xếp, và sau đó hiệu quả hợp chúng lại với nhau. Và đó là, dám nói, một kỹ thuật hoàn toàn. Bạn đã không xử lý nó như một chồng, bạn chia vấn đề thành bốn quads, nếu bạn muốn, và sau đó bằng cách nào đó sáp nhập chúng cuối cùng. 

Vì vậy, hãy cân nhắc, cuối cùng, làm thế nào khác chúng ta có thể làm điều này. Chúng tôi chính thức hóa khái niệm các bong bóng sắp xếp thời gian qua, và bong bóng sắp xếp thu hồi là một thuật toán mà chúng tôi hình dung với tám người bạn cùng lớp của bạn lên đây, dường như được sắp xếp ngẫu nhiên lần đầu tiên. Và sau đó chúng tôi quyết định cặp, nếu hai yếu tố là ra lệnh, chỉ đơn giản là trao đổi chúng. Vì vậy, bốn và hai là rõ ràng là ra lệnh, vì vậy hai bạn cùng lớp chuyển vị trí. Và sau đó chúng ta lặp đi lặp lại với bốn và sáu, sau đó sáu và tám, trên mỗi lần lặp, di chuyển sang phải. 

Vì vậy, cho tám người, có bao nhiêu cặp so sánh những gì đã làm trong khi đi bộ từ trái sang phải trong một sự lặp lại như vậy? Có bao nhiêu so sánh? Bảy, phải không? Bởi vì nếu có tám mọi người nhưng bạn có cặp họ và bạn tiếp tục di chuyển một hop bên phải, bạn sẽ không có tám so sánh bởi vì bạn không thể so sánh một yếu tố chống lại chính nó, hoặc nó sẽ chỉ là vô nghĩa, vì vậy bạn có bảy. Hay rộng hơn, nếu chúng tôi có n người, chúng tôi làm n trừ đi 1 so sánh với bong bóng sắp xếp. 

Vì vậy, chúng ta hãy xem xét bây giờ như thế nào tốt hay bong bóng xấu loại thực sự là, và cố gắng để cung cấp cho mình vốn từ vựng với để thuật toán phê bình như thế này, và ngay sau đó của chúng ta. Vì vậy, đầu tiên vượt qua thông qua bong bóng sắp xếp, lần đầu tiên Tôi đi từ trái qua phải của sân khấu, đã cho tôi n trừ đi 1 so sánh. Và đó sẽ là của tôi đơn vị đo lường, phải không? Tôi đã loại nói chuyện và đi dạo, hơi nhanh, hơi chậm, để đếm số của tôi giây không đặc biệt nói, nhưng đếm số lượng hoạt động mà tôi đã làm vào thứ hai, so sánh hai người, mà cảm thấy như một đơn vị tốt đẹp của các biện pháp. 

Vì vậy, n trừ đi 1 bước là lần đầu tiên, nhưng sau đó những gì xảy ra sau đó? Một trong những xu hướng tăng của một đường chuyền là gì thông qua một danh sách khác được phân loại? Những gì bạn có thể cho tôi biết về các yếu tố là ai tất cả các cách trên không? Vâng? Đó là yếu tố lớn nhất, phải không? Số tám, mặc dù cô bắt đầu ở đây, mỗi khi tôi so sánh cô với một người hàng xóm, cô vẫn giữ nổi lên bên phải bên của danh sách. Và quả thực, đó là nơi các thuật toán được tên của nó. 

Bây giờ bằng cách logic, có bao nhiêu so sánh cần tôi thực hiện trên lần thứ hai Tôi thực hiện qua đó từ trái sang phải? n trừ đi 2, phải không? Nó sẽ chỉ lãng phí thời gian của tôi nếu tôi giữ tám so sánh với một người nào đó khác vì chúng ta đã biết cô đã ở đúng nơi. Vì vậy, đó là một chút của một tối ưu hóa, do đó, qua tiếp theo là có được cộng với n trừ đi hai bước, trong đó n là số lượng người. Bây giờ bạn có thể loại suy, thậm chí nếu bạn không phải là một nhà khoa học máy tính, cách này kết thúc. Vào cuối của thuật toán này, có lẽ bạn đã có chỉ là một so sánh lại. Bạn cần phải loại sửa chữa bắt đầu của danh sách trong trường hợp hai và một là ra lệnh và nên là một và hai, vì vậy đây đáy hiện tại cộng thêm 1 so sánh thức. 

Bây giờ các dấu chấm, dấu chấm, dấu chấm loại sóng đó là tay ở một số chi tiết juicier, nhưng chúng ta chỉ cần đi trước và đơn giản hóa. Nếu bạn nhớ lại từ mức cao trường học, thẳng thắn, rất nhiều bạn có cuốn sách toán học mà có một chút cheat sheet trên trang bìa hoặc bìa sau cho thấy bạn summations loạt như những gì điều này cuối cùng thêm lên đến. Trong trường hợp chung, nếu bạn có một biến như n, và thực sự thế này, nếu bạn nhìn của bạn cuốn sách toán học cũ, bạn sẽ thấy rằng điều này thực sự thêm lên đến số tiền này ở đây, n lần n trừ đi 1 tất cả chia cho 2. Vì vậy, bây giờ hãy để tôi chỉ định điều này là đúng, như vậy một bước nhảy vọt của đức tin, đó là những gì này tóm tắt đến, và chúng ta có thể chứng minh rằng trong trường hợp tổng quát hơn. Nhưng bây giờ chúng ta hãy mở rộng này ra. Vì vậy, hãy nhân này ra, vì vậy đó là n bình phương, trừ đi n, tất cả chia cho 2. Đó là thực sự n bình phương, chia cho 2, trừ n hơn 2, vì vậy đó là tất cả tốt đẹp và thú vị. Nhưng những gì xảy ra nếu chúng ta tại plug-in một giá trị? Giả sử tôi không có tám người, nhưng nói một triệu USD. Và một triệu chỉ vì đó là một số lượng khá lớn, hãy cắm vào đó và xem những gì sẽ xảy ra. Vì vậy, nếu tôi cắm một triệu USD vào công thức Tôi sẽ nhận được một triệu phương, chia cho 2, trừ một triệu, chia cho 2. Bây giờ những gì mà sẽ bằng? Vì vậy, 500 tỷ, trừ đi 500.000. Và nếu tôi thực sự làm mà toán học ra, có nghĩa là mà sắp xếp một triệu những người có các loại bong bóng có thể đưa tôi 499.999.500.000 bước hoặc so sánh cuối cùng, chúng tôi chỉ ngoại suy. 

Mà cảm thấy khá chậm, nhưng thẳng thắn đo một đầu vào đặc biệt như thế này, không phải là tất cả những gì kể. Nhưng thực sự nó không cho thấy có đến n được lớn hơn và lớn hơn, thuật toán này loại cảm thấy tồi tệ hơn và tồi tệ hơn, hoặc bạn thực sự bắt đầu cảm thấy nỗi đau đó lũy thừa, n là hình vuông, được biết thêm khá nhanh. Và chi tiết này không phải là bị mất trên người, trên thực tế một số năm trước, một thượng nghị sĩ nào đó là ai vận động, ngồi xuống cho một cuộc phỏng vấn với Eric của Google Schmidt, Giám đốc điều hành vào thời điểm đó, và đã được thử thách với một câu hỏi giống như chúng ta đang khai thác hiện nay. Chúng ta hãy có một cái nhìn. 

[VIDEO xem lại] 

-Senator, Bạn đang ở đây tại Google, và tôi thích suy nghĩ của tổng thống như một cuộc phỏng vấn việc làm. Bây giờ, thật khó để có được một công việc làm tổng thống, và bạn đang trải qua sự khắc nghiệt bây giờ. Nó cũng khó để có được một công việc tại Google. 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, và điều này là từ Larry Schwimmer. What-- các bạn nghĩ tôi đùa, đó là ngay tại đây. Cách hiệu quả nhất để là gì sắp xếp một số nguyên triệu 32-bit? 

-Well-- 

Tôi xin lỗi, maybe-- 

Không, không, không. Tôi nghĩ rằng các loại bong bóng sẽ là con đường sai để đi. 

-Thôi Nào, người nói với anh điều này? Tôi không nhìn thấy máy tính khoa học trong nền của bạn. 

-We've Có gián điệp của chúng tôi trong đó. 

-Ok, Hãy hỏi một khác nhau câu hỏi phỏng vấn. 

[END IMG xem lại] 

SPEAKER: Vì vậy, nói về mặc dù con số cụ thể, sẽ không có tất cả những gì hữu ích. Nó không phải là một bài học cuộc sống mà bong bóng sắp xếp, cho một triệu đầu vào, có thể mất bao nhiêu là 500 tỷ bước. Bạn có thể không thực sự khái quát quá hiệu quả từ đó và đưa ra quyết định thiết kế tốt khi viết chương trình. Vì vậy, hãy tập trung mặc dù về cách chúng ta có thể đơn giản hóa kết quả này. 

Vì vậy, tôi đã đánh dấu màu vàng ở đây kết quả của n bình phương chia cho 2, do đó, một triệu phương chia cho 2, và sau đó Tôi đã nhấn mạnh những gì câu trả lời cuối cùng là một khi chúng ta trừ đi n chia cho 2. Và tuyên bố tôi sẽ làm bây giờ, người có hề quan tâm nếu bạn trừ đi một chút n cũ hơn 2 khi lần đầu tiên một phần của công thức này là như vậy lớn hơn nhiều? Nó chi phối khác hạn, n bình phương chia cho 2 có kích thước lớn, rõ ràng, như n được lớn như một triệu, đó là có thực sự là một sự khác biệt lớn ở cuối ngày giữa 500 tỷ và 499.999.500.000? Không thực sự. Và vì vậy những gì chúng ta sẽ làm như các nhà khoa học máy tính bỏ qua những điều kiện bậc thấp hơn và có một cái gì đó như thế này và thực sự chỉ đơn giản hóa nó đến hạn đó sẽ có vấn đề. Lớn hơn các bộ dữ liệu của chúng tôi có được, lớn hơn cơ sở dữ liệu của chúng tôi có được, các trang web nhiều hơn chúng ta phải tìm kiếm, càng có nhiều bạn bè bạn có trên Facebook. 

Khi n càng lớn hơn, chúng tôi thực sự sẽ quan tâm lớn nhất hạn trong bất kỳ phân tích như vậy thực hiện các thuật toán của chúng tôi. Và tôi sẽ nói, bạn biết những gì, bong bóng sắp xếp là vào thứ tự của O lớn, vào thứ tự của n bình phương. Nó không chính xác n phương như chúng ta đã thấy, nhưng những người thực sự quan tâm về những điều khoản nhỏ hơn, và thẳng thắn, những người thực sự quan tâm nếu chúng ta chia cho 2? Đó chỉ là một yếu tố không đổi. Và là 500 tỷ đồng so với 250 tỷ thực sự là vấn đề lớn? Tôi chỉ có thể chờ đợi một năm, cho máy tính xách tay của tôi theo nghĩa đen được nhanh gấp hai lần trong phần cứng, và sắp xếp của sự khác biệt chỉ mất đi một cách tự nhiên theo thời gian. 

Những gì chúng tôi quan tâm là các biểu hiện, phần của biểu thức đó là sẽ thay đổi như là đầu vào của chúng tôi được lớn hơn và lớn hơn. Và quả thực, trong thế giới thực, đó là những gì đang xảy ra ngày càng là đầu vào cho các vấn đề của chúng tôi và thuật toán được nhận được lớn hơn. Vì vậy, O lớn là có được các ký hiệu, các ký hiệu tiệm cận, mà chúng tôi chỉ sử dụng như là các nhà khoa học máy tính để mô tả hiệu quả hoạt động, hoặc thời gian chạy, của một thuật toán. Vì vậy, chúng ta có thể so sánh các thuật toán trên các máy tính khác nhau bằng văn bản bởi những người khác nhau, bằng cách sử dụng một số số liệu về cơ bản tương tự như số lượng so sánh bạn làm, hoặc có thể là số lượng giao dịch hoán đổi bạn đang làm. 

Những gì chúng ta sẽ không số là số lượng thời gian mà đi trên đồng hồ trên tường thường. Những gì chúng ta sẽ không phải lo lắng về là bao nhiêu bộ nhớ bạn đang sử dụng ngày hôm nay tại ít nhất, mặc dù đó là một nguồn tài nguyên chúng ta có thể đo lường. Chúng tôi sẽ cố gắng để căn cứ phân tích của chúng tôi trên chỉ là hoạt động cơ bản, những người, thẳng thắn, bạn có thể xem trực quan nhất. Vì vậy, với một cái gì đó như O lớn của n phương, tôi cho rằng O n bình phương là một trên ràng buộc về cái gọi là chạy thời điểm bong bóng sắp xếp. Nói cách khác, nếu bạn muốn khẳng định rằng có giới hạn trên này có bao nhiêu bước một thuật toán có thể mất, nó sẽ được trong O lớn của n phương trong trường hợp này, một trên ràng buộc. 

Nếu tôi thay vì thay đổi câu chuyện là không về bong bóng sắp xếp, nhưng về điều này ràng buộc trên. Bạn có thể nghĩ về một thuật toán mà chúng tôi đã nhìn đã có trên ràng buộc, tối đa đo thời gian hoặc hoạt động, sẽ được cho là được bao quanh bởi n, chức năng tuyến tính, không phải là một bậc hai đó là cong? Một thuật toán là cái gì luôn luôn có không hơn như n bước, hoặc Bước 2n, hoặc các bước 3n? Vâng? 

TƯỢNG: Tìm kiếm số lượng lớn nhất trong một danh sách? 

SPEAKER: Perfect, tìm kiếm số lượng lớn nhất trong danh sách. Nếu tôi đưa ra một danh sách các người chẳng hạn, mỗi người đang nắm giữ một số, số lượng tối đa là những gì các bước nó sẽ đưa tôi, một người khá thông minh, để tìm thấy những người lớn nhất trong danh sách đó? n, phải không? Bởi vì trong trường hợp xấu nhất, nơi có giá trị lớn nhất là gì? Phải, tất cả các cách ở cuối. Vì vậy, trong trường hợp xấu nhất trên ràng buộc, tôi có thể phải đi tất cả các cách ở đây và như thế nào, oh, đây là số tám, hoặc bất cứ điều gì giá trị là. Bây giờ nó sẽ chỉ là ngu ngốc nếu tôi tiếp tục đi, phải không? Tìm kiếm ngày càng nhiều yếu tố nếu cuối cùng của họ là ở đó? Vì vậy, chắc chắn, n là một ràng buộc trên. Tôi không cần phải bước nhiều hơn thế. 

Vì vậy, nếu thay vào đó tôi đã đề xuất có những thuật toán trong thế giới này mà có một thời gian chạy đó là giới hạn bởi O lớn của log n, log n? Trong trường hợp chúng tôi đã nhìn thấy điều này trước khi? Vâng? 

TƯỢNG: Trong vấn đề danh bạ điện thoại? SPEAKER: Cũng giống như các vấn đề danh bạ điện thoại. Biện pháp như thế nào là gì nhiều thời gian hoặc có bao nhiêu nước mắt nó took tôi tìm thấy một người như Mike Smith trong sổ điện thoại? Chúng tôi tuyên bố đó là log n, và ngay cả khi không quen thuộc hoặc nó nó mơ hồ một chút những gì một logarit hoặc mũ là, chỉ cần nhớ rằng log n thường dùng để chỉ quá trình này, trong trường hợp này, chia một cái gì đó trong một nửa một lần nữa, và một lần nữa, và một lần nữa, và một lần nữa, như vậy mà nó được ngày càng nhỏ như bạn làm điều đó. 

Vì vậy, đăng nhập của n đề cập, chắc chắn, với ví dụ danh bạ điện thoại, để tìm kiếm nhị phân trong lý thuyết, khi chúng tôi có cửa ảo trên diễn đàn, hoặc khi Sean là tìm kiếm một cái gì đó. Nếu ông đã sử dụng tìm kiếm nhị phân, đăng nhập n sẽ là giới hạn trên bao nhiêu thời gian mà có. Nhưng những thuật toán chạy trong log n giả định những gì quan trọng cụ thể? Đó là danh sách đã được sắp xếp, phải không? Thuật toán của bạn là sai lầm nếu đầu vào của bạn không được sắp xếp, nhưng bạn đang sử dụng cái gì đó như tìm kiếm nhị phân bởi vì bạn có thể nhảy quyền đối với các phần tử mà không nhận ra nó thực sự có. 

Bây giờ điều này có thể có nghĩa là, O lớn của một trong những? Điều này không có nghĩa là thuật toán của bạn có một và chỉ một bước, nó chỉ có nghĩa là phải mất một hằng số của các bước. Có thể đó là 1, có thể đó là 10, có lẽ đó là 1000, nhưng nó độc lập kích thước của vấn đề. Không có vấn đề lớn như thế nào là n, một thuật toán thời gian cố định luôn luôn có cùng một số bước. Vì vậy, những gì có thể là một thuật toán chúng tôi đã nói về hoặc chỉ trực giác mà đến với bạn rằng luôn luôn chạy trong cái gọi là hằng số thời gian? Vâng? 

TƯỢNG: Thêm hai con số. SPEAKER: Thêm hai con số, 2 cộng 2 bằng 4, thực hiện. Vì vậy, có thể làm việc, những gì khác? Làm thế nào về thế giới thực hơn, được chứ? 

TƯỢNG: Tìm kiếm Điều đầu tiên trong danh sách. SPEAKER: Tìm kiếm đầu tiên phần tử trong một danh sách, chắc chắn. Chúng tôi đã thực sự được nói về mảng đã có, làm thế nào để bạn nhận được ở Yếu tố đầu tiên trong một mảng, không có vấn đề bao lâu mảng trong C? Bạn chỉ cần sử dụng như khung không ký hiệu, bam, bạn đang có. Và thực sự mảng, như là một sang một bên, hỗ trợ một cái gì đó thường được biết đến như truy cập ngẫu nhiên, truy cập ngẫu nhiên bộ nhớ, bởi vì bạn có thể theo nghĩa đen nhảy đến bất kỳ một nơi. Chúng ta có thể làm điều này thậm chí đơn giản hơn chúng ta có thể quay lại với tuần không khi chúng tôi đã làm cào. Bao nhiêu thời gian đã làm nó đưa cho nói khối trong Scratch để thực hiện? Chỉ cần thời gian liên tục, phải không? Nói điều gì đó, nói một cái gì đó, nó không quan trọng cách vết xước lớn trên thế giới là, nó luôn luôn sẽ mất cùng một lượng thời gian chỉ đơn giản là nói điều gì đó. 

Vì vậy, đó là thời gian liên tục, nhưng mặt trái là những gì? Nếu đó là trên giới hạn, nếu chúng ta muốn để mô tả các giới hạn thấp hơn các thuật toán của chúng tôi thời gian chạy? Gần một trường hợp tốt nhất có khả năng, nếu bạn muốn, mặc dù các điều khoản này có thể áp dụng cho tốt nhất trường hợp, trường hợp xấu nhất, trường hợp trung bình hơn nói chung, nhưng hãy tập trung về giới hạn thấp hơn nói chung. Một thuật toán mà có là gì một giới hạn thấp hơn n bậc, hoặc các bước 2n, hoặc các bước 3n? Một số yếu tố của n bước, đó là thấp hơn của nó bị ràng buộc. Vâng? 

TƯỢNG: Sắp xếp nổi bọt? 

SPEAKER: Sắp xếp nổi bọt có bạn n tối thiểu các bước, tại sao? Tại sao vậy? Tại sao nên đầu rằng để đến với bạn trực giác, ngay cả khi nó không chỉ chưa? Vâng? 

TƯỢNG: [không nghe được]. SPEAKER: Chính xác. Trong kịch bản tốt nhất có thể bong bóng sắp xếp, và rất nhiều các thuật toán, nếu tôi đưa cho bạn tám người những người đã được sắp xếp, nó sẽ là ngu ngốc cho bạn, các thuật toán, đi lại nhiều hơn một lần, phải không? Bởi vì ngay sau khi bạn đi bộ qua danh sách một lần, bạn nên nhận ra, oh, tôi đã không có giao dịch hoán đổi, danh sách này được sắp xếp, xuất cảnh. Nhưng điều đó sẽ đưa bạn n bước. 

Và ngược lại, những gì khác cách suy nghĩ về nó? Sắp xếp nổi bọt là một omega, có thể nói, của n, bởi vì nếu bạn nhìn vào ít hơn n yếu tố, những gì là vấn đề cơ bản đó? Bạn không biết nếu nó được sắp xếp, phải. Chúng tôi con người sức mạnh trong nháy mắt tại tám người và được như thế, oh, nó được sắp xếp, rằng tôi đã không mất n bước này, nhưng nó đã làm. Đôi mắt của bạn, ngay cả khi bạn loại trong có một lĩnh vực lớn của tầm nhìn, bạn nhìn vào tám yếu tố, bạn nhìn vào tám người, đó là tám bước có hiệu quả. Và chỉ khi tôi đi qua toàn bộ danh sách làm tôi nhận ra, có, được sắp xếp. Nếu tôi dừng lại nửa chừng suy nghĩ, tất cả phải, nó khá sắp xếp cho đến nay, tỷ lệ cược nó không được sắp xếp là gì? Đó là thuật toán sẽ không được chính xác. Có thể là nhanh hơn, nhưng không chính xác. 

Vì vậy, bây giờ chúng ta có một cách mô tả một giới hạn thấp hơn, và những gì về thời gian liên tục? Một thuật toán mà có thấp hơn là những gì bị ràng buộc về thời gian hoạt động của một trong những? 1 bước, 2 bước, 10 bước, nhưng không đổi, không phụ thuộc vào n, kích thước của đầu vào? Vâng, ở phía sau. 

TƯỢNG: printf? SPEAKER: Cái gì thế? TƯỢNG: printf? SPEAKER: printf. OK, chắc chắn. Vì vậy, nó có một số cố định các bước. Và tôi nên now-- bây giờ mà chúng ta đang nói về mã C và không cào, một cái gì đó như nói, với printf, chúng ta nên bắt đầu để có được cẩn thận. Bởi vì printf không mất đầu vào, đó là một chuỗi, và chuỗi làm kỹ thuật có chiều dài. Vì vậy, nếu bây giờ chúng ta muốn chọn bạn, nếu bạn không nhớ, về mặt kỹ thuật chúng ta có thể tranh luận rằng printf không mất một đầu vào biến chiều dài, và chắc chắn nó có thể mất nhiều hơn thời gian in một chuỗi dài này, dài hơn này. 

Vì vậy, nếu chúng ta xem xét chỉ phân loại và tìm kiếm các ví dụ? Những gì về Mike Smith trong điện thoại cuốn sách, hoặc tìm kiếm nhị phân thường nhiều hơn? Trong trường hợp tốt nhất, những gì có thể xảy ra? Tôi mở cuốn sách điện thoại và, bam, có số lượng Mike Smith. Tôi có thể gọi anh ta ngay lập tức. 

Bước một bước, có lẽ hai bước, nhưng một số liên tục của bước nếu tôi có may mắn. Và thẳng thắn mà nói, chúng ta đã thấy trên Thứ hai bạn cùng lớp của bạn nhận được khá may mắn hai lần liên tiếp. Và đó là thực sự liên tục thời gian trong một giới hạn thấp hơn vào các thuật toán trong câu hỏi cho việc tìm kiếm số 50 đằng sau những đóng cửa ra vào. 

Bây giờ, khi một sang một bên, nếu bạn phát hiện ra rằng cả hai O lớn, các ràng buộc trên, và omega, thấp hơn bị ràng buộc, là một trong cùng, đó là cùng một công thức trong ngoặc đơn, bạn cũng có thể nói, chỉ được ưa thích, cái gì đó là trong theta n hoặc theta của một số giá trị khác. Điều đó chỉ có nghĩa là khi lớn O và omega đều giống nhau. Bây giờ những gì về việc lựa chọn loại? Hãy sử dụng từ vựng mới này. Trong việc lựa chọn loại, là những gì chúng tôi làm một lần nữa, và một lần nữa, và một lần nữa? Tôi đã trở lại và ra thông qua danh sách, tìm kiếm ai? Số lượng nhỏ nhất. 

Vì vậy, có bao nhiêu bước, làm thế nào nhiều sự so sánh đã làm tôi phải thực hiện để tìm ra người phần tử nhỏ nhất trong danh sách là? n trừ đi 1, phải không? Bởi vì nếu tôi chỉ cần bắt đầu với một trong những tôi đưa ra và tôi bắt đầu so sánh anh ta hoặc cô, sau đó anh ta hoặc cô ấy, anh ấy mình, anh ta hoặc cô ấy, tôi chỉ có thể ghép các yếu tố cùng n trừ đi 1 lần. Vì vậy, lựa chọn có loại tương tự n trừ đi 1 bước lần đầu tiên. 

Có bao nhiêu bước nó đưa tôi đến tìm các phần tử nhỏ nhất thứ hai? n trừ đi 2, bởi vì tôi bị câm nếu tôi cứ nhìn những người cùng một lần nữa nếu tôi đã chọn anh mình và đặt chúng ở vị trí của họ. Và bước thứ ba, n trừ đi 3, sau đó n trừ đi 4. Chúng tôi đã nhìn thấy mô hình này trước, và thực sự lựa chọn loại tương tự có một trên ràng buộc n bình nếu chúng ta làm tăng tổng kết đó. Ràng buộc thấp hơn, lựa chọn phân loại của nó là gì? Tối thiểu, bao nhiêu thời gian lựa chọn phải loại có, như chúng ta định nghĩa nó vào thứ hai? Đề xuất hai lựa chọn. Có lẽ đó là n, như trước đây. Có thể nó n bình phương, vì nó giờ là như ranh giới trên. 

TƯỢNG: n bình phương. SPEAKER: n bình phương. Tại sao? 

TƯỢNG: Bởi vì bạn có để xác định [không nghe được]. 

SPEAKER: Chính xác. Ít nhất là tôi đã xác định lựa chọn loại nó đã được khá ngây thơ, tiếp tục đi, tìm các phần tử nhỏ nhất. Tới một lần nữa, tìm các phần tử nhỏ nhất. Tới một lần nữa, tìm các phần tử nhỏ nhất. Không có loại tối ưu hóa trong đó mà có thể cho tôi sau khi hủy bỏ chỉ n, hay như vậy bước. Vì vậy, trên thực tế, lựa chọn sắp xếp, omega n bình phương. 

Những gì về sắp xếp chèn, nơi mà tôi đã người mà tôi đã được đưa ra, và sau đó tôi ngồi phịch anh mình vào đúng chỗ? Sau đó, tôi tiếp tục đến người thứ hai, ngồi phịch người đó ở đúng nơi. Sau đó, người kế tiếp, ngồi phịch anh ta hoặc cô ở đúng nơi. Chú ý rằng điều này là rất tuyến tính, vậy để nói chuyện. Tôi là một đường thẳng, tôi không đi lại, Tôi chưa bao giờ nhìn lại thực sự, nhưng những gì đang xảy ra khi tôi chèn ông mình vào đầu danh sách như chúng tôi đã làm vào thứ hai? Điều gì đang xảy ra? Vâng? TƯỢNG: [không nghe được]. SPEAKER: Vâng, đó là đánh bắt, phải không? Bạn có thể nhớ lại từ bạn cùng lớp của bạn, nếu họ được thực hiện bất kỳ chuyển động với đôi chân của mình, đó là một hoạt động. Vì vậy, nếu ba người dân ở đây đó và người mới áp đảo thuộc về cách qua đó, vào một giai đoạn dài như thế này, chắc chắn, ông hay cô chỉ có thể đi đến cuối cùng. Nhưng nếu chúng ta đang suy nghĩ về một máy tính và một mảng của bộ nhớ, những người này sẽ phải xáo trộn trên để nhường chỗ cho người đó. Và đó n trừ đi 1 shufflings, n trừ đi 2 shufflings, n trừ 3 shufflings chỉ là loại xảy ra đằng sau tôi, không phải trước mặt tôi như trước đây, trong một ý nghĩa. Bây giờ là một sang một bên, và như bạn có thể đã nhìn thấy trực tuyến nếu bạn bắt đầu chĩa ra xung quanh về các loại, có rất nhiều những người khác nhau trên mạng, một số trong số họ tốt hơn so với những người khác. Thật vậy, bogosort là một đó là loại thú vị để tìm kiếm. Bogosort có một tập hợp các số hoặc nói một cỗ bài, lê bước ngẫu nhiên họ, và kiểm tra nếu họ đang sắp xếp. Và nếu không, hiện nó một lần nữa. Và nếu không, hiện nó một lần nữa. Nếu không, hiện nó một lần nữa. Cực kỳ ngu ngốc. 

Và quả thực, nếu bạn đọc như bài viết Wikipedia, biệt danh của nó là loại ngu ngốc. Nó cuối cùng sẽ làm việc, hy vọng, có đủ thời gian, nhưng số lượng thời gian có thể mất một thời gian khá lâu. Vì vậy, điều tốc độ nếu tôi có thể, chúng ta hãy từ ví dụ của Mary Beth trước đó, bởi có một vài yếu tố khác, nhưng hai bộ xử lý hơn. Hai con người, nếu bạn sẽ không nhớ tôi tham gia. Làm thế nào về 1 trên đây, và hãy go-- không có ai ở đó không? Không ai ở đó không? OK. Bạn với màu đen áo sơ mi, có, đi trên xuống. Được rồi, tên của bạn là gì? 

TƯỢNG: Peter. 

SPEAKER: Cái gì thế? 

TƯỢNG: Peter. SPEAKER: Peter, David, rất vui được gặp bạn. Được rồi, chúng ta có Peter ở đây, nếu bạn muốn đi lên bàn ở đây. Và tên của bạn là gì? 

TƯỢNG: Elena. SPEAKER: Elena. OK, rất vui được gặp bạn. Elena gặp Peter. Peter, Elena. Và chúng ta sẽ cần Andrew ở đây là tốt, xin vui lòng. Và thách thức của bạn sẽ là để sắp xếp một bộ bài. Và nếu không quen thuộc, boong thẻ nên cuối cùng được sắp xếp một chút gì đó giống như này, nơi chúng tôi sẽ làm các câu lạc bộ, sau đó các mai, sau đó trái tim và kim cương, từ ace như một, tất cả các con đường lên cho nhà vua. 

Các thẻ tôi sẽ cung cấp cho bạn đang có được 52 trong số lượng. Chúng ta sẽ tương tự Hiện bạn, chỉ trong một thời điểm. Chúng ta sẽ ném Andrew lên trên màn hình ở đây, để xem như là bạn làm điều này. Và đó là tất cả điều này là tất cả các rõ ràng hơn, đó là những thẻ tôi đã nhận trên Amazon. Vì vậy, họ đã ngẫu nhiên sắp xếp, và chúng ta sẽ để thời gian bạn. Và chúng ta sẽ giữ nó thực sự thời gian này, vì vậy chúng tôi sẽ cố gắng để áp lực cho bạn bởi vì nếu không điều này sẽ giúp tẻ nhạt một cách nhanh chóng. Nếu bạn có thể tiến hành để sắp xếp 52 các yếu tố với nhau thông qua một số phương tiện, bây giờ. 

Và một lần nữa, như chúng ta xem những kẻ làm những gì, cuối cùng sẽ tạo ra một rõ ràng Kết quả, suy nghĩ về thực sự làm thế nào họ đang từng làm việc đó, làm thế nào bạn có thể mô tả nó. Bởi vì một lần nữa, đây là những tất cả các quá trình, các thuật toán mà chúng tôi đưa cho các cấp như một con người. Tuy nhiên, bạn đã có thể lâu đã trực giác, rất lâu trước khi bạn thậm chí nghĩ về việc tham gia một khoa học máy tính lớp bạn có thể có trực giác với để giải quyết vấn đề như thế này. Nhưng một khi bạn nhận ra các mô hình và bắt đầu để chính thức hóa các bước mà bạn đang giải quyết những vấn đề này, bạn sẽ thấy rằng bạn có thể giải quyết nhiều thú vị hơn và phức tạp hơn nhiều vấn đề một cách nhanh chóng. Vì vậy, một người nào đó từ phía khán giả, là những gì ít nhất một phần tử của thuật toán rằng họ đang sử dụng ở đây? 

TƯỢNG: [không nghe được] SPEAKER: Cái gì thế? TƯỢNG: Bằng cách phù hợp. SPEAKER: Bằng cách phù hợp. Vì vậy, đầu tiên họ được phân nhóm tất cả các viên kim cương cùng có vẻ như, tất cả các trái tim lại với nhau có vẻ như, và vv, mà không có sự tôn trọng cho những con số trên thẻ. Và bây giờ chúng xuất hiện, ví dụ, được phân loại chúng theo số lượng. Rất tốt. 

Được rồi, vậy điều gì sẽ là bước cuối cùng sau đó ở đây? Khi chúng ta có bốn bộ quần áo được sắp xếp, những gì chúng ta cần phải làm gì để bốn cọc để đạt được một sắp xếp tầng, khá đơn giản? Vì vậy, chúng ta cần phải hợp nhất chúng lại một lần nữa. 

Vì vậy, có một ý tưởng thú vị mà một lần nữa, dám nói, thậm chí là rất trực quan nếu bạn không bao giờ có thể đã tát là loại nhãn trên đó. Điều này khái niệm cơ bản của phân chia vấn đề không phải trong một nửa thời gian này, nhưng ít nhất thành bốn miếng. Giải quyết khá nhiều vấn đề cơ bản giống hệt nhau trong sự cô lập của nhau, và sau đó kết hợp các kết quả. Và, tuyệt vời, thực hiện. Được rồi, một vòng lớn vỗ tay, nếu chúng ta có thể. 

[Vỗ tay] 

SPEAKER: Tôi không có ý tưởng những gì bạn sẽ thấy làm với này, nhưng ở đây bạn đi. Cảm ơn bạn rất nhiều. Vì vậy, chúng ta hãy xem, hai phút và tám giây, nếu bạn muốn thách thức bạn bè của bạn. Điều gì sau đó sẽ là một lấy đi từ này chúng ta có thể tận dụng nói chung? Vâng, nghĩ lại mảng này các con số, và bây giờ nghĩ lại cho một số các giả chúng tôi đã viết trong quá khứ, và đây là giả cho giải quyết vấn đề danh bạ điện thoại. Nhờ đó mà trong giả tôi liệt kê một cách có phương pháp hơn mô tả làm thế nào tôi đã làm một rất trực quan Thuật toán nhân chia điện thoại cuốn sách trong một nửa, lặp lại, lặp lại, lặp lại, cho đến khi tôi tìm thấy một người như Mike Smith, nếu anh ta thực sự là trong sổ điện thoại. 

Nhưng tôi loại sử dụng những gì tôi sẽ gọi một cách tiếp cận rất lặp đi lặp lại ở đây, trong thông báo cụ thể đường 8 và đường 11. Đó là những bằng chứng cho thấy lặp đi lặp lại cách tiếp cận, một cách tiếp cận vòng lặp, bởi vì đó là chính xác hành vi mà họ gây ra. Những dòng đều nói đi loại ba dòng, và bạn có thể của nghĩ về điều đó trong bạn mắt của tâm trí như là một vòng lặp. Nó nói cho bạn để quay trở lại bước ba và lặp lại, một lần nữa, và một lần nữa, và một lần nữa. 

Nhưng nếu chúng ta tận dụng một ý tưởng quan trọng ở đây là chúng tôi đã làm không phải là lần cuối cùng, và đơn giản hóa dòng 8 và dòng 11 và hàng xóm như chỉ này, màu vàng. Đó là về cơ bản không rút ngắn mã giả rất nhiều, nhưng nó thay đổi căn bản bản chất của thuật toán của tôi. Những gì chúng ta đang nói trong bước 7, trong bước 10, là để tìm kiếm Mike trong một cách chính xác, nhưng chỉ ở bên trái một nửa hoặc nửa bên phải. 

Vì vậy, nói cách khác, nếu Tôi bắt đầu từ bước một, nhận cuốn sách điện thoại, mở cửa cho trung danh bạ điện thoại, nhìn vào tên, nếu Smith là một trong những tên, gọi Mike, khác Smith là nếu trước đó trong cuốn sách, bước bảy tìm kiếm Mike ở nửa bên trái của cuốn sách. Tuy nhiên, các cảm giác như nó để lại cho tôi treo, phải không? Màu vàng, là một hướng dẫn, nhưng làm cách nào để tìm kiếm Mike ở bên trái một nửa số danh bạ điện thoại? Tôi có một nơi thuật toán mà tôi có thể tìm kiếm một người như Mike Smith? Vâng, nó nhìn chằm chằm chúng tôi trong khuôn mặt. Tôi nghĩa là có thể sử dụng chính xác cùng chương trình có hiệu quả sẽ lên đến đỉnh một lần nữa và lại chạy cùng một dòng mã. 

Vì vậy, mặc dù điều này nên cảm thấy giống như một chút của một định nghĩa mang tính chu kỳ nơi bạn đang trả lời một ai đó câu hỏi bằng cách chỉ là loại yêu cầu cùng một câu hỏi một lần nữa, như lý do tại sao, tại sao, tại sao? Thực tế là bởi vì chúng tôi đã cứng mã hoá một vài dòng đặc biệt, bước 4, mà là một nếu, và bước 12, là có hiệu quả một chi nhánh, bởi vì chúng tôi có những biện pháp lấp chỗ trống, thuật toán này sẽ chấm dứt nếu chúng ta Mike tìm thấy, hoặc nếu chúng ta không. Nhưng trong bước 7 và 10 giờ, chúng tôi có những gì chúng tôi sẽ gọi một thuật toán đệ quy. Và đệ quy thực sự là một ý tưởng mạnh mẽ đó là một chút tâm uốn lúc đầu, mà bây giờ chúng ta có thể áp dụng như sau. 

Kết hợp các loại sẽ là loại cuối cùng mà chúng ta nhìn vào, ít nhất là trong các lớp học chính thức. Và đó là cơ bản khác nhau từ những người cuối cùng ba, và chắc chắn cuối cùng bốn nếu chúng tôi bao gồm bogosort. Đây là giả cho sắp xếp hợp nhất. Khi vào đầu vào của n phần tử, vì vậy được một mảng có kích thước n, nếu n là ít hơn 2, trở lại. Vì vậy, tại sao tôi có mà sự tỉnh táo kiểm tra đầu tiên? Ngụ ý gì nếu tôi đưa cho bạn một mảng có n chiều dài là ít hơn 2? Nó đã được sắp xếp, rõ ràng, đúng không? Bởi vì danh sách hoặc có một yếu tố, đó là tầm thường sắp xếp bởi vì nó điều duy nhất đó. Hoặc, nó có kích thước bằng không có nghĩa là không có gì để sắp xếp là, do bản chất nó được sắp xếp. Không chỉ là không có gì sai trái đó. Vì vậy, đó là cái gọi là trường hợp cơ sở của chúng tôi. 

Đó là tinh thần tương tự những gì chúng ta đã làm với Mike. Nếu Mike trong sổ điện thoại, gọi anh ta. Nếu anh ta không có ở đó, bỏ cuộc. Đó là một trường hợp cơ sở cái gọi là, để đảm bảo thuật toán này vào cuối ngày sẽ chấm dứt trong những trường hợp nhất định. 

Nhưng đây là bước nhảy vọt của đức tin bây giờ, khác, sắp xếp nửa trái của các yếu tố, sau đó sắp xếp bên phải một nửa trong số các yếu tố, và sau đó hợp nhất hai nửa được sắp xếp. Và đây là nơi mà nó cảm thấy như chúng ta đang Copping ra. Tôi đã hỏi bạn sắp xếp n yếu tố, và tôi nói, OK, làm điều đó bằng cách phân loại bên trái và phân loại bên phải. Nhưng tôi nói một điều khác, và điều này là chủ đề quan trọng có vẻ như trong trực giác vậy, đến nay, có bước thứ ba này hợp nhất. Mà mặc dù nó có vẻ rất ngớ ngẩn trong tinh thần, như chỉ hợp điều với nhau, có vẻ như là một bước quan trọng hướng tới tái gộp hai vấn đề mà cuối cùng được chia một nửa. 

Vì vậy, hợp nhất phân loại, chúng ta hãy làm điều này, nếu bạn sẽ hài hước tôi, với một cuộc biểu tình nhiều, chỉ để chúng tôi có một số số điện thoại để làm việc với. Tôi có thể trao đổi tám căng thẳng quả bóng cho tám người? Được rồi, làm thế nào về bạn ba, bốn bạn trong phần này, năm, sáu, và chúng ta hãy làm 7, 8, đến ngày lên. OK, yeah OK. Trừ đi 8, có chúng tôi đi, cộng với 1. Tuyệt vời. Rồi đến ngày lên, chúng ta hãy nhanh chóng cung cấp cho bạn số điện thoại. Thứ hai, thứ ba, thứ tư, thứ năm, sáu, bảy, tám người. Tôi đã làm tám một cách chính xác thời gian này. 

OK, nên đi trước nếu bạn có thể, và chúng ta hãy sắp xếp theo thứ tự ban đầu rằng chúng tôi đã có ngày hôm qua mà nhìn như thế này, nếu bạn không quan tâm. Và chúng ta hãy làm điều đó trước mặt bàn. Được rồi, để hợp nhất phân loại. Đây là nơi mà nó sẽ để có được loại thú vị, bởi vì tôi dường như được cho bản thân mình quá nhiều ngày nay ít thông tin. 

Vì vậy, hợp nhất phân loại đầu tiên của tất cả các trên đầu vào của các yếu tố n, và rõ ràng là không ít hơn hai, đó là tám, vì vậy tôi có một số công việc nhiều hơn để làm. Vì vậy, bây giờ tinh thần chúng tôi như là một lớp hiện nay trong ngành khác, có nghĩa là ba bước. Trước tiên, tôi phải sắp xếp các nửa bên trái của các yếu tố. Vì vậy, làm thế nào để đi về việc này? Vâng, tôi sẽ loại tinh thần chia danh sách ở đây, bạn không cần phải thể chất di chuyển, và tôi sẽ chỉ tập trung vào nửa bên trái của các yếu tố ở đây. Vậy làm thế nào để tôi đi về phân loại một danh sách hiện nay có kích thước bốn? Thuật toán của tôi là gì? Lần đầu tiên tôi kiểm tra là n ít hơn hai, không, vì vậy tôi tiến hành các khối khác nữa. Sắp xếp lại một nửa số yếu tố. 

Vì vậy, bây giờ một lần nữa, tinh thần, và đây là nơi bạn phải tích lũy rất nhiều lịch sử tâm thần, nếu bạn sẽ. Bây giờ tôi đang sắp xếp bên trái một nửa của một nửa trái. Được rồi, vì vậy bây giờ tôi gọi cùng hợp nhất của tôi thuật toán phân loại, được n ít hơn hai? Không, nó là hai, vì vậy tôi phải sắp xếp nửa bên trái và nửa bên phải. Vì vậy, ở đây chúng tôi đi, sắp xếp các nửa trái. Tại sao bạn không chỉ đi trước một bước. Tên của bạn là gì? 

TƯỢNG: Darren. 

SPEAKER: Dan. Dan đã bước về phía trước. 

TƯỢNG: Darren. SPEAKER: Darren, thực hiện. Bạn đã nói Darren hoặc Dan? 

TƯỢNG: Darren. 

SPEAKER: Darren. OK, Darren đã tăng cường về phía trước và bây giờ anh đã được sắp xếp. Và điều này gần như là một tuyên bố ngớ ngẩn, phải không? Tôi không thực sự dường như đạt được bất cứ điều gì, nhưng chúng ta hãy tiến hành. Bây giờ hãy để tôi sắp xếp bên phải một nửa trong số các yếu tố. Tên của bạn là gì? 

TƯỢNG: Luke. 

SPEAKER: Luke. Thôi nào, bước về phía trước. Thực hiện, tôi đã sắp xếp Luke. Nửa bên trái bây giờ được sắp xếp và nửa bên phải bây giờ được sắp xếp, nhưng một lần nữa, có một bước tiến quan trọng ở đây. Tôi phải làm gì tiếp theo cần phải làm gì? Hợp nhất nửa sắp xếp. Bây giờ chúng ta sẽ chỉ có tất cả mọi người qua lại theo cách này, bởi vì tôi cần phải loại một số không gian đầu. Nó gần giống như những kẻ đang ở trên một bảng, và tôi cần một số phòng để di chuyển chúng xung quanh trên. Vì vậy, tôi sẽ hợp nhất các bạn bằng cách tìm kiếm ở nửa trái và nửa bên phải. Và rõ ràng là người đến trước, nửa trái hoặc nửa phải không? Vì vậy, nửa bên phải, vì vậy chúng ta hãy chuyển qua Luke ở đây vị trí ban đầu của Darren. Và bây giờ kết hợp của họ trong nửa trái, Darren sẽ di chuyển ngay. 

Vì vậy, cảm thấy giống như hầu hết một hiệu ứng bong bóng sắp xếp, nhưng thuật toán cơ bản của tôi, rất khác nhau thời gian này. Nhưng bây giờ là nơi mà mọi thứ có được một ít gây phiền nhiễu bởi vì bạn phải tua lại tinh thần nơi mà tôi không còn. Tôi vừa mới sáp nhập hai nửa đã được sắp xếp, có nghĩa là tôi đang ở đâu trong thuật toán của tôi? Tôi phải sắp xếp nửa bên phải, phải không? 

Nếu bạn quay lại, theo nghĩa đen trên video, bạn sẽ thấy rằng chúng tôi đã đến đây điểm của Luke và Darren bằng cách phân loại trái một nửa của một nửa trái. Sau đó, chúng tôi kết hợp những nửa sắp xếp, mà có nghĩa là bước tiếp theo là sắp xếp các nửa bên phải của một nửa trái. Được rồi, vậy chúng ta hãy làm điều này một cách nhanh chóng hơn. Được rồi, sáu, tôi sẽ yêu cầu bồi thường bây giờ bạn đều được sắp xếp, đi về phía trước. Tên của bạn là gì? 

TƯỢNG: Adriano. 

SPEAKER: Adriano. Adriano hiện đang được sắp xếp. Và tên của bạn là gì? 

TƯỢNG: Alex. 

SPEAKER: Alex bây giờ được sắp xếp. Còn lại một nửa, nửa bên phải, bước cuối cùng là gì? Merge. Khá tầm thường, vì vậy tôi sẽ hợp nhất trong sáu, lùi lại một bước, tám, lùi lại một bước. Và bây giờ nhận thấy điều này là một takeaway hữu ích, những gì bây giờ là sự thật về nửa bên trái của danh sách, bất kể như thế nào chúng tôi bắt đầu? Nó được sắp xếp. 

Bây giờ nó không được sắp xếp trong các đề án lớn của sự vật, nhưng nó được sắp xếp một cách độc lập của nửa kia. Bây giờ những gì tôi bước vào nếu tôi giữ tua như thế nào câu chuyện bắt đầu? Bây giờ tôi phải sắp xếp nửa bên phải. Vì vậy, bây giờ chúng tôi cách trở lại đầu của câu chuyện, và chúng ta hãy làm điều này nhanh hơn. Vì vậy, tôi sẽ sắp xếp nửa bên phải của toàn bộ danh sách. Bước tiếp theo là gì? Sắp xếp một nửa còn lại của nửa bên phải. Sắp xếp một nửa bên trái của nửa bên trái của nửa bên phải. Và tên của bạn là gì? 

TƯỢNG: Omar. 

SPEAKER: Omar, bước về phía trước, thực hiện. Nửa còn lại được sắp xếp. Và tên của bạn là gì? 

TƯỢNG: Chris. 

SPEAKER: Chris, có một bước về phía trước, bạn đang sắp xếp. Các bước quan trọng bây giờ là gì? Merge. Vì vậy, một là sẽ hợp nhất vào vị trí ở đây, nếu bạn có thể lùi lại một bước, và ba sẽ lùi lại một bước, sáp nhập. Vì vậy, nửa bên trái của nửa bên phải, bây giờ được sắp xếp. Thành thật mà nói, thuật toán này cảm thấy như chúng tôi đang lãng phí thời gian cách hơn trước, nhưng nếu chúng ta đã làm điều này trong thời gian thực, chúng ta sẽ xem những gì takeaways có được. Bây giờ tôi ở đây, phải một nửa nửa bên phải, hãy để tôi đi trước và sắp xếp nửa trái. Bước về phía trước, tên của bạn là gì? TƯỢNG: Ramsey. SPEAKER: Ramsey hiện đang được sắp xếp. Tên của bạn là gì? 

TƯỢNG: Marina. 

SPEAKER: Marina giờ được sắp xếp như tốt, nếu bạn đi trước một bước. Bước quan trọng ở đây là hợp nhất, tôi sẽ nhổ từ hai danh sách của tôi, trái và phải. Năm là sẽ đi đầu tiên, và bảy là sẽ đi tiếp theo. Và một lần nữa, điều này là có chủ ý. Thực tế là họ đang dùng bước lên phía trước và trở lại có nghĩa là để bảo đảm rằng chúng ta không thể làm thuật toán này ở vị trí một cách dễ dàng như bong bóng sắp xếp, lựa chọn và sắp xếp, và sắp xếp chèn nơi chúng tôi chỉ tiếp tục trao đổi người. Tôi thật sự cần một loại giấy đầu trong đó để đưa những người này trong khi tôi làm việc sáp nhập, và sau đó tôi có thể đưa chúng trở lại tại chỗ. Và đó là quan trọng bởi vì tôi đang sử dụng một tài nguyên mới, không gian, không chỉ là thời gian. 

OK, điều này là tuyệt vời. Còn lại một nửa được sắp xếp, nửa bên phải là sắp xếp, bây giờ mà chính hợp nhất bước. Làm thế nào tôi sẽ kết hợp này? Vì vậy, nếu bạn làm theo tôi tay trái và tay phải, Tôi sẽ chỉ cho tay trái của tôi ở nửa bên trái, tay phải của tôi ở nửa bên phải, và bây giờ tôi phải quyết định từng bước mà để trộn. Ai rõ ràng đến trước? Số một. Vì vậy, đến trên đây, đây là pad đầu của chúng tôi. Vì vậy, bây giờ số một, và thông báo những gì tôi sẽ làm gì với bàn tay phải của tôi, Tôi sẽ di chuyển một bàn tay phải của tôi bước qua chỉ số ba, và bây giờ tôi phải làm quyết định tương tự. Và thực sự đứng ngay phía trước của Luke ở đây nếu bạn có thể, bởi vì đây là pad đầu của chúng tôi. Vì vậy, những người đến tiếp theo? Chúng tôi có với Luke thứ hai hoặc với Chris thứ ba. Rõ ràng là Luke, số hai, vì vậy bạn đến đây. 

Nhưng bàn tay trái của tôi bây giờ sẽ được tăng lên tới điểm Darren, và đây là chìa khóa lấy đi với sáp nhập, tôi sẽ tiếp tục làm điều này, rõ ràng là, nếu bạn loại của theo logic. Nhưng bàn tay của tôi là không bao giờ sẽ đi ngược trở lại, có nghĩa là tôi chỉ có bao giờ di chuyển đến trái với quá trình sáp nhập của tôi, và đó sẽ là chìa khóa để phân tích của chúng tôi chỉ trong một khoảnh khắc. 

Vì vậy, bây giờ chúng ta hãy hoàn thành điều này nhanh chóng. Vì vậy, ba đến tiếp theo, sau đó bốn đến tiếp theo, và bây giờ năm đến tiếp theo, sau đó sáu, và bảy, và cuối cùng tám. Có cảm giác như các thuật toán chậm nhất nêu ra, nhưng nếu chúng ta không thực sự chạy nó ở cùng một loại tốc độ đồng hồ, do đó, để nói, với cùng một đánh dấu đồng hồ như trước đây. Tại sao? Vâng, Chúng ta hãy nhìn vào kết quả cuối cùng. 

Hãy trở lại đây, cho tôi kéo lên một cuộc biểu tình trực quan về những gì chúng ta đã làm. Phóng to ở đây, trên này trang ở đây, nói với Firefox mà chúng tôi muốn xếp hàng trong hộp này, chúng ta hãy nói bong bóng sắp xếp, mà chúng tôi bây giờ cũng quen thuộc, lựa chọn sắp xếp, mà là một một khá đơn giản, và bây giờ loại hợp nhất hiện nay, trong đó sẽ kết thúc cao trào của chúng tôi. Lý do phải mất quá nhiều thời gian ở đây với con người và tôi bằng lời nói là, rõ ràng, tôi giải thích từng bước. Nhưng nếu bạn chỉ đơn giản là thực hiện điều này, nhiều như chúng tôi đã làm bong bóng sắp xếp và lựa chọn loại không chỉ trực quan, xem chỉ có bao nhiêu hiệu quả hơn đòn bẩy này phân chia và chinh phục có thể được khi áp dụng cho một tập dữ liệu đó là thậm chí không kích thước tám, nhưng ngay cả nhiều, lớn hơn nhiều. Tôi cung cấp cho bạn hợp nhất phân loại, bên mặt với những thuật toán khác. Điều này sẽ có được đau đớn nhanh chóng, và kết thúc không phải là đặc biệt về khí hậu, họ chỉ kết thúc được sắp xếp. Nhưng chìa khóa lấy đi là trông như thế nào nhanh hơn nhiều hợp nhất phân loại là, trừ khi bạn nghĩ tôi chỉ cần loại rối tung với bạn. Nếu chúng ta làm một lần cuối cùng này, hãy để của lại này, hãy quay trở lại và chọn bong bóng sắp xếp, và chỉ cần cho đá, hãy chọn chèn sắp xếp, chỉ dành cho các biện pháp tốt. Và lần này một lần nữa, chúng ta hãy chọn sắp xếp hợp nhất và chúng ta hãy thực sự chạy các cạnh. 

Và nó không phải là, trên thực tế, một sự may mắn. Những gì tôi đã thực hiện có hiệu quả là tôi đã chia đầu vào của tôi trong một nửa, một lần nữa, và một lần nữa, và một lần nữa. Và chỉ có rất nhiều lần bạn có thể chia đầu vào của bạn thành hai nửa, còn lại và phải. Công thức mà chúng ta tiếp tục nhìn thấy gì mô tả sự phân chia trong một nửa một lần nữa, và một lần nữa, và một lần nữa, và một lần nữa? 

TƯỢNG: Đăng nhập n. 

SPEAKER: Đăng nhập n. Nhưng sau đó có một bước tiến quan trọng khác, Thuật toán này không được đăng nhập n bước. Nếu nó chỉ được log n bước, chúng ta sẽ được ở cùng một vấn đề như trước khi mà chúng ta không thể chắc chắn mọi thứ đều được sắp xếp. Bạn cần phải nhìn vào các yếu tố tối thiểu n chắc chắn n yếu tố đều được sắp xếp, nếu không nó là một bước nhảy vọt của đức tin. 

Vì vậy, nó ghi tối thiểu n bước, nhưng những gì về bước kết hợp phím này nơi tôi sáp nhập một nửa bên trái và bên phải một nửa và đi ngang qua sân khấu? Có bao nhiêu bước là để hợp nhất? Đó là n, nhưng tôi đã không chỉ hợp nhất lần cuối cùng. Trên mỗi của những cuộc gọi lồng nhau, trên mỗi hòa trộn của những lồng nhau, tôi vẫn sắp xếp. Tôi kết hợp hai người này, sau đó hai chàng trai, sau đó hai người này và vân vân. 

Vì vậy, tôi đã kết hợp một lần nữa, và một lần nữa. Đã bao nhiêu lần? Vì vậy, mỗi khi tôi chia danh sách một nửa, tôi đã làm một hợp nhất. Chia danh sách trong một nửa, làm một hợp nhất. Vì vậy, nếu phân chia danh sách có thể được thực hiện log n lần, và cuối cùng là sự kết hợp có n bước, những gì có thể tại phía trên bị ràng buộc vào các hoạt động thời gian của thuật toán của chúng tôi? n log n. 

Và quả thực, đó là những gì chúng tôi đã đạt được ở đây. Vì vậy, những cảm nhận mà bạn nhìn thấy bằng mắt khi những ba điều chạy bên cạnh được n bình phương với n phương với n log n. Mà về cơ bản chúng ta sẽ thấy, không chỉ ngày hôm nay nhưng trong tương lai, là nhiều, nhanh hơn nhiều. Một tràng pháo tay cho những kẻ, Tôi sẽ thưởng cho họ với quả bóng căng thẳng. Hãy hoãn ở đây ngày hôm nay, và chúng ta sẽ thấy bạn vào thứ hai.