[Powered by Google Translate] [Phần 3 - thoải mái hơn] [Rob Bowden - Đại học Harvard] 

[Đây là CS50. - CS50.TV] 

Vì vậy, câu hỏi đầu tiên là lạ worded. GDB cho phép bạn "gỡ lỗi" một chương trình, nhưng cụ thể hơn, những gì hiện nó cho bạn làm gì? Tôi sẽ trả lời rằng một trong, và tôi không biết những gì là chính xác mong đợi, vì vậy tôi đoán đó là một cái gì đó dọc theo dòng của nó cho phép bạn từng bước đi bộ thông qua chương trình, tương tác với nó, các biến thay đổi, làm tất cả những điều này - về cơ bản hoàn toàn kiểm soát thực hiện của một chương trình và kiểm tra bất kỳ phần nào của việc thực hiện của chương trình. Vì vậy, những tính năng cho phép bạn gỡ lỗi thứ. Okay. Tại sao tìm kiếm nhị phân yêu cầu rằng một mảng được sắp xếp? Ai muốn trả lời điều đó? [Sinh viên] Bởi vì nó không làm việc nếu nó không được sắp xếp. >> Yeah. [Cười] Nếu nó không được sắp xếp, sau đó nó không thể tách nó ra và biết rằng tất cả mọi thứ bên trái là ít hơn và tất cả mọi thứ ở bên phải lớn hơn giá trị trung bình. Vì vậy, nó cần phải được sắp xếp. Okay. Tại sao là bong bóng sắp xếp trong O n bình phương? Có ai đầu tiên muốn cung cấp cho một cái nhìn tổng quan cao cấp rất nhanh chóng những bong bóng sắp xếp? [Sinh viên] Về cơ bản bạn đi qua mỗi phần tử và bạn kiểm tra các yếu tố đầu tiên. Nếu họ đang ra khỏi nơi bạn trao đổi chúng, sau đó bạn kiểm tra các yếu tố tiếp theo và như vậy. Khi bạn đến cuối, sau đó bạn biết rằng các phần tử lớn nhất được đặt ở cuối, do đó, bạn bỏ qua điều đó một sau đó bạn tiếp tục đi qua, và mỗi lần bạn phải kiểm tra một trong những yếu tố ít hơn cho đến khi bạn không có thay đổi. >> Yeah. Nó được gọi là bong bóng sắp xếp bởi vì nếu bạn lật mảng trên mặt của nó vì vậy nó lên và xuống, dọc, sau đó các giá trị lớn sẽ chìm xuống đáy và các giá trị nhỏ sẽ bong bóng lên đến đỉnh. Đó là làm thế nào nó có tên của nó. Và yeah, bạn chỉ cần đi qua. Bạn tiếp tục đi qua mảng, trao đổi các giá trị lớn hơn để có được các giá trị lớn nhất để phía dưới. 

Tại sao nó O n bình phương? Đầu tiên, không ai muốn nói lý do tại sao nó là O của n bình phương? [Sinh viên] Bởi vì cho mỗi lần chạy nó đi n lần. Bạn chỉ có thể chắc chắn rằng bạn đã thực hiện các yếu tố lớn nhất tất cả các con đường xuống, sau đó bạn phải lặp lại rằng đối với nhiều yếu tố. >> Yeah. Vì vậy, giữ trong tâm trí O lớn có nghĩa là gì và những gì phương tiện Omega lớn. O lớn như trên ràng buộc về cách làm chậm nó thực sự có thể chạy. Vì vậy, bằng cách nói rằng O của n bình phương, nó không phải là O của n hoặc khác nó sẽ có thể chạy trong thời gian tuyến tính, nhưng nó là O của n cubed bởi vì nó được bao bọc bởi O n cubed. Nếu nó được bao bọc bởi O n bình phương, sau đó nó giáp còn bởi n cubed. Vì vậy, nó là n bình phương, và trong trường hợp tồi tệ nhất tuyệt đối không thể làm tốt hơn so với n bình phương, đó là lý do tại sao nó là O n bình phương. Vì vậy, để xem toán học nhỏ như thế nào đi ra để được n bình phương, nếu chúng ta có năm điều trong danh sách của chúng tôi, lần đầu tiên có bao nhiêu giao dịch hoán đổi chúng ta có thể có khả năng cần phải thực hiện để có được điều này? Hãy thực sự chỉ - Làm thế nào nhiều giao dịch hoán đổi chúng ta sẽ phải thực hiện trong thời gian đầu tiên của loại bong bóng thông qua các mảng? [Sinh viên] n - 1. >> Yeah. 

Nếu có 5 yếu tố, chúng ta sẽ cần phải thực hiện n - 1. Sau đó, một trong những thứ hai có bao nhiêu giao dịch hoán đổi chúng ta sẽ phải thực hiện? [Sinh viên] n - 2. >> Yeah. Và thứ ba sẽ là n - 3, và sau đó để thuận tiện tôi sẽ viết cuối cùng hai như sau đó chúng ta sẽ cần phải thực hiện 2 giao dịch hoán đổi và trao đổi 1. Tôi đoán là người cuối cùng có thể hoặc có thể không thực sự cần phải xảy ra. Nó là một trao đổi? Tôi không biết. Vì vậy đây là tổng số tiền giao dịch hoán đổi hoặc ít nhất là so sánh bạn có để làm. Thậm chí nếu bạn không trao đổi, bạn vẫn cần phải so sánh các giá trị. Vì vậy, có n - 1 so sánh trong lần chạy đầu tiên thông qua các mảng. Nếu bạn sắp xếp lại những điều này, chúng ta hãy thực sự làm cho sáu điều mọi thứ chồng lên độc đáo, và sau đó tôi sẽ làm 3, 2, 1. Vì vậy, chỉ cần sắp xếp lại số tiền này, chúng tôi muốn thấy chúng tôi làm cho bao nhiêu so sánh trong toàn bộ các thuật toán. Vì vậy, nếu chúng ta mang lại cho những kẻ ở đây, sau đó chúng tôi vẫn đang tổng hợp so sánh tuy nhiên nhiều người đã có. Nhưng nếu chúng ta tổng hợp những điều này và chúng tôi tổng hợp những điều này và chúng tôi tổng hợp các, nó vẫn là cùng một vấn đề. Chúng tôi chỉ tổng hợp những nhóm cụ thể. 

Vì vậy, bây giờ chúng tôi đang tổng hợp 3 n. Nó không phải chỉ là 3 của n. Nó luôn luôn sẽ là n / 2 n. Vì vậy, ở đây chúng tôi xảy ra để có 6. Nếu chúng ta có 10 điều, sau đó chúng ta có thể làm điều này nhóm cho 5 cặp khác nhau của sự vật và kết thúc với n + n + n + n + n. Vì vậy, bạn luôn luôn để có được n / 2 n, và do đó, điều này chúng tôi sẽ ghi nó ra bình phương / 2 n. Và do đó, mặc dù nó là yếu tố của một nửa, mà xảy ra để đi vào vì thực tế là thông qua mỗi lần lặp trên mảng, chúng tôi so sánh 1 ít vì vậy đó là làm thế nào chúng tôi nhận được hơn 2, nhưng nó vẫn còn n bình phương. Chúng tôi không quan tâm về các yếu tố liên tục của một nửa. Vì vậy, rất nhiều các công cụ O lớn như thế này dựa trên chỉ là loại việc sắp xếp của toán học, làm tiền số học và các công cụ loạt hình học, nhưng hầu hết trong số họ trong khóa học này là khá đơn giản. Okay. Tại sao chèn sắp xếp trong Omega của n? Omega có nghĩa là gì? Hai học sinh nói cùng một lúc - không thể hiểu] >> Vâng. Omega bạn có thể nghĩ là giới hạn thấp hơn. 

Vì vậy, không có vấn đề như thế nào hiệu quả chèn thuật toán sắp xếp của bạn, không phân biệt của danh sách là thông qua tại, nó luôn luôn phải so sánh ít nhất n vật hoặc nó có để lặp lại những thứ n. Tại sao vậy? [Sinh viên] Bởi vì nếu danh sách đã được sắp xếp, sau đó thông qua phiên đầu tiên bạn chỉ có thể đảm bảo rằng các phần tử đầu tiên là ít nhất, và lặp thứ hai, bạn chỉ có thể đảm bảo đầu tiên hai là bởi vì bạn không biết rằng phần còn lại của danh sách được sắp xếp. >> Yeah. Nếu bạn vượt qua trong một danh sách được sắp xếp hoàn toàn, ít nhất bạn phải đi qua tất cả các yếu tố để thấy rằng không có gì cần phải được di chuyển xung quanh. Vì vậy, đi qua danh sách và nói oh, điều này đã được sắp xếp, nó không thể cho bạn biết nó được sắp xếp cho đến khi bạn kiểm tra từng phần tử để thấy rằng họ đang có trong thứ tự sắp xếp. Vì vậy, các ràng buộc về sắp xếp chèn là Omega của n. Trường hợp xấu nhất là những gì thời gian chạy của hợp nhất loại, trường hợp xấu nhất là O lớn một lần nữa? Vì vậy, trong trường hợp kịch bản tồi tệ nhất, hợp nhất loại chạy như thế nào? [Sinh viên] N log n. >> Yeah. Nhanh nhất các thuật toán phân loại chung là n log n. Bạn không thể làm tốt hơn. 

