>> [Chơi nhạc]
DAVID Malan: Được rồi.
Được rồi, chào đón trở lại.
Vì vậy, đây là tuần 4, đầu của chúng, đã.
Và bạn sẽ nhớ lại rằng tuần trước, chúng tôi đặt mã dành cho chỉ cần một chút
và chúng tôi bắt đầu nói chuyện nhiều hơn một chút cấp cao, về những thứ như
tìm kiếm và phân loại, mà mặc dù ý tưởng khá đơn giản, là
đại diện của một lớp học của các vấn đề bạn sẽ bắt đầu để giải quyết đặc biệt
khi bạn bắt đầu suy nghĩ về thức dự án và các giải pháp thú vị mà bạn
có thể có các vấn đề thực tế.
Bây giờ bong bóng sắp xếp là một trong những đơn giản nhất các thuật toán như vậy, và nó
làm việc bởi có những con số nhỏ trong một danh sách hoặc trong một loạt các loại
bong bóng theo cách của họ lên đến đỉnh, và số lượng lớn di chuyển theo cách của họ xuống
cuối danh sách đó.
>> Và nhớ lại rằng chúng ta có thể hình dung bong bóng sắp xếp một chút
một cái gì đó như thế này.
Vì vậy, hãy để tôi đi về phía trước và nhấn Start.
Tôi đã chọn trước bong bóng sắp xếp.
Và nếu bạn nhớ lại rằng màu xanh cao dòng đại diện cho số lớn, nhỏ
đường màu xanh đại diện cho số lượng nhỏ, như chúng tôi đi qua này một lần nữa và một lần nữa và
một lần nữa, so sánh hai thanh cạnh nhau khác màu đỏ, chúng ta sẽ trao đổi các
lớn nhất và nhỏ nhất nếu họ ra lệnh.
>> Vì vậy, đây sẽ đi vào và đi vào và đi trên, và bạn sẽ thấy rằng càng lớn
yếu tố này được thực hiện theo cách của họ đến phải, và các yếu tố nhỏ hơn
thực hiện theo cách của họ bên trái.
Nhưng chúng tôi bắt đầu để định lượng hiệu quả, các
chất lượng của thuật toán này.
Và chúng tôi cho rằng trong điều tồi tệ nhất trường hợp, thuật toán này mất
khoảng bao nhiêu bước?
>> Vì vậy, n bình phương.
Và là những gì n?
>> ĐỐI TƯỢNG: Số phần tử.
>> DAVID Malan: Vì vậy, n là số yếu tố.
Và vì vậy chúng tôi sẽ làm điều này thường xuyên.
Bất cứ lúc nào chúng ta muốn nói về kích thước của một vấn đề hoặc kích thước của một
đầu vào, hoặc số lượng thời gian cần để sản xuất ra, chúng tôi sẽ chỉ
tổng quát bất cứ điều gì đầu vào là như n.
Vì vậy, trở lại trong tuần 0, trang số trong danh bạ điện thoại là n.
Số lượng sinh viên trong căn phòng n.
Vì vậy, ở đây, chúng tôi đang theo rằng mô hình.
>> Bây giờ n bình phương là không đặc biệt nhanh chóng, vì vậy chúng tôi đã cố gắng để làm tốt hơn.
Và vì vậy chúng tôi đã xem xét một vài các thuật toán khác, trong đó
là lựa chọn sắp xếp.
Vì vậy, lựa chọn loại là một chút khác nhau.
Nó đã gần như đơn giản, tôi dám nói, theo đó tôi bắt đầu vào đầu của
danh sách các tình nguyện viên của chúng tôi và tôi chỉ một lần nữa và một lần nữa và một lần nữa đã đi qua
danh sách, tuốt ra nhỏ nhất yếu tố tại một thời gian và đưa anh ta hoặc
mình vào đầu danh sách.
>> Nhưng điều này cũng vậy, một khi chúng ta bắt đầu suy nghĩ qua toán học và lớn hơn
hình ảnh, nghĩ về bao nhiêu lần Tôi đã đi lại và trở lại
và ra, chúng tôi đã nói trong trường hợp xấu nhất, lựa chọn sắp xếp, cũng là những gì?
n bình phương.
Bây giờ trong thế giới thực, nó có thể thực sự được nhẹ nhanh hơn.
Bởi vì một lần nữa, tôi đã không cần phải giữ thụt lùi trong khi tôi đã sắp xếp các
nhỏ nhất yếu tố.
Nhưng nếu chúng ta suy nghĩ về rất lớn n, và nếu bạn loại làm ra toán học như
Tôi đã làm trên bảng, với phương n một cái gì đó trừ đi, tất cả mọi thứ khác
bên cạnh n bình phương, một lần n được thực sự lớn, không
thực sự quan trọng nhiều.
Vì vậy, các nhà khoa học máy tính, chúng tôi sắp xếp của nhắm mắt làm ngơ để nhỏ hơn
yếu tố và chỉ tập trung vào các yếu tố trong một biểu thức sẽ làm cho
sự khác biệt lớn nhất.
>> Vâng, cuối cùng, chúng tôi đã tại sắp xếp chèn.
Và điều này cũng tương tự như trong tinh thần, nhưng chứ không phải là đi qua và lặp đi lặp lại
chọn một trong những phần tử nhỏ nhất ở một thời gian, tôi thay vào đó là bàn tay tôi
đã được xử lý, và tôi quyết định, tất cả bên phải, bạn thuộc về nơi này.
Sau đó, tôi chuyển sang phần tử tiếp theo và quyết định rằng ông hoặc
cô thuộc về đây.
Và sau đó tôi chuyển trên và trên.
Và tôi có thể đến, trên đường đi, chuyển những người này để
nhường chỗ cho họ.
Vì vậy, đó là sắp xếp của đảo ngược tinh thần lựa chọn loại mà chúng ta
gọi là sắp xếp chèn.
>> Vì vậy, các chủ đề này xảy ra trong thế giới thực.
Chỉ cần một vài năm trước đây, khi một số Thượng nghị sĩ tranh cử tổng thống,
Eric Schmidt, tại thời điểm Giám đốc điều hành của Google, thực sự đã có cơ hội
phỏng vấn ông.
Và chúng tôi nghĩ rằng chúng tôi muốn chia sẻ YouTube cắt cho bạn ở đây, nếu chúng ta có thể bật lên
khối lượng.
>> [VIDEO xem lại]
>> -Bây giờ, Thượng nghị sĩ, bạn đang ở đây tại Google, và tôi thích nghĩ về nhiệm kỳ tổng thống
như một cuộc phỏng vấn việc làm.
>> [Cười]
>> -Bây giờ thật khó để có được một công việc như tổng thống.
Và bạn đang trải qua sự khắc nghiệt tại.
Nó cũng khó để có được một công việc tại Google.
Chúng tôi có thắc mắc và chúng tôi yêu cầu các ứng cử viên của chúng tôi câu hỏi.
Và điều này là từ Larry Schwimmer.
>> [Cười]
-Các bạn nghĩ tôi đang đùa à?
Nó ở ngay đây.
Cách hiệu quả nhất để là gì sắp xếp một triệu số nguyên hai-bit?
>> [Cười]
>> -À, uh -
>> -Tôi xin lỗi.
Có lẽ chúng ta nên -
>> -Không, không, không, không, không.
>> -Đó không phải là một -
OK.
>> -Tôi nghĩ rằng bong bóng sắp xếp sẽ là con đường sai để đi.
>> [Cười]
>> [Cổ vũ và vỗ tay]
>> -Thôi nào, người nói với anh điều này?
OK.
>> [END xem video]
>> DAVID Malan: Vì vậy, có bạn có nó.
Vì vậy, chúng tôi bắt đầu để định lượng các hoạt động thời gian, có thể nói, với một cái gì đó
được gọi là ký hiệu tiệm cận, đó là chỉ đề cập đến loại của chúng tôi biến
nhắm mắt làm ngơ để những yếu tố nhỏ hơn và chỉ nhìn vào thời gian chạy,
hiệu quả hoạt động của các thuật toán, như n được thực sự lớn theo thời gian.
Và vì vậy chúng tôi giới thiệu lớn O. Và O lớn một cái gì đó đại diện mà chúng tôi nghĩ
như là một trên ràng buộc.
Và trên thực tế, Barry, chúng ta có thể giảm hơn mic một chút?
>> Chúng tôi nghĩ đây là một ràng buộc trên.
O quá lớn của n có nghĩa là bình phương trong trường hợp xấu nhất, một cái gì đó như
lựa chọn loại sẽ mất n bước phương.
Hoặc một cái gì đó như sắp xếp chèn sẽ bước n bình phương.
Bây giờ cho một cái gì đó như chèn sắp xếp, là trường hợp xấu nhất những gì?
Cho một mảng, những gì là tồi tệ nhất kịch bản có thể bạn có thể tìm thấy
mình phải đối mặt với?
>> Nó hoàn toàn ngược lại, phải không?
Bởi vì nếu nó hoàn toàn ngược lại, bạn phải làm nhiều công việc.
Bởi vì nếu bạn hoàn toàn ngược lại, bạn sẽ tìm thấy những
yếu tố lớn nhất ở đây, mặc dù nó thuộc về dưới đó.
Vì vậy, bạn sẽ nói, được rồi, tại thời điểm này trong thời gian, bạn thuộc về nơi này,
do đó, bạn để lại một mình.
>> Sau đó, bạn nhận ra, oh, chết tiệt, tôi phải di chuyển này phần tử nhỏ hơn một chút để
bên trái của bạn.
Sau đó, tôi phải làm điều đó một lần nữa và một lần nữa và một lần nữa.
Và nếu tôi đi tới đi lui, bạn sẽ sắp xếp của cảm thấy hiệu suất của
thuật toán đó, bởi vì tôi liên tục xáo trộn tất cả mọi người khác xuống trong
mảng để nhường chỗ cho nó.
Vì vậy, đó là trường hợp tồi tệ nhất.
>> Ngược lại -
và đây là một cliffhanger lần cuối cùng -
chúng tôi cho rằng sắp xếp chèn là một omega của những gì?
Là tốt nhất-trường hợp chạy là những gì thời gian sắp xếp chèn?
Vì vậy, nó thực sự n.
Đó là trống mà chúng tôi rời trên diễn đàn thời gian qua.
>> Và đó là omega n vì lý do tại sao?
Vâng, trong trường hợp tốt nhất, những gì sắp xếp chèn sẽ được bàn giao?
Vâng, một danh sách đó là hoàn toàn sắp xếp đã có, công việc tối thiểu để làm.
Nhưng những gì gọn về sắp xếp chèn là bởi vì nó bắt đầu ở đây và
quyết định, oh, bạn là số lượng một, bạn thuộc về nơi này.
Ồ, thật là may mắn.
>> Anh là số hai.
Bạn cũng thuộc về nơi này.
Số ba, thậm chí tốt hơn, bạn thuộc về nơi này.
Ngay sau khi nó được cho là cuối giả danh sách, mỗi sắp xếp chèn của
mà chúng tôi đi qua bằng lời nói Lần cuối cùng, hoàn thành công việc.
Nhưng lựa chọn loại, ngược lại, tiếp tục làm những gì?
>> Tiếp tục đi qua danh sách một lần nữa và một lần nữa và một lần nữa.
Bởi vì cái nhìn sâu sắc quan trọng là chỉ có một khi bạn đã xem xét tất cả các cách để các
cuối danh sách, bạn có thể chắc chắn rằng các phần tử bạn chọn là
thực sự là yếu tố nhỏ nhất hiện nay.
Vì vậy, các mô hình về tinh thần kết thúc khác nhau tăng năng suất một số rất thực tế
sự khác biệt cho chúng ta, cũng như những sự khác biệt tiệm cận lý thuyết.
>> Vì vậy, tóm lại là, sau đó, O lớn của n phương, chúng tôi đã nhìn thấy một vài ví dụ
các thuật toán cho đến nay.
O lớn của n?
Một thuật toán mà có thể là những gì được cho là lớn O n?
Trong trường hợp xấu nhất, phải mất một số tuyến tính của các bước.
>> OK, tìm kiếm tuyến tính.
Và trong trường hợp xấu nhất, mà là yếu tố bạn đang tìm kiếm khi
áp dụng tìm kiếm tuyến tính?
>> OK, trong trường hợp xấu nhất, nó thậm chí không có.
Hoặc trong trường hợp thứ hai tồi tệ nhất, nó tất cả các cách cuối cùng, đó là
cộng-hay-trừ một sự khác biệt một bước.
Vì vậy, vào cuối ngày, chúng ta có thể nói đó là tuyến tính.
O lớn của n sẽ tìm kiếm tuyến tính, bởi vì trong trường hợp xấu nhất, các
yếu tố thậm chí không có hoặc nó tất cả các cách ở cuối.
>> Vâng, O lớn của nhật ký của n.
Chúng tôi đã không nói chuyện rất chi tiết về này, nhưng chúng tôi đã nhìn thấy điều này trước đây.
Những gì chạy trong cái gọi là logarit thời gian, trong trường hợp xấu nhất?
>> Yeah, tìm kiếm để nhị phân.
Và tìm kiếm nhị phân trong trường hợp xấu nhất có thể có yếu tố một nơi nào đó trong
giữa, hoặc ở một nơi trong mảng.
Nhưng bạn chỉ tìm thấy nó khi bạn phân chia danh sách trong một nửa, trong
một nửa, một nửa, còn một nửa.
Và sau đó thì đấy, nó ở đó.
Hoặc một lần nữa, trường hợp xấu nhất, nó thậm chí không có.
Nhưng bạn không biết rằng nó không có cho đến khi bạn loại đạt đến cuối cùng
dưới hầu hết các yếu tố bằng cách chia đôi và giảm một nửa và giảm một nửa.
>> O lớn của 1.
Vì vậy, chúng ta có thể lớn O 2, O lớn của 3.
Bất cứ lúc nào bạn muốn chỉ là một số không đổi, chúng ta chỉ cần sắp xếp chỉ đơn giản hóa
đó là O lớn của 1.
Mặc dù nếu thực tế, phải mất 2 hoặc thậm chí 100 bước, nếu đó là một
hằng số của các bước, chúng ta chỉ nói O lớn của 1.
Một thuật toán đó là những gì trong O lớn trong tổng số 1?
>> ĐỐI TƯỢNG: Tìm chiều dài của một biến.
>> DAVID Malan: Tìm kiếm chiều dài của một biến?
>> ĐỐI TƯỢNG: Không, chiều dài nếu nó đã được sắp xếp.
>> DAVID Malan: Tốt.
OK, vì vậy việc tìm kiếm theo chiều dài của một cái gì đó nếu chiều dài của một cái gì đó, như
một mảng, được lưu trữ trong một số biến.
Bởi vì bạn chỉ có thể đọc các biến, hoặc in các biến, hoặc
chỉ thường truy cập vào biến đó.
Và thì đấy, mà cần có thời gian liên tục.
>> Ngược lại, nghĩ lại đến đầu.
Hãy nhớ lại tuần đầu tiên của C, gọi chỉ printf và in ấn
một cái gì đó trên màn hình được cho là thời gian liên tục, bởi vì nó chỉ mất
một số chu kỳ CPU để hiển thị rằng văn bản trên màn hình.
Hoặc chờ đợi - hiện nó?
Làm thế nào khác chúng ta có thể mô hình thực hiện printf?
Ai đó muốn không đồng ý, mà có lẽ đó là thời gian thực sự không liên tục?
Trong ý thức những gì có thể printf đang chạy thời gian, thực sự in một chuỗi trên
màn hình, có một cái gì đó khác hơn liên tục.
>> ĐỐI TƯỢNG: [nghe được].
>> DAVID Malan: Vâng.
Vì vậy, nó phụ thuộc vào quan điểm của chúng tôi.
Nếu chúng ta thực sự nghĩ về đầu vào printf như là chuỗi, và
do đó chúng tôi đo kích thước của mà đầu vào theo chiều dài của nó - vì vậy chúng ta hãy gọi
có chiều dài n cũng -
cho là, printf là tự O lớn của n bởi vì nó sẽ đưa bạn bước n
để in ra mỗi người n nhân vật, rất có thể.
Ít nhất là trong phạm vi mà chúng tôi giả định rằng có lẽ nó sử dụng một vòng lặp for
bên dưới mui xe.
>> Nhưng chúng ta sẽ phải nhìn vào đó code để hiểu nó tốt hơn.
Và thực sự, một khi các bạn bắt đầu phân tích thuật toán của riêng bạn, bạn sẽ
nghĩa là làm việc đó.
Loại nhãn cầu mã của bạn và suy nghĩ về - tất cả các quyền, tôi có vòng lặp này
đây hoặc tôi có một vòng lặp lồng nhau đây, đó là sẽ làm n thứ n lần,
và bạn có thể sắp xếp các lý do theo cách của bạn thông qua các mã, ngay cả khi nó
giả và không mã thực tế.
>> Vì vậy, những gì về omega n bình phương?
Một thuật toán là những gì mà trong sản phẩm tốt nhất trường hợp, phải mất n bước bình?
Yeah?
>> ĐỐI TƯỢNG: [nghe được].
>> DAVID Malan: Vì vậy, lựa chọn loại.
Bởi vì trong vấn đề đó thực sự giảm thực tế là một lần nữa, tôi không biết
Tôi đã tìm thấy nhỏ nhất hiện nay cho đến khi Tôi đã kiểm tra tất cả các yếu tố darn.
Vì vậy, omega, nói rằng, n, chúng tôi chỉ đến với một.
Sắp xếp chèn.
Nếu danh sách này sẽ xảy ra để được sắp xếp đã có, trong trường hợp tốt nhất, chúng tôi chỉ có
để làm cho một đi qua nó, lúc này chúng tôi chắc chắn.
Và sau đó có thể được cho biết là tuyến tính, chắc chắn.
>> Những gì về omega của 1?
Những gì, trong trường hợp tốt nhất, có thể mất một hằng số của các bước?
Vì vậy, tìm kiếm tuyến tính, nếu bạn chỉ nhận được may mắn và các yếu tố bạn đang tìm kiếm
là ngay từ đầu của danh sách, nếu đó là nơi bạn đang bắt đầu của bạn
tuyến tính traversal của danh sách đó.
>> Và điều này là thực sự của một số thứ.
Ví dụ, ngay cả nhị phân tìm kiếm là omega của 1.
Bởi vì những gì nếu bạn thực sự darn may mắn và Smack-thoa ở giữa
mảng của bạn là số bạn đang tìm kiếm?
Vì vậy, bạn có thể nhận được may mắn đó, là tốt.
>> Này, cuối cùng, omega n log n.
Vì vậy, n log n, chúng tôi đã không thực sự nói về, nhưng -
>> ĐỐI TƯỢNG: Kết nối loại?
>> DAVID Malan: Merge loại.
Đó là cliffhanger thời gian qua, nơi mà chúng tôi đề xuất, và chúng tôi cho thấy
trực quan, mà có những thuật toán.
Và hợp nhất các loại chỉ là một ví dụ thuật toán đó là nhanh cơ bản
hơn một số trong những kẻ khác.
Trong thực tế, kết hợp ngắn không chỉ trong trường hợp tốt nhất n n log, trong điều tồi tệ nhất
trường hợp n n log.
Và khi bạn có sự trùng hợp này omega và lớn O được điều tương tự?
Chúng ta có thể mô tả đó là những gì gọi là theta, mặc dù đó là một
chút ít phổ biến hơn.
Nhưng điều đó chỉ có nghĩa là hai giới hạn, trong trường hợp này là như nhau.
>> Vì vậy, hợp nhất phân loại, những gì thực hiện điều này thực sự sôi xuống để cho chúng tôi?
Vâng, nhớ lại những động lực.
Hãy để tôi kéo lên một hình ảnh động chúng tôi đã không nhìn vào thời gian qua.
Điều này, cùng một ý tưởng, nhưng nó lớn hơn một chút.
Và tôi sẽ đi trước và chỉ ra đầu tiên - chúng tôi đã sắp xếp chèn trên
phía trên bên trái, sau đó lựa chọn sắp xếp, bong bóng sắp xếp, một vài loại khác -
vỏ và nhanh chóng - mà chúng tôi đã không nói chuyện về, và đống và hợp nhất phân loại.
>> Vì vậy, ít nhất là cố gắng tập trung vào đôi mắt của bạn ba người đứng đầu bên trái và sau đó
hợp nhất phân loại khi tôi nhấp mũi tên màu xanh lá cây này.
Nhưng tôi sẽ cho tất cả chúng chạy, chỉ để cung cấp cho bạn một cảm giác của sự đa dạng của
các thuật toán tồn tại trên thế giới.
Tôi sẽ để cho chạy này cho chỉ một vài giây.
Và nếu bạn tập trung đôi mắt của bạn - chọn một thuật toán, tập trung vào nó chỉ là một
giây - bạn sẽ bắt đầu thấy mô hình mà nó được thực hiện.
>> Hợp nhất phân loại, thông báo, được thực hiện.
Đống phân loại, sắp xếp nhanh chóng, vỏ -
vậy có vẻ như chúng tôi giới thiệu ba tồi tệ nhất các thuật toán tuần trước.
Nhưng đó là tốt mà chúng ta ở đây ngày hôm nay để nhìn vào hợp nhất loại, trong đó là một trong những
những người dễ dàng hơn là nhìn vào, thậm chí mặc dù nó có thể sẽ uốn cong tâm trí của bạn
chỉ cần một chút.
Ở đây chúng ta có thể thấy chỉ có bao nhiêu lựa chọn loại hút.
>> Nhưng theo khía cạnh khác, đó là thực sự dễ dàng để thực hiện.
Và có thể cho P Set 3, đó là một trong những các thuật toán bạn đã chọn để thực hiện
cho phiên bản tiêu chuẩn.
Hoàn toàn tốt đẹp, hoàn toàn chính xác.
>> Nhưng một lần nữa, như n được lớn, nếu bạn chọn để thực hiện một thuật toán nhanh hơn
thích hợp nhất phân loại, tỷ lệ cược là trong lớn hơn và đầu vào lớn hơn, mã của bạn chỉ là
sẽ chạy nhanh hơn.
Trang web của bạn sẽ làm việc tốt hơn.
Người dùng của bạn sẽ được hạnh phúc hơn.
Và do đó, có những tác dụng của thực sự cho
chúng tôi một số sâu suy nghĩ.
>> Vì vậy, chúng ta hãy nhìn vào những gì hợp nhất loại thực sự là tất cả về.
Điều thú vị là hợp nhất loại chỉ là thế này.
Đây là, một lần nữa, những gì chúng tôi đã gọi giả, con giả
Cú pháp tiếng Anh như thế nào.
Và đơn giản là loại hấp dẫn.
>> Vì vậy, trên đầu vào của n phần tử - để chỉ có nghĩa là, đây là một mảng.
Nó có mọi thứ n trong nó.
Đó là tất cả chúng ta đang nói ở đó.
>> Nếu n là ít hơn 2, quay trở lại.
Vì vậy, đó chỉ là trường hợp tầm thường.
Nếu n là ít hơn 2, thì rõ ràng đó là 1 hoặc 0, trong trường hợp này, điều
đã được sắp xếp hay không tồn tại, vì vậy chỉ cần quay trở lại.
Không có gì để làm.
Vì vậy, đó là một trường hợp đơn giản để nhổ ra.
>> Khác, chúng tôi có ba bước.
Sắp xếp nửa bên trái của các yếu tố, loại nửa bên phải của các yếu tố,
và sau đó hợp nhất hai nửa được sắp xếp.
Điều thú vị ở đây là Tôi là loại punting, phải không?
Có loại một định nghĩa tròn thuật toán này.
Trong ý thức những gì là thuật toán của này tròn nghĩa?
>> ĐỐI TƯỢNG: [nghe được].
>> DAVID Malan: Vâng, thuật toán sắp xếp của tôi, hai bước của nó là "loại
một cái gì đó. "Và như vậy đó đặt ra câu hỏi, tốt, những gì tôi sẽ sử dụng
để sắp xếp nửa bên trái và nửa bên phải?
Và vẻ đẹp ở đây là mặc dù một lần nữa, đây là tâm-uốn
một phần có khả năng, bạn có thể sử dụng cùng một thuật toán sắp xếp nửa trái.
>> Nhưng chờ một phút.
Khi bạn đang nói để sắp xếp các nửa bên trái, hai là những gì
bước tiếp theo sẽ là?
Chúng tôi sẽ sắp xếp nửa bên trái của nửa bên trái và bên phải
một nửa của một nửa trái.
Chết tiệt, làm thế nào để sắp xếp hai nửa, hoặc quý, bây giờ?
>> Nhưng đó là OK.
Chúng tôi có một thuật toán sắp xếp ở đây.
Và mặc dù bạn có thể lo lắng ở đầu tiên này là loại vô hạn
vòng lặp, đó là một chu kỳ đó là không bao giờ sẽ kết thúc - nó sẽ
kết thúc khi những gì sẽ xảy ra?
Một khi n là ít hơn 2.
Mà cuối cùng sẽ xảy ra, bởi vì nếu bạn giữ giảm một nửa và
giảm một nửa trong giảm một nửa những nửa, chắc chắn cuối cùng bạn sẽ kết thúc
với chỉ 1 hoặc 0 yếu tố.
Tại thời điểm đó, thuật toán này nói rằng bạn đang thực hiện.
>> Vì vậy, sự kỳ diệu thực trong này thuật toán có vẻ là trong
là bước cuối cùng, sáp nhập.
Đó là ý tưởng đơn giản chỉ là sáp nhập hai điều, đó là cuối cùng là những gì sẽ
cho phép chúng tôi để sắp xếp một mảng của, hãy nói, tám yếu tố.
Vì vậy, tôi có tám quả bóng căng thẳng hơn lên ở đây, tám miếng giấy, và một
Google Glass -
mà tôi nhận được để giữ.
>> [Cười]
>> DAVID Malan: Nếu chúng ta có thể mất tám tình nguyện viên, và hãy xem liệu chúng ta có thể
chơi này ra, vì vậy.
Wow, OK.
Khoa học máy tính là nhận được vui vẻ.
Được rồi.
Vì vậy, làm thế nào về bạn ba, bàn tay lớn nhất ở đó.
Bốn ở phía sau.
Và làm thế nào về chúng tôi sẽ làm bạn ba trong hàng này?
Và bốn ở phía trước.
Vì vậy, bạn tám, đi lên trên.
>> [Cười]
>> DAVID Malan: Tôi thực sự không chắc chắn những gì nó được.
Đó có phải là quả bóng căng thẳng?
Các loại đèn bàn?
Vật liệu?
Internet?
>> OK.
Vì vậy, đến ngày lên.
Ai muốn -
tiếp tục đến.
Chúng ta hãy xem.
Và điều này đặt bạn vào vị trí -
bạn đang ở trong vị trí một.
Uh-oh, chờ một phút.
1, 2, 3, 4, 5, 6, 7 - oh, tốt.
Được rồi, chúng tôi đang tốt.
Được rồi, vì vậy tất cả mọi người có một chỗ ngồi, nhưng không phải trên kính Google.
Hãy để tôi xếp hàng này lên.
Tên của bạn là gì?
>> Michelle: Michelle.
>> DAVID Malan: Michelle?
Tất cả các bên phải, bạn có thể trông giống như đam mê, nếu đó là OK.
Vâng, tôi cũng vậy, tôi cho rằng, chỉ trong khoảnh khắc.
Được rồi, chế độ chờ.
Chúng tôi đã cố gắng để đưa ra một trường hợp sử dụng cho Google Glass, và chúng tôi
nghĩ rằng nó sẽ được vui vẻ để chỉ cần làm này khi mọi người trên sân khấu.
Chúng tôi sẽ ghi lại thế giới từ quan điểm của họ.
Được rồi.
Không lẽ là những gì Google dự định.
Được rồi, nếu bạn không nhớ mặc này cho lúng túng phút tiếp theo,
đó sẽ là tuyệt vời.
>> Được rồi, vì vậy chúng tôi có ở đây một loạt các các yếu tố, và mảng, theo
mảnh giấy với những kẻ ' bàn tay, hiện đang được phân loại.
>> Michelle: Ồ, thật là kỳ lạ.
>> DAVID Malan: Đó là khá nhiều ngẫu nhiên.
Và chỉ trong một thời điểm, chúng tôi sẽ cố gắng thực hiện hợp nhất phân loại lại với nhau
và nhìn thấy nơi đó chính là cái nhìn sâu sắc.
Và các trick ở đây với hợp nhất là loại một cái gì đó mà chúng tôi đã không giả định được nêu ra.
Chúng tôi thực sự cần một số không gian bổ sung.
Vì vậy, những gì đang có được đặc biệt quan tâm ở đây là những
kẻ sẽ di chuyển xung quanh một chút chút, bởi vì tôi sẽ cho rằng
có một mảng thêm không gian, nói, ngay sau họ.
>> Vì vậy, nếu họ đang đứng sau ghế của mình, đó là mảng thứ cấp.
Nếu họ đang ngồi ở đây, đó là mảng chính.
Nhưng đây là một nguồn tài nguyên mà chúng ta có không thừa hưởng vậy, đến nay với bong bóng
sắp xếp, với các lựa chọn sắp xếp, với sắp xếp chèn.
Nhớ lại tuần trước, tất cả mọi người chỉ loại xáo trộn tại chỗ.
Họ không sử dụng bất kỳ bộ nhớ bổ sung.
Chúng tôi đã làm chỗ cho mọi người bằng cách di chuyển những người xung quanh.
>> Vì vậy, đây là một cái nhìn sâu sắc quan trọng, quá.
Có này cân bằng, nói chung trong khoa học máy tính, các nguồn tài nguyên.
Nếu bạn muốn tăng tốc độ một cái gì đó như thời gian, bạn sẽ
phải trả một giá.
Và một trong những giá là rất thường xuyên không gian, số lượng bộ nhớ hoặc cứng
không gian đĩa mà bạn đang sử dụng.
Hoặc, thẳng thắn, số tiền thời gian lập trình.
Bao nhiêu thời gian nó sẽ đưa bạn, con người, để thực sự thực hiện một số chi tiết
thuật toán phức tạp.
Nhưng ngày hôm nay, thương mại-off là thời gian và không gian.
>> Vì vậy, nếu các bạn chỉ có thể giữ lên của bạn số vì vậy chúng tôi có thể thấy rằng bạn đang
thực sự phù hợp với 4, 2, 6, 1, 3, 7, 8.
Tuyệt vời.
Vì vậy, tôi sẽ cố gắng dàn xếp điều, nếu các bạn có thể chỉ cần
theo sự hướng dẫn của tôi ở đây.
>> Vì vậy, tôi sẽ thực hiện, đầu tiên, Bước đầu tiên của mã giả, đó là
trên đầu vào của n phần tử, nếu n là ít hơn 2, sau đó quay trở lại.
Rõ ràng, đó không áp dụng, vì vậy chúng tôi di chuyển trên.
Vì vậy, sắp xếp nửa bên trái của các yếu tố.
Vì vậy, có nghĩa là tôi sẽ tập trung của tôi sự chú ý cho một thời điểm trên những
bốn chàng trai ở đây.
Được rồi, tôi làm những gì tiếp theo làm gì?
>> ĐỐI TƯỢNG: Sắp xếp nửa trái.
>> DAVID Malan: Vì vậy, bây giờ tôi phải sắp xếp nửa bên trái của những kẻ.
Bởi vì một lần nữa, giả định cho mình những Mục đích là để sắp xếp một nửa trái.
Làm thế nào để bạn làm điều đó?
Chỉ cần làm theo các hướng dẫn, thậm chí mặc dù chúng tôi đang làm điều đó một lần nữa.
Vì vậy, sắp xếp nửa trái.
Bây giờ tôi sắp xếp hai chàng trai.
Những gì xảy ra tiếp theo?
>> ĐỐI TƯỢNG: Sắp xếp nửa trái.
>> DAVID Malan: Sắp xếp nửa trái.
Vì vậy, bây giờ này, chỗ này đây, là một danh sách các kích thước 1.
Và tên của bạn là gì nữa?
>> PRINCESS DAISY: Công chúa Daisy.
>> DAVID Malan: Công chúa Daisy là đây.
Và vì vậy cô đã được sắp xếp, bởi vì danh sách có kích thước 1.
Tôi phải làm gì tiếp theo làm gì?
OK, quay trở lại, bởi vì danh sách đó là của kích thước 1, đó là ít hơn 2.
Sau đó, bước tiếp theo là gì?
Và bây giờ bạn phải loại quay lại trong tâm trí của bạn.
>> Sắp xếp nửa bên phải, đó là -
Tên của bạn là gì?
>> LINDA: Linda.
>> DAVID Malan: Linda.
Và do đó chúng ta làm gì bây giờ chúng tôi có một danh sách các kích thước 1?
>> ĐỐI TƯỢNG: Trở về.
>> DAVID Malan: cẩn thận.
Chúng tôi quay trở lại đầu tiên, và bây giờ là thứ ba bước - và nếu tôi loại mô tả nó bằng cách
ôm lấy hai chỗ ngồi bây giờ, bây giờ tôi phải kết hợp hai yếu tố này.
Vì vậy, bây giờ không may, các yếu tố là ra lệnh.
Nhưng đó là nơi quá trình sáp nhập bắt đầu để có được hấp dẫn.
>> Vì vậy, nếu các bạn có thể đứng lên chỉ một thời điểm, tôi sẽ cần bạn, trong một
thời điểm, bước đằng sau ghế của bạn.
Và nếu Linda, bởi vì 2 là nhỏ hơn 4, tại sao không
bạn đi xung quanh đầu tiên?
Ở lại đó.
Vì vậy, Linda, bạn đi xung quanh đầu tiên.
>> Bây giờ trong thực tế nếu nó chỉ là một mảng chúng tôi chỉ có thể di chuyển của cô trong thời gian thực
từ ghế này đến chỗ này.
Vì vậy, hãy tưởng tượng rằng lấy một số không đổi số bước 1.
Và bây giờ -
nhưng chúng ta cần phải đưa bạn vào vị trí đầu tiên ở đây.
>> Và bây giờ nếu bạn có thể đi xung quanh, là tốt, chúng ta sẽ
được vị trí hai.
Và mặc dù điều này cảm thấy như đó là một khoảng thời gian, những gì tốt đẹp hiện nay là
rằng nửa bên trái của nửa bên trái bây giờ được sắp xếp.
Vì vậy, những gì đã được bước tiếp theo, nếu chúng ta bây giờ tua lại tiếp tục trong câu chuyện này?
>> ĐỐI TƯỢNG: phải nửa.
>> DAVID Malan: Sắp xếp đúng một nửa.
Vì vậy, các bạn phải làm điều này, là tốt.
Vì vậy, nếu bạn có thể đứng lên cho một thời điểm?
Và tên của bạn là gì?
>> JESS: Jess.
>> DAVID Malan: Jess.
OK, vì vậy Jess hiện đang là trái một nửa của nửa bên phải.
Và vì vậy cô ấy là một danh sách các kích thước 1.
Cô ấy rõ ràng là sắp xếp.
Và tên của bạn một lần nữa?
>> Michelle: Michelle.
>> DAVID Malan: Michelle là rõ ràng một danh sách các kích thước 1.
Cô ấy đã được sắp xếp.
Vì vậy, bây giờ sự kỳ diệu xảy ra, quá trình sáp nhập.
Vì vậy, ai sẽ đến trước?
Rõ ràng là Michelle.
Vì vậy, nếu bạn có thể đi xung quanh trở lại.
Không gian, chúng tôi đã có sẵn cho cô ấy bây giờ là ngay phía sau ghế này đây.
Và bây giờ nếu bạn có thể trở lại là tốt, bây giờ chúng ta có, để được rõ ràng, hai
nửa, mỗi kích thước 2 -
và chỉ vì lợi ích của mô tả, nếu bạn có thể làm cho một chút của một không gian -
còn ai nửa đây, nửa bên phải ở đây.
>> Tua lại tiếp tục trong câu chuyện.
Bước gì tiếp theo?
>> ĐỐI TƯỢNG: Merge.
>> DAVID Malan: Vì vậy, bây giờ chúng ta phải hợp nhất.
Vì vậy, OK, vì vậy bây giờ, may mắn thay, chúng tôi chỉ giải phóng lên bốn ghế.
Vì vậy, chúng tôi đã sử dụng gấp đôi bộ nhớ, nhưng chúng tôi có thể cung cấp cho thể đảo ngược giữa
hai mảng.
Vì vậy, con số nào thì đến đầu tiên?
Vì vậy, Michelle, rõ ràng.
Vì vậy, đến xung quanh và mất chỗ ngồi của bạn ở đây.
Và sau đó số 2 là rõ ràng tiếp theo, vì vậy bạn đến đây.
Số 4, số 6.
Và một lần nữa, mặc dù có một chút đi bộ có liên quan,
thực sự, đây có thể xảy ra ngay lập tức, bằng cách di chuyển một -
OK, cũng chơi.
>> [Cười]
>> DAVID Malan: Và bây giờ chúng tôi trong hình dạng khá tốt.
Nửa bên trái của toàn bộ đầu vào đã được sắp xếp.
Được rồi, vì vậy những kẻ có lợi thế của tôi -
làm thế nào nó kết thúc tất cả các cô gái trên trái và tất cả các chàng trai bên phải?
>> OK, vì vậy chàng trai 'biến ngay bây giờ.
Vì vậy, tôi sẽ không hướng dẫn bạn qua các bước sau.
Chúng ta sẽ thấy nếu chúng ta có thể nộp đơn xin lại cùng giả.
Nếu bạn muốn đi trước và đứng lên, và các bạn, hãy để tôi cung cấp cho bạn mic.
Xem nếu bạn không thể tái tạo những gì chúng ta chỉ cần làm ở đây trên
đầu kia của danh sách.
Ai có nhu cầu nói chuyện đầu tiên, dựa trên các thuật toán?
Vì vậy, giải thích những gì bạn đang làm trước bạn thực hiện bất kỳ chuyển động chân.
>> SPEAKER 1: Được rồi, như vậy kể từ Tôi là một nửa bên trái của
nửa bên trái, tôi quay trở lại.
Phải không?
>> DAVID Malan: Tốt.
>> SPEAKER 1: Và sau đó -
>> DAVID Malan: Ai làm mic đi đến tiếp theo?
>> SPEAKER 1: số kế tiếp.
>> SPEAKER 2: Vì vậy, tôi nửa bên phải nửa bên trái của
nửa bên trái, và tôi quay trở lại.
>> DAVID Malan: Tốt.
Bạn quay trở lại.
Vì vậy bây giờ lên tới cho bạn hai là những gì?
>> SPEAKER 2: Chúng tôi muốn xem ai là nhỏ hơn.
>> DAVID Malan: Chính xác.
Chúng tôi muốn kết hợp.
Không gian chúng ta sẽ sử dụng để hợp nhất bạn vào, mặc dù họ
rõ ràng là đã được sắp xếp, chúng ta sẽ theo cùng một thuật toán.
Vì vậy, những người đi ở phía trước?
Vì vậy, 3, và sau đó 7.
Và bây giờ là mic đi để những kẻ, OK?
>> SPEAKER 3: Vì vậy, tôi nửa bên phải của nửa bên trái, và n của tôi là ít hơn
1, vì vậy tôi chỉ cần đi để vượt qua -
>> DAVID Malan: Tốt.
>> SPEAKER 4: Tôi là một nửa bên phải của nửa bên phải của nửa bên phải, và tôi
cũng là một người, vì vậy tôi sẽ trở lại.
Vì vậy, bây giờ chúng tôi hợp nhất.
>> SPEAKER 3: Vì vậy, chúng tôi quay trở lại.
>> DAVID Malan: Vì vậy, bạn đi vào phía sau.
Vì vậy, 5 đi đầu tiên, sau đó 8.
Và bây giờ khán giả, đó là bước chúng ta phải bây giờ quay lại
sao để trong tâm trí của chúng tôi?
>> ĐỐI TƯỢNG: Merge.
>> DAVID Malan: sáp nhập nửa trái và phải một nửa của một nửa trái ban đầu.
Vì vậy, bây giờ -
và chỉ để làm cho rõ ràng, làm cho một ít không gian
giữa hai chàng trai.
Vì vậy, bây giờ đó là hai danh sách, trái và phải.
Vì vậy, làm thế nào để chúng ta hợp nhất các bạn vào hàng ghế đầu của ghế một lần nữa?
>> 3 đi đầu tiên.
Sau đó, 5, rõ ràng.
Sau đó, 7, và bây giờ 8.
OK, và bây giờ chúng tôi?
>> ĐỐI TƯỢNG: Không thực hiện.
>> DAVID Malan: Không thực hiện, bởi vì rõ ràng, có một bước còn lại.
Nhưng một lần nữa, lý do tôi đang sử dụng này thuật ngữ như "tua lại trong tâm trí của bạn,"
đó là bởi vì đó là thực sự những gì đang xảy ra.
Chúng tôi đang trải qua tất cả các bước, nhưng chúng tôi đang sắp xếp tạm dừng cho một
thời điểm, lặn sâu hơn vào thuật toán, tạm dừng một lúc,
lặn sâu hơn vào các thuật toán, và bây giờ chúng tôi phải sắp xếp của tua lại trong chúng tôi
tâm trí và quay lại tất cả các lớp mà chúng tôi đã loại tay vào.
>> Vì vậy, bây giờ chúng tôi có hai danh sách có kích thước 4.
Nếu các bạn có thể đứng lên một lần cuối cùng và làm cho một chút không gian ở đây để
làm cho rõ ràng rằng đây là trái một nửa của bản gốc,
nửa bên phải của bản gốc.
Ai là số đầu tiên mà chúng tôi cần phải kéo vào phía sau?
Michelle, tất nhiên.
>> Vì vậy, chúng tôi đưa Michelle đây.
Và những người có số 2?
Số 2 đi kèm trên lại là tốt.
Số 3?
Tuyệt vời.
Số 4, số 5, số 6, số 7 và số 8.
>> OK, vì vậy nó cảm thấy như rất nhiều các bước, chắc chắn.
Nhưng bây giờ chúng ta hãy xem nếu chúng tôi không thể xác nhận loại trực giác rằng điều này
thuật toán cơ bản, đặc biệt là n được thực sự lớn, như chúng ta đã thấy
với những hình ảnh động, là về cơ bản nhanh hơn.
Vì vậy, tôi khẳng định thuật toán này, trong điều tồi tệ nhất trường hợp và thậm chí cả trong trường hợp tốt nhất,
là O lớn của n lần log n.
Đó là, có một số khía cạnh của này thuật toán mà phải mất n bước, nhưng
có một khía cạnh khác nơi nào đó trong đó lặp đi lặp lại, vòng lặp đó, mà
có log n bước.
Chúng ta có thể đặt ngón tay của chúng tôi về những gì những hai con số được đề cập đến?
Vâng, nơi -
đi đâu rồi cầm mic đi?
>> SPEAKER 1: Liệu đăng nhập n là phá vỡ chúng thành hai -
chia hai, về cơ bản.
>> DAVID Malan: Chính xác.
Bất cứ lúc nào chúng ta thấy trong bất kỳ thuật toán như vậy, đến nay, đã có mô hình này
phân chia, phân chia, phân chia.
Và nó thường được giảm để một cái gì đó
logarit, đăng nhập cơ sở 2.
Nhưng nó thực sự có thể là bất cứ điều gì, nhưng đăng nhập cơ sở 2.
>> Bây giờ những gì về n?
Tôi có thể thấy rằng chúng tôi loại chia bạn kẻ - chia bạn, chia bạn,
chia bạn, chia bạn.
Trường hợp nào cuối cùng đến từ đâu?
>> Vì vậy, đó là sáp nhập.
Bởi vì suy nghĩ về nó.
Khi bạn kết hợp tám người với nhau, trong đó một nửa trong số đó là một bộ bốn
và một nửa khác là khác bộ bốn, làm thế nào để bạn đi
về làm việc sáp nhập?
Vâng, các bạn đã làm nó khá trực quan.
>> Nhưng nếu tôi thay vì làm điều đó nhiều hơn một chút có phương pháp, tôi có thể chỉ vào
người ngoài cùng bên trái đầu tiên với trái của tôi tay, chỉ vào người ngoài cùng bên trái
của một nửa với bàn tay phải của tôi, và chỉ sau đó đi qua
danh sách, chỉ vào phần tử nhỏ nhất mỗi thời gian, di chuyển ngón tay của tôi hơn và
hơn là cần thiết trong suốt danh sách.
Nhưng điều quan trọng về việc sáp nhập này quá trình là tôi so sánh những cặp
các yếu tố.
Từ nửa bên phải và từ bên trái một nửa, tôi sẽ không bao giờ một lần thụt lùi.
>> Vì vậy, việc hợp nhất chính nó được dùng không quá n bước.
Và bao nhiêu lần tôi có để làm điều đó sáp nhập?
Vâng, không quá n, và chúng tôi chỉ thấy rằng với sự hợp nhất thức.
Và vì vậy nếu bạn làm điều gì đó mà có đăng nhập n bước n lần, hoặc ngược lại,
nó sẽ cung cấp cho chúng tôi n lần log n.
>> Và tại sao điều này tốt hơn?
Vâng, nếu chúng ta đã biết bản ghi n là tốt hơn so với n - phải không?
Chúng ta đã thấy trong tìm kiếm nhị phân, danh bạ điện thoại Ví dụ, đăng nhập n là chắc chắn
tốt hơn so với tuyến tính.
Vì vậy, có nghĩa là n lần đăng nhập n là chắc chắn tốt hơn so với n lần khác
n, AKA n bình phương.
Và đó là cuối cùng những gì chúng tôi cảm thấy.
>> Vòng quá lớn của tiếng vỗ tay, nếu chúng ta có thể, những người này.
>> [Vỗ tay]
>> DAVID Malan: Và món quà chia tay của bạn - bạn có thể giữ cho các con số,
nếu bạn muốn.
Và món quà chia tay của bạn, như thường lệ.
Oh, và chúng tôi sẽ gửi cho bạn các cảnh quay, Michelle.
Cảm ơn bạn.
Được rồi.
Giúp mình để một quả bóng căng thẳng.
>> Và cho tôi kéo lên, trong khi đó, người bạn của chúng tôi Rob Bowden cung cấp
quan điểm hơi khác nhau về điều này, vì bạn có thể suy nghĩ về những
bước xảy ra trong một phần nào cách khác nhau.
Trong thực tế, các thiết lập cho những gì Rob là về để cho chúng ta giả định rằng chúng tôi đã
đã thực hiện các phân chia của danh sách lớn thành tám danh sách nhỏ,
mỗi kích thước 1.
>> Vì vậy, chúng tôi đang thay đổi một giả chút chỉ để sắp xếp của có được ở các
ý tưởng cốt lõi của cách thức hoạt động sáp nhập.
Nhưng thời gian chạy của những gì anh đang làm là vẫn còn
sẽ được như vậy.
Và một lần nữa, các thiết lập ở đây là anh ấy bắt đầu với tám danh sách các kích thước 1.
Vì vậy, bạn đã bị mất một phần nơi ông là thực sự thực hiện các log n, n log, log n
phân chia của đầu vào.
>> [VIDEO xem lại]
>> -Đó là nó cho bước một.
Đối với bước hai, nhiều lần kết hợp cặp danh sách.
>> DAVID Malan: Hm.
Chỉ có âm thanh là đến ra khỏi máy tính của tôi.
Hãy thử này một lần nữa.
>> -Chỉ cần tùy tiện chọn đó - bây giờ chúng tôi có bốn danh sách.
Tìm hiểu trước.
>> DAVID Malan: Hiện chúng tôi đi.
>> -Kết hợp 108 và 15, chúng tôi kết thúc với danh sách 15, 108.
Sáp nhập 50 và 4, chúng tôi kết thúc với 4, 50.
Sáp nhập 8 và 42, chúng tôi kết thúc với 8, 42.
Và sáp nhập 23 và 16, chúng tôi kết thúc với 16, 23.
>> Bây giờ tất cả danh sách của chúng tôi có kích thước 2.
Chú ý rằng mỗi bốn danh sách được sắp xếp.
Vì vậy, chúng ta có thể bắt đầu sáp nhập cặp danh sách một lần nữa.
Sáp nhập 15 và 108 và 4 và 50, chúng tôi đầu tiên lấy 4, sau đó 15, sau đó
50, sau đó là 108.
Sáp nhập 8, 42 và 16, 23, đầu tiên chúng tôi thực hiện 8, sau đó là 16, sau đó 23,
sau đó là 42.
>> Vì vậy, bây giờ chúng tôi chỉ có hai danh sách các kích thước 4, mỗi trong số đó được sắp xếp.
Vì vậy, bây giờ chúng ta hợp nhất hai danh sách này.
Đầu tiên, chúng ta lấy 4, sau đó chúng tôi đi 8, sau đó chúng ta lấy 15, sau đó 16, sau đó
23, sau đó 42, sau đó 50, sau đó 108.
>> [END xem video]
>> DAVID Malan: Một lần nữa, thông báo, ông không bao giờ chạm vào một tách cho nhiều hơn một thời gian
sau khi tiến xa hơn nữa.
Vì vậy, ông không bao giờ lặp lại.
Vì vậy ông ta luôn luôn di chuyển sang một bên, và đó là nơi chúng tôi có n của chúng tôi.
>> Tại sao không cho tôi kéo lên một hình ảnh động mà chúng ta đã thấy trước đó, nhưng lần này
chỉ tập trung vào việc hợp nhất loại.
Hãy để tôi đi trước và phóng to trong này đây.
Trước tiên cho tôi chọn một đầu vào ngẫu nhiên, phóng đại này, và bạn có thể sắp xếp của thấy
những gì chúng tôi đã cho các cấp, trước đó, hợp nhất phân loại là thực sự làm.
>> Vì vậy, nhận thấy rằng bạn có được những nửa hoặc các khu vực này hoặc những phần tám của
vấn đề mà tất cả của một đột ngột bắt đầu hình thành tốt.
Và cuối cùng, bạn nhìn thấy ở kết thúc rất có bam,
tất cả mọi thứ được sáp nhập với nhau.
>> Vì vậy, đây chỉ là ba khác nhau có trên ý tưởng tương tự.
Nhưng cái nhìn sâu sắc quan trọng, giống như chia và chinh phục trong các lớp học đầu tiên,
là chúng tôi quyết định bằng cách nào đó chia vấn đề thành một cái gì đó lớn, thành
một cái gì đó loại giống hệt nhau trong tinh thần, nhưng nhỏ hơn và nhỏ hơn và nhỏ hơn
và nhỏ hơn.
>> Bây giờ một cách thú vị để sắp xếp các suy nghĩ về các, mặc dù nó không
sẽ cung cấp cho bạn cùng trực quan sự hiểu biết, là
các hình ảnh động sau đây.
Vì vậy, đây là một người nào đó phim cùng nhau có liên quan khác nhau
âm thanh với các hoạt động khác nhau cho sắp xếp chèn, cho hợp nhất sắp xếp, và
cho một vài người khác.
Vì vậy, trong một thời điểm, tôi sẽ nhấn Play.
Đó là khoảng một phút dài.
Và ngay cả khi bạn vẫn có thể thấy mô hình xảy ra, thời gian này bạn có thể
cũng nghe như thế nào các thuật toán thực hiện khác nhau và với
mô hình hơi khác nhau.
>> Đây là sắp xếp chèn.
>> [Nhạc CHƠI]
>> DAVID Malan: Một lần nữa, đang cố gắng để chèn mỗi phần tử
vào nơi mà nó thuộc về.
Đây là bong bóng sắp xếp.
>> [Nhạc CHƠI]
>> DAVID Malan: Và bạn có thể sắp xếp của cảm giác cách tương đối ít làm việc nó làm
trên mỗi bước.
Đây là những gì tediousness giống như âm thanh.
>> [Nhạc CHƠI]
>> DAVID Malan: Đây là lựa chọn sắp xếp, nơi mà chúng tôi lựa chọn các yếu tố chúng ta muốn bằng cách
đi qua một lần nữa và một lần nữa và một lần nữa và đặt nó ngay từ đầu.
>> [Nhạc CHƠI]
>> DAVID Malan: Đây là hợp nhất phân loại, mà bạn thực sự có thể bắt đầu cảm thấy.
>> [Nhạc CHƠI]
>> [Cười]
>> DAVID Malan: Một cái gì đó gọi là gnome loại, trong đó chúng tôi đã không nhìn.
>> [Nhạc CHƠI]
>> DAVID Malan: Vì vậy, chúng tôi thấy, bây giờ, bị phân tâm như bạn hy vọng là do
âm nhạc, nếu tôi có thể ra một chút bit của toán học trong đây.
Vì vậy, có một cách thứ tư mà chúng ta có thể suy nghĩ về những gì nó có nghĩa là các
chức năng được nhanh hơn so với những người mà chúng ta đã thấy trước đây.
Và nếu bạn đến vào khóa học từ một nền tảng toán học, bạn
thực sự biết có lẽ đã là bạn có thể tát một thuật ngữ về kỹ thuật này -
cụ thể là đệ quy, một chức năng bằng cách nào đó tự gọi mình.
>> Và một lần nữa, nhớ lại rằng hợp nhất loại giả là đệ quy trong ý nghĩa
là một trong những bước hợp nhất của loại đã gọi loại -
có nghĩa là, chính nó.
Nhưng may mắn, bởi vì chúng tôi giữ gọi loại, hoặc hợp nhất phân loại,
đặc biệt, trên một nhỏ hơn và nhỏ hơn và danh sách nhỏ hơn, chúng tôi cuối cùng
đáy nhờ vào những gì chúng tôi sẽ gọi một trường hợp cơ sở, các trường hợp mã hóa cứng mà
cho biết nếu danh sách là nhỏ, ít hơn 2 trong trường hợp đó, chỉ trả lại ngay lập tức.
Nếu chúng ta không có mà trường hợp đặc biệt, các thuật toán sẽ không bao giờ chạm đáy,
và bạn thực sự sẽ nhận được vào một vòng lặp vô hạn thực sự mãi mãi.
>> Nhưng giả sử rằng chúng tôi muốn bây giờ đặt một số con số về điều này, một lần nữa, sử dụng n
như kích thước của đầu vào.
Và tôi muốn hỏi bạn, những gì tổng thời gian tham gia vào
chạy hợp nhất loại?
Hay rộng hơn, những gì chi phí của nó trong thời gian?
>> Vâng đó là khá dễ dàng để đo lường đó.
Nếu n là ít hơn 2, thời gian tham gia trong sắp xếp n phần tử,
trong đó n là 2, là 0.
Bởi vì chúng tôi chỉ trả lại.
Không có việc phải làm.
Bây giờ cho là, có lẽ đó là một bước hoặc hai các bước để tìm ra số lượng
làm việc, nhưng nó đủ gần để 0 mà Tôi chỉ muốn nói không làm việc là
yêu cầu nếu danh sách là quá nhỏ được nhàm chán.
>> Nhưng trường hợp này rất thú vị.
Trường hợp đệ quy là chi nhánh của mã giả mà nói khác, loại
nửa bên trái, sắp xếp quyền một nửa, hợp nhất hai nửa.
Bây giờ tại sao biểu hiện này đại diện cho chi phí đó?
Vâng, T n chỉ có nghĩa là thời gian để sắp xếp các yếu tố n.
Và sau đó ở phía bên phải của dấu bằng ở đó, T n chia
2 là đề cập đến chi phí của những gì?
Sắp xếp nửa trái.
T khác của n khi chia cho 2 là có lẽ đề cập đến chi phí để
sắp xếp nửa bên phải.
>> Và sau đó là n cộng?
Là sáp nhập.
Bởi vì nếu bạn có hai danh sách, một trong những kích thước n hơn 2 và một kích thước n
hơn 2, bạn phải chạm vào cơ bản mỗi người trong những yếu tố, giống như Rob
chạm vào mỗi ly, và chỉ như chúng tôi chỉ vào từng
tình nguyện viên trên sân khấu.
Vì vậy, n là các chi phí của hợp nhất.
>> Bây giờ không may, công thức này cũng là chính nó đệ quy.
Vì vậy, nếu hỏi những câu hỏi, nếu n là, nói, 16, nếu có 16 người trên sân khấu
hoặc 16 ly trong video, bao nhiêu tổng số bước hiện nó đi để sắp xếp chúng
hợp nhất với loại?
Nó thực sự không phải là một câu trả lời rõ ràng, bởi vì bây giờ bạn phải phân loại của
đệ quy trả lời công thức này.
>> Nhưng đó là OK, vì cho tôi đề xuất mà chúng ta làm như sau.
Thời gian tham gia để sắp xếp 16 người hoặc 16 ly sẽ được đại diện
nói chung như T 16.
Nhưng mà bằng, theo chúng tôi công thức trước, 2 lần số tiền
thời gian cần thiết để sắp xếp 8 ly cộng với 16.
Và một lần nữa, cộng với 16 là thời gian để hợp nhất, và hai lần T của 8 là
thời gian để sắp xếp một nửa trái và nửa bên phải.
>> Nhưng một lần nữa, điều này là không đủ.
Chúng ta phải lặn sâu hơn.
Điều này có nghĩa chúng ta phải trả lời câu hỏi, là những gì T của 8?
Cũng T của 8 chỉ là 2 lần T của 4 cộng với 8.
Vâng, T 4 là gì?
T của 4 chỉ là 2 lần T của 2 cộng 4.
Vâng, T 2 là gì?
T của 2 chỉ là 2 lần T của 1 cộng với 2.
>> Và một lần nữa, chúng ta đang loại nhận bị mắc kẹt trong chu kỳ này.
Nhưng đó là về để đạt mà cái gọi là trường hợp cơ sở.
Bởi vì những gì là T 1, đã làm chúng tôi yêu cầu bồi thường?
0.
Vì vậy, bây giờ cuối cùng, chúng ta có thể làm việc ngược.
>> Nếu T của 1 là 0, tôi bây giờ có thể quay trở lại một xếp hàng để anh chàng này ở đây, và tôi có thể
cắm vào 0 cho T 1.
Vì vậy, có nghĩa là nó tương đương với 2 lần số không, hay còn gọi là 0, cộng với 2.
Và để biểu hiện toàn bộ là 2.
>> Bây giờ nếu tôi lấy T 2, có câu trả lời là 2, cắm nó vào các đường trung tuyến, T
4, cung cấp cho tôi 2 lần 2 cộng với 4, do đó 8.
Nếu tôi sau đó cắm trong 8 với trước đó đường, cung cấp cho tôi 2 lần 8, 16.
Và nếu chúng ta sau đó tiếp tục có với 24, thêm vào 16, chúng tôi cuối cùng đã có được một
giá trị 64.
>> Bây giờ trong và của chính nó loại nói không có gì để ký hiệu n,
O lớn, omega rằng chúng tôi đã được nói đến.
Nhưng nó chỉ ra rằng 64 thực sự là 16, kích thước của đầu vào,
đăng nhập cơ sở 2 của 16.
Và nếu điều này là một chút không quen thuộc, chỉ nghĩ lại, và nó sẽ trở lại
để bạn cuối cùng.
Nếu đây là nhật ký cơ sở 2, nó giống như 2 nâng lên những gì cho bạn 16?
Ồ, đó là 4, vì vậy 16 lần 4.
>> Và một lần nữa, nó không phải là một vấn đề lớn nếu điều này là sắp xếp của một bộ nhớ mơ hồ bây giờ.
Nhưng hiện nay, có trên đức tin có 16 bản ghi 16 là 64.
Và như vậy thực sự, với sự tỉnh táo đơn giản này kiểm tra, chúng tôi đã xác nhận -
nhưng không chứng minh chính thức -
rằng thời gian hoạt động của hợp nhất loại thực sự là n log n.
>> Vì vậy, không xấu.
Đó chắc chắn là tốt hơn so với các thuật toán chúng tôi đã nhìn thấy cho đến nay, và
đó là bởi vì chúng ta đã thừa hưởng, một, một kỹ thuật được gọi là đệ quy.
Nhưng thú vị hơn đó, mà khái niệm về phân chia và chinh phục.
Một lần nữa, thực sự tuần 0 thứ mà ngay cả bây giờ được tái diễn trong một
hơn cách thuyết phục.
>> Bây giờ một ít tập thể dục vui vẻ, nếu bạn đã không bao giờ làm điều này - và bạn có thể
sẽ không có, bởi vì loại bình thường mọi người không nghĩ để làm điều này.
Nhưng nếu tôi đi vào google.com và nếu Tôi muốn tìm hiểu về
đệ quy, Enter.
>> [Cười]
[THÊM cười]
DAVID Malan: Bad trò đùa từ từ lan rộng.
[Cười]
DAVID Malan: Chỉ trong trường hợp, nó ở đó.
Tôi không đánh vần sai, và có những trò đùa.
Được rồi.
Giải thích cho những người bên cạnh bạn nếu nó đã không hoàn toàn nhấp chỉ được nêu ra.
Nhưng đệ quy, nói chung, đề cập đến quá trình một chức năng gọi điện
chính nó, hay rộng hơn, phân chia một vấn đề thành một cái gì đó có thể được
giải quyết từng phần bằng cách giải quyết giống hệt nhau vấn đề đại diện.
>> Vâng, chúng ta hãy thay đổi bánh răng chỉ trong khoảnh khắc.
Chúng tôi muốn kết thúc vào cliffhangers nhất định, vì vậy hãy bắt đầu thiết lập
sân khấu, trong vài phút, trên một ý tưởng rất đơn giản -
trao đổi của hai yếu tố này, phải không?
Tất cả các thuật toán chúng tôi đã nói về quá khứ vài
bài giảng liên quan đến một số loại trao đổi.
Hôm nay nó đã được hình dung bằng cách họ nhận được ra khỏi ghế và
đi bộ xung quanh, nhưng trong mã, chúng tôi sẽ chỉ cần lấy một phần tử từ một mảng
và tiếng tom nó vào một.
>> Vì vậy, làm thế nào để chúng tôi đi về việc này?
Vâng, hãy để tôi đi trước và viết một chương trình nhanh chóng ở đây.
Tôi sẽ đi trước và làm này như sau.
Chúng ta hãy gọi này -
những gì chúng ta muốn gọi này?
>> Trên thực tế, không.
Hãy để tôi quay lại.
Tôi không muốn làm điều đó cliffhanger được nêu ra.
Nó sẽ làm hỏng sự vui vẻ.
Hãy làm điều này để thay thế.
>> Giả sử tôi muốn viết một chút chương trình và giờ đây đã này
ý tưởng của đệ quy.
Tôi loại có trước bản thân mình có.
Tôi sẽ phải làm như sau.
>> Đầu tiên, một cách nhanh chóng bao gồm các tiêu chuẩn io.h, cũng như bao gồm các cs50.h.
Và sau đó tôi sẽ đi trước và tuyên bố int main trống
theo cách thông thường.
Tôi nhận ra tôi đã bị đặt tên sai các tập tin, để hãy để tôi chỉ cần thêm một c mở rộng. đây để
chúng tôi có thể biên dịch nó đúng cách.
Bắt đầu chức năng này.
>> Và các chức năng tôi muốn viết, khá đơn giản, là một trong những yêu cầu
người sử dụng cho một số và sau đó tăng dần lên tất cả các số giữa các
số lượng và, nói, 0.
Vì vậy, đầu tiên tôi sẽ đi trước và tuyên bố n int.
Sau đó sao chép một số mã chúng tôi đã sử dụng trong một thời gian.
Trong khi một cái gì đó là sự thật.
Tôi sẽ trở lại đó trong một thời điểm.
>> Tôi phải làm gì muốn làm gì?
Tôi muốn nói printf tích cực nguyên xin.
Và sau đó tôi sẽ nói n được lấy int.
Vì vậy, một lần nữa, một số mã soạn mà chúng ta đã sử dụng trước.
Và tôi sẽ làm điều này trong khi n là nhỏ hơn 1.
Vì vậy, điều này sẽ đảm bảo rằng người sử dụng mang lại cho tôi một số nguyên dương.
>> Và bây giờ tôi sẽ phải làm như sau.
Tôi muốn thêm lên tất cả các con số từ 1 đến n, hoặc 0 và n,
tương đương, để có được tổng số tiền.
Vì vậy, các biểu tượng sigma lớn mà bạn có thể nhớ lại.
Vì vậy, tôi sẽ làm điều này bằng cách gọi đầu tiên một chức năng gọi là sigma,
đi qua nó trong n, và sau đó tôi sẽ printf nói, câu trả lời là phải có.
>> Vì vậy, trong ngắn hạn, tôi nhận được và int từ người sử dụng.
Tôi đảm bảo nó là tích cực.
Tôi khai báo một biến được gọi là câu trả lời của kiểu int và lưu trữ nó trong sự trở lại
giá trị của sigma, đi qua trong n như đầu vào.
Và sau đó tôi in ra câu trả lời.
>> Thật không may, mặc dù sigma âm thanh như một cái gì đó mà có thể trong
các tập tin math.h, tuyên bố của mình, nó thực sự không.
Vì vậy, đó là OK.
Tôi có thể thực hiện điều này bản thân mình.
Tôi sẽ thực hiện một chức năng được gọi là sigma, và nó sẽ mất một
tham số -
chúng ta hãy gọi nó là m, chỉ vì vậy nó khác nhau.
Và sau đó lên đây, tôi sẽ nói, tốt, nếu m là ít hơn 1 - đây là một
rất không thú vị của chương trình.
Vì vậy, tôi sẽ đi trước và ngay lập tức trở về 0.
Nó chỉ có ý nghĩa để gắn lên tất cả các con số từ 1 đến m nếu m
bản thân nó là 0 hoặc âm.
>> Và sau đó tôi sẽ đi trước và làm điều này rất lặp đi lặp lại.
Tôi sẽ làm việc này của trường học cũ, và tôi sẽ đi trước
và nói rằng tôi sẽ khai báo một số tiền là 0.
Sau đó, tôi sẽ có một vòng lặp của int -
và để cho tôi làm điều đó để phù hợp với chúng tôi đang phân phối, vì vậy bạn có một bản sao
ở nhà. int i được 1 trên lên đến i nhỏ hơn hoặc bằng m.
i cộng cộng.
Và sau đó bên trong này cho vòng lặp -
chúng tôi hầu như có -
tổng số tiền được cộng thêm 1.
Và sau đó tôi sẽ trả lại số tiền.
>> Vì vậy, tôi đã làm điều này một cách nhanh chóng, khá thừa nhận.
Nhưng một lần nữa, các chức năng chính khá đơn giản, dựa trên mã chúng tôi đã
bằng văn bản cho đến nay.
Sử dụng vòng lặp kép để có được một dương int từ người sử dụng.
Sau đó tôi vượt qua int rằng đến một chức năng mới gọi là sigma, gọi đó là, một lần nữa, n.
Và tôi lưu trữ các giá trị trả về, câu trả lời từ hộp đen hiện nay
được biết đến như sigma, trong một biến gọi là câu trả lời.
Sau đó, tôi in nó.
>> Nếu bây giờ chúng ta tiếp tục câu chuyện, làm thế nào là sigma thực hiện?
Tôi đề nghị để thực hiện như sau.
Đầu tiên, một chút kiểm tra lỗi để đảm bảo rằng người dùng không
rối tung với tôi và đi qua trong một số giá trị âm hoặc 0.
Sau đó, tôi khai báo một biến được gọi là tổng hợp và đặt nó là 0.
>> Và bây giờ tôi bắt đầu di chuyển từ tôi bằng 1 tất cả các con đường lên đến và bao gồm m,
bởi vì tôi muốn bao gồm tất cả các số từ một đến m, đã bao gồm.
Và bên trong này cho vòng lặp, tôi chỉ cần làm số tiền được bất cứ điều gì nó là bây giờ, cộng với
giá trị của tôi.
Cộng với giá trị của tôi.
>> Như một sang một bên, nếu bạn đã không nhìn thấy điều này trước đây, có một số cú pháp đường
cho dòng này.
Tôi có thể viết lại này như cộng bằng tôi, chỉ để tiết kiệm cho mình một vài tổ hợp phím
và để tìm một chút mát.
Nhưng đó là tất cả.
Đó là chức năng điều tương tự.
>> Thật không may, mã này của sẽ không biên dịch được nêu ra.
Nếu tôi chạy làm cho sigma 0, làm thế nào am Tôi sẽ bị mắng?
Đó là những gì sẽ không như thế nào?
>> ĐỐI TƯỢNG: [nghe được].
>> DAVID Malan: Vâng, tôi đã không khai báo chức năng lên hàng đầu, phải không?
C là ngu ngốc, nó chỉ ở đó những gì bạn nói với nó để làm, và bạn
phải làm điều đó trong thứ tự đó.
Và do đó, nếu tôi nhấn Enter ở đây, tôi sẽ nhận được một cảnh báo về sigma ngầm
kê khai.
>> Oh, không phải là một vấn đề.
Tôi có thể đi lên đến đỉnh, và tôi có thể nói, được rồi, chờ một phút.
Sigma là một hàm trả về một int và dự kiến ​​một
int như đầu vào, dấu chấm phẩy.
Hoặc tôi có thể đặt toàn bộ chức năng trên chính, nhưng nói chung, tôi muốn
khuyên bạn nên chống lại điều đó, bởi vì nó tốt đẹp luôn luôn có chính ở phía trên để
bạn có thể nhảy ngay trong và biết những gì một chương trình đang làm bằng cách đọc chính đầu tiên.
>> Vì vậy, bây giờ hãy để tôi xóa màn hình.
Làm lại sigma 0.
Tất cả dường như để kiểm tra.
Cho phép tôi chạy sigma 0.
Liên quan.
Tôi sẽ cho nó số 3 để giữ cho nó đơn giản.
Vì vậy, cần cung cấp cho tôi 3 cộng với 2 cộng với 1, vì vậy 6.
Nhập, và thực sự tôi nhận được 6.
>> Tôi có thể làm một cái gì đó lớn hơn -
50, 12, 75.
Cũng giống như một tiếp tuyến, tôi sẽ làm một cái gì đó vô lý như một thực sự lớn
số lượng, Oh, mà thực sự đã làm việc ra -
eh, tôi không nghĩ điều đó đúng.
Chúng ta hãy xem.
Chúng ta hãy thực sự gây rối với nó.
>> Đó là một vấn đề.
Những gì đang xảy ra?
Mã này không phải là xấu.
Nó vẫn còn tuyến tính.
Huýt sáo là một hiệu ứng tốt, mặc dù.
Những gì đang xảy ra?
>> Không chắc chắn nếu tôi nghe nó.
Vì vậy, nó quay ra - và đây là như một sang một bên.
Đây không phải là cốt lõi cho ý tưởng của đệ quy.
Hóa ra, vì tôi đang cố gắng để đại diện cho một số lượng lớn như vậy, nhất
khả năng nó được diễn giải sai bằng C như một số không tích cực,
nhưng số âm.
>> Chúng tôi đã không nói về điều này, nhưng nó Hóa ra có một số lượng tiêu cực
trong thế giới ngoài với số dương.
Và các phương tiện mà bạn có thể đại diện một số tiêu cực
chủ yếu là, bạn sử dụng một bit đặc biệt để chỉ ra
tích cực hơn tiêu cực.
Đó là một ít phức tạp hơn, nhưng đó là ý tưởng cơ bản.
>> Vì vậy, không may, nếu C là khó hiểu một của các bit như thực sự có nghĩa là,
oh, đây là một số âm, vòng lặp của tôi ở đây, ví dụ, thực sự là không bao giờ
sẽ chấm dứt.
Vì vậy, nếu tôi đã thực sự in một cái gì đó một lần nữa và một lần nữa, chúng tôi sẽ
thấy một toàn bộ rất nhiều.
Nhưng một lần nữa, đây là bên cạnh những điểm.
Điều này thực sự chỉ là một loại sự tò mò trí tuệ mà chúng ta sẽ đến
sao để cuối cùng.
Nhưng bây giờ, đây là một chính xác thực hiện nếu chúng ta giả định rằng
người sử dụng sẽ cung cấp cho ints mà phù hợp trong số nguyên.
>> Nhưng tôi cho rằng mã này, thẳng thắn, có thể được thực hiện rất nhiều đơn giản hơn.
Nếu mục tiêu trong tầm tay là để có một số như m và thêm lên tất cả các
số giữa nó và 1, hoặc ngược lại từ 1 đến nó, tôi yêu cầu bồi thường
mà tôi có thể mượn ý tưởng này hợp nhất loại đã có, đã được tham gia một vấn đề
kích thước này và chia vào một cái gì đó nhỏ hơn.
Có lẽ không một nửa, nhưng nhỏ hơn, nhưng representatively cùng.
Cùng một ý tưởng, nhưng một vấn đề nhỏ hơn.
>> Vì vậy, tôi thực sự - cho tôi lưu tập tin này với một số phiên bản khác nhau.
Chúng tôi sẽ gọi phiên bản này 1 thay vì 0.
Và tôi cho rằng tôi có thể thực sự reimplement này trong loại này
tâm-uốn cách.
>> Tôi sẽ để lại một phần của nó một mình.
Tôi sẽ nói rằng nếu m là ít hơn hoặc thậm chí bằng 0 -
Tôi chỉ đi được một chút hậu môn hơn thời gian này
với kiểm tra lỗi của tôi -
Tôi sẽ đi trước và trở về 0.
Này là tùy ý.
Tôi chỉ đơn giản là quyết định nếu người dùng mang lại cho tôi một số tiêu cực, tôi
trở về 0, và họ nên đã đọc các tài liệu hướng dẫn chặt chẽ hơn.
>> Khác -
thông báo những gì tôi sẽ làm.
Khác tôi sẽ quay trở lại cộng với m -
sigma của m là gì?
Vâng, sigma m cộng trừ 1 m, cộng trừ m 2, cộng trừ 3 m.
Tôi không muốn viết tất cả ra ngoài.
Tại sao không tôi chỉ punt?
Đệ quy gọi bản thân mình với một chút vấn đề nhỏ hơn, dấu chấm phẩy,
và gọi nó là một ngày?
>> Phải không?
Bây giờ ở đây, bạn có thể cảm thấy lo lắng hay rằng đây là một vòng lặp vô hạn mà tôi
dụ dỗ, theo đó tôi đang thực hiện sigma bằng cách gọi sigma.
Nhưng đó là hoàn toàn OK, bởi vì tôi nghĩ trước một thêm vào đó dòng?
>> ĐỐI TƯỢNG: [nghe được].
>> DAVID Malan: 23-26, mà là nếu tình trạng của tôi.
Vì những gì tốt đẹp về trừ ở đây, bởi vì tôi giữ
bàn giao vấn đề nhỏ hơn sigma, nhỏ hơn vấn đề, nhỏ hơn - đó là không
một nửa kích thước.
Nó chỉ là một bước nhỏ bé, nhưng đó là OK.
Bởi vì cuối cùng, chúng tôi sẽ làm việc cách của chúng tôi xuống 1 hoặc 0.
Và một khi chúng ta nhấn 0, sigma là không sẽ gọi cho bản thân nữa.
Nó sẽ ngay lập tức trở về 0.
>> Vì vậy, có hiệu lực, nếu bạn loại gió này lên trong tâm trí của bạn, là thêm m cộng
m trừ đi 1, cộng trừ 2 m, cộng với m trừ 3, cộng với dấu chấm, dấu chấm, dấu chấm, trừ m
m, cuối cùng đem lại cho bạn 0, và hiệu quả là cuối cùng để thêm tất cả
những điều này lại với nhau.
Vì vậy, chúng ta có không, với đệ quy, giải quyết các vấn đề mà chúng tôi
không thể giải quyết trước.
Trên thực tế, phiên bản 0 điều này, và mỗi vấn đề cho đến nay, đã có khả năng giải quyết
với chỉ sử dụng cho vòng lặp hoặc trong khi vòng hoặc các cấu trúc tương tự.
>> Nhưng đệ quy, tôi dám khẳng định rằng, cho chúng ta một cách nghĩ khác nhau về
vấn đề, theo đó nếu chúng ta có thể có một vấn đề, phân chia nó từ một cái gì đó
phần lớn thành một cái gì đó hơi nhỏ hơn, tôi cho rằng chúng ta có thể giải quyết nó
có lẽ một chút thanh lịch hơn về của thiết kế, với mã ít hơn,
và thậm chí có thể giải quyết vấn đề mà có thể khó khăn hơn, như chúng tôi sẽ cuối cùng
thấy, giải quyết hoàn toàn lặp đi lặp lại.
>> Nhưng cliffhanger mà tôi đã làm muốn để lại cho chúng tôi, đây.
Hãy để tôi đi trước và mở lên một tập tin từ -
thực sự, hãy để tôi đi và làm nhanh thật này.
Hãy để tôi đi trước và đề xuất sau.
Trong số đang ngày nay là tập tin này đây.
Này ở đây, noswap.
>> Vì vậy, đây là một chương trình nhỏ ngu ngốc mà Tôi whipped lên rằng tuyên bố để làm
sau.
Trong chính, nó đầu tiên khai báo một int x và gán nó
giá trị của 1.
Sau đó, nó tuyên bố một y int và gán cho nó giá trị 2.
Sau đó nó in ra những gì x và y được.
Sau đó nó nói, trao đổi, chấm chấm chấm.
>> Sau đó nó tuyên bố được gọi một chức năng được gọi là trao đổi, đi qua trong x và
y, ý tưởng trong số đó là hy vọng x và y sẽ quay trở lại
khác nhau, điều ngược lại.
Sau đó, nó tuyên bố trao đổi!
với một dấu chấm than.
Sau đó nó in ra x và y.
>> Nhưng nó quay ra rằng điều này rất trình diễn đơn giản xuống
đây thực sự là lỗi.
Mặc dù tôi tuyên bố tạm thời biến và tạm thời đặt một trong
nó, sau đó tôi giao lại một giá trị của b -
mà cảm thấy hợp lý, bởi vì tôi đã lưu một bản sao của một trong tạm thời.
Sau đó, tôi cập nhật b để bằng bất cứ điều gì là trong tạm thời.
Điều này loại trò chơi vỏ di chuyển một vào b và b thành một bằng cách sử dụng này
người đàn ông trung được gọi là tạm thời cảm thấy hoàn toàn hợp lý.
>> Nhưng tôi cho rằng khi tôi chạy mã, như tôi sẽ làm gì bây giờ -
hãy để tôi đi trước và dán nó vào đây.
Tôi sẽ gọi noswap.c này.
Và như tên cho thấy, đây không phải là sẽ là một chương trình chính xác.
Làm noswap. / Không trao đổi.
x 1, y là 2, trao đổi, trao đổi.
x 1, y là 2.
Điều này là sai về cơ bản, thậm chí mặc dù điều này dường như hoàn hảo
hợp lý với tôi.
Và có một lý do, nhưng chúng tôi không sẽ tiết lộ lý do chỉ được nêu ra.
>> Chính vì điều đó cliffhanger thứ hai tôi muốn để lại cho bạn là điều này, một
thông báo của các loại trên mã số phiếu giảm giá.
Đổi mới của chúng tôi với cuối ngày trong năm nay đã gây nên một số lượng không nhỏ
các câu hỏi, đó là không ý định của chúng tôi.
Mục đích của các mã số phiếu giảm giá, theo đó nếu bạn làm một phần của vấn đề
thiết lập ban đầu, do đó nhận thêm một ngày, đã thực sự để giúp các bạn giúp đỡ
mình bắt đầu sớm, sắp xếp bởi các tổn của bạn.
Giúp chúng tôi phân phối tải trên giờ làm việc tốt hơn để
đó là loại win-win.
>> Thật không may, tôi nghĩ rằng hướng dẫn của tôi đã không được, cho đến nay, rất rõ ràng, vì vậy
Tôi quay trở lại vào cuối tuần này và cập nhật spec trong lớn hơn, táo bạo hơn để văn bản
giải thích đạn như thế này.
Và chỉ để nói rằng nó công khai hơn, bởi Mặc định, bộ vấn đề là do thứ năm
vào buổi trưa, mỗi giáo trình.
Nếu bạn bắt đầu sớm, kết thúc một phần của vấn đề đặt ra hôm qua tại 12:00
PM, phần có liên quan đến một phiếu giảm giá mã, ý tưởng là bạn có thể mở rộng
thời hạn của bạn cho P thiết lập cho đến thứ sáu.
Đó là, chút đi một phần nhỏ của P thiết lập liên quan đến những gì thường là
vấn đề lớn hơn, và bạn mua mình thêm một ngày.
Một lần nữa, nó giúp bạn suy nghĩ về bộ vấn đề, giúp bạn để
giờ làm việc sớm hơn.
Nhưng vấn đề mã phiếu giảm giá vẫn còn cần thiết, ngay cả khi bạn không gửi nó.
>> Nhưng compellingly hơn là thế này.
(Giai đoạn WHISPER) Và những folks để lại đầu là sẽ hối tiếc.
Như là những người bạn trên ban công.
Tôi xin lỗi trước tới những người trên ban công vì lý do đó sẽ
rõ ràng chỉ trong một thời điểm.
>> Vì vậy, chúng ta may mắn có một trong Cựu nghiên cứu sinh giảng dạy đầu CS50 tại
một công ty gọi là dropbox.com.
Họ đã rất hào phóng tặng một phiếu mua hàng ở đây cho nhiều không gian này,
đó là từ các bình thường 2 GB.
Vì vậy, những gì tôi nghĩ chúng tôi sẽ làm gì về điều này lưu ý cuối cùng là làm một chút về một quà tặng,
theo đó chỉ trong một thời điểm, chúng tôi sẽ tiết lộ người chiến thắng và những người có một phiếu giảm giá
mã mà bạn có thể đi đến của họ trang web, gõ vào, và thì đấy, có được một
nhiều hơn cả không gian Dropbox cho bạn thiết bị và cho các tập tin cá nhân của bạn.
>> Và lần đầu tiên, những người muốn tham gia trong bản vẽ này?
OK, bây giờ mà làm cho nó thú vị hơn nữa.
Người nhận này 25 GB phiếu mua hàng - đó là xa
hấp dẫn hơn vào cuối ngày nay, có lẽ -
là một trong những người đang ngồi trên đầu trang của một ghế đệm bên dưới mà có
mã phiếu giảm giá.
Bây giờ bạn có thể xem bên dưới đệm ghế của bạn.
>> [VIDEO xem lại]
>> -Một, hai, ba.
>> [Hét]
>> -Bạn sẽ có được một chiếc xe hơi!
Bạn sẽ có được một chiếc xe hơi!
>> DAVID Malan: Chúng ta sẽ thấy bạn vào thứ tư.
>> -Bạn sẽ có được một chiếc xe hơi!
Bạn sẽ có được một chiếc xe hơi!
>> DAVID Malan: folks Ban công, đến xuống đây phía trước,
nơi chúng tôi có tính năng bổ sung.
>> -Mọi người đều có một chiếc xe!
Tất cả mọi người có một chiếc xe!
>> [END xem video]
>> Người kể chuyện: Tại tới CS50 -
>> SPEAKER 5: Ôi chúa ơi ơi ơi ơi Chúa ơi ơi ơi ơi ơi ơi -
>> [UKELELE lượt]