3 - Thuật toán - Lecture Flashcards
- Thuật toán
cách chính thức hóa bằng mã giả mà còn bằng mã thực tế
trục x là kích thước của vấn đề
và trục y là thời gian cần thiết để giải quyết vấn đề tính bằng giây, phút
bộ nhớ máy tính của bạn thực sự chỉ là một mạng lưới các byte.
Và vì vậy hôm nay chúng ta bắt đầu với cái nhìn về một loại thuật toán cụ thể.
ĐÓ LÀ ĐỂ TÌM KIẾM
- Tìm kiếm tuyến tính
Có thể để theo ngẫu nhiên
Nhưng chúng tôi muốn bạn thực hiện một thuật toán nhất định. Và trên thực tế, tôi sẽ cung cấp cho bạn một số mã giả cho việc này
Mã giả xuất hiện là dành cho thuật toán
Bước đầu tiên của bạn sẽ suy nghĩ giống như một vòng lặp
Đối với mỗi cửa từ trái sang phải, chúng tôi muốn bạn làm gì trên mỗi lần lặp lại?
Chà, nếu 50 ở đằng sau cánh cửa đó, thì chúng tôi muốn tiếp tục và yêu cầu bạn trở về đúng.
Và hãy tự hào giơ cao con số 50, nếu bạn muốn, cho cả nhóm.
Ngược lại nếu bạn đi hết vòng đó mà vẫn chưa tìm thấy số 50, bạn chỉ có thể giơ tay trong sự thất vọng.
Sai – bạn chưa tìm thấy số 50.
Hình ảnh
https://imgur.com/a/HOYBvDP
Mã giả toàn tiếng anh
Mã giả chưa chắc đã là toàn tiếng anh
Mã thực
Hình ảnh
https://imgur.com/a/06aIIxD
Mã thực tế nó có toán học phức tạp hơn
Làm nhiều bài tập để thực sự hiểu họ đang hỏi về nghĩa gì và trả lời đúng theo ý họ hỏi
- Tìm kiếm nhị phân
Mã giả
Hình ảnh
https://imgur.com/RDF6vBM
Mã thực
Hình ảnh
https://imgur.com/ENGCw0G
Tại sao cuối cùng Jackson lại có thể tìm ra số 50 chỉ trong ba bước thay vì đủ bảy bước như Stephanie ?
Vì mảng đã được sắp xếp.
- Thời gian chạy (Running Time)
Chà một người như Carter đã mất bao nhiêu nỗ lực. Điện thoại của bạn cần bao nhiêu nỗ lực để sắp xếp tất cả các tên và số đó.
Bởi vì có lẽ nó không thực sự xứng đáng với thời gian.
Giờ đây, một người nào đó như Google có thể bằng cách nào đó sắp xếp cơ sở dữ liệu của các trang web. Bạn có thể tưởng tượng nó sẽ siêu chậm nếu khi bạn nhập mèo hoặc thứ gì đó khác vào google.com, nếu họ tìm kiếm tuyến tính trên toàn bộ tập dữ liệu của họ.
Vì vậy, bây giờ, chúng tôi sẽ chính thức hóa chính xác loại phân tích này. Và nó sẽ không quá nặng về toán học vì nó vẫn sẽ trực quan.
18:42
Nhưng chúng tôi sẽ giới thiệu cho bạn một số biệt ngữ, một số thuật ngữ mà hầu hết mọi lập trình viên hoặc nhà khoa học máy tính đều có thể sử dụng.
18:48
khi phân tích các thuật toán của riêng họ.
Vì vậy, bây giờ, chúng tôi sẽ chính thức hóa chính xác loại phân tích này. Và nó sẽ không quá nặng về toán học vì nó vẫn sẽ trực quan.
Mã giả không quá nặng nề về toán học
Đây là nội dụng thuật ngữ mà họ nhắc đến
Vì vậy, ngay bây giờ, tôi khẳng định tìm kiếm nhị phân tốt hơn tìm kiếm tuyến tính. Nhưng chính xác thì tốt hơn bao nhiêu và tại sao?
Và chính xác, nếu bạn đếm số trang tôi đã chạm vào
19:19
hoặc số trang tôi đã xé, công bằng mà nói thì thuật toán đầu tiên, trong trường hợp xấu nhất, có thể đã chiếm tổng cộng n trang.
n là 1 trang một lần
n/2 là 2 trang một lần
Khi sử dụng ký hiệu O lớn, bạn thực sự không quan tâm đến, chúng ta sẽ thấy, các số hạng bậc nhỏ hơn.Chúng ta sẽ không quan tâm đến số chia cho 2 vì bạn biết không? Hình dạng của các thuật toán này gần như giống nhau.
khi bạn thu nhỏ,
thu nhỏ, thu nhỏ, thu nhỏ và khi n trở nên lớn hơn rất nhiều trên trục x, đường màu đỏ và màu vàng
về cơ bản sẽ giống nhau khi n đủ lớn. Nhưng đường màu xanh lá cây sẽ không bao giờ giống nhau.
Hình ảnh
https://imgur.com/uZSVJpp
Bảng tóm tắt các công thức phổ biến mà một nhà khoa học máy tính, chắc chắn là trong ngữ cảnh giới thiệu, có thể sử dụng khi phân tích các thuật toán.
Hình ảnh
https://imgur.com/kU17gkv
Được sắp xếp từ trên xuống dưới theo mức độ chậm nhất đến nhanh nhất
Trong trường hợp xấu nhất, một người như Stephanie phải mất bao nhiêu bước để tìm ra giải pháp cho vấn đề, giả sử không phải bảy cánh cửa mà là n cánh cửa?
23:23
Vâng? Vì vậy, theo thứ tự của n. Và trong trường hợp này, nó chính xác là n. Nhưng bạn biết không, có lẽ nó được cho là 2n vì nó đã lấy mất Stephanie
23:32
một vài bước. Cô phải nhấc chốt lên. Cô phải mở cửa. Có lẽ đó là ba bước. Cô phải cho xem tiền. Vì vậy, bây giờ là 3n, 2n.
Trong trường hợp xấu nhất, một người như Stephanie phải mất bao nhiêu bước để tìm ra giải pháp cho vấn đề
OMEGA
Mô tả giới hạn dưới của một thuật toán
Không muốn xem xét các trường hợp xấu nhất mà còn muốn xem xét các trường hợp tốt nhất (gặp may)
bảng công thức OMEGA tương ứng
Hình ảnh
https://imgur.com/TZLfcdV
THETA
Chỉ ra giới hạn trên giống với giới hạn dưới
- search.c
Vì vậy, bây giờ nếu bạn tua nhanh vài tháng, vài năm, khi bạn thực sự
41:35
viết mã trong công ty hoặc cho các dự án lớn hơn, bạn có thể muốn tự động hóa phần mềm. Bạn có thể không muốn con người nhất thiết phải chạy thủ công.
41:43
Bạn có thể muốn mã được tự động hóa bởi một số quy trình hàng đêm hoặc điều gì đó tương tự.
41:48
Sử dụng các mã thoát này, chương trình có thể xác định có hay không rằng mã khác thành công hay thất bại.
return 0
return 1