Có những trường hợp đặc biệt, và nếu chúng ta có ngày hôm nay - thời gian nhưng chúng tôi có thể won't chúng ta có thể thấy một mà không tốt hơn so với n log n. Tuy nhiên, trong trường hợp chung, bạn không thể làm tốt hơn so với n log n. Và hợp nhất các loại sẽ xảy ra là một trong những bạn nên biết cho khóa học này là n log n. Và vì vậy chúng tôi thực sự sẽ được thực hiện mà ngày hôm nay. Và cuối cùng, không quá ba câu, công tác loại lựa chọn như thế nào? Không ai muốn trả lời, và tôi sẽ đếm các câu của bạn bởi vì nếu bạn đi trên 3 - Có ai nhớ loại lựa chọn? Lựa chọn loại thường là khá dễ dàng để nhớ từ tên. Bạn chỉ cần lặp qua mảng tìm thấy bất cứ điều gì có giá trị lớn nhất hoặc nhỏ nhất - để bất cứ điều gì bạn đang phân loại. Vì vậy, hãy nói rằng chúng tôi đang phân loại từ nhỏ nhất đến lớn nhất. Bạn lặp qua mảng, tìm kiếm bất cứ điều gì các yếu tố tối thiểu, chọn nó và sau đó chỉ cần trao đổi nó bất cứ điều gì ở nơi đầu tiên. Và sau đó trên đèo thứ hai trên mảng, tìm kiếm các yếu tố tối thiểu một lần nữa, chọn nó và sau đó trao đổi nó với những gì ở vị trí thứ hai. Vì vậy, chúng tôi chỉ chọn và lựa chọn các giá trị tối thiểu và chèn chúng vào mặt trước của mảng cho đến khi nó được sắp xếp. Câu hỏi về điều đó? 

Đây chắc chắn xuất hiện trong các hình thức mà bạn phải điền vào khi bạn đang trình pset. Đó là về cơ bản các câu trả lời cho những người. Được rồi, vì vậy bây giờ mã hóa vấn đề. Tôi đã gửi qua email - bất cứ ai không nhận được rằng email? Okay. Tôi đã gửi qua email không gian mà chúng ta sẽ được sử dụng, và nếu bạn nhấn chuột vào tên của tôi - vì vậy tôi nghĩ rằng tôi sẽ được ở phía dưới vì r ngược - nhưng nếu bạn nhấn chuột vào tên của tôi, bạn sẽ thấy 2 phiên bản. Phiên bản 1 sẽ được tôi đã sao chép và dán mã vào không gian cho việc tìm kiếm, bạn sẽ phải thực hiện. Và sửa đổi 2 sẽ được điều sắp xếp mà chúng ta thực hiện sau đó. Vì vậy, bạn có thể bấm vào sửa đổi của tôi 1 và làm việc từ đó. Và bây giờ chúng tôi muốn thực hiện tìm kiếm nhị phân. 

Có ai muốn chỉ cần cung cấp cho một lời giải thích giả cấp cao của những gì chúng ta sẽ phải làm cho tìm kiếm? Yeah. [Sinh viên] Bạn chỉ mất giữa của mảng và xem những gì bạn đang tìm kiếm là ít hơn hoặc nhiều hơn thế. Và nếu nó ít hơn, bạn đi đến một nửa đó là ít, và nếu nó nhiều hơn, bạn đi đến một nửa sau đó là nhiều và bạn lặp lại cho đến khi bạn chỉ nhận được một điều. [Bowden] Yeah. Chú ý rằng số mảng của chúng tôi đã được sắp xếp, và do đó có nghĩa rằng chúng ta có thể tận dụng lợi thế đó và chúng tôi lần đầu tiên có thể kiểm tra, okay, tôi đang tìm cho số 50. Vì vậy, tôi có thể đi vào giữa. Trung là khó để xác định khi nó là một số thậm chí của vật, nhưng chúng ta hãy chỉ nói rằng chúng ta sẽ luôn luôn cắt ngắn để giữa. Vì vậy, ở đây chúng tôi có 8 điều, do đó, giữa sẽ là 16. Tôi đang tìm cho 50, do đó, 50 là lớn hơn 16. Vì vậy, bây giờ tôi về cơ bản có thể xử lý mảng của tôi như những yếu tố này. Tôi có thể vứt bỏ tất cả mọi thứ từ trên 16. Bây giờ mảng của tôi chỉ là 4 yếu tố này, tôi nhắc lại. Vì vậy, sau đó tôi muốn tìm giữa một lần nữa, đó là sẽ là 42. 42 là ít hơn 50, vì vậy tôi có thể vứt bỏ hai yếu tố này. Đây là mảng còn lại của mình. Tôi sẽ tìm thấy giữa một lần nữa. Tôi đoán 50 là một ví dụ xấu bởi vì tôi đã luôn luôn ném đi mọi thứ bên trái, nhưng bằng biện pháp tương tự, nếu tôi đang tìm kiếm một cái gì đó và nó ít hơn so với các yếu tố tôi hiện đang xem xét, sau đó tôi sẽ vứt bỏ tất cả mọi thứ bên phải. Vì vậy, bây giờ chúng tôi cần phải thực hiện điều đó. Chú ý rằng chúng ta cần phải vượt qua trong kích thước. Chúng tôi cũng có thể không cần phải cứng mã kích thước. Vì vậy, nếu chúng tôi nhận được thoát khỏi đó # xác định Okay. Làm thế nào tôi có thể độc đáo tìm ra những gì kích thước của mảng số hiện nay là? 

Làm thế nào nhiều yếu tố trong mảng số? [Sinh viên] số, khung, chiều dài? [Bowden] không tồn tại trong C. Cần chiều dài. Mảng không có tài sản, do đó, không có tài sản dài của mảng mà chỉ cần sẽ cung cấp cho bạn lâu dài tuy nhiên nó sẽ xảy ra. [Sinh viên] Xem nó có bao nhiêu bộ nhớ và phân chia bao nhiêu - >> Vâng. Vì vậy, làm thế nào chúng ta có thể xem nó có bao nhiêu bộ nhớ? >> [Sinh viên] sizeof. >> Yeah, sizeof. Sizeof là các nhà điều hành đó là sẽ trở lại kích thước của các mảng số. Và đó sẽ là các số nguyên tuy nhiên nhiều lần kích thước của một số nguyên vì đó là bao nhiêu bộ nhớ nó thực sự chiếm. Vì vậy, nếu tôi muốn có số thứ trong mảng, sau đó tôi sẽ muốn chia bởi kích thước của một số nguyên. Okay. Vì vậy, cho phép tôi vượt qua kích thước ở đây. Tại sao tôi cần phải vượt qua kích thước ở tất cả? Tại sao tôi không thể chỉ cần làm ở đây int size = sizeof (haystack) / sizeof (int)? Tại sao điều này không làm việc? [Sinh viên] Nó không phải là một biến toàn cầu. Bowden] Haystack tồn tại và chúng ta đang đi qua với số lượng như haystack, và đây là loại tiên báo về những gì sắp tới. Yeah. [Sinh viên] Haystack chỉ là tham chiếu đến nó, vì vậy nó sẽ trở lại tham khảo đó là lớn như thế nào. Yeah. Tôi nghi ngờ trong bài giảng mà bạn đã nhìn thấy ngăn xếp nhưng thực sự, phải không? Chúng tôi đã chỉ nói về nó. Vì vậy, ngăn xếp là nơi mà tất cả các biến của bạn sẽ được lưu trữ. 

Bất kỳ bộ nhớ đó là phân bổ cho các biến địa phương trong ngăn xếp, và chức năng cho từng không gian riêng của mình trên stack, stack frame của nó là những gì nó được gọi là. Vì vậy, chính có stack frame của nó, và bên trong của nó sẽ tồn tại mảng này số, và nó sẽ là sizeof kích cỡ (số). Nó sẽ có kích thước của các số chia cho kích thước của các yếu tố, nhưng đó là tất cả cuộc sống trong khung chính stack. Khi chúng tôi gọi là tìm kiếm, tìm kiếm được khung stack riêng của mình, không gian riêng của mình để lưu trữ tất cả các biến địa phương của mình. Tuy nhiên, lập luận này - vì vậy haystack không phải là một bản sao của toàn bộ mảng này. Chúng tôi không vượt qua trong toàn bộ mảng như là một bản sao vào tìm kiếm. Nó chỉ cần vượt qua một tham chiếu đến mảng đó. Vì vậy, tìm kiếm có thể truy cập vào những con số này thông qua tham chiếu này. Nó vẫn còn truy cập vào những điều mà sống bên trong của khung chính stack, nhưng về cơ bản, khi chúng tôi nhận được cho con trỏ, mà nên được sớm, đây là những gì con trỏ. Con trỏ chỉ là tài liệu tham khảo cho những thứ, và bạn có thể sử dụng con trỏ để truy cập mọi thứ là trong khung stack những thứ khác. Vì vậy, dù các con số là địa phương chính, chúng tôi vẫn có thể truy cập nó thông qua con trỏ này. Nhưng kể từ khi nó chỉ là một con trỏ và nó chỉ là một tài liệu tham khảo, sizeof (haystack) chỉ trả về kích thước của các tài liệu tham khảo chính nó. Nó không trả lại kích thước của điều nó trỏ đến. Nó không trả lại kích thước thực tế của các số. Và do đó, điều này không phải là đi làm việc như chúng ta muốn nó. 

