>> [MUSIC CHƠI]
>> GIÁO SƯ: Tất cả các quyền.
Đây là CS50 và điều này là cuối tuần ba.
Vì vậy, chúng tôi ở đây ngày hôm nay, không phải trong Sanders Nhà hát, thay vì trong Weidner Library.
Bên trong đó là một phòng thu được gọi là Hauser Studio,
hoặc chúng ta sẽ nói Studio H, hoặc có trách nhiệm chúng tôi say-- nếu bạn rất thích câu nói đùa rằng,
nó thực sự từ bạn cùng lớp, Mark, trực tuyến,
những người đề nghị càng nhiều thông qua Twitter.
Bây giờ những gì là thú vị về được ở đây trong một phòng thu
là tôi đang được bao quanh bởi những màu xanh lá cây bức tường, một màn hình màu xanh lá cây hoặc chromakey,
vậy để nói chuyện, có nghĩa là CS50 của Đội ngũ sản xuất, unbeknownst với tôi
ngay bây giờ, có thể được đặt tôi bất cứ nơi nào nhất trên thế giới,
cho tốt hơn hoặc tồi tệ hơn.
>> Bây giờ những gì nằm phía trước, vấn đề đặt hai là trong tay của bạn trong tuần này,
nhưng với vấn đề đặt ba này trong tuần tới,
bạn sẽ được thử thách với các trò chơi được gọi là 15,
một lợi đảng cũ bạn có thể gọi lại nhận
như một đứa trẻ mà có cả một bó con số đó có thể trượt lên, xuống,
trái và phải, và có một khoảng cách trong câu đố, nơi mà bạn
thực sự có thể trượt những mảnh ghép.
Cuối cùng bạn nhận được điều này lúng túng trong một số lệnh bán ngẫu nhiên,
và mục tiêu là để sắp xếp nó, trên xuống dưới,
trái sang phải, từ một tất cả các con đường lên đến 15.
>> Thật không may, việc thực hiện bạn sẽ có trong tay
là có được phần mềm dựa, không thể chất.
Bạn đang thực sự sẽ phải viết mã với đó là sinh viên hoặc người dùng can
chơi các trò chơi của 15.
Và trên thực tế, trong các hacker phiên bản của trò chơi của 15,
bạn sẽ là một thách thức để thực hiện, không chỉ là sân chơi của trường học cũ này
trò chơi, mà là việc giải quyết của nó, thực hiện chế độ thần,
có thể nói, đó thực sự giải quyết các câu đố cho con người,
bằng cách cung cấp cho họ với các gợi ý, sau khi gợi ý, sau khi gợi ý.
Vì vậy, thêm vào đó vào tuần tới.
Nhưng đó là những gì ở phía trước.
>> Để bây giờ nhớ lại rằng hồi đầu tuần này chúng tôi đã có cliffhanger này, nếu bạn muốn,
nhờ đó mà tốt nhất chúng tôi đã làm phân loại khôn ngoan là một giới hạn trên của o lớn của n
bình phương.
Nói cách khác, bong bóng sắp xếp, sắp xếp chọn, sắp xếp chèn,
tất cả trong số họ, trong khi khác nhau trong việc thực hiện của họ,
thoái hóa thành một n bình chạy thời gian trong trường hợp xấu nhất.
Và chúng ta thường cho rằng trường hợp rất tồi tệ nhất để phân loại
là một trong những yếu tố đầu vào của bạn là hoàn toàn ngược lại.
Và quả thực, nó mất khá một vài bước để thực hiện mỗi người trong những thuật toán.
>> Bây giờ, ở cuối của lớp thu hồi, chúng tôi so sánh bong bóng sắp xếp
chống lựa chọn loại chống lại một khác mà chúng ta gọi là sắp xếp hợp nhất vào thời điểm đó,
và tôi đề xuất rằng nó lấy lợi thế của một bài học từ tuần
bằng không, phân chia và chinh phục.
Và bằng cách nào đó đạt được một số loại logarit chạy lần cuối cùng,
thay vì một cái gì đó mà hoàn toàn là bậc hai.
Và nó không hoàn toàn logarit, nó là nhiều hơn một chút so với điều đó.
Nhưng nếu bạn gọi lại từ trường, nó đã được nhiều hơn, nhanh hơn nhiều.
Chúng ta hãy nhìn vào nơi chúng tôi rời đi.
>> Bubble sort so với lựa chọn loại so với sắp xếp hợp nhất.
Bây giờ tất cả chúng đang chạy, trong Về 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 rất nhanh chóng sẽ trở thành,
và chỉ cần nhanh như thế nào, khi chúng ta tiêm một chút về thuật toán tuần số không,
chúng ta có thể đẩy nhanh tốc độ.
>> Vì vậy, loại nhãn trông tuyệt vời.
Làm thế nào chúng ta có thể tận dụng nó, để để sắp xếp các số một cách nhanh chóng hơn.
Vâng chúng ta hãy nghĩ lại để một thành phần mà chúng ta
đã trở lại trong tuần không, mà của tìm kiếm một người nào đó trong một cuốn sách điện thoại,
và nhớ lại rằng giả mà chúng tôi đề xuất,
thông qua đó chúng ta có thể tìm thấy một người như Mike Smith,
nhìn một chút gì đó như thế này.
>> Bây giờ có một cái nhìn đặc biệt ở dòng 7 và 8, và 10 và 11,
mà gây ra vòng lặp đó, nhờ đó chúng ta giữ đi lại cho dòng 3 một lần nữa, và một lần nữa,
Và một lần nữa.
Nhưng nó chỉ ra rằng chúng ta có thể xem thuật toán này, ở đây trong giả,
một chút một cách toàn diện hơn.
Trong thực tế, những gì tôi đang tìm kiếm ở đây trên màn hình,
là một thuật toán để tìm kiếm Mike Smith trong một số bộ trang.
Và quả thực, chúng ta có thể đơn giản hóa này thuật toán trong những dòng 7 và 8,
và 10 và 11 để chỉ nói điều này, mà tôi đã trình bày ở đây trong màu vàng.
Nói cách khác, nếu Mike Smith là trước đó trong cuốn sách,
chúng ta không cần phải xác định bước bước giờ làm thế nào để đi tìm anh ta.
Chúng tôi không có chỉ định để quay lại dòng 3,
tại sao chúng ta không chỉ thay vào đó, nói rằng, nói chung,
tìm kiếm cho Mike trong nửa bên trái của cuốn sách.
>> Ngược lại, nếu Mike là thực sự sau này trong các cuốn sách,
tại sao chúng ta không chỉ trích dẫn tìm kiếm unquote cho Mike ở nửa bên phải của cuốn sách.
Nói cách khác, tại sao chúng ta không chỉ loại đá trái banh để mình nói,
tìm kiếm cho Mike ở đây tập hợp con của cuốn sách,
và để nó tồn tại của chúng tôi thuật toán để cho chúng tôi
làm thế nào để tìm kiếm cho Mike ở rằng một nửa bên trái của cuốn sách.
Nói cách khác, chúng tôi thuật toán hoạt động cho dù nó
một cuốn sách điện thoại của độ dày này, điều này độ dày, hoặc bất kỳ độ dày nào.
Vì vậy, chúng ta có thể đệ quy xác định thuật toán này.
Nói cách khác, trên màn hình ở đây, là một thuật toán
để tìm kiếm cho Mike Smith trong số các trang của một cuốn sách điện thoại.
Vì vậy, trong dòng 7 và 10, chúng ta hãy chỉ cần nói chính xác điều đó.
Và tôi sử dụng thuật ngữ này một thời điểm trước đây, và quả thật, đệ quy
là từ thông dụng hiện nay, và đó là quá trình này
làm điều gì đó mang tính chu kỳ bằng cách nào đó sử dụng mã mà bạn đã có,
và gọi đó là một lần nữa, và một lần nữa, và một lần nữa.
Bây giờ nó sẽ là quan trọng rằng chúng tôi bằng cách nào đó dưới
ra, và không làm điều đó vô cùng dài.
Nếu không chúng ta sẽ có thực sự là một vòng lặp vô hạn.
Nhưng chúng ta hãy xem liệu chúng ta có thể mượn ý tưởng này của một đệ quy, làm cái gì nữa
và một lần nữa và một lần nữa, để giải quyết vấn đề phân loại thông qua hợp nhất
sắp xếp, hiệu quả tất cả các chi tiết.
>> Vì vậy, tôi cung cấp cho bạn hợp nhất phân loại.
Hãy nhìn xem.
Vì vậy, đây là giả, với mà chúng tôi có thể thực hiện phân loại,
sử dụng thuật toán này được gọi là sắp xếp hợp nhất.
Và nó khá đơn giản này.
Trên đầu vào của n phần tử, nói cách khác, nếu bạn
cho n phần tử và các con số và chữ hoặc bất cứ điều gì các đầu vào là,
nếu bạn đang đưa ra các yếu tố n, nếu n là nhỏ hơn 2, chỉ cần trả lại.
Phải không?
Bởi vì nếu n là nhỏ hơn 2, mà có nghĩa là danh sách các yếu tố
là một trong hai kích thước 0 hoặc 1, và trong cả hai trường hợp tầm thường,
danh sách đã được sắp xếp.
Nếu không có danh sách, nó được sắp xếp.
Và nếu có một danh sách dài 1, nó rõ ràng là sắp xếp.
Vì vậy, các thuật toán chỉ cần thực sự làm điều gì đó thú vị,
nếu chúng ta có hai hoặc nhiều hơn các yếu tố ban cho chúng ta.
Vì vậy, chúng ta hãy nhìn vào sự kỳ diệu đó.
Khác sắp xếp một nửa trái của các yếu tố, sau đó sắp xếp một nửa bên phải của các yếu tố,
sau đó hợp nhất hai nửa được sắp xếp.
Và loại tâm uốn là gì ở đây, là tôi không thực sự
dường như đã nói với bạn bất cứ điều gì chỉ được nêu ra, phải không?
Tất cả tôi đã nói được, đưa ra một danh sách các n phần tử, sắp xếp lại một nửa,
sau đó nửa bên phải, sau đó hợp nhất hai nửa sắp xếp,
nhưng mà là nước sốt bí mật thực tế?
Trường hợp là thuật toán?
Vâng nó chỉ ra rằng những người hai dòng đầu tiên, một nửa loại bỏ các yếu tố,
và sắp xếp đúng một nửa của các yếu tố, những cuộc gọi đệ quy, do đó, để nói chuyện.
>> Sau khi tất cả, lúc này điểm trong thời gian, tôi có
một thuật toán nào đó để sắp xếp một bó toàn bộ các yếu tố?
Vâng.
Nó ở ngay đây.
Nó ở ngay trên màn hình, và vì vậy tôi có thể sử dụng cùng một tập hợp các bước
để sắp xếp một nửa trái, như tôi có thể nửa bên phải.
Và quả thực, một lần nữa, và một lần nữa.
Vì vậy, bằng cách này hay khác, và chúng tôi sẽ sớm thấy điều này, sự kỳ diệu của sắp xếp hợp nhất
được nhúng vào trong đó rất thức dòng, việc sáp nhập hai nửa được sắp xếp.
Và điều đó có vẻ khá trực quan.
Bạn lấy hai nửa, và bạn, bằng cách nào đó, kết hợp chúng lại với nhau,
và chúng ta sẽ thấy điều này cụ thể trong một khoảnh khắc.
>> Nhưng đây là một thuật toán hoàn chỉnh.
Và chúng ta hãy xem chính xác lý do tại sao.
Cũng giả sử rằng chúng ta đang đưa ra những giống tám yếu tố ở đây trên màn hình, một
thông qua tám, nhưng chúng nhằm dường như ngẫu nhiên.
Và mục tiêu trước mắt là để sắp xếp các yếu tố này.
Vâng làm thế nào tôi có thể đi về làm việc đó bằng cách sử dụng, một lần nữa,
hợp nhất phân loại, theo giả này?
Và một lần nữa, làm biến đổi màu sắc này trong tâm trí của bạn, chỉ trong một khoảnh khắc.
Trường hợp đầu tiên là khá tầm thường, nếu nó nhỏ hơn 2,
chỉ cần trả lại, không có việc phải làm.
Vì vậy, thực sự đó chỉ là ba các bước để thực sự giữ trong tâm trí.
Một lần nữa, và một lần nữa, tôi sẽ muốn có
để sắp xếp một nửa trái, sắp xếp một nửa bên phải,
và sau đó một lần họ hai nửa đều được sắp xếp,
Tôi muốn kết hợp chúng lại với nhau vào một danh sách được sắp xếp.
Vì vậy, giữ cho rằng trong tâm trí.
>> Vì vậy, đây là danh sách ban đầu.
Hãy coi đây là một mảng, như chúng ta bắt đầu
trong tuần thứ hai, đó là một khối liên tục của bộ nhớ.
Trong trường hợp này, có chứa tám số, trở lại trở lại để trở lại.
Và bây giờ chúng ta áp dụng sắp xếp hợp nhất.
Vì vậy, lần đầu tiên tôi muốn sắp xếp nửa bên trái của danh sách này,
và chúng ta, do đó, tập trung vào 4, 8, 6, và 2.
>> Bây giờ làm thế nào để tôi đi về sắp xếp một danh sách các kích thước 4?
Vâng tôi phải bây giờ xem xét sắp xếp bên trái của một nửa trái.
Một lần nữa, chúng ta hãy quay lại với chỉ một khoảnh khắc.
Nếu giả là điều này, và tôi cho tám yếu tố,
8 rõ ràng là lớn hơn hơn hoặc bằng 2.
Vì vậy, với những trường hợp đầu tiên không áp dụng.
Vì vậy, để sắp xếp tám yếu tố, tôi lần đầu tiên sắp xếp một nửa trái của các yếu tố,
sau đó tôi sắp xếp một nửa bên phải, sau đó tôi hợp nhất hai nửa được sắp xếp, mỗi kích thước 4.
ĐƯỢC.
>> Nhưng nếu bạn vừa nói với tôi, sắp xếp các nửa bên trái, mà bây giờ có kích thước 4,
làm thế nào để sắp xếp các nửa còn lại?
Vâng, nếu tôi có một đầu vào của bốn yếu tố,
Lần đầu tiên tôi sắp xếp bên trái hai, sau đó quyền hai,
và sau đó tôi kết hợp chúng lại với nhau.
Vì vậy, một lần nữa, nó sẽ trở thành một chút của một tâm uốn trò chơi ở đây,
bởi vì bạn, loại, phải nhớ bạn đang ở đâu trong câu chuyện,
nhưng vào cuối ngày, đưa ra bất kỳ số lượng các yếu tố,
đầu tiên bạn muốn sắp xếp nửa bên trái, sau đó nửa bên phải,
sau đó kết hợp chúng lại với nhau.
Hãy bắt đầu làm chính xác điều đó.
Dưới đây là các đầu vào của tám yếu tố.
Bây giờ chúng tôi đang tìm kiếm một nửa trái ở đây.
Làm thế nào để sắp xếp bốn yếu tố?
Cũng lần đầu tiên tôi sắp xếp một nửa còn lại.
Bây giờ làm thế nào để sắp xếp các nửa còn lại?
Vâng tôi đã được trao hai yếu tố.
Vì vậy, hãy sắp xếp hai yếu tố này.
2 là lớn hơn hoặc bằng 2, tất nhiên.
Vì vậy, trường hợp đầu tiên mà không áp dụng.
>> Vì vậy, bây giờ tôi phải sắp xếp bên trái một nửa của hai yếu tố này.
Nửa bên trái, tất nhiên, chỉ 4 là.
Vậy làm thế nào để sắp xếp một danh sách của một phần tử?
Vâng bây giờ, mà trường hợp cơ sở đặc biệt lên hàng đầu, do đó, để nói chuyện, được áp dụng.
1 là ít hơn 2, và tôi danh sách thực sự có kích thước 1 là.
Vì vậy, tôi chỉ trả lại.
Tôi không làm bất cứ điều gì.
Và quả thực, nhìn vào những gì tôi đã thực hiện, 4 đã được sắp xếp.
Giống như tôi đã phần nào thành công ở đây.
>> Bây giờ có vẻ ngu ngốc yêu cầu bồi thường, nhưng đó là sự thật.
4 là một danh sách có kích thước 1.
Nó đã được sắp xếp.
Đó là một nửa trái.
Bây giờ tôi sắp xếp một nửa bên phải.
Đầu vào của tôi là một yếu tố, 8 tương tự, đã được sắp xếp.
Ngu ngốc, quá, nhưng một lần nữa, nguyên tắc cơ bản này
sẽ cho phép chúng ta bây giờ xây dựng trên đầu trang này thành công.
4 sắp xếp, 8 được sắp xếp, bây giờ bước cuối cùng là gì?
Vì vậy, bước thứ ba và cuối cùng, bất kỳ Hiện bạn đang sắp xếp một danh sách, thu hồi,
là để hợp nhất hai nửa, bên trái và bên phải.
Vì vậy, chúng ta hãy làm chính xác điều đó.
Nửa bên trái của tôi là, tất nhiên, 4.
Nửa bên phải của tôi là 8.
>> Vì vậy, hãy làm điều này.
Đầu tiên tôi sẽ phân bổ một số bộ nhớ bổ sung,
rằng tôi sẽ đại diện ở đây, như chỉ là một mảng thứ cấp,
đó là đủ lớn để phù hợp này.
Nhưng bạn có thể tưởng tượng được mở rộng rằng hình chữ nhật toàn bộ chiều dài,
nếu chúng ta cần nhiều hơn sau này.
Làm thế nào để tôi mất 4 và 8, và hợp nhất hai danh sách có kích thước 1 với nhau?
Cũng ở đây, khá đơn giản.
4 đến trước, sau đó đến 8.
Bởi vì nếu tôi muốn sắp xếp nửa bên trái, sau đó nửa bên phải,
và sau đó hợp nhất hai nửa với nhau, trong thứ tự sắp xếp,
4 đến trước, sau đó đến 8.
>> Vì vậy, chúng tôi dường như có tiến bộ, thậm chí mặc dù tôi đã không thực hiện bất kỳ công việc thực tế.
Nhưng hãy nhớ rằng chúng ta ở đâu trong câu chuyện.
Chúng tôi ban đầu mất tám yếu tố.
Chúng tôi sắp xếp một nửa trái, đó là 4.
Sau đó, chúng tôi sắp xếp một nửa trái của một nửa trái, đó là 2.
Và ở đây chúng tôi đi.
Chúng tôi đang thực hiện với bước đó.
>> Vì vậy, nếu chúng ta đã sắp xếp các còn lại một nửa số 2, bây giờ chúng tôi
phải sắp xếp một nửa bên phải của 2.
Vì vậy, nửa bên phải của 2 hai giá trị ở đây, 6 và 2.
Vì vậy, bây giờ chúng ta có một đầu vào kích thước 2, và sắp xếp lại một nửa, và sau đó
nửa bên phải, và sau đó kết hợp chúng lại với nhau.
Vâng làm thế nào để sắp xếp một danh sách các kích thước 1, có chứa chỉ số 6?
Tôi đã thực hiện.
Danh sách đó có kích thước 1 được sắp xếp.
>> Làm thế nào để sắp xếp một danh sách kích thước 1, cái gọi là một nửa bên phải.
Vâng nó cũng đã được sắp xếp.
Số 2 là một mình.
Vì vậy, bây giờ tôi có hai nửa, bên trái và Đúng vậy, tôi cần phải hợp nhất chúng lại với nhau.
Hãy để tôi cung cấp cho bản thân mình một số không gian thêm.
Và đặt 2 trong đó, sau đó 6 trong đó, do đó
phân loại danh sách đó, trái và phải, và sáp nhập nó với nhau, cuối cùng.
Vì vậy, tôi đang ở trong hình dạng tốt hơn một chút.
Tôi làm không phải, bởi vì rõ ràng 4, 8, 2, 6 không phải là sự sắp đặt cuối cùng mà tôi muốn.
Nhưng bây giờ tôi có hai danh sách kích thước 2, mà có cả hai, tương ứng, được sắp xếp.
Vì vậy, bây giờ nếu bạn tua lại trong tâm trí của bạn mắt, đâu đó lại cho chúng tôi?
Tôi bắt đầu với tám yếu tố, sau đó tôi đẽo nó xuống một nửa trái của 4,
sau đó nửa bên trái là 2, và sau đó nửa bên phải của 2,
Tôi đã hoàn thành, do đó, phân loại trái một nửa số 2, và nửa bên phải của 2,
do đó, bước thứ ba và cuối cùng là những gì ở đây?
Tôi phải kết hợp với nhau hai danh sách kích thước 2.
Vì vậy, chúng ta hãy đi trước.
Và trên màn hình ở đây, cung cấp cho tôi một số bộ nhớ bổ sung,
mặc dù về mặt kỹ thuật, nhận thấy rằng tôi đã có một bó toàn bộ các không gian trống lên đầu
có.
Nếu tôi muốn đặc biệt không gian hiệu quả khôn ngoan,
Tôi chỉ có thể bắt đầu di chuyển các yếu tố qua lại, trên và dưới.
Nhưng chỉ cho hình ảnh rõ nét, Tôi sẽ đặt nó xuống bên dưới,
để giữ cho mọi thứ tốt đẹp và sạch sẽ.
>> Vì vậy, tôi đã có hai danh sách kích thước 2.
Danh sách đầu tiên có 4 và 8.
Danh sách thứ hai có 2 và 6.
Hãy kết hợp những cùng trong thứ tự sắp xếp.
2, tất nhiên, đến trước, sau đó 4, sau đó 6, sau đó 8.
Và bây giờ chúng ta dường như nhận được một nơi nào đó thú vị.
Nửa bây giờ tôi đã sắp xếp của liệt, và tình cờ, đó là
tất cả các số chẵn, nhưng đó là, thực sự, chỉ là một sự trùng hợp.
Và bây giờ tôi đã sắp xếp bên trái một nửa, vì vậy mà nó là 2, 4, 6, và 8.
Không có gì là không theo thứ tự.
Mà cảm thấy như tiến độ.
>> Bây giờ nó cảm thấy như tôi đã được nói chuyện mãi mãi bây giờ,
vì vậy những gì vẫn còn để được nhìn thấy nếu điều này Thuật toán là, thực sự, hiệu quả hơn.
Nhưng chúng ta đang trải qua nó siêu có phương pháp.
Một máy tính, tất nhiên, sẽ làm điều đó như thế.
Vì vậy, nơi là chúng tôi?
Chúng tôi bắt đầu với tám yếu tố.
Tôi sắp xếp một nửa trái của 4.
Tôi dường như được thực hiện với điều đó.
Vì vậy, bây giờ các bước tiếp theo là sắp xếp một nửa bên phải của 4.
Và phần này chúng ta có thể đi thông qua nhiều hơn một chút
nhanh chóng, mặc dù bạn chào đón để tua lại hoặc tạm dừng, chỉ
nghĩ qua nó ở tốc độ của riêng của bạn, nhưng những gì
chúng tôi có bây giờ là một cơ hội để làm các thuật toán chính xác cùng trên bốn
số khác nhau.
>> Vì vậy, chúng ta hãy đi trước, và tập trung vào nửa bên phải, mà chúng tôi đang ở đây.
Nửa trái mà nửa bên phải, và bây giờ
nửa bên trái của trái một nửa số đó một nửa bên phải,
và làm thế nào để sắp xếp một danh sách các kích thước 1 chỉ chứa các số 1?
Nó đã được thực hiện.
Làm thế nào để tôi làm điều tương tự cho một danh sách có kích thước 1 chỉ chứa 7?
Nó đã được thực hiện.
Bước thứ ba hiệp này sau đó được kết hợp hai yếu tố này
vào một danh sách mới có kích thước 2, 1 và 7.
Không có vẻ đã làm tất cả công việc thú vị mà nhiều.
Hãy xem những gì sẽ xảy ra tiếp theo.
Tôi chỉ cần sắp xếp một nửa bên trái của nửa bên phải của đầu vào ban đầu của tôi.
Bây giờ chúng ta hãy sắp xếp đúng các một nửa, trong đó có 5 và 3.
Chúng ta hãy nhìn lại bên trái một nửa, sắp xếp, nửa bên phải, sắp xếp,
và kết hợp hai với nhau, vào một số không gian bổ sung,
3 đến trước, sau đó đến 5.
Và vì vậy bây giờ, chúng tôi đã sắp xếp các nửa bên trái của nửa bên phải
của vấn đề ban đầu, và nửa bên phải của nửa bên phải
của vấn đề ban đầu.
Bước thứ ba và cuối cùng là gì?
Cũng kết hợp hai nửa lại với nhau.
Vì vậy, hãy để tôi có được bản thân mình một số thêm không gian, nhưng, một lần nữa, tôi
có thể được sử dụng mà không gian lên top tùng.
Nhưng chúng tôi sẽ tiếp tục nó đơn giản trực quan.
Hãy để tôi kết hợp trong doanh nghiệp 1, và sau đó 3, và sau đó 5, và sau đó 7.
Qua đó để lại cho tôi bây giờ với nửa bên phải của vấn đề gốc
đó là hoàn toàn được sắp xếp.
>> Vì vậy, những gì còn lại?
Tôi cảm thấy như tôi luôn nói sự những điều tương tự một lần nữa, và một lần nữa,
nhưng đó là phản xạ của thực tế mà chúng ta đang sử dụng đệ quy.
Quá trình sử dụng một Thuật toán một lần nữa, và một lần nữa,
trên tập con nhỏ hơn của các vấn đề ban đầu.
Vì vậy, bây giờ tôi đã sắp xếp một trái một nửa của vấn đề ban đầu.
Tôi có một nửa được sắp xếp đúng của vấn đề ban đầu.
Bước thứ ba và cuối cùng là gì?
Oh, đó là sáp nhập.
Vì vậy, hãy làm điều đó.
Hãy phân bổ một số bổ sung bộ nhớ, nhưng thần của tôi, chúng tôi
có thể đặt nó ở bất cứ đâu bây giờ.
Chúng tôi có rất nhiều không gian có sẵn cho chúng tôi, nhưng chúng tôi sẽ giữ nó đơn giản.
Thay vì đi lại và ra với bộ nhớ ban đầu của chúng tôi,
chúng ta hãy làm điều đó thị xuống dưới đây,
để hoàn tất việc sáp nhập nửa bên trái và nửa bên phải.
>> Vì vậy, bằng việc sáp nhập, những gì tôi cần phải làm gì?
Tôi muốn sử dụng yếu tố theo thứ tự.
Vì vậy, nhìn vào nửa trái, Tôi thấy số đầu tiên là 2.
Tôi nhìn vào nửa bên phải, Tôi thấy số đầu tiên
là 1, như vậy rõ ràng mà số làm tôi muốn nhổ ra,
và đưa lên đầu tiên trong danh sách cuối cùng của tôi?
Tất nhiên, 1.
Bây giờ tôi muốn hỏi rằng cùng một câu hỏi.
Trên một nửa trái, tôi đã vẫn có số lượng 2.
Trên nửa bên phải, Tôi đã có số lượng 3.
Mà một trong những tôi muốn để lựa chọn?
Tất nhiên, số 2 và bây giờ thấy các ứng cử viên
4 trên bên trái, 3 ở bên phải.
Hãy, tất nhiên, chọn 3.
Bây giờ các ứng cử viên trên 4 bên trái, 5 bên phải.
Chúng tôi, tất nhiên, chọn 4.
6 trên bên trái, 5 bên phải.
Chúng tôi, tất nhiên, chọn 5.
6 trên bên trái, 7 bên phải.
Chúng tôi lựa chọn 6, và sau đó chúng tôi chọn 7, và sau đó chúng tôi chọn 8.
Thì đấy.
>> Vì vậy, một số lượng lớn các từ ngữ sau, chúng tôi đã sắp xếp danh sách này trong tám yếu tố
vào một danh sách của một đến tám, đó là tăng theo mỗi bước đi,
nhưng bao nhiêu thời gian đã làm nó đưa chúng ta để làm điều đó.
Vâng, tôi đã cố tình điều đặt ra những bức tranh
ở đây, để chúng ta có thể loại thấy hay đánh giá cao các bộ phận
trong chinh phục đó đang diễn ra.
>> Thật vậy, nếu bạn nhìn lại sự trỗi dậy, Tôi đã để lại tất cả các đường chấm
trong giữ chỗ, bạn có thể, loại, xem, theo thứ tự ngược,
nếu bạn loại nhìn lại lịch sử bây giờ, danh sách ban đầu của tôi
là, tất nhiên, có kích thước 8.
Và sau đó trước đây, tôi đã đối phó với hai danh sách kích thước 4,
và sau đó bốn danh sách kích thước 2, và sau đó tám danh sách có kích thước 1.
>> Vì vậy, những gì thực hiện điều này, loại, nhắc nhở bạn về?
Vâng, thực sự, bất kỳ các thuật toán chúng tôi đã
nhìn vậy, đến nay, nơi chúng tôi chia và phân chia, và phân chia,
tiếp tục có điều một lần nữa, và một lần nữa, kết quả trong ý tưởng chung này.
Và do đó, có một cái gì đó logarit xảy ra ở đây.
Và nó không hoàn toàn log của n, nhưng có một thành phần logarit
những gì chúng ta vừa làm.
>> Bây giờ hãy xem xét làm thế nào mà là thực sự.
Vì vậy, đăng nhập của n, một lần nữa là một thời gian chạy tuyệt vời,
khi chúng tôi đã làm một cái gì đó như tìm kiếm nhị phân, cũng như bây giờ chúng ta gọi nó,
các chiến lược chia và chinh phục qua đó, chúng tôi thấy Mike Smith.
Bây giờ về mặt kỹ thuật.
Đó là log cơ số 2 của n, thậm chí mặc dù trong hầu hết các lớp học toán,
10 thường là các cơ sở mà bạn giả định.
Nhưng các nhà khoa học máy tính hầu như luôn luôn suy nghĩ và nói về cơ sở 2,
vì vậy chúng tôi thường chỉ nói log của n, thay vì log cơ số 2 của n,
nhưng chúng một cách chính xác và cùng trong thế giới của máy tính
khoa học, và là một sang một bên, có một yếu tố không đổi
Sự khác biệt giữa hai người, vì vậy nó Moot anyway, vì lý do chính thức hơn.
>> Nhưng bây giờ, những gì chúng tôi quan tâm về là ví dụ này.
Vì vậy, chúng ta không chứng minh bằng ví dụ, nhưng tại ít nhất là sử dụng một ví dụ về những con số
ở bàn tay như một kiểm tra sự tỉnh táo, nếu bạn sẽ.
Vì vậy, trước đây công thức là cơ sở log 2 của n, nhưng là những gì n trong trường hợp này.
Tôi đã có con số n ban đầu, hoặc 8 của số lượng ban đầu cụ thể.
Bây giờ nó được một chút trong khi, nhưng tôi khá
chắc chắn rằng bản ghi cơ sở 2 giá trị 8 là 3,
và quả thật, những gì là tốt đẹp về điều đó rằng 3 là chính xác số lần
mà bạn có thể chia một danh sách chiều dài 8 một lần nữa, và một lần nữa,
và một lần nữa, cho đến khi bạn đang trái với danh sách các chỉ 1 kích thước.
Phải không?
8 đi đến 4, đi vào 2, đi đến 1, và đó là
phản ánh chính xác điều đó hình ảnh, chúng tôi chỉ vừa mới đây.
Vì vậy, một chút tỉnh táo kiểm tra khi đến nơi logarit được thực sự tham gia.
>> Vì vậy, bây giờ, những gì người khác đang tham gia ở đây? n.
Vì vậy, nhận thấy rằng mỗi thời gian tôi chia danh sách,
mặc dù trong thứ tự ngược lại trong lịch sử ở đây, tôi vẫn đang làm điều n.
Đó là biện pháp sáp nhập đòi hỏi Tôi chạm vào mỗi một trong số các con số,
để trượt nó vào vị trí thích hợp của nó.
Vì vậy, mặc dù chiều cao của này sơ đồ có kích thước log n của n hoặc 3,
Cụ thể, nói cách khác, Tôi đã làm ba sư đoàn ở đây.
Bao nhiêu công việc tôi làm theo chiều ngang cùng biểu đồ này mỗi lần?
>> Vâng, tôi đã làm n bước làm việc, bởi vì nếu tôi đã
có bốn yếu tố và bốn yếu tố, và tôi cần phải hợp nhất chúng lại với nhau.
Tôi cần phải đi qua bốn và bốn,
cuối cùng để hợp nhất chúng trở thành tám yếu tố.
Nếu ngược lại tôi đã có tám ngón tay ở đây, mà tôi thì không, và tám
fingers-- sorry-- Nếu tôi đã có bốn ngón tay trên đây,
mà tôi làm, bốn ngón tay ở đây, mà tôi làm,
thì đó là cùng Ví dụ như trước đây, nếu tôi làm
có tám ngón tay mặc dù trong Tổng cộng, mà tôi có thể, loại, làm.
Tôi chính xác có thể làm ở đây, sau đó tôi có thể chắc chắn
hợp nhất tất cả các danh sách này có kích thước 1 với nhau.
Nhưng tôi chắc chắn phải nhìn tại mỗi phần tử đúng một lần.
Vì vậy, chiều cao của quá trình này là log n, chiều rộng của quá trình này, có thể nói,
là n, vì vậy những gì chúng ta dường như có, cuối cùng, là
một thời gian chạy của kích thước n lần log n.
>> Nói cách khác, chúng ta chia danh sách, log n lần,
nhưng mỗi lần chúng tôi đã làm điều đó, chúng tôi đã có chạm vào mỗi một trong những yếu tố
để hợp nhất chúng tất cả cùng nhau, mà
được n bước, vì vậy chúng tôi có n lần log n, hoặc như một nhà khoa học máy tính sẽ nói,
tiệm cận, mà sẽ là từ lớn
để mô tả trên bị ràng buộc vào một thời gian chạy,
chúng tôi đang chạy trong một o lớn các log n thời gian, do đó, để nói chuyện.
>> Bây giờ điều này là quan trọng, bởi vì nhớ lại những gì lần chạy là
với bong bóng sắp xếp, và lựa chọn sắp xếp, và sắp xếp chèn,
và thậm chí một vài người khác đang tồn tại, n bình phương là nơi mà chúng tôi đang ở.
Và bạn có thể, loại, thấy điều này ở đây.
Nếu n bình phương rõ ràng là n lần n, nhưng ở đây chúng tôi có n lần log n,
và chúng ta đã biết từ tuần bằng không, mà log n, logarit,
là tốt hơn so với một cái gì đó tuyến tính.
Sau khi tất cả, nhớ lại những hình ảnh với màu đỏ và màu vàng
và các đường màu xanh lá cây mà chúng tôi đã thu hút, các dòng logarit xanh là thấp hơn nhiều.
Và do đó, tốt hơn nhiều và nhanh hơn hơn so với các dòng màu vàng và đỏ trực tiếp,
n lần đăng nhập n là, thực sự, tốt hơn hơn n lần n, hoặc n bình phương.
>> Vì vậy, chúng tôi dường như có xác định một thuật toán hợp nhất
loại chạy trong nhiều thời gian nhanh hơn, và quả thật,
đó là lý do tại sao, hồi đầu tuần này, khi chúng ta thấy rằng cuộc thi giữa bong bóng
phân loại, sắp xếp chọn, và hợp nhất sắp xếp, hợp nhất phân loại thực sự, thực sự chiến thắng.
Và quả thực, chúng tôi thậm chí còn không chờ đợi cho bong bóng sắp xếp và lựa chọn loại
kêt thuc.
>> Bây giờ chúng ta hãy một pass khác lúc này, từ một hơi hơn
quan điểm chính thức, chỉ trong trường hợp, điều này tạo ra tiếng vang tốt hơn
hơn so với cuộc thảo luận cấp cao hơn.
Vì vậy, đây là thuật toán nữa.
Hãy tự hỏi mình, những gì thời gian chạy
là các thuật toán này bước khác nhau?
Chúng ta hãy chia nó thành người đầu tiên trường hợp và trường hợp thứ hai.
IF và ELSE Trong trường hợp IF, NẾU n là nhỏ hơn 2, chỉ cần trả lại.
Cảm thấy như thời gian liên tục.
Đó là, loại, giống như hai bước, NẾU n là nhỏ hơn 2, sau đó quay trở lại.
Nhưng như chúng tôi đã nói hôm thứ Hai, thời gian liên tục, hoặc lớn o 1,
có thể được hai bước, ba bước, thậm chí 1.000 bước.
Điều quan trọng là nó một hằng số của các bước.
Vì vậy, màu vàng đánh dấu giả ở đây chạy trong, chúng tôi sẽ gọi nó,
thời gian liên tục.
Vì vậy, nhiều chính thức, và chúng ta sẽ đối với: này
sẽ là mức độ mà chúng ta chính thức hóa quyền này now-- T n,
thời gian chạy của một vấn đề mà phải mất n somethings như đầu vào,
bằng lớn o của một, NẾU n là ít hơn 2.
Vì vậy, nó có điều kiện về điều đó.
Vì vậy, để được rõ ràng, IF n là ít hơn 2, chúng tôi có một danh sách rất ngắn, sau đó
thời gian chạy, T n, trong đó n là 1 hoặc 0, trong trường hợp này rất cụ thể,
nó chỉ sẽ là thời gian liên tục.
Nó sẽ mất một bước, hai bước, bất cứ điều gì.
Đó là một số cố định của các bước.
>> Vì vậy, phần ngon ngọt chắc chắn phải có trong các trường hợp khác trong mã giả.
Các trường hợp ELSE.
Sắp xếp một nửa bên trái của các yếu tố, sắp xếp đúng một nửa của các nguyên tố, hợp nhất hai nửa được sắp xếp.
Không mỗi người trong những bước đi trong bao lâu?
Vâng, nếu chạy thời gian để sắp xếp n phần tử
là, chúng ta hãy gọi nó rất quát, T n,
sau đó phân loại trái nửa các nguyên tố
là, loại, giống như nói rằng, T của n khi chia cho 2,
và tương tự như phân loại nửa bên phải của các nguyên tố là, loại, giống như nói rằng,
T n chia 2, và sau đó sáp nhập hai nửa được sắp xếp.
Vâng, nếu tôi đã có một số số phần tử ở đây,
như bốn, và một số số các yếu tố ở đây, giống như bốn,
và tôi phải hợp nhất mỗi trong bốn trong, và mỗi bốn năm, một
sau khi khác, do đó cuối cùng tôi có tám yếu tố.
Nó cảm thấy như đó là lớn o n bậc?
Nếu tôi đã có n ngón tay và mỗi chúng phải được sáp nhập vào vị trí,
đó là giống như một bước n.
>> Vì vậy, thực sự formulaically, chúng ta có thể thể hiện điều này,
mặc dù là một chút đáng sợ lúc đầu Trong nháy mắt, nhưng nó là cái gì
mà bắt chính xác logic.
Thời gian chạy, T n, IF n là lớn hơn hoặc bằng 2.
Trong trường hợp này, các trường hợp ELSE, là T của n chia 2, cộng với T của N chia hết cho 2,
cộng lớn o n, một số số tuyến tính của các bước,
có lẽ chính xác n, có thể 2 lần n, nhưng đó là khoảng, thứ tự của n.
Vì vậy, điều đó cũng là cách chúng ta có thể thể hiện điều này formulaically.
Bây giờ bạn sẽ không biết điều này trừ khi bạn đã ghi nó trong tâm trí của bạn,
hoặc nhìn nó trong các trở lại của một cuốn sách giáo khoa, mà
có thể có một chút cheat sheet ở cuối,
nhưng điều này là, thực sự, sẽ cho chúng ta một o n log n lớn,
bởi vì việc lặp lại bạn nhìn thấy ở đây trên màn hình,
nếu bạn thực sự đã làm nó ra, với một số lượng vô hạn các ví dụ,
hoặc bạn đã làm nó formulaically, bạn sẽ thấy rằng điều này, bởi vì công thức này
chính nó là đệ quy, với t của n trên một cái gì đó ở bên phải,
và t trong n qua bên trái, điều này có thể thực sự được thể hiện, cuối cùng,
đi như là lớn của n log n.
Nếu không thuyết phục, đó là tốt cho bây giờ, chỉ cần
mất trên đức tin, mà đó là, thực sự, những gì tái phát dẫn đến,
nhưng đây chỉ là một chút của một Phương pháp toán học để tìm kiếm
tại thời gian chạy của sắp xếp hợp nhất dựa trên giả của nó một mình.
>> Bây giờ chúng ta hãy xem một chút của một tạm nghỉ từ tất cả điều đó,
và có một cái nhìn tại một một số cựu thượng nghị sĩ, người
có thể nhìn một chút quen thuộc, người ngồi xuống với Eric của Google
Schmidt, một số thời gian trước đây, cho một cuộc phỏng vấn trên sân khấu, trước mặt cả một bó
người, nói chuyện cuối cùng về một chủ đề, đó là khá quen thuộc.
Hãy nhìn xem.
>> ERIC Schmidt: Bây giờ Thượng nghị sĩ, bạn đang ở đây tại Google,
và tôi thích suy nghĩ của các tổng thống như một cuộc phỏng vấn việc làm.
Bây giờ thật khó để có được một công việc làm chủ tịch.
TỔNG THỐNG OBAMA: Đúng vậy.
ERIC Schmidt: Và bạn sẽ làm [Không nghe thấy] bây giờ.
Nó cũng khó để có được một công việc tại Google.
TỔNG THỐNG OBAMA: Đúng vậy.
>> ERIC Schmidt: Chúng tôi có câu hỏi, và chúng tôi đặt câu hỏi các ứng cử viên của chúng tôi,
và điều này là từ Larry Schwimmer.
>> TỔNG THỐNG OBAMA: OK.
>> ERIC Schmidt: Cái gì?
Bạn có nghĩ rằng tôi đang đùa đấy à?
Nó ở ngay đây.
Cách hiệu quả nhất để là gì sắp xếp một số nguyên triệu 32 bit?
>> TỔNG THỐNG OBAMA: Well--
ERIC Schmidt: Đôi khi, có lẽ tôi xin lỗi, maybe--
TỔNG THỐNG OBAMA: Không, không, không, không, không, tôi think--
ERIC Schmidt: Đó không phải là it--
TỔNG THỐNG OBAMA: Tôi nghĩ, tôi nghĩ rằng các bong bóng
loại sẽ là con đường sai để đi.
ERIC Schmidt: Thôi nào.
Ai nói với anh điều này?
ĐƯỢC.
Tôi đã làm không phải là khoa học máy tính on--
>> TỔNG THỐNG OBAMA: Chúng tôi đã có điệp viên của chúng tôi trong đó.
GIÁO SƯ: Tất cả các quyền.
Hãy để lại phía sau chúng tôi bây giờ thế giới lý thuyết của thuật toán
trong phân tích tiệm cận của chúng, và trở về một số chủ đề
từ tuần không và một, và khởi động để loại bỏ một số bánh xe đào tạo,
nếu bạn sẽ.
Vì vậy mà bạn thực sự hiểu cuối cùng từ mặt đất lên, có chuyện gì
xảy ra dưới mui xe, khi bạn viết, biên dịch và thực thi chương trình.
Nhớ lại đặc biệt, rằng đây là Chương trình C đầu tiên chúng ta nhìn vào,
một chương trình đơn giản kinh điển của các loại, tương đối nói,
trong đó, nó in, Hello World.
Và nhớ lại rằng tôi đã nói, quá trình rằng mã nguồn đi qua
là chính xác này.
Bạn lấy mã nguồn của bạn, vượt qua nó thông qua một trình biên dịch, như Clang,
và đi ra mã đối tượng, mà có thể trông như thế này, số không và những người thân
rằng CPU của máy tính, trung tâm đơn vị xử lý hoặc não,
cuối cùng hiểu.
>> Nó chỉ ra rằng đó là một bit của một sự đơn giản,
rằng chúng tôi bây giờ trong một vị trí để trêu chọc nhau
để hiểu những gì đang thực sự được xảy ra dưới mui xe
mỗi khi bạn chạy Clang, hay rộng hơn,
mỗi khi bạn thực hiện một chương trình, Hãy sử dụng và CF 50 IDE.
Đặc biệt, công cụ như này là lần đầu tiên tạo ra,
khi lần đầu tiên bạn biên dịch chương trình của bạn.
Nói cách khác, khi bạn lấy mã nguồn của bạn
và biên dịch nó, những gì đầu tiên được xuất ra bởi Clang
là một cái gì đó gọi là mã lắp ráp.
Và trên thực tế, nó trông giống hệt như thế này.
>> Tôi chạy một lệnh tại dòng lệnh trước đó.
Hello.c Clang vốn dash s, và điều này tạo ra một tập tin
cho tôi gọi hello.s, trong số đó là chính xác
những nội dung này, và nhiều hơn một chút ở trên và một chút dưới hơn,
nhưng tôi đã đặt juiciest thông tin ở đây trên màn hình.
Và nếu bạn nhìn kỹ, bạn sẽ thấy ít nhất là một vài từ khóa quen thuộc.
Chúng tôi có chính ở đầu trang.
Chúng tôi đã printf xuống ở giữa.
Và chúng tôi cũng có hello world backslash n trong dấu ngoặc kép xuống dưới đây.
>> Và mọi thứ khác ở đây là hướng dẫn mức rất thấp
rằng CPU của máy tính hiểu được.
Hướng dẫn CPU di chuyển bộ nhớ xung quanh, rằng dây tải từ bộ nhớ,
và cuối cùng, in thứ trên màn hình.
Bây giờ những gì xảy ra mặc dù sau mã lắp ráp này được tạo ra?
Cuối cùng, bạn làm gì, thực sự, vẫn tạo ra mã đối tượng.
Nhưng những bước mà có thực sự được diễn ra dưới mui xe
nhìn nhiều hơn một chút như thế này.
Mã nguồn trở thành mã lắp ráp, mà sau đó trở thành mã đối tượng,
và những lời tác ở đây là rằng, khi bạn biên dịch mã nguồn của bạn,
đi ra mã lắp ráp, và sau đó khi bạn lắp ráp mã lắp ráp của bạn,
đi ra mã đối tượng.
>> Bây giờ Clang là siêu tinh vi, giống như rất nhiều các trình biên dịch,
và nó hiện tất cả các bước với nhau, và nó không nhất thiết
đầu ra bất kỳ trung gian tập tin mà bạn thậm chí có thể nhìn thấy.
Nó chỉ biên dịch mọi thứ, đó là thuật ngữ chung
mô tả toàn bộ quá trình này.
Nhưng nếu bạn thực sự muốn để được cụ thể, có
rất nhiều nhiều đang xảy ra ở đó là tốt.
>> Nhưng chúng ta hãy cũng xem xét bây giờ mà thậm chí mà chương trình siêu đơn giản, hello.c,
được gọi là một hàm.
Nó được gọi là printf.
Nhưng tôi đã không viết printf, thực sự, mà đi kèm với c, vậy để nói chuyện.
Đó là một hồi chức năng mà khai báo trong io.h tiêu chuẩn, mà
là một tập tin tiêu đề, mà là một chủ đề chúng ta sẽ thực sự
lặn xuống sâu hơn trước khi dài.
Nhưng một tập tin tiêu đề là thường đi kèm
bởi một tập tin mã, tập tin mã nguồn, vì vậy giống như có tồn tại io.h. chuẩn
>> Đôi khi trước đây, một người nào đó, hoặc ai đó, cũng đã viết
một tập tin gọi là io.c tiêu chuẩn, trong đó các định nghĩa thực tế,
hoặc triển khai của printf, và chùm của các chức năng khác,
đang thực sự được viết.
Vì vậy, cho rằng, nếu chúng ta xem xét việc có đây trên bên trái, hello.c, rằng khi
biên soạn, cho chúng ta hello.s, ngay cả khi Clang không bận tâm tiết kiệm ở một nơi
chúng ta có thể nhìn thấy nó, và rằng mã lắp ráp được lắp ráp thành hello.o, mà
là, thực sự, tên mặc định đưa ra bất cứ khi nào bạn biên dịch mã nguồn
mã vào mã đối tượng, nhưng không phải là hoàn toàn sẵn sàng để thực hiện nó chưa,
bởi vì một bước đã xảy ra, và có
đã xảy ra trong vài quá khứ tuần, có lẽ unbeknownst cho bạn.
>> Cụ thể ở đâu đó trong CS50 IDE, và điều này,
quá, sẽ là một chút của một sự đơn giản trong một khoảnh khắc,
có, hoặc là có một thời gian, một tập tin gọi là io.c tiêu chuẩn,
rằng ai đó biên dịch vào io.s tiêu chuẩn hoặc tương đương,
rằng một người nào đó sau đó lắp ráp vào io.o tiêu chuẩn,
hoặc nó biến ra thành một tập hơi khác nhau
định dạng mà có thể có một khác nhau tập tin mở rộng hoàn toàn,
nhưng trong lý thuyết và khái niệm, chính xác những bước đã phải xảy ra trong một số hình thức.
Mà là để nói, mà bây giờ khi tôi đang viết một chương trình,
hello.c, mà chỉ nói rằng, xin chào thế giới, và tôi đang sử dụng mã của người khác
như printf, mà là một lần khi một thời gian, trong một tập tin gọi là io.c tiêu chuẩn,
sau đó bằng cách nào đó tôi đã để mất tôi mã đối tượng, số không và những người thân của tôi,
và đối tượng của người đó code, hay số không và những người thân,
và bằng cách nào đó liên kết chúng lại với nhau thành một tập tin cuối cùng, gọi là hello, mà
có tất cả các số không và những người từ chức năng chính của tôi,
và tất cả các số không và những người cho printf.
>> Và quả thực, đó là quá trình cuối cùng gọi là, liên kết mã đối tượng của bạn.
Đầu ra của mà là một tập tin thực thi.
Vì vậy, trong công bằng, tại cuối ngày, không có gì
đã thay đổi kể từ tuần thứ nhất, khi chúng ta đầu tiên bắt đầu biên soạn chương trình.
Thật vậy, tất cả những điều này đã được xảy ra dưới mui xe,
nhưng bây giờ chúng tôi đang ở trong một vị trí nơi chúng ta có thể thực sự
trêu chọc nhau những bước khác nhau.
Và quả thực, ở cuối trong ngày, chúng tôi vẫn
trái với số không và những người thân, mà thực sự là một segue tuyệt vời bây giờ
đến một khả năng của C, mà chúng tôi đã không có để tận dụng khả năng nhất
cho đến nay, được gọi là toán tử trên bit.
Nói cách khác, cho đến nay, bất cứ lúc nào chúng tôi đã xử lý dữ liệu trong C hoặc các biến trong C,
chúng tôi đã có những thứ như chars và phao nổi và các ins
và chờ đợi và đôi và như thế, nhưng tất cả những người đang có ít nhất tám bit.
Chúng tôi chưa bao giờ được thể thao tác bit riêng lẻ,
mặc dù một chút cá nhân, chúng tôi biết, có thể đại diện cho một 0 và 1.
Bây giờ nó chỉ ra rằng trong C, bạn có thể có được quyền truy cập vào các bit riêng lẻ,
nếu bạn biết cú pháp, mà để có được ở họ.
>> Vì vậy, chúng ta hãy có một cái nhìn tại toán tử trên bit.
Vì vậy, trong hình ở đây là một vài biểu tượng chúng tôi, loại, loại, nhìn thấy trước.
Tôi nhìn thấy một dấu, một dọc thanh, và một số người khác là tốt,
và nhớ lại rằng dấu và ký hiệu là một cái gì đó chúng ta đã thấy trước đây.
Các toán tử logic AND, nơi bạn có hai trong số chúng lại với nhau, hoặc logic OR
điều hành, nơi bạn có hai thanh dọc.
Toán tử trên bit, mà chúng tôi sẽ thấy hoạt động trên bit riêng lẻ,
chỉ cần sử dụng một ký hiệu duy nhất, một đơn thanh dọc, các biểu tượng caret
đến tiếp theo, ít dấu ngã, và sau đó còn lại
khung bên trái khung, hoặc khung bên phải khung bên phải.
Mỗi trong số này có ý nghĩa khác nhau.
>> Trong thực tế, chúng ta hãy có một cái nhìn.
Hãy đi học cũ ngày hôm nay, và sử dụng một màn hình cảm ứng từ năm qua,
được biết đến như một bảng trắng.
Và bảng trắng này sẽ cho phép chúng tôi
để bày tỏ một số biểu tượng khá đơn giản, hay đúng hơn là một số công thức khá đơn giản,
rằng chúng ta có thể sau đó cuối cùng đòn bẩy, để
để truy cập cá nhân bit trong một chương trình C.
Nói cách khác, chúng ta hãy làm điều này.
Hãy nói chuyện đầu tiên cho một lúc về ký hiệu,
đó là các phép toán AND điều hành.
Nói cách khác, đây là một nhà điều hành, cho phép
tôi phải có một biến trái tay thường, và một biến cánh tay phải,
hoặc một giá trị cá nhân, rằng nếu chúng VÀ chúng lại với nhau, mang lại cho tôi một kết quả cuối cùng.
Vì vậy, tôi có nghĩa là gì?
Nếu trong một chương trình, bạn có một biến mà các cửa hàng một trong những giá trị,
hoặc chúng ta hãy giữ cho nó đơn giản, và chỉ viết ra số không và những cá nhân,
đây là cách các nhà điều hành dấu và làm việc.
0 ký hiệu 0 được sẽ bằng 0.
Bây giờ tại sao vậy?
>> Nó rất giống với Biểu thức Boolean,
mà chúng ta đã thảo luận tới.
Nếu bạn nghĩ rằng sau khi tất cả, 0 là sai, 0 là sai, sai và sai
là, như chúng ta đã thảo luận một cách hợp lý, cũng sai.
Vì vậy, chúng tôi nhận được 0 ở đây là tốt.
Nếu bạn lấy dấu và 0 1, cũng vậy, quá,
sẽ là 0, vì cho điều này biểu hiện bên tay trái là đúng hay 1,
nó sẽ cần phải là sự thật và đúng sự thật.
Nhưng ở đây chúng tôi có sai và sự thật, hoặc 0 và 1.
Bây giờ một lần nữa, nếu chúng ta có 1 ký hiệu 0, điều đó cũng sẽ là 0,
và nếu chúng tôi có 1 ký hiệu 1, cuối cùng chúng ta có một chút 1.
Vì vậy, nói cách khác, chúng ta không làm bất cứ điều gì thú vị với nhà điều hành này
chỉ được nêu ra, nhà điều hành ký hiệu này.
Đó là bitwise AND.
Nhưng đó là những thành phần thông qua đó chúng ta có thể làm
những điều thú vị, như chúng ta sẽ sớm thấy.
>> Bây giờ chúng ta hãy nhìn vào chỉ duy nhất thanh dọc ở đây ở bên phải.
Nếu tôi có một bit 0 và tôi Hoặc nó có, các phép toán
OR, một bit 0, đó là sẽ cho tôi 0.
Nếu tôi mất một chút và OR nó với 0 một bit 1, sau đó tôi sẽ có được 1.
Và trên thực tế, chỉ cần cho sự rõ ràng, để tôi đi lại,
để thanh dọc của tôi không được nhầm lẫn với 1.
Hãy để tôi viết lại tất cả 1 của tôi là nhiều hơn một chút
rõ ràng, vì vậy mà chúng tôi tới xem, nếu tôi đã 1 OR 0, đó sẽ là một 1,
và nếu tôi có một 1 OR 1 mà, quá, là có được một 1.
Vì vậy, bạn có thể nhìn thấy một cách logic rằng OR điều hành hoạt động rất khác nhau.
Điều này mang lại cho tôi 0 OR 0 mang lại cho tôi 0, nhưng mọi sự kết hợp khác mang lại cho tôi 1.
Vì vậy, miễn là tôi có một 1 trong công thức, kết quả là có được 1.
>> Ngược lại với AND điều hành, các ký hiệu,
chỉ khi tôi có hai 1 trong việc phương trình, tôi thực sự có được một 1 ra.
Bây giờ có một vài khác nhà khai thác là tốt.
Một trong số đó là một chút liên quan hơn.
Vì vậy, hãy để tôi đi trước và xóa này để giải phóng một số không gian.
Và chúng ta hãy nhìn vào biểu tượng dấu nháy, chỉ trong một khoảnh khắc.
Đây thường là một nhân vật bạn có thể gõ
trên bàn phím của bạn phím Shift và giữ sau đó một trong những con số trên đỉnh Hoa Kỳ của bạn
bàn phím.
>> Vì vậy, đây là độc quyền OR, độc quyền OR.
Vì vậy, chúng tôi chỉ thấy các nhà điều hành OR.
Đây là độc quyền OR.
Những gì là sự khác biệt thực sự?
Vâng chúng ta hãy nhìn vào công thức, và sử dụng như là thành phần cuối cùng.
0 0 XOR.
Tôi sẽ nói luôn là 0.
Đó là định nghĩa của XOR.
0 XOR 1 là có được 1.
1 XOR 0 là có được 1, và 1 XOR 1 là có được?
Sai rồi?
Hoặc đúng?
Tôi không biết.
0.
Bây giờ những gì đang xảy ra ở đây?
Cũng suy nghĩ về tên của nhà điều hành này.
Exclusive OR, vì vậy, khi tên, loại, cho thấy,
câu trả lời là chỉ có được 1 nếu đầu vào là độc quyền,
độc quyền khác nhau.
Vì vậy, đây là những yếu tố đầu vào tương tự, do đầu ra là 0.
Dưới đây là những yếu tố đầu vào tương tự, do đầu ra là 0.
Sau đây là các kết quả đầu ra là khác nhau, họ là độc quyền, và như vậy đầu ra là 1.
Vì vậy, nó rất giống với AND, nó rất giống,
hay đúng hơn là nó rất giống với OR, nhưng chỉ trong một cách độc quyền.
Điều này không còn là 1, bởi vì chúng tôi có hai 1 của,
và không độc quyền, chỉ một trong số họ.
Được rồi.
Còn những người khác?
Vâng dấu ngã, trong khi đó, thực sự đẹp và đơn giản, may mắn.
Và đây là một unary điều hành, có nghĩa là
nó được áp dụng để chỉ có một đầu vào, một toán hạng, vậy để nói chuyện.
Không để một bên trái và một bên phải.
Nói cách khác, nếu bạn có dấu ngã của 0, câu trả lời sẽ là ngược lại.
Và nếu bạn có dấu ngã của 1, Câu trả lời sẽ có điều ngược lại.
Vì vậy, các nhà điều hành là dấu ngã một cách phủ một chút,
hoặc lật một chút từ 0-1, hoặc 1-0.
>> Và đó lại cho chúng ta cuối cùng chỉ với hai nhà khai thác cuối cùng,
cái gọi là sự chuyển đổi trái, và cái gọi là dịch phải.
Chúng ta hãy xem làm thế nào những người làm việc.
Các nhà điều hành dịch trái, bằng văn bản với hai dấu ngoặc nhọn như thế,
hoạt động như sau.
Nếu đầu vào của tôi, hoặc toán hạng của tôi, bên trái điều hành dịch chuyển là khá đơn giản chỉ là 1.
Và sau đó tôi nói với các máy tính để lại sự thay đổi đó 1, nói bảy bậc,
kết quả là như thể tôi đi mà 1, và di chuyển nó
bảy bậc so với trái, và theo mặc định,
chúng ta giả sử rằng các không gian bên phải
sẽ được đệm bằng số không.
Nói cách khác, 1 trái shift 7 sẽ để cung cấp cho tôi rằng 1, tiếp theo là 1, 2, 3,
4, 5, 6, 7 số không.
Vì vậy, trong một cách, nó cho phép bạn mất một số nhỏ như 1,
và rõ ràng làm cho nó nhiều nhiều, lớn hơn nhiều trong cách này,
nhưng chúng tôi đang thực sự đi vào xem cách tiếp cận thông minh hơn cho nó
thay vào đó, là tốt,
>> Được rồi.
Đó là nó cho tuần ba.
Chúng ta sẽ thấy bạn thời gian tới.
Đây là CS50.
>> [MUSIC CHƠI]
>> SPEAKER 1: Ông được tại các bữa ăn nhẹ bar ăn một fudge sundae nóng.
Ông đã có tất cả trên khuôn mặt của mình.
Anh ta mặc rằng sô cô la như một bộ râu
SPEAKER 2: Bạn đang làm gì?
SPEAKER 3: Hmmm?
Cái gì?
>> SPEAKER 2: Bạn chỉ cần suy thoái kép?
Bạn đôi nhúng chip.
SPEAKER 3: Xin lỗi.
SPEAKER 2: Bạn nhúng chip, bạn cắn một miếng, và bạn nhúng một lần nữa.
SPEAKER 3:
SPEAKER 2: Vì vậy, đó là giống như đặt toàn bộ miệng bên phải của bạn trong dip.
Tiếp theo thời gian bạn có một chip, chỉ nhúng nó một lần, và kết thúc nó.
>> SPEAKER 3: Bạn biết những gì, Dan?
Bạn nhúng theo cách mà bạn muốn nhúng.
Tôi sẽ nhúng các cách mà tôi muốn để nhúng.