>> [MUSIC CHƠI]
>> DAVID J. Malan: Đây là CS50.
Và đây là sự bắt đầu của tuần ba.
Vì vậy, chúng tôi đã có rất nhiều thú vị thứ để trang trải ngày hôm nay.
Rất nhiều cơ hội cho tình nguyện viên trên sân khấu.
Và cuối cùng, hôm nay là không về mã nào cả.
Nhưng đó là về ý tưởng, và đó là về các thuật toán,
và thực sự mang lại một số các bài học kinh nghiệm từ tuần không,
trong đó thu hồi, chúng tôi giới thiệu con quái vật này.
Và vay mượn cảm hứng từ đó, để bắt đầu
để giải quyết phức tạp hơn bao giờ hết vấn đề thuật toán.
Nhưng trước tiên, một vài thông báo.
Vì vậy, một, nếu bạn muốn tham gia Nhân viên và các bạn cùng lớp CS50 tại bữa ăn trưa
Thứ Sáu tuần này, cả hai ở đây và ở Cambridge, và ở New Haven,
xin vui lòng truy cập vào các khóa học của trang web, nơi một URL có thể được tìm thấy.
Bài giảng thứ Tư này sẽ không được ở đây trong Sanders.
Nó sẽ được trực tuyến chỉ, vì vậy điều chỉnh trong tại website của CS50,
cho dù ở đây tại Cambridge hoặc New Haven là tốt.
>> Và sau đó vấn đề đặt hai là đã có trong tay của bạn.
Nếu bạn chưa lặn trong chưa, cho phép tôi cung cấp các gợi ý ngôn từ mạnh mẽ
đó, đặc biệt là bây giờ, khi vấn đề đặt ra trước,
bạn thực sự muốn bắt đầu bây giờ, nếu không vọc một chút vào cuối tuần hoặc trước
khi họ lần đầu tiên đi ra ngoài vào Thứ Sáu, bởi vì bạn sẽ
thấy rằng họ không nhất thiết nhận được lâu hơn hoặc nhiều thách thức cho mỗi
se.
Tôi nghĩ rằng bạn sẽ tìm thấy rằng, trong Nói chung, họ có xu hướng mất khoảng
xung quanh cùng một lượng thời gian.
Nhưng chắc chắn nó phụ thuộc vào học sinh, và nó
phụ thuộc vào những suy nghĩ mà bạn tiếp cận nó.
Nhưng lúc nào, bạn đang đi chạy lên chống lại một bức tường,
và bạn đang đi để đạt một số lỗi, và bạn chỉ
sẽ không có khả năng vượt qua được nó tại một số điểm.
Và đó là cực kỳ có giá trị để có thể để bước đi, trở lại vào ngày hôm sau,
đi đến giờ làm việc, bài đăng trên CS50 Thảo luận hay như thế, để thực sự có được cấm.
Vì vậy, giữ cho rằng trong tâm trí.
Bắt đầu sớm nhất có thể là điều tốt nhất bạn có thể làm.
Vì vậy, đây là nơi chúng ta bắt đầu lớp, trong tuần qua không.
Và chúng ta có thể có được một tình nguyện viên ở đây để giúp tôi tìm mics?
ĐƯỢC.
Đứng lên đã.
Nào lên.
Đoán đó là cách nó sẽ làm việc.
Tên bạn là gì?
ALAN Estrada: Alan Estrada.
DAVID J. Malan: Alan Estrada.
Nào lên.
Rất hân hạnh được biết bạn.
ALAN Estrada: Rất vui được gặp bạn.
DAVID J. Malan: Và em có ở đây với chúng tôi trong tuần bằng không, tất nhiên.
ALAN Estrada: Tôi đã.
Tôi đã.
>> DAVID J. Malan: Vì vậy, bạn có thể đi trước và tìm cho chúng tôi Mike Smith,
nhanh như bạn có thể?
Nhanh như bạn có thể.
Nghĩa đen rách vấn đề trong nửa như bạn cần.
>> ALAN Estrada: Um.
DAVID J. Malan: Nghĩa đen rách vấn đề trong một nửa.
>> ALAN Estrada: Oh.
Mm.
Rất tốt.
>> DAVID J. Malan: OK.
Tốt.
Cam on.
ALAN Estrada: Rất tốt.
ĐƯỢC.
>> DAVID J. Malan: Và bây giờ, bạn đã đẽo nó xuống
đến một nửa kích thước của vấn đề.
Bây giờ, chúng tôi đang xuống đến một phần tư.
Bạn đang chú ý đến mà bên chúng tôi đang giữ?
>> [Cười]
>> ALAN Estrada: Vâng, tôi think--
>> DAVID J. Malan: phần gì chúng ta đang ở?
ALAN Estrada: Mufflers, như vậy.
>> DAVID J. Malan: OK.
Nhưng Mike Smith sẽ là sau khi Mufflers.
So--
>> [Cười]
>> Được rồi.
ALAN Estrada: Chúng ta tìm ở đâu?
DAVID J. Malan: Mike Smith.
ALAN Estrada: Mike Smith.
DAVID J. Malan: Bây giờ, chúng ta đang ở trong phẫu thuật.
Bây giờ, các bác sĩ.
Now--
>> ALAN Estrada: Let's- chúng ta hãy đi với thực tế.
Real.
>> DAVID J. Malan: Real.
ĐƯỢC.
Nếu bạn cần Real.
Bây giờ, đó là cách Mike Smith?
>> ALAN Estrada: Bằng cách này.
>> DAVID J. Malan: Dùng cách nào?
ALAN Estrada: Chờ.
M is-- phải không?
Chúng tôi bắt đầu with--
>> DAVID J. Malan: Yeah.
Họ đang trái.
Quyền của bạn.
>> ALAN Estrada: Yeah.
>> DAVID J. Malan: Vì vậy, Mike ở đây.
ALAN Estrada: Cái gì?
>> [Cười]
>> Bad dụ, guys.
Xin lỗi.
DAVID J. Malan: Điều này sẽ dạy bạn nhảy ra khỏi ghế của bạn.
>> ALAN Estrada: Oh.
Oh.
Tôi đã có em.
Oh.
Đây is-- OK, tôi đã có em.
Smith ngay tại đây?
>> DAVID J. Malan: Smith, cảm ơn bạn.
Vì vậy, tôi sẽ tiếp tục tìm lên Smith?
>> ALAN Estrada: Oh, yeah.
Không không không.
Ồ không.
Cái này của tôi.
>> DAVID J. Malan: Oh, bạn đã nhận Smith.
ĐƯỢC.
>> ALAN Estrada: Yeah, tôi đã Smith ngay tại đây.
Xin lỗi các bạn.
Tôi nghĩ chúng ta Michael-- đang tìm kiếm cho Michael.
Xin lỗi.
>> DAVID J. Malan: Đó là OK.
Được rồi, bây giờ chúng tôi vào Paccini and Sons.
>> ALAN Estrada: Paccini và con trai.
DAVID J. Malan: Chỉ có bạn và tôi ở trên này.
ĐƯỢC.
Tìm chúng tôi Mike Smith.
Smith.
>> ALAN Estrada: Smith.
>> DAVID J. Malan: Smith.
Chúng tôi đang ở trong R rác.
ALAN Estrada: rác.
Oh.
Điều này sẽ mất một thời gian.
>> [Cười]
DAVID J. Malan: Giày dép.
Chúng tôi đang ở trong giày.
>> ALAN Estrada: Bây giờ chúng tôi đang gonna--
>> DAVID J. Malan: Nice.
ALAN Estrada: Which--
[Cười]
Oh, điều này là rất tốt.
[Cười]
>> DAVID J. Malan: Đó là OK.
>> ALAN Estrada: Oh, điều này là tốt.
Tôi không nghĩ rằng tôi sẽ có bạn bè PSAT sau này.
DAVID J. Malan: Tốt.
Sporting.
ALAN Estrada: Sporting.
Um, L, M, N, O, P.
DAVID J. Malan: OK.
Vì vậy, hãy xé này trong một nửa.
Đó là OK.
Điều này kết thúc kém anyway, vì Mike Smith sẽ không được trong các trang vàng.
>> ALAN Estrada: Aw.
>> DAVID J. Malan: Không, nó là OK.
Nhưng chúng ta hãy giả vờ như ông trên trang này.
Vì vậy, bây giờ, bạn đã đẽo vấn đề xuống một trang, và chúng tôi thấy Mike Smith.
>> [Cổ vũ]
Được rồi cám ơn bạn.
ĐƯỢC.
Đó là điều bất thường.
Nhưng nó vẫn còn nhanh hơn so với tìm kiếm tuyến tính,
trong đó chúng tôi bắt đầu vào bắt đầu của cuốn sách,
và chúng tôi di chuyển theo cách của chúng tôi từ trái sang phải, Cuối cùng tìm kiếm Mike Smith.
Và như vậy, nếu cuốn sách điện thoại có lẽ 1.000 trang,
có thể nó đã có thể lấy chúng tôi 10 hoặc để trang nước mắt.
>> Nhưng bạn có thể đã thừa hưởng chạm vào một giả định
trong tất cả điều đó, mà là để nói rằng các cuốn sách điện thoại trước là gì?
Đung Sắp xếp.
DAVID J. Malan: Nó được sắp xếp.
Phải không?
Nó được sắp xếp theo thứ tự abc, vì vậy rằng tất cả những tên và số
đều được sắp xếp từ A đến Z, và theo bảng chữ cái ở giữa.
Nhưng hôm nay, chúng ta bây giờ yêu cầu các câu hỏi, tốt,
Làm thế nào mà Verizon hoặc điện thoại Công ty có được nó vào trạng thái đó?
>> Bởi vì nó là một điều để tận dụng Giả định rằng, và do đó,
giải quyết một vấn đề với một thuật toán hiệu quả hơn.
Nhưng chúng ta không bao giờ thực sự hỏi trong tuần không, tốt,
bao nhiêu đã làm nó chi phí Verizon hoặc người khác
để nhận được rằng cuốn sách điện thoại để sắp xếp?
>> Phải không?
Nó không quan trọng nếu nhìn lên Mike Smith
là siêu nhanh, nếu bạn cần một năm để sắp xếp các trang ban đầu.
Phải không?
Bạn cũng có thể chỉ chọn lọc thông qua một cuốn sách điện thoại ngẫu nhiên,
nếu nó sẽ là siêu đắt tiền để sắp xếp nó.
Vì vậy, nếu chúng ta có thể có tình nguyện viên khác.
Chúng ta hãy nhìn lên tại đây làm thế nào chúng ta might-- đi trên up-- như thế nào
chúng tôi có thể đi về phân loại này.
>> Và nếu thực sự có thể Jordan tham gia chúng tôi lên đây trên sân khấu.
Nào lên chỉ trong một khoảnh khắc.
Tên bạn là gì?
CAROLINE: Caroline.
DAVID J. Malan: Caroline, đi lên trên.
Và bạn sẽ được tham gia bởi tôi và Jordan ở đây.
Caroline, cảm ơn bạn.
Được rồi.
Vì vậy, những gì chúng tôi có ở đây cho Caroline là 26 cuốn sách màu xanh
mà FAS sử dụng để quản lý một số kỳ thi cuối cùng.
Đây là nhận được khó khăn để tìm kiếm, nhưng những gì chúng tôi đã thực hiện trước
là chúng ta đã đặt tên của ai đó trên mặt trước của mỗi trong số này,
nhưng chúng tôi đã giữ nó đơn giản bằng sau đó đưa ra tên đầy đủ.
Vì vậy, chúng tôi sẽ đưa cho người có tên L, D, J, B, tất cả các cách từ A đến Z,
nhưng họ đang ở trong thứ tự ngẫu nhiên.
Và do đó, nếu bạn muốn, bạn nói chuyện cách thức thông qua các vấn đề như bạn
làm điều đó, bạn có thể đi trước và sắp xếp những đối với chúng tôi, từ A đến Z.
>> Đung OK, do đó L là như thế, giữa.
C đang bắt đầu.
B. J trước khi L. B, Q.
>> DAVID J. Malan: Giữ rằng suy nghĩ trong một giây.
Bởi vì nếu không, đây chỉ là thú vị cho bạn, cho tôi, và Jordan.
Hiện chúng tôi đi.
Đung [không nghe được].
R.
DAVID J. Malan: OK.
Bạn đang lam gi thê?
>> CAROLINE: M đưa ra sau khi O.
>> DAVID J. Malan: OK.
>> CAROLINE: O.
DAVID J. Malan: O, Tốt.
>> CAROLINE: E.
>> DAVID J. Malan: E, F. Yeah.
>> CAROLINE: T, U, V.
>> DAVID J. Malan: V, T, U, V. Vì vậy, nó Có vẻ như bạn đang making-- tiếp tục đi.
Có vẻ như bạn đang làm một đống lớn trên đây,
và loại một đống lớn trên đó.
Vì vậy, nửa đầu của bảng chữ cái, nửa thứ hai của bảng chữ cái.
ĐƯỢC.
Tốt.
Kind tách các vấn đề trong hai.
M, N, X. Yeah.
CAROLINE: K.
DAVID J. Malan: OK.
K. Vì vậy, bạn đang loại lựa chọn họ cái khác,
đặt nó hoặc trái hoặc phải, hoặc Z đi trên sàn nhà.
ĐƯỢC.
>> CAROLINE: Z đang xảy ra sàn.
>> DAVID J. Malan: OK.
Y đang đi trên sàn nhà.
Bây giờ chúng ta có thể đưa X.
>> CAROLINE: G.
DAVID J. Malan: G của going trái.
S được đi bên phải.
Tất cả các quyền, A được đi tất cả các cách còn lại.
>> CAROLINE: A, B, C, D.
>> DAVID J. Malan: Bây giờ, tốt.
Chúng tôi đã có A, B, C. W đi xuống đó.
Tất cả các quyền, T.
>> CAROLINE: H, I, J.
DAVID J. Malan: H, I, J. Tốt.
CAROLINE: Ở trung tâm, tôi gonna--
DAVID J. Malan: OK.
Vì vậy, bây giờ, chúng ta sẽ loại của hợp nhất các cọc khác nhau.
Vì vậy, từ A đến C, sau đó tôi thấy D, và E và F, và G, và H và I. Nice.
J, K. Và sau đó, đống này là lộn ngược, nhưng đó là OK.
Chắc chắn.
Chúng tôi có thể cắt giảm một số góc.
ĐƯỢC.
Và sau đó chúng ta cần W, X, Y, Z.
>> CAROLINE: Yeah.
>> DAVID J. Malan: Tuyệt vời.
Vì vậy, một lớn, cảm ơn bạn Caroline để phân loại này.
>> [Cổ vũ]
>> Cam on.
Cảm ơn rất nhiều.
Vì vậy, bây giờ chúng ta hãy xem xét một lúc cách Caroline đã đi về làm điều đó,
và chính xác những gì chúng tôi đã có thể đối với: làm thế nào chúng tôi
đã có thể giải quyết điều đó vấn đề khi chúng tôi chỉ
đưa ra một bó toàn bộ các yếu tố đầu vào ngẫu nhiên.
>> Vâng, có vẻ như có là một chút của một hệ thống có?
Phải.
Vì vậy, các chữ cái đầu trong bảng chữ cái, cô
đã đặt sang bên trái, và chữ sau trong bảng chữ cái,
cô đã gửi gắm vào bên phải.
Và ngay khi cô tìm thấy một số chữ cái gần, những người
mà đi ngay bên cạnh nhau, cô sẽ đưa những người trong đơn đặt hàng.
Và vì vậy chúng tôi đã có những loại nhỏ đống đầu vào được sắp xếp diễn ra.
>> Và đó là khá giống như những gì nhất của con người chúng ta sẽ làm gì.
Chúng tôi sẽ sắp xếp của sàng lọc thông qua nó, và chúng tôi chắc hẳn sẽ có một cơ chế.
Nhưng nó có thể là khó khăn để viết nó xuống trong một công thức cho mỗi gia nhập.
Nó cảm thấy nhiều hơn một chút hữu cơ hơn.
Vì vậy, chúng ta hãy xem nếu chúng ta bây giờ có thể bị ràng buộc các vấn đề với ít đầu vào.
>> Thay vì 26, chúng ta hãy làm một cái gì đó rất ít
chỉ nói, bảy, đằng sau các cửa ra vào, vì vậy để nói chuyện.
Là chỉ có bảy con số?
Và nếu mục tiêu tại mặt là để tìm một giá trị,
chúng ta hãy xem làm thế nào có hiệu quả chúng ta có thể đi về việc này.
Và chúng ta hãy xem liệu chúng ta có thể bây giờ bắt đầu áp dụng một số con số,
hoặc một số công thức nào đó để mô tả hiệu quả của cuốn sách điện thoại của chúng tôi
Thuật toán, thuật toán sách thi của chúng tôi, và nói chung, việc tìm kiếm thông tin.
>> Vì vậy, đối với chuyện này, tôi đi trước, và trên màn hình cảm ứng trên đây,
đưa ra một trình duyệt web có chính xác những bảy cửa.
Và nếu chúng ta có thể có được một khác tình nguyện đến trên hơn ở đây,
Tôi đã đặt các cửa ra vào cùng ở đây.
Tình nguyện viên nhanh chóng.
>> Đây demo one-- đang đi đến một nhanh hơn và nhanh hơn bây giờ.
Come on xuống.
Tên bạn là gì?
TREVOR: Trevor.
>> DAVID J. Malan: Trevor?
Tất cả các quyền, Trevor, đi trên xuống.
Vì vậy, Trevor đã tình nguyện ở đây để làm một vấn đề tương tự, nhưng một trong đó là
hẹp trong phạm vi, và điều đó để cho phép chúng tôi cố gắng để chính thức hóa doanh nghiệp
quá trình để phân loại những con số này.
>> Vì vậy, Trevor, rất vui được gặp bạn.
Vì vậy, đây là một mảng, do đó, để nói, một danh sách bảy cửa.
Đi trước và tìm thấy chúng tôi số 50.
Và sau đó sau khi thực tế, cho chúng tôi biết làm thế nào bạn tìm thấy nó.
Nên be-- tất cả các quyền.
Vâng, đây là một trong đây?
Uh-oh.
ĐƯỢC.
Bạn nhấp một.
Tốt.
>> Và tốt.
Bây giờ bạn nhấp một.
Và hãy để tôi cung cấp cho bạn các microphone, do đó bạn có nó chỉ trong một khoảnh khắc.
Đi trước và nhấp vào cửa tiếp theo mà bạn dự định.
Vâng tốt.
TREVOR: Tôi có thể bỏ chọn một cánh cửa?
DAVID J. Malan: Không, bạn không thể bỏ chọn.
TREVOR: OK.
Cái này.
DAVID J. Malan: Nơi nào bạn muốn đi đâu?
Cái nào?
>> TREVOR: Đó là một trong.
>> DAVID J. Malan: No.
>> TREVOR: OK.
Cái này.
>> DAVID J. Malan: Yes.
Đó là tốt.
Được rồi.
Vì vậy, những gì đã được thuật toán của bạn hoặc thủ tục để làm điều này, Trevor?
>> TREVOR: Tôi chỉ cần đi qua cửa cho đến khi tôi tìm thấy một 50.
DAVID J. Malan: OK.
Excellent thuật toán.
Vì vậy, đó là tốt.
Bởi vì trong thực tế, nếu tôi tiết lộ những gì đằng sau hai cánh cửa khác, những gì
chúng ta sẽ tìm thấy ở đây là chúng ta chỉ có đầu vào ngẫu nhiên.
Vì vậy, đó là thực sự là tốt như bạn có thể có được.
Và trong thực tế, bạn đã tốt hơn so với triệt tìm kiếm toàn bộ mảng,
vì nó đã thực sự không may mắn nếu bạn đã trúng số
50 mua tại cửa cuối cùng.
Nhưng nếu chúng ta thay vì đã cho bạn một giả định.
Giả sử tôi sắp xếp tất cả các các cửa xung quanh,
vì vậy mà bạn có số sắp xếp thời gian này,
nhưng lần này nó thực sự một different-- thời gian này,
nó thực sự được sắp xếp cho bạn.
Và bây giờ là mục tiêu trong tầm tay là để đánh số 50.
>> TREVOR: OK.
>> DAVID J. Malan: Có gì thuật toán của bạn sẽ được?
>> TREVOR: Vâng, nếu nó sắp xếp, nó hoặc là đi
để be-- nếu lớn nhất đến lớn nhất, giảm dần, nó sẽ là người đầu tiên,
hoặc nếu nó là ngược lại, nó sẽ là người cuối cùng.
Vì vậy, tôi sẽ chỉ cần gõ nhẹ cánh cửa này, và sau đó chỉ cần gõ nhẹ vào cánh cửa cuối cùng.
DAVID J. Malan: Tuyệt vời.
Được rồi.
Vì vậy, chúng tôi nhận thấy số lượng 50.
Vì vậy, ngay sau khi bạn biết họ đã được sắp xếp, chúng tôi
đã có thể tận dụng giả định này.
Vì vậy, họ quá giống ví dụ danh bạ điện thoại.
Ngay khi bạn có, ngay cả với một vấn đề nhỏ như thế này,
đầu vào của bạn trước khi sắp xếp, chúng ta có thể thực sự tìm ra giá trị cho là
hiệu quả hơn.
>> Và tôi đã không nói cho bạn nếu nó là sắp xếp nhỏ đến lớn, hoặc lớn đến nhỏ,
và do đó, nó là rất hợp lý để bắt đầu ở một đầu hay khác
để thực sự thấy rằng giá trị đích.
Vì vậy, cảm ơn đến Trevor là tốt.
Và tôi sẽ propose-- thực hiện độc đáo.
Chúng tôi có một chút clip, thực sự, mà là một trong những khoảnh khắc yêu thích của chúng tôi trong CS50,
nhờ đó mà đôi khi những bản demo không hoàn toàn đi theo kế hoạch.
Và thực sự ngay bây giờ, tôi kéo lên các giao diện sai
mà để sử dụng màn hình cảm ứng.
Vì vậy, đó là lỗi của tôi ở đó.
>> Vì vậy, điều này sẽ làm cho Clip năm tới như
tại sao tôi đã nhấp vào màn hình của riêng tôi.
Nhưng chúng ta hãy có một cái nhìn nhanh chóng vào những gì xảy ra năm ngoái
với Jay, người đã đưa ra, nhiều như Trevor đây, tình nguyện,
và trong đoạn clip ngắn này, bạn sẽ thấy như thế nào cùng một bản demo này không hoàn toàn
tiết lộ những bài học cùng học.
[VIDEO PLAYBACK]
Tôi muốn -Tất cả các bạn phải làm bây giờ là để tìm cho tôi, và cho chúng ta,
thực sự, số 50 một bước tại một thời điểm.
>> -Các Số 50?
>> -Các Số 50.
Và bạn có thể tiết lộ những gì đằng sau mỗi cánh cửa
chỉ đơn giản bằng cách chạm vào nó với một ngón tay.
Chết tiệt.
>> [Cười]
>> [END PLAYBACK]
DAVID J. Malan: Vì vậy mà đã đi rất tốt.
Đó là những cánh cửa không được phân loại.
Và Jay, tất nhiên, tìm thấy nó quá nhanh.
Trevor đã làm một công việc tốt hơn nhiều về một thời điểm có thể dạy dỗ,
có thể nói, năm nay ở mất nhiều thời gian để tìm thấy nó.
Tất nhiên, sau đó chúng tôi đã cho Jay một cơ hội thứ hai,
nhờ đó chúng ta sắp xếp các cửa ra vào, cũng như chúng ta đã làm cho Trevor,
và Trevor đã làm siêu cũng thời gian này.
Nhưng Jay đã làm nó một nửa là nhanh chóng.
[VIDEO PLAYBACK]
Mục tiêu -Các bây giờ là cũng tìm thấy chúng tôi số 50,
nhưng làm điều đó thuật toán, và cho chúng tôi biết bạn đang đi về nó.
>> -ĐƯỢC.
>> -Và Nếu bạn tìm thấy nó, bạn giữ cho bộ phim.
Nếu bạn không tìm thấy nó, bạn cho nó trở lại.
>> -Man.
>> -Oh!
>> - [Không nghe thấy] OK.
Vì vậy, tôi sẽ đến kiểm tra kết thúc đầu tiên để xác định nếu there's-- Oh.
>> [Vỗ tay]
>> [END PLAYBACK]
DAVID J. Malan: OK.
Vì vậy, phân loại rõ ràng cửa dẫn đến hiệu quả cao hơn.
Và như vậy, nhanh gấp hai lần là những gì tôi có nghĩa là ở đó.
Và do đó, Jay đã may mắn cả hai lần.
Và anh cũng đã may mắn vì cuối cùng năm, tôi ra lệnh cho một số đĩa Blu-ray
để thực sự đưa ra.
Tôi xin lỗi năm nay, chúng tôi không có cùng, Trevor.
Nhưng vẫn còn tốt hơn là một vài năm trở lại.
Và một số bạn có thể biết điều này đồng, Sean, khi ông ở CS50,
đã được thử thách với chính xác cùng một vấn đề, mặc dù trong SD,
như bạn sẽ sớm thấy, trở lại trong ngày.
Và bạn sẽ thấy rằng không chỉ anh lâu hơn một chút so với Jay,
lâu hơn một chút so với Trevor, nó là thực sự có cơ hội tuyệt vời này
để tham gia vào hầu như tất cả mọi người trong một đám đông la Price is Right, khuyến khích
anh ta để tìm số chúng tôi đang tìm kiếm.
Hãy. có một cái nhìn nhanh chóng.
>> [VIDEO PLAYBACK]
>> -ĐƯỢC.
Vì vậy, nhiệm vụ của bạn ở đây, Sean, là sau đây.
Tôi đã giấu đằng sau những cửa số bảy.
Nhưng nằm khuất trong một số các cửa cũng như là những con số tiêu cực khác.
Và mục tiêu của bạn là để suy nghĩ của hàng trên cùng của số
như chỉ là một mảng, hoặc chỉ chuỗi các mẩu giấy
với những con số phía sau họ.
Và mục tiêu của bạn là, chỉ sử dụng đầu mảng ở đây, tìm thấy tôi số bảy.
Và chúng tôi đang đi sau đó để phê phán làm thế nào bạn đi về làm việc đó.
-Được rồi.
-find Chúng tôi biết số bảy, xin vui lòng.
Không.
Năm, 19, 13.
>> [Cười]
>> Nó không phải là một câu hỏi trick.
One.
>> [Cười]
Tại thời điểm này, điểm số của bạn không phải là rất tốt, vì vậy bạn cũng có thể tiếp tục đi.
Ba.
>> [Cười]
>> Đi trên.
Thành thật mà nói, tôi không thể không tự hỏi thậm chí những gì bạn đang suy nghĩ về, so--
>> [Cười]
Chỉ có hàng hàng đầu, do bạn đã có ba trái.
Vì vậy, tìm thấy tôi bảy.
>> [Cười]
17.
Bảy.
>> [Vỗ tay]
>> Được rồi.
>> [END PLAYBACK]
>> DAVID J. Malan: Vì vậy, chúng ta có thể xem các tất cả các ngày dài.
Và tất nhiên, một số trình diễn năm nay có lẽ
bây giờ sẽ kết thúc trong tiếp theo Video của năm là tốt.
Vì vậy, bây giờ chúng ta thực sự tập trung vào các thuật toán
ở đây, và xem nếu chúng ta không thể bây giờ bắt đầu để chính thức hóa
làm thế nào chúng ta có thể đi về việc dữ liệu của chúng tôi vào trạng thái này mà nó được sắp xếp,
vì vậy mà cuối cùng, chúng ta có thể thực sự tìm kiếm nó một cách hiệu quả hơn.
Và mặc dù chúng ta đang đi sử dụng bộ dữ liệu tương đối nhỏ,
như tám con số chúng tôi có ở đây trên bảng,
cuối cùng những ý tưởng tương tự có thể được áp dụng 1.000 đầu vào, một triệu đầu vào,
4 tỷ đầu vào, bởi vì các thuật toán đang có được về cơ bản giống nhau.
>> Và do đó, đây là cuối cùng của chúng tôi cơ hội cho các tình nguyện viên ngày hôm nay,
nhưng có lẽ là một trong tham gia nhiều nhất, mà chúng cần tám tình nguyện viên
để đi lên và đi bộ với chúng tôi qua quá trình phân loại những gì sẽ sớm
được các nhạc đứng ở đây.
Hãy để tôi bắt đầu trở lại đây.
>> Vì vậy, một trong các màu xanh lá cây turquoise-- là nó?
Bạn đang cam kết?
Hai.
Come on xuống.
ĐƯỢC.
Ba.
Bốn.
Hãy me-- OK, năm.
Bạn đang được đề cử bởi bạn bè của bạn.
Sáu, bảy, tám người.
Nào lên.
Được rồi.
Cam ơn rât nhiêu.
Nào lên.
>> Được rồi.
Vì vậy, những gì chúng tôi có và here-- này là một trong số những người vụng về,
vì điều này sẽ yêu cầu bạn hài hước tôi chỉ là một chút ít thời gian.
Bạn phải là số một.
Tên bạn là gì?
>> Annan: Annan.
>> DAVID J. Malan: Annan.
David.
Tên bạn là gì?
>> JOSEPH: Joseph.
>> DAVID J. Malan: Joseph, bạn là số hai.
>> SERENA: Serena, số ba.
Stefan, số bốn.
CYNTHIA: Cynthia.
DAVID J. Malan: Cynthia, thứ năm.
[Không nghe thấy]
DAVID J. Malan: [Không nghe thấy].
David, số sáu.
MATT: Matt.
DAVID J. Malan: số Matt bảy.
Và?
>> WAVERLY: Waverly.
>> DAVID J. Malan: Waverly, số tám.
Được rồi.
Nếu bạn could-- whoops.
Nếu tất cả các bạn, như bạn Thách thức đầu tiên, có
tám khán đài âm nhạc ở đây phải đối mặt với khán giả.
Nếu bạn có thể đưa con số của bạn trên những nhạc đứng theo cách như vậy
rằng họ lên đường với cùng một số trên bảng.
Vì vậy, làm cho mình trông như thế bởi đưa con số của bạn bằng các nhạc
đứng ở đây.
Tuyệt vời cho đến nay.
>> Tuyệt vời.
ĐƯỢC.
Vì vậy, bây giờ, chúng tôi sẽ yêu cầu các câu hỏi trong một vài cách khác nhau.
Làm thế nào chúng ta có thể đi về phân loại những người này lên đây?
Bởi vì chúng tôi đã có một vài phương pháp trước đó, nhờ đó mà chúng tôi đã
loại làm hai xô nước khác nhau.
Và sau đó chúng tôi đã thường vẽ ra những thứ cùng nhau.
Ngay khi chúng tôi nhìn thấy hai con số mà thuộc về nhau,
chúng tôi đặt chúng lại với nhau.
Hai chữ cái thuộc về nhau.
>> Nhưng chúng ta hãy xem chúng tôi không thể chính thức hóa này,
vì vậy mà cuối cùng chúng ta có một số mã giả bạn sẽ,
mà bạn có thể giải quyết những vấn đề này.
Vì vậy, bây giờ, tôi nhìn ra ngoài ở những con số ở đây.
Và tôi nhìn thấy một bó toàn bộ những sai lầm.
Cuối cùng, tôi muốn một trên trái và tám trên bên phải.
>> Và vì vậy tôi đang tìm kiếm tại hai, bốn và hai.
Và vấn đề là gì, rõ ràng?
Yeah.
So.
Hai rõ ràng là đi trước bốn, vì vậy bạn có biết những gì?
Hãy để chúng tôi có cách tiếp cận tham lam, nếu bạn sẽ, nhiều vấn đề như thế
thiết one-- nếu bạn nhớ lại từ Standard Edition của Problem Set One,
nơi mà tôi chỉ ở địa phương giải quyết vấn đề mà ở ngay tại đây trước mặt tôi
và nhìn thấy nơi nó dẫn tôi.
>> ĐƯỢC.
Vì vậy, hai và bốn, để tôi đi trước và chỉ trao đổi hai bạn.
Nếu bạn có thể chất có thể di chuyển mình và giấy của bạn,
Tôi dường như đã nhận liệt kê trong một nhà nước tốt hơn.
>> Bây giờ, họ đang tốt.
Tôi sẽ di chuyển trên, bốn và sáu, có vẻ tốt.
Không thành vấn đề.
Sáu và tám, OK.
Tám và một người, một vấn đề khác.
Bởi vì những gì là sự thật về tám và một trong những?
One đến trước tám, và vì vậy những gì chúng ta nên làm gì?
Hãy trao đổi hai.
Một tám người.
Và bây giờ, tôi sẽ tiếp tục đi.
Tôi sẽ tiếp tục tìm kiếm ở phía trước.
Và chúng ta hãy xem những gì sẽ xảy ra.
Tám và ba, của Tất nhiên, trong trật tự.
Hãy trao đổi.
Tám và bảy, tất nhiên.
Trong trật tự.
Hãy trao đổi.
Tám và năm, tất nhiên, chúng ta hãy trao đổi.
Được rồi.
Danh sách được sắp xếp.
yes?
>> OK, rõ ràng là không.
Nhưng nó là một chút tốt hơn, phải không?
Bởi vì thông báo những gì đã xảy ra.
Mỗi lần chúng tôi thực hiện một trao đổi, một nhỏ hơn số loại percolated theo cách đó,
và một số lớn hơn percolated cách này, hoặc chúng tôi sẽ
bắt đầu câu nói hởi đến trái hoặc bọt khí bên phải.
>> Bây giờ, đó là không đủ, bởi vì lúc tốt nhất một số có thể
đã di chuyển một chỗ về phía trước, hoặc ít nhất
một số có thể có chuyển một chỗ xa hơn.
Vì vậy, bạn biết những gì, loại này của làm việc khá tốt cho đến nay.
Hãy để tôi chỉ cần thử nó một lần nữa.
Hai và bốn, họ đang OK.
Bốn và sáu, họ đang OK.
Sáu và một, trong trật tự.
Vì vậy, hãy trao đổi hai bạn.
Và bây giờ, thấy ra vấn đề của bắt đầu để có được một chút tốt hơn nữa.
Sáu và ba, trong trật tự.
Hãy trao đổi hai bạn.
Sáu và bảy, bạn tốt.
Bảy năm và, tất nhiên, không theo thứ tự.
Bảy và tám, theo thứ tự.
Và bây giờ, tôi có thể cần đến làm điều này một vài lần nữa.
Và trên thực tế, suy nghĩ cho mình có lẽ bao nhiêu lần tối đa
Có lẽ tôi phải đi bộ qua lại?
>> Chúng ta sẽ quay trở lại đó.
Vì vậy, hai và bốn là vẫn OK.
Bốn và một, nope.
Vì vậy, chúng ta hãy trao đổi.
Và một lần nữa, thông báo trực quan một là loại bọt
bên trái, nơi mà nó nên được.
Bốn và ba swap.
Bốn và sáu.
Sáu năm và trao đổi.
Sáu và bảy.
Bảy và tám là tốt.
>> Tốt.
Chúng tôi đang nhận được thậm chí còn tốt hơn.
Vì vậy, chúng ta hãy xem.
Bây giờ, chúng ta có hai và một.
Tất nhiên, trao đổi.
Hai và ba, ba và bốn, bốn và năm, sáu và bảy, bảy và tám.
Tốt.
Và bạn biết những gì?
Bởi vì tôi đã thực hiện một sự thay đổi đó, hãy để tôi làm một kiểm tra sự tỉnh táo.
Hãy để tôi đi tất cả các cách bắt đầu trở lại.
ĐƯỢC.
Một, two-- yup, thấy không?
Một cái gì đó đã sai.
Ba, bốn, năm, sáu, bảy, tám.
Và trong đường chuyền cuối cùng này, là bạn cảm thấy thoải mái với bây giờ của tôi
tuyên bố đây là sắp xếp?
ĐƯỢC.
Nhìn bề ngoài, điều đó hoàn toàn đúng.
Nhưng chức năng, những gì đã làm cũng chỉ xảy ra
trong đó đường chuyền cuối cùng cho phép bạn để xác nhận rằng danh sách này thực sự là
sắp xếp?
>> Tôi đã làm gì hoặc không làm vượt qua cuối cùng này?
Đung Không có thay đổi.
DAVID J. Malan: Xin lỗi?
Đung Không có thay đổi.
DAVID J. Malan: Không có thay đổi.
Vì vậy, nó sẽ là ngu ngốc của tôi làm điều đó một lần nữa cùng một thuật toán
nếu tôi không thực hiện bất kỳ thay đổi lần đầu tiên.
Và nhà nước đã không thay đổi.
Chắc chắn, tôi sẽ không làm cho bất kỳ thay đổi lần thứ hai.
Và như vậy, nó an toàn hiện nay để nói, danh sách được sắp xếp.
>> Và quả thực, đây là bây giờ một cái gì đó mà chúng ta sẽ thường
gọi bong bóng sắp xếp, theo đó cặp, bạn sửa chữa sai lầm một lần nữa,
và một lần nữa, và một lần nữa, và bạn tiếp tục đi qua lại,
và qua lại, cho đến khi bạn làm cho không có giao dịch hoán đổi như vậy, tại thời điểm đó
bạn có thể tự tin, yeah, tôi hoàn thành sửa chữa tất cả những sai lầm.
Hãy thiết lập lại và cố gắng tiếp cận khác.
Nếu các bạn có thể quay trở lại thứ tự mà bạn đã được một thời gian trước đây,
mà nhìn như thế này.
Bây giờ, chúng ta hãy một cách tiếp cận một ít nhiều giống như cuốn sách kỳ thi,
nhờ đó mà chúng tôi đã không ngừng chọn mẫu tự của bảng chữ cái
rằng chúng tôi loại muốn để đối phó với tới.
Có lẽ đó là một lá thư cao, như A, hoặc một thư Z. thấp
>> Vì vậy, tất cả mọi người trở lại theo thứ tự này.
Và bây giờ hãy để tôi làm việc này.
Hãy xem tôi biết tôi có tám số ở đây.
Tôi sẽ đi trước và chỉ cố tình chọn
các yếu tố nhỏ nhất.
Phải không?
Điều này có vẻ trực quan quá.
Tại sao tôi không tìm nhỏ nhất phần tử, đặt nó nơi nó thuộc về,
sau đó nhận được các phần tử nhỏ nhất tiếp theo, đặt nó, nơi nó thuộc về, và chỉ cần lặp lại.
>> Bởi vì trực giác, mà nên làm việc quá.
Vì vậy, bốn, đó là một con số khá nhỏ.
Tôi sẽ nhớ nơi này là.
Đợi một lát.
Hai là nhỏ hơn.
Bây giờ tôi nhớ nơi hai là, và quên đi bốn.
Chúng tôi sẽ đối phó với điều đó sau này.
Six, tôi không quan tâm.
Tám, tôi không quan tâm.
Một là số lượng nhỏ mới của tôi.
Vì vậy, tôi sẽ nhớ nơi có một.
Ba, không quan tâm.
Bảy, không quan tâm.
Năm, không quan tâm.
>> Vì vậy mà không rơi khỏi các giai đoạn trong năm nay,
Tôi sẽ lấy số one-- và là những gì tên của bạn một lần nữa?
>> Annan: Annan.
>> DAVID J. Malan: Annan.
Và nếu bạn có thể tham gia cùng tôi tại đầu của danh sách,
chúng ta hãy đưa bạn về nơi anh.
Unfortunately-- tên của bạn là gì?
>> STEFAN: Stefan.
>> DAVID J. Malan: Stefan là trong cách.
Vì vậy, trước khi Stefan giải quyết điều này vấn đề, những gì chúng ta nên làm gì?
Chúng ta làm gì với Stefan?
>> Đung [không nghe được].
DAVID J. Malan: OK.
Vì vậy, chúng ta có thể làm điều đó.
Chúng ta có thể loại mất Stefan và mình bốn, và chỉ cần đặt nó trong một biến
và giữ nó cho một số lượng thời gian,
do đó để có chỗ cho số một.
Và đó không phải là xấu.
Tôi có thể đề xuất, tại sao không chúng ta chỉ cần đặt Stefan ở đây?
Tại sao điều này có thể vi phạm một của ý tưởng chúng tôi bắt đầu
nói về thời gian trước, tuần qua?
Yeah?
>> Đung [không nghe được].
>> DAVID J. Malan: Không có chỉ số cho nó.
Nếu bạn nghĩ về điều này, thực sự, như một mảng, đây giống như một tiêu cực,
vì vậy không có bộ nhớ thực sự ở đây nếu điều này thực sự là một mảng,
như chúng ta tuyên bố tuần trước trong bài giảng.
Vì vậy, chúng ta không nên làm điều này.
Chúng ta có thể lưu trữ nó trong một biến.
>> Hoặc bạn biết những gì?
Tôi nghe ai đó khuyên nó.
Những gì người khác chúng ta có thể làm gì với Stefan?
Tại sao chúng ta không đuổi anh ta và đưa anh ta về nơi số một là.
Vì vậy, nếu bạn muốn đi qua đó.
Và quả thực, đây là một giải pháp khá tốt.
Bây giờ trên một mặt, tôi đã loại của làm cho vấn đề tồi tệ hơn.
Bốn giờ xa từ nơi nó nên được.
Nó sẽ được hướng tới một nửa này.
>> Nhưng bạn biết những gì?
Có thể đã là may mắn.
Có lẽ số tám đã ở đây.
Và như vậy, có lẽ chúng ta sẽ đã nhận được may mắn,
và đẩy tám gần hơn đến cùng.
Vì vậy, vào cuối ngày, nó loại của tất cả các trung bình ra.
Chúng ta không cần phải quan tâm đến bốn.
Tất cả tôi quan tâm bây giờ là lựa chọn các phần tử nhỏ nhất.
>> Và bây giờ, những gì tôi sẽ làm là quên về một số
vĩnh viễn, bởi vì tôi biết danh sách phía sau tôi bây giờ được sắp xếp.
Vì vậy, danh sách của tôi trước đây là kích thước tám.
Bây giờ, nó có kích thước bảy.
Vì vậy, vấn đề của tôi là nhận được nhỏ hơn, mặc dù tuyến tính.
Vì vậy, bây giờ, tôi sẽ chọn phần tử nhỏ nhất hiện nay, hai.
Sáu, tám, bốn, ba, bảy, năm.
Đó là yếu tố nhỏ nhất.
Vì vậy, những gì tôi sẽ làm gì with-- là những gì tên của bạn một lần nữa?
>> JOSEPH: Joseph.
>> DAVID J. Malan: Joseph?
Chúng tôi đang đi để lại Joseph tại chỗ.
Bây giờ, tôi sẽ giả vờ rằng những kẻ are-- tốt,
Tôi biết rằng hai đã được sắp xếp.
Bây giờ chúng ta tập trung vào các còn lại của danh sách.
Sáu là nhỏ nhất hiện nay.
Tám là lớn hơn.
Bốn doanh nghiệp là nhỏ nhất hiện nay.
Bây giờ ba là nhỏ nhất hiện nay.
Và vì vậy bây giờ, tôi sẽ chọn ba, người is-- tên của bạn là gì nữa?
SERENA: Serena.
DAVID J. Malan: Serena, nếu bạn có thể lấy số lượng và trao đổi của bạn with--
Kalsang: Kalsang.
DAVID J. Malan: Kalsang.
Quay trở lại sau, và chúng tôi đi để trao đổi hai.
Và bây giờ, chúng ta hãy đặt này trên máy lái tự động.
Tôi sẽ đi và để nó đến với bạn để chọn các yếu tố nhỏ nhất tiếp theo.
Dun, dun, dun, dun.
Số bốn, những gì bạn nên làm gì?
Tuyệt vời.
Bây giờ, tôi sẽ làm cho đường chuyền khác.
Dun, dun, dun, dun.
Tôi thấy năm là nhỏ nhất tiếp theo.
Bây giờ, tôi sẽ đi đường chuyền khác.
Dun, dun, dun, dun.
Sáu là nhỏ nhất.
Tốt.
Bảy là nhỏ nhất.
Không thay đổi.
Tám là nhỏ nhất.
Xong.
>> Vì vậy, những gì chúng ta vừa thực hiện bằng cách lặp đi lặp lại chọn một trong các yếu tố sau khi khác
được thực hiện một cái gì đó mà chúng tôi sẽ chính thức hóa như sắp xếp chọn.
Và nó có lẽ thậm chí đơn giản để giải thích,
trong đó nghĩa là tất cả các bạn muốn làm là chỉ cần giữ
đi lui trong danh sách lựa chọn, các phần tử nhỏ nhất tiếp theo,
cho đến khi bạn thực hiện xong.
>> Vì vậy, nó thậm chí còn đơn giản hơn, có lẽ trực giác, so với năm ngoái.
Hãy thử một lần cuối cùng.
Nếu các bạn có thể thiết lập lại chính mình vào các vị trí sau
một lần cuối cùng, chúng ta hãy xem nếu chúng ta không thể Bây giờ chính thức hóa một cách tiếp cận khác.
Trong thực tế, sẽ có ai đó ra có muốn đề nghị
làm thế nào khác chúng ta có thể đi về việc này?
Nếu không có tung ra từ thông dụng hoặc loại các câu trả lời đó đã được biết đến,
chỉ bằng trực giác, những gì chúng ta có thể làm gì?
>> Đung [không nghe được].
DAVID J. Malan: Yeah.
Vì vậy, có một số trực giác tuyệt vời đó.
Những điều tốt đẹp dường như xảy ra vậy, đến nay khoa học máy tính khi chúng ta chia
và chinh phục các vấn đề về phân chia nó trong một nửa và một nửa và một nửa.
Và như vậy thực sự, chúng tôi có thể bắt đầu để làm điều đó.
Và trên thực tế, đó là có được, chúng tôi sẽ thấy, một trong những giải pháp tốt nhất của chúng tôi nêu ra.
Nhưng chúng ta hãy quay trở lại mà chẳng bao lâu.
Trong thực tế, chúng tôi đang đi làm rằng một chút vào cuối tuần này.
Những gì người khác chúng ta có thể làm gì để giải quyết này?
Vì vậy, tất cả mọi người ở đây là trong Để dường như ngẫu nhiên.
Bạn biết gì?
Thay vì đi qua lại, qua lại, lui
mỗi thời gian, điều này cảm thấy như Tôi đang làm rất nhiều đi bộ.
Tại sao tôi không chỉ bắt đầu ở đầu của danh sách,
và chỉ cần đặt bốn nơi mà nó thuộc?
Vì vậy, hãy để tôi giả định cho thời điểm đó danh sách của tôi chỉ là yếu tố đầu tiên này.
Được bốn phân loại tại thời điểm này trong thời gian, nếu tất cả tôi quan tâm là tất cả mọi thứ ở đây?
Đây là loại tầm thường đúng, phải không?
Giống như các danh sách có chứa một số, và rằng số bốn rõ ràng là sắp xếp.
>> Vì vậy, hãy để tôi chỉ định là danh sách này được sắp xếp.
Nhưng bây giờ tôi có phần còn lại của danh sách này.
Vì vậy, bây giờ, tôi gặp hai.
Trong trường hợp hai không rõ ràng thuộc đối với bốn với?
Trước khi bốn.
Vì vậy, những gì tôi có thể làm ở đây?
Nhắc lại xem tên bạn là gì?
>> JOSEPH: Joseph.
>> DAVID J. Malan: Joseph, nếu bạn có thể bước trở lại
chỉ trong một khoảnh khắc nào với số của bạn.
Và bây giờ những gì Stefan nên làm ở đây?
Hãy chuyển Stefan ở đây.
Và bây giờ, chúng ta hãy Joseph vào đây.
Và bây giờ, hãy để tôi cho rằng tất cả mọi thứ ở đây được sắp xếp.
Vì vậy, kết quả tương tự, nhưng một cách tiếp cận cơ bản khác nhau.
Tôi thậm chí còn không nhìn những gì ở dưới đó.
Tôi chỉ tiếp tục dùng các yếu tố như họ đang giao cho tôi,
và đối phó với chúng.
>> Vì vậy, bây giờ, tôi thấy số sáu.
Không số sáu thuộc về đâu?
Chúng tôi có hai, bốn, sáu.
Chính xác nơi cô là ngay bây giờ.
Vì vậy, chúng ta hãy rời khỏi đó một mình, và bây giờ cho rằng điều này một phần của danh sách
bây giờ được sắp xếp.
Và như vậy, điều này cảm thấy cơ bản khác nhau trong đó tôi chỉ
di chuyển qua danh sách ở đây tuyến tính, và tôi sẽ không bao giờ trở lại tăng gấp đôi.
Vâng.
Được rồi.
Vì vậy, tám, nơi nào bạn thuộc về ai?
Ngay tại đây.
Perfect.
Vì vậy, bây giờ, một.
Uh-oh.
Điều này dường như là sẽ rất tốn kém.
Bây giờ, trong thuật toán trước đó, Tôi chỉ cần hoán đổi người.
Vì vậy, tôi có thể đưa anh ta tất cả các con đường ở đầu, nhưng sau đó chuyển Joseph.
Nhưng nếu tôi chuyển Joseph, bây giờ những gì sẽ là sai lầm?
>> Bây giờ, tôi đã loại undone-- tôi đã thực hiện một bước về phía trước và sau đó
một bước trở lại, bởi vì bây giờ Joseph sẽ được ra khỏi trật tự.
Vì vậy, hãy làm điều này.
Nếu bạn có thể mất một số và bước trở lại chỉ trong một khoảnh khắc.
Làm thế nào chúng ta có thể put-- gì là tên của bạn một lần nữa?
>> Annan: Annan.
>> DAVID J. Malan: Annan tại chỗ?
Những gì cần phải xảy ra đối với hai, bốn, sáu, tám?
Tất cả họ cần phải thay đổi.
Vì vậy, nếu tám muốn chuyển đầu tiên, sau đó sáu, sau đó bốn, sau đó hai.
Và sau đó Annan, nếu bạn muốn muốn đến ở đây, tốt.
Nhưng ở đây, chúng tôi đã chỉ loại đã phải trả giá
tại một điểm khác nhau trong các thuật toán.
Trong khi đó, lần cuối cùng với lựa chọn sắp xếp, và thậm chí bong bóng sắp xếp,
Tôi đang đi đi lại ra, qua lại,
đó là chắc chắn thêm lên thời gian khôn ngoan, và theo nghĩa đen từng bước.
>> Sắp xếp chèn, lúc đầu Trong nháy mắt, có vẻ như nó là
siêu thông minh hơn, trong đó tôi chỉ làm chậm, tiến bộ đáng kể,
nhưng tôi sẽ không này lại.
Nhưng nếu một người nào đó thực sự là trong trật tự, thông báo
tất cả các công việc tôi phải làm như thế.
Tôi đã phải di chuyển một nửa trong danh sách chỉ để nhường chỗ cho số một.
Vì vậy, nó là cùng một lượng công việc như vậy, cho đến nay nó
cảm thấy, chỉ là một loại công việc khác nhau.
>> Tiếp tục đi.
Vì vậy, bây giờ chúng ta biết rằng tất cả mọi người từ một đến tám đều được sắp xếp.
Ở đây, tôi có số ba.
Nếu bạn muốn đến lấy số ba, bước trở lại một.
Và những gì các bạn cần phải làm gì?
Yep.
Vì vậy, đó là một trong một, hai, ba bước.
Ba đơn vị thời gian mà chỉ có giá tôi, vì vậy mà ba có thể gắn vừa khít.
Cuối cùng, bảy.
>> Chúng ta hãy đi trước và có bạn hãy quay trở lại bước.
Đây chỉ là sẽ chi phí cho chúng tôi một đơn vị thời gian, nhưng đó là OK.
Và bây giờ, năm của đi có đắt hơn một chút.
Nếu bạn muốn để bước trở lại.
Chúng tôi cần phải di chuyển tám, và bảy, và sáu.
Và sau đó tất cả mọi người hiện nay được sắp xếp.
Vì vậy, một bàn tay lớn để các tình nguyện viên của chúng tôi ở đây.
Cam ơn rât nhiêu.
>> [Vỗ tay]
>> Cảm ơn tất cả.
Cảm ơn tất cả.
Vì vậy, chúng ta hãy xem làm thế nào bây giờ chỉ tốn kém tất cả điều đó đã.
Chúng ta hãy xem xét có lẽ đơn giản nhất trong số này, bong bóng sắp xếp.
Và tôi nói đơn giản, chỉ vì bạn có thể giải quyết một cách thèm khát bởi chỉ
sửa chữa các vấn đề cặp ở đây.
Sửa chữa các vấn đề cặp ở đây, một lần nữa và một lần nữa
và một lần nữa, lặp đi lặp lại nhiều lần như bạn thực sự cần.
>> Vì vậy, nó chỉ ra rằng với một loại bong bóng, tốt,
bao nhiêu bước để tôi phải mất trên đèo đầu tiên của thuật toán?
Tôi có thể take-- hãy see-- một, hai, ba, bốn, năm, sáu, bảy.
Và có tám yếu tố ở đây.
Vì vậy, nó giống như n trừ đi 1 bước để nhận được từ sự khởi đầu của danh sách
đến cuối danh sách.
>> Nhưng với sắp xếp chọn, nhớ lại rằng tôi lựa chọn các yếu tố một lần nữa và một lần nữa
và một lần nữa đó là nhỏ nhất, Tôi đang đặt nó tại chỗ,
nhưng sau đó tôi không nhìn phía sau tôi một lần nữa.
Vì vậy, tôi nghĩ rằng đó là một chút rõ ràng hơn sau đó lần đầu tiên, tôi có thể
phải mất tất cả n trừ đi 1 bước để tìm các phần tử nhỏ nhất.
Sau đó, tôi đặt chúng tại chỗ, và tôi đuổi bất cứ ai đã ở đây trước đó.
>> Nhưng sau đó tôi không phải cứ nhìn vào yếu tố này,
vì tôi biết nó đã là nhỏ nhất.
Vì vậy, bây giờ, tôi có thể nhìn vào chỉ bảy yếu tố, sau đó sáu yếu tố,
sau đó năm yếu tố, sau đó bốn yếu tố.
Và do đó, về mặt toán học, nếu n là số phần tử hoặc số
rằng chúng ta bắt đầu với, bạn có thể tưởng tượng rằng đây là giống như n trừ đi 1,
cộng với n trừ đi 2 bước, cộng với n trừ đi 3 bước,
cộng với n trừ đi 4 bước, tất cả các cách xuống chỉ còn một bước.
Và tôi đang trên người cuối cùng của tôi.
>> Và nếu bạn nhớ lại rằng rất nhiều các số liệu thống kê sách hoặc sách toán
có những công thức trên bìa cứng lại hoặc mặt trước của họ,
nó quay ra rằng loạt bài này có thể được thể hiện đơn giản hơn
là n lần n trừ đi 1 trong 2.
Và điều đó là tốt nếu đó là không đi đầu trong tâm trí của bạn.
Nhưng điều này là thực sự đúng.
Đó chỉ là một cách đơn giản của văn bản đó.
Và sau đó nếu bạn nghĩ trở lại trường lớp,
khi bạn chỉ cần bắt đầu nhân những điều trên, điều này tất nhiên,
chỉ được n bình phương trừ đi n chia cho 2.
Tất cả tôi đã làm là mở rộng các biểu thức đó.
Và như vậy chúng ta hãy viết lại này một chút khác nhau.
Đó là n bình phương chia cho 2 trừ đi n / 2.
>> Vì vậy, một lần nữa, tôi chỉ là loại áp dụng một số số học quy tắc đó.
Nhưng nhận thấy bây giờ mà các hạn lớn nhất trong biểu thức này, có thể nói,
là n bình phương.
Vì vậy, có, đó là n bình phương chia cho 2, trừ đi n / 2.
>> Nhưng nói chung, nếu n là sẽ là một giá trị lớn,
Tôi sẽ yêu cầu bồi thường n rằng bình phương sẽ là yếu tố chi phối.
Nó chỉ có được một đóng góp lớn hơn
với số lượng các bước hơn n / 2.
Vì vậy, tôi có ý nghĩa gì bởi điều này?
Hãy thử một ví dụ đơn giản, thậm chí mặc dù toán học được một chút lớn.
>> Vì vậy, giả sử chúng ta đã có 1 triệu người trên sân khấu, hoặc 1 triệu thứ
rằng chúng ta muốn sắp xếp.
Hãy cắm một triệu vào chính xác công thức
để xem có bao nhiêu bước cần phải mất tổng cộng để sắp xếp một triệu yếu tố sử dụng tiếng nói,
sắp xếp chọn.
>> Vì vậy, chúng tôi muốn có một công thức như trước.
Tôi muốn cắm một triệu, vì vậy mà tôi nhận được một triệu bình phương chia cho 2,
trừ đi một triệu chia cho 2.
Nếu tôi làm toán mà trước ở đây, chúng tôi có 500 tỷ
trừ đi 500.000, trong đó cho chúng ta 499.999.500.000,
mà là khá darn lớn.
>> Trong thực tế, nếu bạn so sánh với doanh nghiệp 499.000.000.000, 999 triệu,
500.000 đối với giá trị ban đầu của chúng tôi, 500 tỷ, nó như vậy damn gần.
Phải không? n bình phương chia cho 2 cho us-- hay đúng hơn, n bình phương chia cho 2
đã cho chúng tôi 500 tỷ đồng.
Đó là khá darn gần để 499.999.500.000,
mà là để nói trừ ra 500.000, hay nói chung, trừ đi off
n bình, không thực sự là một vấn đề lớn.
Các n bình phương làm cho các số tăng trưởng rất nhanh.
>> Bây giờ, đây chỉ là quan trọng trong chừng mực như chúng ta, như nhà khoa học máy tính,
nói chung là sẽ không quan tâm quá nhiều về các sắc thái của các công thức
và chính xác những gì câu trả lời chính xác được.
Chúng tôi chăm sóc chỉ có vậy, bạn biết những gì?
Vào cuối ngày, công thức này là vào thứ tự của n bình phương.
>> Vâng, chúng tôi đang phân chia bởi 2 trong đó.
Vâng, chúng tôi đã trừ đi n trừ đi 2.
Nhưng vào cuối ngày, thuật ngữ rằng chúng tôi thực sự đau và tốn chúng tôi
nhiều bước là hạn vuông.
Và vì vậy những gì một nhà khoa học máy tính sẽ thường làm
được bỏ qua tất cả những điều kiện bậc nhỏ hơn,
và chỉ cần nhìn vào một trong đó đóng góp nhiều nhất cho các chi phí.
>> Và điều này là tốt đẹp, bởi vì chúng ta có thể Bây giờ nói chuyện trong tính tổng quát hơn nhiều
về các thuật toán, và có thể so sánh chúng.
Và thực tế là tôi sử dụng O này là cố ý.
Khi tôi nói về thứ tự của, Tôi đặc biệt
đề cập đến một cái gì đó gọi là O. lớn Và lớn O
là một ký hiệu mà một máy tính nhà khoa học sử dụng để mô tả
một trên ràng buộc vào một cái gì đó.
>> Vì vậy, nếu bạn nói rằng một thuật toán là trong O lớn của n bình phương,
như tôi đã đề xuất chỉ là một thời điểm trước đây, phương tiện đó
rằng trong điều khoản của nó đang chạy thời gian hay hiệu quả của nó,
phải mất trên thứ tự của n bình bước.
Có lẽ hơn, có thể ít hơn.
Nhưng đó là vào thứ tự của n bình phương.
Và đó là sự ràng buộc trên.
Nó sẽ không được đau đớn hơn đó.
Nó sẽ không phải là n cubed, hoặc 2 đến n, hoặc một cái gì đó lớn hơn nhiều.
Đây là một ràng buộc trên trên bất cứ chi phí đó là.
Vì vậy, cho rằng, chúng ta hãy xem xét một số ví dụ.
Và đây chỉ là một danh sách hữu hạn lần chạy của rất phổ biến
cho các thuật toán đó có nghĩa là phải minh họa của một số thứ chúng tôi đã
nhìn thấy đã.
>> Vì vậy, ví dụ, trong trường hợp sắp xếp chọn, những gì tôi đang tự xưng ở đây
là chạy mà sắp xếp chọn của thời gian là vào thứ tự của n bình phương.
Trong trường hợp xấu nhất, tôi sẽ có một bó toàn bộ các số ngẫu nhiên ở đây.
Và như chúng ta đã thấy toán học, nếu tôi tiếp tục đi bộ
thông qua danh sách, thông qua các danh sách, chọn nhỏ nhất tiếp theo
yếu tố một lần nữa và một lần nữa, nếu tôi thực sự viết xuống tất cả các bước
Tôi đang tham gia như tôi đã đề xuất formulaically trước đây, đó là vào thứ tự của n bình phương
bước mà tôi lựa chọn.
>> Và hóa ra bong bóng đó phân loại và sắp xếp chèn
chỉ là chậm trong trường hợp xấu nhất.
Xem xét, ví dụ, sắp xếp chèn, các thuật toán cuối cùng chúng tôi xử lý,
trong đó có chúng tôi xem xét các yếu tố, và sau đó chèn nó, nơi nó thuộc về.
Và sau đó chúng tôi nhìn vào các phần tử tiếp theo, và chèn nó, nơi nó thuộc về.
>> Vì vậy, xem xét các kịch bản tốt nhất có thể.
Giả sử tôi đã tình nguyện của tôi xếp hàng nghĩa đen như thế này, một đến tám,
đã được sắp xếp.
Có bao nhiêu bước là sắp xếp chèn sẽ đi để sắp xếp tám người,
nếu họ đến trên sân khấu nhìn như thế này?
>> Tám người đã được sắp xếp.
Và tôi sử dụng sắp xếp chèn.
Điều đó cuối cùng của thuật toán.
Vâng, chúng ta hãy diễn lại nhanh thật.
Vì vậy, nếu tôi bắt đầu ở đây, tôi thấy một.
Một thuộc về nơi nào?
Nó thuộc ngay tại đây.
Tôi thấy hai.
Không hai thuộc về đâu?
Ngay tại đây.
Tôi nhìn thấy ba.
Trường hợp nào ba thuộc về ai?
Ngay tại đây.
>> Tôi thấy bốn.
Ngay tại đây.
Năm, sáu, bảy, tám.
Không có lý do để lặp lại bản thân mình.
Và như vậy, có bao nhiêu bước là trong điều kiện của n?
Đó là vào thứ tự của n bước, phải không? n trừ đi 1.
Nhưng tôi lấy một số tuyến tính các bước, và bây giờ tôi đang làm.
Vì vậy, đó là trường hợp tốt nhất, mặc dù.
Những gì về trường hợp tồi tệ nhất?
Những gì là tám trên đó, và bảy là xuống đó,
và một và hai là ở đây, vì vậy rằng danh sách đã thực sự đảo ngược?
>> Vâng, những gì xảy ra thực sự nếu điều này là số?
Và chúng tôi sẽ làm chỉ là một vài ví dụ.
Nếu như, thực sự, số tám là ở đây, và whoops number--.
Vì vậy, những gì nếu quả thực, số tám là tất cả các cách trên đây,
và tôi đang sử dụng sắp xếp chèn?
>> ĐƯỢC.
Tôi khẳng định tại thời điểm đó là tại chỗ.
Nhưng bây giờ, seven-- nơi nào bảy đi?
Tất nhiên, nó đi qua đây.
Vì vậy, tôi phải di chuyển tám trên một nơi.
Bây giờ sáu, nơi nào nó đi?
Vâng, tất cả các quyền.
Bây giờ, tôi phải di chuyển tám trên một nơi, và bảy qua một nơi,
và sau đó tôi plop xuống sáu.
>> Vì vậy, lần đầu tiên, nó chi phí tôi một bước để khắc phục điều này,
sau đó chi phí cho tôi hai bước để sửa chữa mọi thứ.
Có bao nhiêu bước là nó sẽ đi để sửa chữa
điều cần đặt năm vào đúng chỗ?
Ba.
Bởi vì bây giờ tôi phải di chuyển một, hai, ba.
Có bao nhiêu bước là nó sẽ mất để đặt bốn ở đúng nơi?
4 và 5, cộng với 6, cộng với 7.
>> Và do đó, nó là toán học giống những gì chúng tôi đã mô tả cho sắp xếp chọn.
Chúng tôi có loạt bài này đó chỉ là tăng.
1 + 2 + 3 cộng với 4, hoặc ngược lại, 7 cộng với 6
cộng với 5 cộng với 4 thêm lên cho hôm nay mục đích để vào thứ tự của n bình phương.
>> Vì vậy, hãy để tôi định quá mà bong bóng sắp xếp cũng là trong n bình phương.
Bởi vì với bong bóng sắp xếp, mỗi lần tôi đi qua danh sách,
Tôi đang dùng khoảng bao nhiêu bước?
Mỗi lần tôi theo nghĩa đen đi bộ từ đó để có?
Khoảng n bước.
Nhưng bao nhiêu lần tôi có thể cần phải đi qua danh sách?
>> Vâng, khoảng thời gian n.
Có lẽ n trừ đi 1, nhưng khoảng n lần.
Vâng, tại sao vậy?
Vâng, với bong bóng sắp xếp, nếu chúng ta bắt đầu với bong bóng sắp xếp,
với danh sách trong tồi tệ nhất có thể tình hình, mà lại là hoàn toàn
trở về trước, điều gì sẽ xảy ra?
Tôi đi qua danh sách, và số ta thuộc về tất cả các cách trên đó.
>> Nhưng với bong bóng sắp xếp, làm thế nào đến nay không có một chuyển qua đầu tiên của tôi thông qua danh sách?
Làm thế nào nhiều điểm không có được anh gần gũi hơn với các địa điểm chính xác?
Chỉ một.
Vì vậy, nếu bạn loại lý do thông qua điều này, mỗi lần thông qua thuật toán này,
Lấy khoảng n bước của David.
Nhưng làm thế nào những đường chuyền thông qua danh sách là nó
sẽ mất một đến bong bóng bên trái nơi mà nó thuộc?
>> Ông ta sẽ di chuyển như thế, n không gian theo cách này.
Như vậy chỉ cần làm việc phân loại danh sách, Tôi phải đi bộ qua lại n lần.
Và mỗi lần, tôi nhìn vào n phần tử.
Vì vậy, làm n thứ n lần trên thứ tự của n bình phương.
>> Bây giờ, chúng ta sẽ thấy trong một số của quần short
được nhúng trong vấn đề tiếp theo của CS50 thiết lập, phương pháp tiếp cận khác tại các,
nhưng bây giờ, chúng ta hãy chỉ cần xem xét một số lần chạy khác,
đặc biệt là nếu những người sắp mất một chút ít thời gian để chìm trong.
Một thuật toán chúng ta đã nhìn thấy đã là gì mà mất vào thứ tự của n bước?
>> Điều gì nên mất một số tuyến tính các bước mà chúng tôi đã nhìn thấy cho đến nay?
Cái gì thế?
Các tìm kiếm danh bạ điện thoại.
Thuật toán đầu tiên.
Phải không?
Nơi chúng tôi tuyến tính tìm kiếm Mike Smith?
Thật.
Từ tuần không, khi tôi bắt đầu chuyển một trang tại một thời gian,
và tôi thậm chí còn nói rằng nó đã được loại của một thuật toán cảm giác tuyến tính,
và chúng tôi đã có hình ảnh trên hội đồng quản trị với các dòng màu đỏ thẳng
và màu vàng thẳng dòng, những người đã thực sự
các thuật toán đó là trong O lớn của n.
>> Bởi vì để tìm Mike Smith trong một điện thoại cuốn sách của các trang n, trong trường hợp xấu nhất,
có thể đưa tôi bước n.
Gì về việc tham dự?
Một hai ba bốn năm sáu.
Thời gian chạy là sao thuật toán cho việc tham dự?
Big O của n, bởi vì trong lý thuyết tôi có điểm tất cả mọi người trong phòng.
>> Bây giờ là một sang một bên, những gì về tối ưu hóa khác từ tuần không?
Hai, bốn, sáu, tám, 10, 12.
Một nhà khoa học máy tính sẽ nhận ra, chờ một phút,
đó là vào thứ tự của n chia hai bước.
Phải không?
Bởi vì tôi đang làm hai người tại một thời gian.
Nhưng chúng ta sẽ bỏ qua những điều kiện bậc thấp hơn,
và chúng tôi chỉ đi vứt chia cho 2,
và chỉ nói, O lớn của n cho các thuật toán đó là tốt.
>> Cái này thì sao?
Chúng tôi sẽ bỏ qua một số trong số này, nhưng những gì là một thuật toán mà là nhật ký của n?
Điều đó đã gần log n bước?
Sự phân chia và chinh phục.
Chính xác.
Cũng giống như các ví dụ trong cuốn sách điện thoại tuần không và trước ngày hôm nay,
nơi chúng ta chia các vấn đề một lần nữa và một lần nữa và một lần nữa.
Chúng tôi đã vẽ nó vào hội đồng quản trị trong tuần không như một dòng màu xanh lá cây cong,
và chúng tôi đã nói ngày hôm đó nó đã được một thuật toán logarit.
>> Và quả thực, số lượng các bước nó cần để thực hiện phân chia và chinh phục,
hoặc tìm kiếm nhị phân như chúng ta sẽ bắt đầu gọi nó, như trong các cuốn sách điện thoại,
là vào thứ tự của bản ghi và các bước.
Và đây là một chút của một kỳ lạ.
>> Mất gì một bước, hay cụ thể hơn
một hằng số của bước?
Có lẽ đó là hai, có lẽ đó là ba, nhưng một nhà khoa học máy tính chỉ
đơn giản hoá nó như O lớn của 1 một số hằng số của các bước.
Một cái gì đó bạn có thể làm điều đó là gì mất một hằng số của bước?
>> Thời gian chạy của vỗ tay là gì?
Thời gian liên tục.
Phải không?
Giống như, thời gian chạy của những gì làm bất cứ điều gì mà chỉ mất một
hoạt động, như in F Hello World.
Đó có thể nói là thời gian liên tục, trừ trường hợp góc ít hơn với in F,
những gì có thể thời gian chạy in F thực sự được?
Và tại sao?
N đo trong trường hợp đó là gì?
>> Đung [không nghe được].
DAVID J. Malan: Chính xác.
Số lượng ký tự chúng ta muốn in.
Vì vậy, nó rất bối cảnh nhạy cảm.
Hôm nay, chúng tôi đã tập trung rất nhiều vào chữ và số ở đây trên diễn đàn.
Nhưng nó cũng có thể là ký tự trong một chuỗi thực tế.
Vì vậy, nó quay ra có khác biện pháp đó sẽ bắt đầu quan tâm đến,
và đó là điều ngược lại của O lớn, do đó, để nói chuyện.
>> Đó là ký hiệu omega.
Trong khi đó O lớn có nghĩa là gì, các trên ràng buộc về thời gian chạy của bạn?
Tối đa, bao nhiêu thời gian một cái gì đó có thể mất?
Omega-- xin lỗi này tiếp tục trở up-- là đối diện đó,
nhờ đó mà nó là một ràng buộc thấp hơn trên lượng thời gian một cái gì đó có thể mất.
>> So. Ví dụ, một thuật toán là những gì đó tiến hành các bước luôn n bình?
Vâng, một trong những thuật toán, chúng tôi đã nhìn thấy ngày hôm nay, trong thực tế, có thể đó là tốt.
Loại lựa chọn.
Lựa chọn loại khá ngu ngốc.
Ngay cả khi xin lỗi algorithm--, thậm chí nếu mảng đã được sắp xếp,
sắp xếp chọn sẽ tiếp tục đi bộ qua danh sách
để chắc chắn rằng nó có nhỏ nhất yếu tố một lần nữa và một lần nữa và một lần nữa.
Và ngay cả khi bạn con người trong khán giả biết rằng, chờ một phút,
bạn đã được thông qua phần tử nhỏ nhất, máy tính
không biết rằng cho đến khi nó tất cả các cách thức thông qua danh sách.
Tương tự như vậy, một giới hạn thấp hơn mà cũng có thể được đưa vào tài khoản
có thể là thời gian tuyến tính.
>> Bao nhiêu thời gian hiện nó đi để yếu tố thứ n trong tốt nhất
trường hợp sử dụng một cái gì đó giống như bong bóng sắp xếp?
Giả danh sách của bạn đã được sắp xếp.
Chúng tôi nói bong bóng sắp xếp đưa vào thứ tự của n bình bước.
Nhưng nếu nó đã được sắp xếp?
Điều gì nếu bạn nhận ra sau một đi qua mảng
mà bạn đã thực hiện giao dịch hoán đổi không?
Bạn cần phải tiếp tục làm nhiều đèo?
>> Không.
Vì vậy, một giới hạn thấp hơn trên bong bóng sắp xếp có thể được cho là tuyến tính.
Omega của n.
Và chúng ta có thể nhìn vào những người khác trong số này là tốt.
Vì vậy, chúng ta hãy có một cái nhìn nhanh chóng lúc chỉ là một hình dung ở đây
để xem làm thế nào những phân biệt mình.
Tôi sẽ đi xuống đây vào đây trang đó là có sẵn trên trang web của C50,
nhưng nó sẽ là một nỗi đau để làm việc, vì nó sử dụng một công nghệ gọi là
Java applet, mà là một phần lớn không được hỗ trợ trong những ngày này,
ít nhất bằng Chrome và một số người khác.
>> Và hãy để tôi đi trước và tăng tốc độ này lên và giải thích những gì đang xảy ra.
Đây là một cuộc biểu tình của bong bóng sắp xếp, thuật toán đầu tiên chúng ta nhìn vào.
Và đó là một hình dung trong đó mỗi của các thanh này đại diện cho một số.
Lớn hơn các quán bar, lớn hơn số lượng.
Nhỏ hơn thanh, nhỏ hơn số lượng.
Và những gì bạn có thể nhìn thấy bằng mắt, thậm chí mặc dù điều này là siêu nhanh,
là thanh màu đỏ giống như tôi, đi đi lại lại sửa chữa vấn đề.
Bạn có thể thấy rằng các yếu tố lớn hơn đang thực sự sủi bọt lên bên phải,
và các yếu tố nhỏ hơn đang sủi bọt lên bên trái.
Và ở đây, nếu chúng ta thực sự xem xét chặt chẽ hơn,
chúng tôi thực sự có thể đếm số lượng so sánh và hoán đổi
mà đã được thực hiện.
>> Nhưng thay vào đó, chúng ta hãy nhìn tại các thuật toán thứ hai
chúng ta nhìn vào trước đó với chúng tôi tình nguyện viên, sắp xếp chọn.
Nhìn bề ngoài, nó có một hiệu ứng rất khác nhau.
Nhưng đó là, một lần nữa, rất trực quan, trong mà chúng tôi giữ lựa chọn nhỏ nhất tiếp theo
phần tử, và chúng tôi đã có một chút may mắn.
Đó là cảm nhận về cơ bản nhanh hơn.
Nhưng nếu chúng tôi chạy này một lần nữa và một lần nữa và một lần nữa với rất nhiều yếu tố đầu vào,
chúng ta sẽ thấy rằng nó thực sự vẫn còn trong O lớn của n bình phương.
>> Hãy làm một người cuối cùng ở đây, sắp xếp chèn,
đó là thuật toán thứ ba chúng ta nhìn vào, và thu hồi
rằng điều này giao dịch với các các yếu tố như nó gặp họ,
nhưng sau đó nó có thể thay đổi những điều trên để làm cho căn phòng,
chèn các yếu tố mà họ thuộc về.
>> Và điều này cũng kết thúc cho các kết quả cuối cùng. Bây giờ tất cả ba trong số những
cảm thấy khá nhanh.
Và quả thực, chúng tôi chạy tại một clip khá tốt.
Nhưng về cơ bản, họ đang tất cả khá khủng khiếp, phải trung thực.
Tất cả những thuật toán vậy, đến nay mà chạy trong O lớn của n bình
mất khá một chút thời gian để chạy cuối cùng.
>> Và quả thực, chúng ta có thể nhìn thấy và cảm thấy điều này cuối cùng
nếu tôi kéo lên bản demo thứ ba và cuối cùng này.
Đây là một hình dung rằng sẽ
để hiển thị bong bóng sắp xếp bên trái, sắp xếp chọn ở giữa,
và một cái gì đó, như là một trong chúng tôi Mặt tăng trước đó đề nghị,
hợp nhất phân loại bên phải.
Một phân chia và chinh phục chiến lược trên bên phải.
Và đó là, trên thực tế, những gì chúng tôi sẽ nhìn vào hôm thứ Tư.
Nhưng chúng ta hãy để thời gian này chạy song song.
Đó là khoảng cùng một số yếu tố, tất cả đều chạy cùng một lúc.
Bubble sort vs lựa chọn loại vs sắp xếp hợp nhất.
>> Bây giờ, tất cả họ đang chạy trong lý thuyết cùng một lúc.
Các CPU đang chạy ở tốc độ như nhau, nhưng bạn
có thể cảm thấy như thế nào nhàm chán này là rất nhanh chóng sẽ trở thành,
và chỉ cần nhanh như thế nào khi chúng ta tiêm vào một chút trong tuần
các thuật toán số không thể chúng ta đẩy nhanh tốc độ.
>> Và bây giờ chúng ta hãy so sánh các trong một hình thức cuối cùng.
Tôi sẽ đi trước để website CS50, nơi
chúng tôi có liên kết cuối cùng này cho ngày hôm nay, nơi một người nào đó trên internet
vui lòng đặt cùng một video nắm bắt những gì phân loại khác nhau
thuật toán âm thanh như thế nào.
Đây là sắp xếp chèn.
>> [Bíp]
>> Nhờ đó mà bạn đang áp dụng một tần số dựa trên chiều cao của thanh bar.
Đây là bong bóng sắp xếp.
>> [Warped bíp]
>> Sắp tới tiếp theo is-- tới lên chọn tiếp theo của loại is--,
đó một lần nữa, chúng tôi đang chọn các phần tử nhỏ nhất tiếp theo,
và chúng ta có thể nhìn thấy nó ngày càng tăng từ trái sang phải.
>> Hợp nhất phân loại, người chiến thắng của chúng tôi cho đến nay ngày hôm nay.
Chú ý cách nó phân chia thứ vào [không nghe được] một nửa và quý.
Loại Gnome, mà chúng tôi có không nói về, và tạo ra thị
và audally một chút của một hình dạng và âm thanh khác nhau.
Đi lại, làm sạch mọi thứ lên.
Ngoài ra kiểm tra heapsort trên trang web của anh chàng này.
>> Và đó là nó.
Chúng ta sẽ thấy bạn thời gian tới.
>> [Whooshing AND MUSIC]