Câu hỏi về điều đó? Con trỏ sẽ được đi vào chi tiết nhiều hơn đáng kể đẫm máu trong tuần tới. Và đây là lý do tại sao rất nhiều những điều mà bạn biết, sự việc tìm kiếm nhiều nhất hoặc những thứ loại, họ đang gần như tất cả sẽ cần phải có kích thước thực tế của mảng, bởi vì trong C, chúng tôi không có ý tưởng những gì các kích thước của mảng. Bạn cần phải tự vượt qua nó. Và bạn có thể không tự vượt qua trong toàn bộ mảng bởi vì bạn chỉ cần đi qua các tài liệu tham khảo và nó không thể có được kích thước từ tài liệu tham khảo. Okay. Vì vậy, bây giờ chúng tôi muốn thực hiện những gì đã được giải thích trước. Bạn có thể làm việc trên nó trong một phút, và bạn không phải lo lắng về việc nhận được tất cả mọi thứ làm việc hoàn hảo 100%. Chỉ cần viết mã giả một nửa để làm thế nào bạn nghĩ rằng nó sẽ làm việc. Okay. Không cần phải hoàn toàn thực hiện với điều này. Nhưng không ai cảm thấy thoải mái với những gì họ có cho đến nay, giống như một cái gì đó, chúng ta có thể làm việc với nhau? Có ai muốn làm tình nguyện? Hoặc tôi sẽ chọn ngẫu nhiên. Nó không có được quyền bởi bất kỳ biện pháp nào, nhưng một cái gì đó chúng ta có thể sửa đổi vào một trạng thái làm việc. [Sinh viên] Chắc chắn rồi. >> Okay. Vì vậy, bạn có thể lưu các sửa đổi bằng cách nhấn vào biểu tượng Save ít. Bạn đang Ramya, phải không? >> [Sinh viên] Yeah. >> [Bowden] Okay. Vì vậy, bây giờ tôi có thể xem sửa đổi của bạn và tất cả mọi người có thể kéo lên sửa đổi. Và ở đây chúng tôi có - Được rồi. Vì vậy, Ramya đi với các giải pháp đệ quy, mà chắc chắn là một giải pháp hợp lệ. Có hai cách bạn có thể làm vấn đề này. Bạn có thể làm điều đó lặp đi lặp lại hoặc đệ quy. Hầu hết các vấn đề bạn gặp phải có thể được thực hiện đệ quy cũng có thể được thực hiện lặp đi lặp lại. Vì vậy, ở đây chúng tôi đã thực hiện nó đệ quy. 

Có ai đó muốn xác định những gì nó có nghĩa là để làm cho một hàm đệ quy? [Sinh viên] Khi bạn có một hàm gọi chính nó và sau đó gọi chính nó cho đến khi nó đi ra với đúng sự thật và đúng sự thật. >> Yeah. Một chức năng đệ quy chỉ là một chức năng mà tự gọi mình. Có ba điều lớn mà một hàm đệ quy phải có. Đầu tiên là rõ ràng, nó gọi chính nó. Thứ hai là trường hợp cơ sở. Vì vậy, tại một số điểm chức năng cần phải ngừng kêu gọi chính nó, và đó là trường hợp cơ sở. Vì vậy, ở đây chúng tôi biết rằng chúng tôi nên dừng lại, chúng ta nên từ bỏ tìm kiếm của chúng tôi khi bắt đầu bằng kết thúc và chúng ta sẽ đi qua đó có nghĩa là gì. Nhưng cuối cùng, điều cuối cùng mà quan trọng cho các chức năng đệ quy: các chức năng bằng cách nào đó phải tiếp cận trường hợp cơ sở. Cũng giống như nếu bạn không thực sự cập nhật bất cứ điều gì khi bạn thực hiện cuộc gọi thứ hai đệ quy, nếu bạn đang nghĩa đen chỉ kêu gọi các chức năng một lần nữa cùng với các đối số và không có biến toàn cầu đã thay đổi hoặc bất cứ điều gì, bạn sẽ không bao giờ đến trường hợp cơ sở, trong trường hợp đó là xấu. Nó sẽ là một đệ quy vô hạn và tràn một chồng. Nhưng ở đây chúng ta thấy rằng bản cập nhật đang diễn ra kể từ khi chúng tôi đang được cập nhật bắt đầu + end / 2, chúng tôi cập nhật các đối số kết thúc ở đây, chúng tôi cập nhật các đối số bắt đầu ở đây. Vì vậy, trong tất cả các cuộc gọi đệ quy, chúng tôi đang được cập nhật một cái gì đó. Okay. Bạn có muốn đi bộ chúng tôi thông qua các giải pháp của bạn? >> Chắc chắn rồi. Tôi đang sử dụng SearchHelp để mỗi khi tôi thực hiện cuộc gọi chức năng này Tôi có một khởi đầu, nơi tôi đang tìm kiếm trong mảng và kết thúc nơi tôi đang tìm các mảng. 

Tại mỗi bước mà nó nói nó là nhân tố trung, đó là bắt đầu + kết thúc / 2, là bằng những gì chúng tôi đang tìm kiếm? Và nếu được, sau đó chúng tôi tìm thấy nó, và tôi đoán được thông qua các cấp độ của đệ quy. Và nếu đó là không đúng sự thật, sau đó chúng tôi kiểm tra xem giá trị đó giữa của mảng là quá lớn, trong trường hợp đó chúng ta nhìn vào nửa bên trái của mảng bằng cách đi từ đầu đến chỉ số trung bình. Và nếu không chúng tôi làm nửa cuối. [Bowden] Okay. Nghe được đó. Được rồi, do một vài điều, và trên thực tế, đây là một điều rất cao cấp rằng bạn sẽ không bao giờ cần biết cho khóa học này, nhưng nó là sự thật. Chức năng đệ quy, bạn luôn nghe thấy rằng họ là một việc xấu bởi vì nếu bạn đệ quy gọi cho mình quá nhiều lần, bạn sẽ có được tràn stack vì, như tôi đã nói, tất cả các chức năng được khung stack riêng của mình. Vì vậy, mỗi cuộc gọi của chức năng đệ quy được khung stack riêng của mình. Vì vậy, nếu bạn thực hiện 1.000 cuộc gọi đệ quy, bạn nhận được 1.000 khung stack, và nhanh chóng dẫn đến khung stack và những thứ quá nhiều mà chỉ vỡ. Vì vậy, đó là lý do tại sao chức năng đệ quy nói chung là xấu. Nhưng có một tập hợp con tốt đẹp của các chức năng đệ quy được gọi là chức năng đệ quy đuôi, và điều này sẽ xảy ra là một ví dụ về một trong những nơi mà nếu trình biên dịch thông báo này và nó nên, tôi nghĩ rằng Clang nếu bạn vượt qua nó-O2 cờ sau đó nó sẽ thông báo này là đệ quy đuôi và làm cho những điều tốt đẹp. 

Nó sẽ sử dụng lại cùng một khung stack hơn và hơn nữa cho mỗi cuộc gọi đệ quy. Và như vậy kể từ khi bạn đang sử dụng cùng một stack frame, bạn không cần phải lo lắng về bao giờ ngăn xếp tràn, và cùng một lúc, như bạn nói, một khi bạn trở lại đúng, sau đó nó đã trở lại tất cả các khung stack và các cuộc gọi ngày 10 đến SearchHelp để quay trở lại lần thứ 9, đã trở lại 8. Vì vậy, mà không cần phải xảy ra khi các chức năng đệ quy đuôi. Và do đó, những gì làm cho chức năng đệ quy đuôi là thông báo cho bất kỳ cuộc gọi cho searchHelp các cuộc gọi đệ quy mà nó làm cho nó trở về. Vì vậy, trong cuộc gọi đầu tiên SearchHelp, chúng tôi ngay lập tức quay trở lại sai, ngay lập tức trở lại đúng, hoặc chúng tôi thực hiện cuộc gọi đệ quy để SearchHelp nơi những gì chúng tôi đang trở về là gì mà cuộc gọi đang trở lại. Và chúng ta không thể làm điều này nếu chúng ta đã làm một cái gì đó giống như int x = SearchHelp, return x * 2, chỉ là một số thay đổi ngẫu nhiên. 

Vì vậy, bây giờ gọi đệ quy, int x = SearchHelp gọi đệ quy, không còn là đệ quy đuôi bởi vì nó thực sự không phải trả lại trở lại trước một khung stack để cuộc gọi trước đến chức năng sau đó có thể làm một cái gì đó với giá trị trả về. Vì vậy, đây không phải là đệ quy đuôi, nhưng những gì chúng ta có trước đây là độc đáo đệ quy đuôi. Yeah. [Sinh viên] Nếu không phải là trường hợp cơ sở thứ hai được kiểm tra bởi vì có thể là một tình huống nơi mà khi bạn vượt qua các đối số bạn đã bắt đầu = kết thúc, nhưng họ là những giá trị kim. Các câu hỏi đã không thể chúng tôi chạy vào trường hợp cuối cùng là giá trị kim hoặc bắt đầu = kết thúc, một cách thích hợp, bắt đầu = kết thúc và bạn đã không thực sự kiểm tra giá trị cụ thể nào được nêu ra, sau đó bắt đầu + end / 2 là chỉ cần đi được cùng một giá trị. Nhưng chúng tôi đã quay trở lại sai lầm và chúng tôi không bao giờ thực sự kiểm tra các giá trị. Vì vậy, ít nhất, trong cuộc gọi đầu tiên, nếu kích thước là 0, sau đó chúng tôi muốn quay trở lại sai. Nhưng nếu kích thước là 1, sau đó bắt đầu được sẽ không kết thúc bằng, và ít nhất chúng ta sẽ kiểm tra một yếu tố. Nhưng tôi nghĩ rằng bạn là đúng trong đó chúng ta có thể kết thúc trong một trường hợp bắt đầu + end / 2, bắt đầu kết thúc lên được giống như là bắt đầu + kết thúc / 2, nhưng chúng tôi không bao giờ thực sự kiểm tra yếu tố đó. 

Vì vậy, nếu chúng tôi kiểm tra đầu tiên là yếu tố giữa các giá trị mà chúng ta đang tìm kiếm, sau đó chúng tôi có thể ngay lập tức trở lại đúng sự thật. Khác nếu chúng bằng nhau, sau đó không có điểm trong việc tiếp tục kể từ khi chúng tôi chỉ để cập nhật cho một trường hợp, nơi chúng tôi đang ở trên một mảng duy nhất phần tử. Nếu đó không phải là yếu tố duy nhất mà chúng ta đang tìm kiếm, sau đó tất cả mọi thứ là sai. Yeah. [Sinh viên] Cái này là kể từ khi kích thước thực sự là lớn hơn số phần tử trong mảng đã có bù đắp - >> tự như vậy, kích thước - [Sinh viên] nếu mảng là kích thước 0 thì SearchHelp sẽ thực sự kiểm tra đống cỏ khô từ 0 cuộc gọi đầu tiên. Mảng có kích thước 0, 0 - >> Vâng. Có một điều mà nó có thể là tốt. Hãy suy nghĩ. Vì vậy, nếu các mảng có 10 yếu tố và một trong những trung chúng ta sẽ kiểm tra là chỉ số 5, vì vậy chúng tôi đang kiểm tra 5, và hãy nói rằng giá trị nhỏ. Vì vậy, chúng tôi đang ném tất cả mọi thứ từ 5 trở đi. Vì vậy, bắt đầu + kết thúc / 2 là có được kết thúc mới của chúng tôi, Vì vậy, yeah, nó luôn luôn ở ngoài cuối của mảng. Nếu đó là một trường hợp nếu nó là chẵn hoặc lẻ, sau đó chúng tôi sẽ kiểm tra, nói rằng, 4, nhưng chúng tôi vẫn ném đi Vì vậy, yeah, cuối cùng là luôn luôn có được vượt quá thực tế của mảng. Vì vậy, các yếu tố mà chúng tôi đang tập trung vào, cuối cùng là luôn luôn có được một sau đó. Và như vậy nếu bắt đầu không bao giờ kết thúc bằng, chúng tôi đang trong một mảng có kích thước 0. 

Những điều khác tôi đã suy nghĩ là chúng tôi đang được cập nhật bắt đầu được bắt đầu + kết thúc / 2, vì vậy đây là trường hợp mà tôi đang gặp rắc rối với nơi bắt đầu + kết thúc / 2 là yếu tố chúng tôi đang kiểm tra. Hãy nói rằng chúng tôi đã có 10-phần tử mảng. Sao cũng được. Vì vậy, bắt đầu + kết thúc / 2 là có được một cái gì đó như thế này, và nếu đó không phải là giá trị, nói rằng chúng ta muốn cập nhật. Giá trị lớn, vì vậy chúng tôi muốn tìm một nửa của mảng này. Vì vậy, làm thế nào chúng tôi cập nhật bắt đầu, chúng tôi đang cập nhật bắt đầu đến nay là yếu tố này. Nhưng điều này vẫn có thể làm việc, hoặc ít nhất, bạn có thể làm bắt đầu + kết thúc / 2 + 1. [Sinh viên] Bạn không cần phải được bắt đầu + end không nghe được] >> Yeah. Chúng tôi đã kiểm tra yếu tố này và biết nó không phải là cái mà chúng ta đang tìm kiếm. Vì vậy, chúng ta không cần phải cập nhật bắt đầu được yếu tố này. Chúng tôi chỉ có thể bỏ qua nó và cập nhật bắt đầu được yếu tố này. Và có bao giờ trường hợp một, hãy nói, rằng đây là kết thúc, để sau đó bắt đầu sẽ được điều này, bắt đầu + end / 2 sẽ được điều này, bắt đầu + end - Vâng, tôi nghĩ rằng nó có thể kết thúc trong đệ quy vô hạn. Hãy nói rằng nó chỉ là một mảng của các kích thước 2 hoặc một mảng có kích thước 1. Tôi nghĩ rằng điều này sẽ làm việc. Vì vậy, hiện nay, bắt đầu là yếu tố đó và cuối cùng là 1 ngoài nó. Vì vậy, các yếu tố đó chúng ta sẽ kiểm tra là một trong những điều này, và sau đó khi chúng tôi cập nhật bắt đầu, chúng tôi đang cập nhật bắt đầu là 0 + 1/2, đó là sẽ kết thúc chúng tôi trở lại với yếu tố này bắt đầu. 

Vì vậy, chúng tôi đang kiểm tra các yếu tố tương tự hơn và hơn nữa. Vì vậy, đây là trường hợp tất cả các cuộc gọi đệ quy thực sự phải cập nhật một cái gì đó. Vì vậy, chúng ta cần phải làm bắt đầu + kết thúc / 2 + 1, hoặc người nào khác có một trường hợp chúng tôi không thực sự cập nhật bắt đầu. Mọi người đều nhìn thấy không? Okay. Có ai có câu hỏi về giải pháp này hay ý kiến ​​nào? Okay. Có ai có một giải pháp mà tất cả chúng ta có thể nhìn vào lặp đi lặp lại? Tất cả chúng ta làm điều đó đệ quy? Hoặc tôi cũng đoán nếu bạn mở cô, sau đó bạn có thể có ghi đè một trong những trang trước của bạn. Liệu nó sẽ tự động tiết kiệm? Tôi không tích cực. Có ai đã lặp đi lặp lại? Chúng tôi có thể đi bộ qua nó với nhau nếu không. Ý tưởng là có được như vậy. Lặp đi lặp lại giải pháp. Chúng tôi sẽ muốn về cơ bản làm cùng một ý tưởng mà chúng tôi muốn theo dõi kết thúc mới của mảng và bắt đầu mới của mảng và làm điều đó hơn và hơn. Và nếu những gì chúng tôi đang theo dõi như là bắt đầu và kết thúc bao giờ giao nhau, sau đó chúng tôi đã không tìm thấy nó và chúng ta có thể quay trở lại sai. Vì vậy, làm thế nào để làm điều đó? Bất cứ ai có đề xuất hoặc mã cho tôi để kéo lên? [Sinh viên] Làm một vòng lặp while. >> Yeah. Bạn sẽ muốn làm một vòng lặp. 

Bạn đã có mã tôi có thể kéo lên, hoặc những gì bạn đã đi để đề nghị? [Sinh viên] Tôi nghĩ vậy. >> Tất cả đúng. Điều này làm cho mọi việc dễ dàng hơn. Tên của bạn là gì? [Sinh viên] Lucas. Phiên bản 1. Okay. Thấp là những gì chúng ta gọi là bắt đầu trước khi. Lên không phải là hoàn toàn những gì chúng tôi gọi là cuối trước khi. Trên thực tế, cuối cùng là trong mảng. Đây là một yếu tố chúng ta nên xem xét. Quá thấp là 0, là kích thước của mảng - 1, và bây giờ chúng tôi đang vòng lặp, và chúng tôi đang kiểm tra - Tôi đoán bạn có thể đi bộ qua nó. Suy nghĩ của bạn là gì thông qua? Đi bộ chúng tôi thông qua mã của bạn. [Sinh viên] Chắc chắn rồi. Nhìn vào giá trị haystack ở giữa và so sánh nó với kim. Vì vậy, nếu nó lớn hơn kim của bạn, sau đó bạn muốn - oh, trên thực tế, mà nên ngược. Bạn sẽ muốn vứt bỏ nửa bên phải, và như vậy, mà nên là cách. [Bowden] Vì vậy, điều này nên được ít hơn? Đó có phải là những gì bạn nói? >> [Sinh viên] Yeah. [Bowden] Okay. Ít hơn. Vì vậy, nếu những gì chúng tôi đang tìm kiếm là nhỏ hơn so với những gì chúng ta muốn, sau đó yeah, chúng tôi muốn vứt bỏ nửa bên trái, có nghĩa là chúng tôi đang cập nhật tất cả mọi thứ chúng tôi đang xem xét bằng cách di chuyển thấp bên phải của mảng. Điều này có vẻ tốt. Tôi nghĩ rằng nó có cùng một vấn đề mà chúng tôi đã nói trước đó, nếu thấp là 0 và là 1, sau đó thấp + lên / 2 sẽ thiết lập được điều tương tự một lần nữa. 

Và ngay cả khi đó không phải là trường hợp, nó vẫn còn ở rất ít hiệu quả hơn chỉ cần vứt bỏ các yếu tố, chúng tôi chỉ nhìn mà chúng ta biết là sai. Quá thấp + lên / 2 + 1 - >> [sinh viên] Điều đó phải được theo cách khác. [Bowden] Hoặc này - 1 và một trong những khác là + 1. [Sinh viên] Và có phải là một đôi dấu bằng. >> [Bowden] Yeah. [Sinh viên] Yeah. Okay. Và cuối cùng, bây giờ mà chúng ta có 1 + 1 điều, là nó - nó có thể không bao giờ có thể thấp để kết thúc với một giá trị lớn hơn lên? Tôi nghĩ rằng cách duy nhất có thể xảy ra - nó có thể? >> [Sinh viên] Tôi không biết. Nhưng nếu nó được cắt ngắn và sau đó được trừ đi 1 và sau đó - >> Yeah. [Sinh viên] có thể sẽ được điều sai lầm. Tôi nghĩ rằng nó sẽ được tốt chỉ vì cho nó để kết thúc thấp hơn, họ sẽ có được bình đẳng, tôi nghĩ. Nhưng nếu chúng bằng nhau, sau đó chúng tôi sẽ không có thực hiện vòng lặp trong khi để bắt đầu với và chúng tôi sẽ trả lại giá trị. Vì vậy, tôi nghĩ rằng bây giờ chúng tôi đang tốt. Chú ý rằng mặc dù vấn đề này không còn là đệ quy, cùng một loại ý tưởng áp dụng, nơi chúng ta có thể xem cách này quá dễ dàng vay chính nó một giải pháp đệ quy bởi thực tế rằng chúng ta chỉ cần cập nhật các chỉ số hơn và hơn nữa, chúng tôi đang làm cho vấn đề nhỏ hơn và nhỏ hơn, chúng tôi đang tập trung vào một tập hợp con của mảng. [Sinh viên] Nếu thấp là 0, và lên là 1, cả hai đều sẽ là 0 + 1/2, mà sẽ đi đến 0, và sau đó sẽ là một trong + 1, một trong những sẽ là - 1. [Sinh viên] Chúng ta đang kiểm tra bình đẳng? Cũng giống như nếu một trong những trung lưu thực sự là kim? Chúng tôi không làm điều đó? Oh! Nếu it's - Vâng. Chúng ta không thể làm bài kiểm tra xuống ở đây bởi vì chúng ta hãy nói rằng giữa đầu tiên - [Sinh viên] Nó thực sự thích Không vứt ràng buộc. Vì vậy, nếu bạn quăng đi những ràng buộc, bạn phải kiểm tra xem nó đầu tiên hoặc bất cứ điều gì. Ah. Yeah. >> [Sinh viên] Yeah. Vì vậy, bây giờ chúng tôi đã vứt bỏ chúng tôi hiện đang nhìn, có nghĩa là bây giờ chúng ta cũng cần phải có nếu (haystack [(+ up) / 2] == kim), sau đó chúng ta có thể trở lại đúng sự thật. Và cho dù tôi đặt khác hoặc chỉ cần thiết nếu, nó có nghĩa là điều tương tự vì điều này sẽ đã trở lại đúng sự thật. Vì vậy, tôi sẽ đặt khác nếu, nhưng nó không quan trọng. 

Vì vậy, nếu người nào khác, khác, và đây là một điều phổ biến tôi làm mà ngay cả khi đó là trường hợp, nơi tất cả mọi thứ là tốt ở đây, như thấp không bao giờ có thể lớn hơn lên, nó không có giá trị lý luận về cho dù đó là sự thật. Vì vậy, bạn cũng có thể nói trong khi thấp là ít hơn hoặc bằng hoặc trong khi thấp là ít hơn do đó, nếu họ có bao giờ bằng hoặc thấp sẽ xảy ra để vượt lên, sau đó chúng ta có thể thoát ra khỏi vòng lặp này. Câu hỏi, bình luận? Okay. Điều này có vẻ tốt. Bây giờ chúng tôi muốn làm loại. Nếu chúng ta đi đến phiên bản thứ hai của tôi, chúng ta thấy những con số tương tự, nhưng bây giờ họ không còn theo thứ tự sắp xếp. Và chúng tôi muốn thực hiện loại bằng cách sử dụng bất kỳ thuật toán trong O n log n. Vì vậy, thuật toán nào bạn nghĩ rằng chúng ta nên thực hiện ở đây? >> [Sinh viên] Merge sắp xếp. [Bowden] Yeah. Hợp nhất sắp xếp là O (n log n), vì vậy đó là những gì chúng ta sẽ làm. Và vấn đề là có được khá tương tự, nó một cách dễ dàng vay chính nó đến một giải pháp đệ quy. Chúng tôi cũng có thể đến với một giải pháp lặp đi lặp lại nếu chúng ta muốn, nhưng đệ quy sẽ được dễ dàng hơn ở đây và chúng ta nên làm đệ quy. Tôi đoán chúng tôi sẽ đi bộ qua các loại hợp nhất đầu tiên, mặc dù là một đoạn video đáng yêu trên loại hợp nhất rồi. [Cười] Vì vậy, kết hợp loại có - Tôi đang lãng phí rất nhiều của bài viết này. Oh, chỉ có một trái. Vì vậy, hợp nhất. Oh, 1, 3, 5. Okay. Merge mất hai mảng riêng biệt. Riêng hai mảng đều được sắp xếp. Vì vậy, mảng này, 1, 3, 5, sắp xếp. Mảng này, 0, 2, 4, sắp xếp. Bây giờ những gì hợp nhất nên làm là kết hợp chúng thành một mảng duy nhất đó là chính nó được sắp xếp. Vì vậy, chúng tôi muốn một mảng có kích thước 6 có nghĩa là sẽ có những yếu tố bên trong của nó theo thứ tự sắp xếp. 

Và vì vậy chúng ta có thể tận dụng lợi thế của thực tế là hai mảng này đều được sắp xếp để làm điều này trong thời gian tuyến tính, tuyến tính thời gian có nghĩa là nếu mảng này là kích thước x và điều này là kích thước y, sau đó tổng số các thuật toán là O (x + y). Okay. Vì vậy, đề nghị. [Sinh viên] chúng ta có thể bắt đầu từ bên trái? Vì vậy, bạn sẽ đặt 0 xuống đầu tiên và sau đó số 1 và sau đó bạn vào 2. Vì vậy, nó là loại như bạn có một tab di chuyển sang bên phải. >> [Bowden] Yeah. Đối với cả hai của các mảng nếu chúng ta chỉ tập trung vào các yếu tố ngoài cùng bên trái. Bởi vì cả hai mảng được sắp xếp, chúng ta biết rằng 2 yếu tố này là những yếu tố nhỏ nhất trong mảng một trong hai. Vì vậy, điều đó có nghĩa là 1 của 2 yếu tố đó phải là phần tử nhỏ nhất trong mảng sáp nhập của chúng tôi. Nó chỉ như vậy sẽ xảy ra rằng nhỏ nhất là một trong những ngày đúng thời điểm này. Vì vậy, chúng ta hãy 0, chèn nó vào bên trái vì 0 là ít hơn 1, do đó, có 0, chèn nó vào vị trí đầu tiên của chúng tôi, và sau đó chúng tôi cập nhật này đến nay tập trung vào các yếu tố đầu tiên. Và bây giờ chúng tôi lặp lại. Vì vậy, bây giờ chúng ta so sánh 2 và 1. 1 là nhỏ hơn, do đó, chúng ta sẽ chèn 1. Chúng tôi cập nhật con trỏ để trỏ đến anh chàng này. Bây giờ chúng ta làm điều đó một lần nữa, do đó, 2. Điều này sẽ cập nhật, so sánh những 2, 3. Điều này cập nhật, sau đó 4 và 5. Vì vậy, đó là hợp nhất. 

Nó nên được khá rõ ràng rằng nó là tuyến tính thời gian kể từ khi chúng tôi chỉ đi qua mỗi phần tử một lần. Và đó là bước lớn nhất để thực hiện hợp nhất loại là làm điều này. Và nó không phải là khó. Một vài điều phải lo lắng về là chúng ta hãy nói rằng chúng tôi đã được sáp nhập 1, 2, 3, 4, 5, 6. Trong trường hợp này, chúng tôi kết thúc trong kịch bản này là một trong những sẽ nhỏ hơn, sau đó chúng tôi cập nhật con trỏ này, một trong những điều này sẽ nhỏ hơn, cập nhật, cái này thì nhỏ hơn, và bây giờ bạn có nhận ra khi bạn đã thực sự chạy ra khỏi các yếu tố để so sánh với. Từ khi chúng tôi đã được sử dụng toàn bộ mảng này, tất cả mọi thứ trong mảng này bây giờ chỉ cần đưa vào đây. Vì vậy, nếu chúng ta bao giờ chạy vào điểm mà một trong các mảng của chúng tôi là hoàn toàn sáp nhập đã, sau đó chúng tôi chỉ đưa tất cả các yếu tố của các mảng khác và chèn chúng vào cuối mảng. Vì vậy, chúng tôi chỉ có thể chèn 4, 5, 6. Okay. Đó là một điều để xem ra cho. Thực hiện có nên bước 1. Hợp nhất sắp xếp sau đó trên cơ sở đó, đó là 2 bước, 2 bước ngớ ngẩn. Hãy chỉ cho mảng này. Vì vậy, hợp nhất sắp xếp, bước 1 là đệ quy phá vỡ các mảng vào nửa. Vì vậy, chia mảng này vào nửa. Bây giờ chúng ta có 4, 15, 16, 50 và 8, 23, 42, 108. Và bây giờ chúng tôi làm điều đó một lần nữa và chúng tôi chia thành các nửa. Tôi sẽ chỉ làm điều đó trên mặt này. Vì vậy, 4, 15, 16, 50. Chúng tôi sẽ làm điều tương tự ở đây. Và bây giờ chúng tôi chia nó thành hai nửa một lần nữa. Và chúng tôi có 4, 15, 16, 50. Vì vậy, đó là trường hợp cơ sở của chúng tôi. Một khi các mảng có kích thước 1, sau đó chúng tôi dừng lại với phân tách thành hai nửa. 

Bây giờ chúng ta phải làm gì với điều này? Chúng tôi kết thúc điều này cũng sẽ phá vỡ thành 8, 23, 42, và 108. Vì vậy, bây giờ chúng ta đang ở vào thời điểm này, bây giờ bước hai của hợp nhất loại chỉ là sáp nhập cặp danh sách. Vì vậy, chúng tôi muốn hợp nhất các. Chúng tôi chỉ cần gọi hợp nhất. Chúng tôi biết hợp nhất sẽ trở lại trong các thứ tự sắp xếp. 4, 15. Bây giờ chúng tôi muốn kết hợp này, và đó sẽ trở lại một danh sách với những người theo thứ tự sắp xếp, 16, 50. Chúng tôi kết hợp những - tôi không thể viết - 8, 23 và 42, 108. Vì vậy, chúng tôi có các cặp sáp nhập một lần. Bây giờ chúng ta chỉ cần kết hợp một lần nữa. Chú ý rằng mỗi các danh sách này được sắp xếp trong chính nó, và sau đó chúng tôi chỉ có thể hợp nhất các danh sách này để có được một danh sách các kích thước 4 được sắp xếp và hợp nhất hai danh sách này để có được một danh sách các kích thước 4 được sắp xếp. Và cuối cùng, chúng ta có thể hợp nhất hai danh sách các kích thước 4 để có được một danh sách các kích thước 8 được sắp xếp. Vì vậy, để thấy rằng đây là tổng thể n log n, chúng ta đã thấy rằng hợp nhất là tuyến tính, do đó, khi chúng ta đang đối phó với việc sáp nhập này, do đó, như tổng chi phí của hợp nhất cho hai danh sách này chỉ là 2 bởi vì - Hoặc tốt, đó là O của n, n ở đây chỉ là 2 yếu tố này, do đó, nó là 2. Và những 2 sẽ là 2 và những 2 sẽ được 2 và những 2 sẽ là 2, do đó, trên tất cả các sáp nhập mà chúng ta cần làm, chúng tôi kết thúc làm n. Giống như 2 + 2 + 2 + 2 là 8, mà là n, do đó, chi phí của việc sáp nhập trong bộ này là n. Và sau đó điều tương tự ở đây. Chúng tôi sẽ hợp nhất các 2, sau đó những 2, và cá nhân hợp nhất này sẽ có bốn hoạt động, này hợp nhất sẽ có bốn hoạt động, nhưng một lần nữa, giữa tất cả các, chúng tôi kết thúc hợp nhất n tổng điều, và do đó, bước này có n. Và do đó, mỗi cấp có n phần tử được sáp nhập. 

Và bao nhiêu cấp? Ở mỗi cấp độ, mảng của chúng tôi phát triển bởi kích thước 2. Mảng của chúng tôi là có kích thước 1, ở đây chúng có kích thước 2, ở đây họ đang có kích thước 4, và cuối cùng, chúng có kích thước 8. Vì vậy, kể từ khi nó được tăng gấp đôi, có sẽ được tổng cộng log n của các cấp độ. Vì vậy, với log n cấp độ, mỗi cấp độ cá nhân n hoạt động tổng, chúng tôi nhận được một log n n thuật toán. Câu hỏi? Có người đã đạt được tiến bộ về làm thế nào để thực hiện điều này? Có ai đã có trong một tiểu bang mà tôi chỉ có thể kéo lên mã của họ? Tôi có thể cung cấp cho một phút. Điều này một là có thể kéo dài hơn. Tôi rất khuyên bạn nên tái diễn - Bạn không phải làm đệ quy cho hợp nhất bởi vì để làm đệ quy cho hợp nhất, bạn sẽ phải vượt qua một loạt các kích cỡ khác nhau. Bạn có thể, nhưng nó gây phiền nhiễu. Nhưng đệ quy để sắp xếp chính nó là khá dễ dàng. Bạn chỉ theo nghĩa đen gọi sắp xếp trên nửa bên trái, sắp xếp trên nửa bên phải. Okay. Bất cứ ai có bất cứ điều gì tôi có thể kéo lên? Hoặc nếu không tôi sẽ cung cấp cho một phút. Okay. Bất cứ ai cũng có một cái gì đó chúng ta có thể làm việc với? Nếu không chúng ta sẽ chỉ làm việc với điều này và sau đó mở rộng từ đó. 

Bất cứ ai có nhiều hơn này mà tôi có thể kéo lên? [Sinh viên] Yeah. Bạn có thể kéo lên tôi. >> Tất cả đúng. Có! [Sinh viên] Có rất nhiều điều kiện. >> Oh, bắn. Bạn có thể không - [Sinh viên] Tôi có để lưu nó. >> Yeah. Vì vậy, chúng tôi đã làm việc hợp nhất một cách riêng biệt. Vâng, nhưng đó không phải là xấu. Okay. Vì vậy, sắp xếp là chính nó chỉ cần gọi điện thoại mergeSortHelp. Giải thích cho chúng tôi những gì mergeSortHelp không. [Sinh viên] MergeSortHelp khá nhiều hiện hai bước chính, đó là để sắp xếp mỗi nửa của mảng và sau đó kết hợp cả hai người trong số họ. [Bowden] rồi, do đó cung cấp cho tôi một giây. Tôi nghĩ rằng điều này - >> [sinh viên] Tôi cần phải - Yeah. Tôi đang thiếu một cái gì đó. Hợp nhất, tôi nhận ra rằng tôi cần phải tạo một mảng mới bởi vì tôi không thể làm điều đó tại chỗ. >>. Bạn có thể không. Chính xác. [Sinh viên] Vì vậy, tôi tạo ra một mảng mới. Tôi quên vào cuối hợp nhất lại thay đổi. Okay. Chúng ta cần một mảng mới. Trong loại hợp nhất, điều này hầu như luôn luôn đúng. Một phần của chi phí của một thuật toán tốt hơn thời gian khôn ngoan hầu như luôn luôn cần phải sử dụng bộ nhớ nhiều hơn một chút. Vì vậy, ở đây, không có vấn đề làm thế nào bạn làm hợp nhất sắp xếp, mà bạn chắc chắn sẽ cần phải sử dụng một số bộ nhớ thêm. Anh ta hoặc cô tạo ra một mảng mới. Và sau đó bạn nói rằng cuối cùng chúng tôi chỉ cần sao chép mảng mới vào mảng ban đầu. [Sinh viên] Tôi nghĩ như vậy, yeah. Tôi không biết rằng các công trình về tính tham khảo hoặc bất cứ điều gì - Yeah, nó sẽ làm việc. >> [Sinh viên] Okay. Bạn hãy thử chạy này? >> [Sinh viên] Không, không phải. >> Okay. Thử chạy nó, và sau đó tôi sẽ nói về nó cho một thứ hai. [Sinh viên] Tôi cần phải có tất cả các nguyên mẫu chức năng và tất cả mọi thứ, mặc dù, phải không? Các chức năng nguyên mẫu. Oh, bạn có nghĩa là như thế - Có. Sắp xếp được gọi mergeSortHelp. 

Vì vậy, để sắp xếp để gọi mergeSortHelp mergeSortHelp hoặc phải được xác định trước khi sắp xếp hoặc chúng ta chỉ cần các mẫu thử nghiệm. Chỉ cần sao chép và dán mà. Và tương tự như vậy, mergeSortHelp đang kêu gọi hợp nhất, nhưng hợp nhất đã được xác định, vì vậy chúng tôi chỉ có thể cho mergeSortHelp biết đó là những gì hợp nhất sẽ trông giống như, và thế là chấm dứt. Vì vậy, mergeSortHelp. Chúng tôi có một vấn đề ở đây, nơi chúng tôi không có trường hợp cơ sở. MergeSortHelp là đệ quy, do đó, bất kỳ chức năng đệ quy sẽ cần một số loại của trường hợp cơ sở để biết khi nào dừng đệ quy tự gọi mình. Trường hợp cơ sở của chúng tôi sẽ được gì đây? Yeah. [Sinh viên] Nếu kích thước là 1? >> [Bowden]. Vì vậy, như chúng ta đã thấy ngay tại đó, chúng tôi dừng mảng tách một khi chúng ta đã tạo thành những mảng có kích thước 1, mà chắc chắn đều được sắp xếp. Vì vậy, nếu kích thước bằng 1, chúng ta biết mảng đã được sắp xếp, vì vậy chúng tôi chỉ có thể trở lại. 

Chú ý rằng có hiệu lực, nên chúng tôi không trả lại bất cứ điều gì đặc biệt, chúng tôi chỉ trả lại. Okay. Vì vậy, đó là trường hợp cơ sở của chúng tôi. Tôi đoán trường hợp cơ sở của chúng tôi cũng có thể được nếu chúng ta xảy ra để được sáp nhập một mảng có kích thước 0, chúng tôi có thể muốn dừng lại tại một số điểm, vì vậy chúng tôi chỉ có thể nói kích thước ít hơn 2 hoặc nhỏ hơn hoặc bằng 1 để điều này sẽ làm việc cho bất kỳ mảng. Okay. Vì vậy, đó là trường hợp cơ sở của chúng tôi. Bây giờ bạn có muốn đi bộ chúng tôi thông qua hợp nhất? Tất cả các trường hợp này có ý nghĩa gì? Lên ở đây, chúng ta chỉ cần làm cùng một ý tưởng, các - [Sinh viên] tôi cần phải được đi qua kích thước với tất cả các cuộc gọi mergeSortHelp. Tôi được thêm vào kích thước như một chính bổ sung và nó không phải ở đó, như kích thước / 2. [Bowden] Oh, kích thước / 2, kích thước / 2. >> [Sinh viên] Yeah, và cũng trong hàm trên cũng. Bowden]? >> [Sinh viên] Chỉ cần kích thước. >> [Bowden] Oh. Kích thước, kích thước? >> [Sinh viên] Yeah. [Bowden] Okay. Hãy để tôi suy nghĩ cho một thứ hai. Chúng tôi chạy vào một vấn đề? Chúng tôi luôn xử lý bên trái là 0. >> [Sinh viên] số Đó là sai quá. Xin lôi. Nó nên được bắt đầu. Yeah. [Bowden] Okay. Tôi thích điều đó tốt hơn. Và kết thúc. Okay. Vì vậy, bây giờ bạn muốn đi bộ chúng tôi thông qua hợp nhất? >> [Sinh viên] Okay. Tôi chỉ đi qua mảng mới này mà tôi đã tạo ra. Kích thước của nó là kích thước của phần của mảng mà chúng tôi muốn được sắp xếp và cố gắng để tìm thấy những yếu tố mà tôi nên đặt trong bước mảng mới. Vì vậy, để làm được điều đó, đầu tiên tôi kiểm tra nếu có một nửa trái của mảng tiếp tục có những yếu tố nào, và nếu nó không, sau đó bạn đi xuống với điều kiện khác, mà chỉ nói okay, nó phải là trong mảng bên phải, và chúng tôi sẽ đặt trong các chỉ số hiện tại của newArray. 

Và sau đó nếu không, tôi kiểm tra nếu phía bên phải của mảng cũng được hoàn thành, trong trường hợp đó, tôi chỉ cần đặt ở bên trái. Điều đó có thể không thực sự cần thiết. Tôi không chắc. Nhưng dù sao, hai kiểm tra của hai nhỏ hơn ở bên trái hoặc bên phải. Và cũng có thể trong mỗi trường hợp, tôi incrementing giữ chỗ nào tôi tăng. [Bowden] Okay. Điều đó có vẻ tốt. Có ai có ý kiến ​​hay quan tâm hoặc câu hỏi? Vì vậy, bốn trường hợp mà chúng tôi đã mang lại những điều chỉ là có vẻ như năm - nhưng chúng ta phải xem xét liệu các mảng bên trái đã chạy ra khỏi những điều chúng ta cần phải hợp nhất, liệu mảng phải đã hết những điều chúng ta cần phải hợp nhất - Tôi chỉ ở không có gì. Vì vậy, liệu các mảng bên trái đã chạy ra khỏi những điều hoặc các mảng bên phải đã chạy ra khỏi những điều. Đó là hai trường hợp. Chúng ta cũng cần trường hợp tầm thường cho dù điều trái là ít hơn đúng. Sau đó, chúng tôi muốn chọn điều trái. Đó là các trường hợp. Vì vậy, điều này là đúng, vì vậy đó mà. Mảng còn lại. Đó là 1, 2, 3. Okay. Vì vậy, yeah, những người đang có bốn điều chúng tôi có thể muốn làm. Và chúng tôi sẽ không đi qua một giải pháp lặp. Tôi sẽ không khuyên - Kết hợp các loại là một ví dụ của một chức năng đó là cả hai không đệ quy đuôi, nó không phải dễ dàng để làm cho nó đệ quy đuôi, nhưng cũng có thể nó không phải là rất dễ dàng để làm cho nó lặp đi lặp lại. Điều này là rất dễ dàng. Điều này thực hiện các loại hợp nhất, sáp nhập, không có vấn đề gì bạn làm, bạn sẽ xây dựng hợp nhất. 

Vì vậy, hợp nhất loại được xây dựng trên đầu trang của hợp nhất đệ quy chỉ là ba dòng này. Lặp đi lặp lại, nó là gây phiền nhiễu và khó khăn hơn để suy nghĩ về. Nhưng hãy chú ý rằng nó không phải đệ quy đuôi từ mergeSortHelp - khi nó gọi chính nó - nó vẫn cần làm những việc sau khi trở về cuộc gọi đệ quy. Vì vậy, stack frame này phải tiếp tục tồn tại ngay cả sau khi kêu gọi này. Và sau đó khi bạn gọi điều này, các stack frame phải tiếp tục tồn tại bởi vì ngay cả sau khi cuộc gọi đó, chúng tôi vẫn cần phải hợp nhất. Và đó là không tầm thường để làm cho đệ quy đuôi. Câu hỏi? Được rồi. Quay trở lại để sắp xếp - oh, có hai điều tôi muốn hiển thị. Okay. Trở lại để sắp xếp, chúng tôi sẽ làm điều này một cách nhanh chóng. Hoặc tìm kiếm. Sắp xếp? Sắp xếp. Yeah. Quay trở lại sự khởi đầu của loại. Chúng tôi muốn tạo ra một thuật toán sắp xếp các mảng bằng cách sử dụng bất kỳ thuật toán O của n. Vì vậy, làm thế nào có thể? Có ai có bất kỳ loại - Tôi gợi ý trước đó tại - Nếu chúng ta để cải thiện từ n log n O n, chúng tôi đã được cải thiện thuật toán của chúng tôi thời gian khôn ngoan, có nghĩa là những gì chúng ta sẽ cần phải làm gì để làm cho điều đó? [Sinh viên] Space. >> Yeah. Chúng tôi sẽ được sử dụng nhiều không gian hơn. Và thậm chí không chỉ cần nhiều không gian hơn, đó là theo cấp số nhân nhiều không gian hơn. Vì vậy, tôi nghĩ rằng loại thuật toán này là một cái gì đó giả, polynom giả - pseudo - Tôi không thể nhớ. Pseudo một cái gì đó. Nhưng đó là bởi vì chúng ta cần phải sử dụng quá nhiều không gian rằng điều này có thể đạt được nhưng không thực tế. 

Và làm thế nào để chúng ta đạt được điều này? Chúng tôi có thể đạt được điều này nếu chúng tôi đảm bảo rằng bất kỳ yếu tố đặc biệt trong mảng dưới đây là một kích thước nhất định. Vì vậy, chúng ta hãy chỉ nói rằng size kích thước là 200, bất kỳ yếu tố trong một mảng dưới kích cỡ 200. Và điều này thực sự là rất thực tế. Bạn có thể dễ dàng có một mảng mà bạn biết tất cả mọi thứ trong nó sẽ được ít hơn so với một số số. Cũng giống như nếu bạn có một số vector hoàn toàn hoặc một cái gì đó lớn nhưng bạn biết tất cả mọi thứ sẽ được giữa 0 và 5, sau đó nó sẽ nhanh hơn đáng kể để làm điều này. Và bị ràng buộc vào bất kỳ của các yếu tố là 5, do đó, điều này bị ràng buộc, đó là bao nhiêu bộ nhớ bạn sẽ được sử dụng. Vì vậy, ràng buộc là 200. Trong lý thuyết luôn luôn bị ràng buộc vì một số nguyên chỉ có thể lên đến 4 tỷ đồng, nhưng đó là không thực tế từ đó chúng tôi muốn được sử dụng không gian về trình tự của 4 tỷ đồng. Vì vậy, đó là không thực tế. Nhưng ở đây chúng tôi sẽ nói ràng buộc của chúng tôi là 200. Các trick để làm nó trong O n là chúng ta thực hiện một mảng gọi là tội kích thước RÀNG BUỘC. Vì vậy, trên thực tế, đây là một phím tắt cho - Tôi thực sự không biết nếu Clang thực hiện điều này. Nhưng trong GCC ít nhất Clang giả sử tôi làm nó quá - điều này sẽ chỉ khởi tạo mảng toàn bộ là số 0. Vì vậy, nếu tôi không muốn làm điều đó, sau đó tôi riêng biệt có thể làm for (int i = 0; i <sách; i + +) và số lượng [i] = 0; Vì vậy, bây giờ tất cả mọi thứ được khởi tạo là 0. Tôi lặp qua mảng của tôi, và những gì tôi đang làm là tôi đếm số lượng của từng - đang đi xuống. Chúng tôi có 4, 15, 16, 50, 8, 23, 42, 108. Những gì tôi đang đếm là số lần xuất hiện của mỗi người trong số những yếu tố. Hãy để thực sự thêm một vài chi tiết ở đây với một số lặp đi lặp lại. Vì vậy, giá trị, chúng tôi có ở đây, giá trị mà là có được mảng [i]. Vì vậy, val có thể là 4 hoặc 8 hoặc bất cứ điều gì. Và bây giờ tôi đếm có bao nhiêu giá trị mà tôi đã nhìn thấy, để tính [val] + +; Sau này được thực hiện, số lượng sẽ xem xét một cái gì đó giống như 0001. Hãy làm tính [val] - RÀNG BUỘC + 1. 

Bây giờ đó là chỉ cần vào tài khoản cho một thực tế mà chúng tôi đang bắt đầu từ 0. Vì vậy, nếu 200 là có được số lượng lớn nhất của chúng tôi, sau đó 0 đến 200 là 201 điều. Vì vậy, số lượng, nó sẽ trông giống như 00.001 bởi vì chúng tôi có một trong 4. Sau đó, chúng ta sẽ có 0001 mà chúng ta sẽ có 1 trong các chỉ số 8 số. Chúng ta sẽ có 2 trong chỉ số 23 số. Chúng ta sẽ có một 2 trong chỉ mục thứ 42 của số. Vì vậy, chúng ta có thể sử dụng số. Vì vậy, num_of_item = đếm [i]. Và vì vậy nếu num_of_item là 2, có nghĩa là chúng ta muốn chèn 2 số tôi vào mảng được sắp xếp của chúng tôi. Vì vậy, chúng ta cần phải theo dõi như thế nào đến nay chúng tôi vào mảng. Vì vậy, chỉ số = 0. Mảng - tôi sẽ chỉ viết nó. Đếm - array [index + +] = i; Có phải đó là những gì tôi muốn? Tôi nghĩ rằng đó là những gì tôi muốn. Có, điều này có vẻ tốt. Okay. Vì vậy, không tất cả mọi người hiểu mục đích của mảng tính của tôi là gì? Nó đếm số lần xuất hiện của mỗi của những con số. Sau đó, tôi đang iterating trên mảng đó tính, và vị trí thứ i trong mảng tính là số của tôi là sẽ xuất hiện trong mảng được sắp xếp của tôi. Đó là lý do tại sao tội 4 có được 1 và số lượng của 8 sẽ được 1, đếm của 23 sẽ là 2. Vì vậy, đó là nhiều người trong số họ như thế nào tôi muốn để chèn vào mảng được sắp xếp của tôi. Sau đó, tôi chỉ làm điều đó. Tôi chèn num_of_item i vào mảng sắp xếp của tôi. 

Câu hỏi? Và như vậy một lần nữa, đây là tuyến tính thời gian kể từ khi chúng tôi chỉ là iterating qua điều này một lần, nhưng nó cũng tuyến tính trong con số này sẽ xảy ra là, và do đó, nó phụ thuộc nhiều vào những gì ràng buộc của bạn. Với một ràng buộc là 200, đó là không phải là xấu. Nếu bị ràng buộc của bạn sẽ là 10.000, thì đó là tồi tệ hơn một chút, nhưng nếu ràng buộc của bạn là có được 4 tỷ đồng, đó là hoàn toàn không thực tế và mảng này sẽ có kích thước 4 tỷ đồng, đó là không thực tế. Vì vậy, đó là điều đó. Câu hỏi? [Không nghe được sinh viên phản ứng] >> Okay. Tôi nhận ra một điều khác khi chúng tôi đã đi qua. Tôi nghĩ rằng vấn đề của Lucas và có lẽ mỗi người trong chúng ta đã thấy. Tôi hoàn toàn quên mất. Điều duy nhất tôi muốn nhận xét về là khi bạn đang làm việc với những thứ như các chỉ số, bạn không bao giờ thực sự thấy điều này khi bạn đang viết một vòng lặp for, nhưng về mặt kỹ thuật, bất cứ khi nào bạn đang làm việc với các chỉ số này, bạn có khá nhiều nên luôn luôn đối phó với số nguyên unsigned. Lý do cho điều này là khi bạn đang làm việc với số nguyên đã ký kết, vì vậy nếu bạn có 2 số nguyên ký và thêm chúng với nhau và họ kết thúc quá lớn, sau đó bạn kết thúc với một số âm. Vì vậy, đó là những gì số nguyên tràn. 

Nếu tôi thêm 2 tỷ đồng và 1 tỷ, tôi kết thúc với tiêu cực 1 tỷ. Đó là cách số nguyên làm việc trên máy tính. Vì vậy, các vấn đề với việc sử dụng - Đó là tốt ngoại trừ nếu thấp sẽ xảy ra là 2 tỷ đồng và sẽ xảy ra là 1 tỷ đồng, sau đó điều này là có được tiêu cực 1 tỷ và sau đó chúng ta sẽ phân chia cho 2 và kết thúc với âm 500 triệu. Vì vậy, đây chỉ là một vấn đề nếu bạn xảy ra để được tìm kiếm thông qua một mảng tỷ thứ. Nhưng nếu thấp + lên xảy ra tràn, thì đó là một vấn đề. Ngay khi chúng tôi làm cho họ unsigned, sau đó 2 tỷ đồng cộng với 1 tỷ là 3 tỷ đồng. 3 tỷ đồng chia cho 2 là 1,5 tỷ đồng. Vì vậy, ngay sau khi chúng được unsigned, mọi thứ đều hoàn hảo. Và đó là cũng là một vấn đề khi bạn đang viết cho các vòng, và trên thực tế, nó có thể sẽ làm tự động. Nó sẽ thực sự chỉ cần hét lên với bạn. Vì vậy, nếu con số này là quá lớn để có trong chỉ là một số nguyên nhưng nó sẽ phù hợp với một số nguyên unsigned, nó sẽ la lên ở bạn, vì vậy đó là lý do tại sao bạn không bao giờ thực sự chạy vào vấn đề. Bạn có thể thấy rằng một chỉ số sẽ không bao giờ được tiêu cực, và do đó, khi bạn đang iterating trên mảng, bạn hầu như luôn luôn có thể nói unsigned int i, nhưng bạn không thực sự có. Những điều sẽ làm việc khá nhiều chỉ là tốt. Okay. [Thì thầm] What time is it? Điều cuối cùng tôi muốn thể hiện và tôi sẽ chỉ làm điều đó thực sự nhanh chóng. Bạn biết làm thế nào chúng ta đã # define # vì vậy chúng tôi có thể xác định MAX là 5 hoặc một cái gì đó? Hãy không làm MAX. # Xác định RÀNG BUỘC tới 200. Đó là những gì chúng tôi đã làm trước đây. Định nghĩa một hằng số, mà chỉ là sẽ được sao chép và dán bất cứ nơi nào chúng tôi xảy ra để viết RÀNG BUỘC. 

Vì vậy, chúng tôi thực sự có thể làm nhiều hơn với # định nghĩa. Chúng tôi # có thể xác định chức năng. Họ không thực sự chức năng, nhưng chúng tôi sẽ gọi cho họ chức năng. Một ví dụ sẽ là một cái gì đó như MAX (x, y) được định nghĩa là (x <y y: x). Okay. Vì vậy, bạn nên làm quen với cú pháp điều hành ternary, nhưng là x ít hơn y? Quay trở lại y, khác trở về x. Vì vậy, bạn có thể thấy bạn có thể làm cho chức năng riêng biệt, và chức năng có thể là như bool MAX mất 2 đối số, trả lại điều này. Đây là một trong những phổ biến nhất mà tôi thấy được thực hiện như thế này. Chúng tôi gọi họ là macro. Đây là một vĩ mô. Đây chỉ là cú pháp cho nó. Bạn có thể viết một macro để làm bất cứ điều gì bạn muốn. Bạn thường xuyên thấy các macro để gỡ lỗi printfs và các công cụ. Vì vậy, một loại printf, có là hằng số đặc biệt trong C như gạch dưới DÒNG gạch dưới, 2 nhấn DÒNG gạch dưới, và tôi cũng nghĩ rằng 2 nhấn FUNC. Đó có thể là nó. Một cái gì đó như thế. Những điều này sẽ được thay thế bằng tên của chức năng hoặc số của dòng mà bạn đang ở trên. Thường xuyên, bạn viết printfs gỡ lỗi mà xuống đây tôi có thể sau đó chỉ cần viết DEBUG và nó sẽ in số dòng và chức năng mà tôi xảy ra được trong mà nó gặp phải tuyên bố rằng DEBUG. Và bạn cũng có thể in những thứ khác. Vì vậy, có một điều bạn nên xem ra cho là nếu tôi xảy ra # define DOUBLE_MAX như là một cái gì đó giống như 2 * y và 2 * x. Vì vậy, đối với lý do nào, bạn xảy ra để làm điều đó rất nhiều. Vì vậy, làm cho nó một macro. Điều này thực sự bị phá vỡ. Tôi sẽ gọi nó bằng cách làm một cái gì đó như DOUBLE_MAX (3, 6). Vì vậy, những gì nên được trả lại? [Sinh viên] 12. Có, 12 nên được trả lại, và 12 được trả lại. 3 được thay thế cho x, 6 được thay thế cho y, và chúng tôi trở lại 2 * 6, là 12. Bây giờ những gì về điều này? Những gì nên được quay trở lại? [Sinh viên] 14. >> Lý tưởng nhất, 14. Vấn đề là làm thế nào băm xác định công việc, hãy nhớ đó là một bản sao đen và dán của tất cả mọi thứ khá nhiều, do đó, điều này sẽ được giải thích như 3 so với 1 cộng với 6, 2 lần 1 cộng với 6, 2 lần 3. 

Vì vậy, vì lý do này, bạn hầu như luôn luôn quấn tất cả mọi thứ trong ngoặc đơn. Bất kỳ biến bạn gần như luôn luôn quấn trong dấu ngoặc đơn. Có những trường hợp mà bạn không có, như tôi biết rằng tôi không cần phải làm điều đó ở đây vì ít hơn khá nhiều luôn luôn chỉ cần đi để làm việc, mặc dù thậm chí có thể không phải là sự thật. Nếu có cái gì đó vô lý như DOUBLE_MAX (1 == 2), sau đó sẽ được thay thế với 3 so với 1 tương đương với bằng 2, và như vậy sau đó nó sẽ phải làm 3 ít hơn 1, điều đó bằng 2, mà không phải là những gì chúng ta muốn. Vì vậy, để ngăn chặn bất kỳ nhà điều hành các vấn đề ưu tiên, luôn luôn bọc trong dấu ngoặc đơn. Okay. Và đó là nó, 5:30. Nếu bạn có bất kỳ câu hỏi trên pset, cho chúng tôi biết. Nó sẽ được vui vẻ, và phiên bản hacker cũng là thực tế hơn nhiều so với phiên bản hacker năm ngoái, vì vậy chúng tôi hy vọng rằng rất nhiều bạn thử nó. Năm ngoái đã rất áp đảo. 

[CS50.TV]