3 - Thuật toán - Lecture Flashcards

1
Q
  1. Thuật toán
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

cách chính thức hóa bằng mã giả mà còn bằng mã thực tế

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

bộ nhớ máy tính của bạn thực sự chỉ là một mạng lưới các byte.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q
  1. Tìm kiếm tuyến tính
A

Có thể để theo ngẫu nhiên

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

Mã giả xuất hiện là dành cho thuật toán

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Bước đầu tiên của bạn sẽ suy nghĩ giống như một vòng lặp

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Đố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.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Mã thực

A

Hình ảnh
https://imgur.com/a/06aIIxD
Mã thực tế nó có toán học phức tạp hơn

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q
  1. Tìm kiếm nhị phân
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Mã giả

A

Hình ảnh
https://imgur.com/RDF6vBM

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Mã thực

A

Hình ảnh
https://imgur.com/ENGCw0G

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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 ?

A

Vì mảng đã được sắp xếp.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q
  1. Thời gian chạy (Running Time)
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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.

A

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ọ.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

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ọ.

A

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?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

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.

A

n là 1 trang một lần
n/2 là 2 trang một lần

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

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.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

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.

A

Hình ảnh
https://imgur.com/uZSVJpp

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

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.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

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.

A

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 đề

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

OMEGA

A

Mô tả giới hạn dưới của một thuật toán

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

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)

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

bảng công thức OMEGA tương ứng

A

Hình ảnh
https://imgur.com/TZLfcdV

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

THETA

A

Chỉ ra giới hạn trên giống với giới hạn dưới

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q
  1. search.c
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

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.

A

return 0
return 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Nhưng bây giờ bạn đang ở trong hệ thống danh dự để biết rằng chuỗi đầu tiên là tên, chuỗi thứ hai là số, chuỗi thứ ba là–
43:42
bạn có thể làm được. Nhưng đó là một chút hack, có thể nói như vậy.

A

Không phải như mình nghĩ nó vẫn dùng cách khai báo hai mảng.

Ở đây là nó nói về việc khai báo một mảng duy nhất trong mảng đó chứa cả tên và và điện thoại nó vẫn làm được nhưng là một kiểu hack.

32
Q

Trong phần xây dựng cs50 không để ý lắm đến loại dữ liệu, hay lo lắng về nó

A
33
Q

Thiết kế ứng dụng của cs50 tốt thật

A
34
Q

Thiết kế của ứng dụng tìm kiếm số điện thoại của cs50

A

Tôi đang tra cứu trong một mảng, một trong các chuỗi.
46:09
Và sau đó tôi in từ mảng khác, câu trả lời.

35
Q
  1. structs
A
36
Q

typedef struct
{
string name;
string number;
}
person;

A

typedef : define your own type
struct = structure (cấu trúc) = nó giống như một cấu trúc có nhiều giá trị bên trong

37
Q

57:29 Trong cấu trúc, bạn có thể đặt giá trị mặc định cho thuộc tính không? Câu trả lời ngắn gọn, không.

A
38
Q

58:04 Làm thế nào chúng ta có thể điều chỉnh hoặc phê bình thiết kế của những gì tôi đang làm?
Đây là một trong số ít tình huống mà tôi sẽ nói, một cách đạo đức giả,
58:12
hãy làm như tôi nói,đừng làm như tôi làm. Tôi đang sử dụng những dòng khá xấu xí như thế này, chỉ để giới thiệu cú pháp.
58:17
Nhưng khẳng định của tôi, về mặt sư phạm ngày nay, là cuối cùng, khi chúng ta bắt đầu lưu trữ tên và số hoặc những thứ khác
58:22
trong tệp hoặc trong cơ sở dữ liệu, bạn sẽ không có sự dư thừa này. Bạn sẽ có một dòng mã hoặc hai dòng mã
58:29
đọc thông tin từ tệp hoặc cơ sở dữ liệu rồi điền dữ liệu đó vào toàn bộ mảng.

A

Hình ảnh:
https://imgur.com/roHxuSe

39
Q
  1. Sắp xếp
A
40
Q

Vì vậy, bây giờ hãy xem xét cách chúng ta có thể sắp xếp các tình nguyện viên tốt bụng của chúng ta ở đây,
1:02:16
mục tiêu là sắp xếp chúng theo thứ tự từ nhỏ nhất đến lớn nhất để, có lẽ sau đó, chúng ta có thể sử dụng thứ gì đó thông minh hơn là chỉ tìm kiếm tuyến tính.
1:02:24
Chúng tôi thực sự có thể sử dụng tìm kiếm nhị phân, giả sử rằng chúng đã được sắp xếp.

A
41
Q
  1. Sắp xếp lựa chọn
A
42
Q

Vì vậy, đây là mã giả của tôi để sắp xếp lựa chọn, theo tên của nó,
1:11:34
Tôi chỉ cần lặp đi lặp lại việc chọn lại phần tử nhỏ nhất tiếp theo.

A
43
Q

Vì vậy, hãy để tôi đề xuất rằng trước tiên chúng ta xem xét một thuật toán thực sự
1:02:30
có tên gọi là sắp xếp lựa chọn. Và sắp xếp lựa chọn sẽ là một trong đó thực sự có tôi,
1:02:36
hoặc thực sự là bạn, với tư cách là lập trình viên, chọn đi chọn lại phần tử nhỏ nhất, rồi đặt chúng vào vị trí thích hợp.

A
44
Q

Vì vậy, nếu bạn muốn tiếp tục và 0, hãy tiếp tục ở vị trí 7. Chúng ta cần nhường chỗ cho số 7. Sẽ là gian lận nếu có thể mọi người lịch sự
1:03:44
bước qua một bên. Tại sao? Bởi vì nếu chúng ta tưởng tượng tất cả các tình nguyện viên của chúng ta ở đây là một mảng, thì đó là một khối lượng công việc điên rồ để có mọi phần tử trong mảng
1:03:52
chuyển sang trái chỉ để nhường chỗ. Vì vậy, chúng tôi sẽ giữ cho nó đơn giản và chỉ trục xuất bất cứ ai ở đó ngay bây giờ. Bây giờ, có lẽ chúng ta gặp may mắn, và số 7 đã thực sự gần đích hơn.
1:04:00
Có lẽ chúng ta không may mắn, và nó đi xa hơn. Nhưng ít nhất chúng ta đã giải quyết được một vấn đề. Nếu ban đầu chúng ta có n vấn đề, bây giờ chúng ta có n trừ 1,

A
45
Q

Và đó là cách rất lập dị để thể hiện sự tối ưu hóa này.
1:06:48
Tôi luôn bắt đầu từ khung số i dù tôi ở đâu. Và sau đó mọi thứ khác ở bên phải.

A
46
Q

For i from 0 to n-1
Find smallest number between
numbers[i] and numbers[n-1]
Swap smallest number with numbers[i]

A

Mã giả

47
Q
  1. Sắp xếp bong bóng
A

các phần tử lớn nhất nổi lên trên cùng

48
Q

1:07:09 Hãy tiếp tục và thực hiện cách tiếp cận thứ hai ở đây bằng cách sử dụng một thuật toán mà tôi sẽ gọi là sắp xếp bong bóng.

A
49
Q

Và hãy để tôi thực hiện một cách tiếp cận khác về cơ bản, bởi vì tôi không
1:07:22
thực sự thích sắp xếp lựa chọn như hiện tại, bởi vì nó giống như đi đi lại lại rất nhiều. Và việc đi bộ nhiều gợi ý rất nhiều bước lặp đi lặp lại.
1:07:30
Vậy tôi có thể làm gì thay thế?

A
50
Q

Làm thế nào máy tính, mã, biết chắc chắn rằng danh sách này hiện đã được sắp xếp?

A
51
Q

Trực giác khác? Sắp xếp lựa chọn so với sắp xếp bong bóng.
1:11:14
Vâng, hãy để tôi đề xuất rằng chúng ta cố gắng định lượng hóa điều này để chúng ta có thể thực sự phân tích nó theo một cách nào đó. Và đây không phải là bài tập chúng ta sẽ làm liên tục cho nhiều thuật toán.
1:11:22
Nhưng đây là những đại diện khá của các thuật toán.

A
52
Q

Trực giác khác? Sắp xếp lựa chọn so với sắp xếp bong bóng.
1:11:14
Vâng, hãy để tôi đề xuất rằng chúng ta cố gắng định lượng hóa điều này để chúng ta có thể thực sự phân tích nó theo một cách nào đó. Và đây không phải là bài tập chúng ta sẽ làm liên tục cho nhiều thuật toán.
1:11:22
Nhưng đây là những đại diện khá của các thuật toán. Vì vậy, chúng ta có thể tập trung vào hiệu suất hoặc thiết kế của những thứ này.

A
53
Q

Vì vậy, làm thế nào chúng ta có thể đi về phân tích một cái gì đó như thế này?
Chà, chúng tôi chỉ có thể làm điều đó trên giấy bút chì và đếm số bước dường như được ngụ ý một cách hợp lý bởi mã.
1:12:08 Khi phân tích các thuật toán như thế này, đếm số lần so sánh,bởi vì nó là một loại đơn vị đo lường toàn cầu mà chúng ta có thể sử dụng để so sánh hoàn toàn các thuật toán khác nhau.

A
54
Q

Repeat n times
For i from 0 to n-2
If numbers[i] and numbers[i+1] out of
order
Swap them

A

Repeat n times
For i from 0 to n-2
Nếu khung số i và khung số i+1 không
thao thứ tự
Hãy hoán đổi chúng

55
Q
  1. Đệ quy - Recursion
A

đề cập đến khả năng tự gọi chính nó của một hàm

56
Q

trong lập trình, bất cứ khi nào một hàm gọi chính nó,
1:27:51
chức năng đó được cho là đệ quy.

A
57
Q

Và thật không may, tôi còn thiếu bất kỳ loại điều kiện nhanh, bất kỳ loại điều kiện nào nói rằng, đợi một chút, khi nó quá cao,
1:36:58
dừng lại hoàn toàn. Vì vậy, đây là một vòng lặp vô hạn. Nhưng nó không phải là một vòng lặp. Đó là một cuộc gọi đệ quy. Và thực sự, làm điều này nói chung, là rất xấu.
1:37:05
Chúng ta sẽ thấy vào tuần tới rằng nếu bạn gọi một chức năng quá nhiều lần, bạn thực sự có thể kích hoạt thêm một trong những lỗi phân đoạn đó, vì về cơ bản bạn đang sử dụng quá nhiều bộ nhớ.

A
58
Q

Và điều kiện đơn giản đó, về mặt kỹ thuật được gọi là trường hợp cơ sở, sẽ đảm bảo rằng mã không chạy mãi mãi.

A
59
Q

Bao nhiêu lần sẽ vẽ cuộc gọi chính nó trong mô hình này? SINH VIÊN: Nó là vô tận.
1:39:28
DAVID Malan: Vô số lần. Tại sao? HỌC SINH: Bởi vì không có chức năng thoát.

A
60
Q

Nhưng bây giờ, chỉ là, nó rất giống với mã giả cho danh bạ điện thoại. Bạn chỉ đang tìm kiếm một lần nữa và một lần nữa.
1:43:09
Nhưng bạn đang đợi cho đến khi kết thúc để lấy lại kết quả cuối cùng.

A
61
Q

Và sẽ có rất nhiều meme mà bạn sẽ bắt gặp bây giờ, nơi
1:43:45
đệ quy, chẳng hạn như nếu bạn đã từng hướng camera vào TV đang chiếu camera và bạn thấy đi nhìn lại chính mình hoặc hình ảnh đó,
1:43:51
đó thực sự là đệ quy. Và trong trường hợp đó, nó chỉ dừng lại khi bạn chạm vào trường hợp cơ bản của một pixel.

A
62
Q

Vậy làm thế nào chúng ta thực sự có thể sử dụng Google, hay đúng hơn, làm thế nào chúng ta thực sự có thể sử dụng đệ quy một cách tích cực?

A
63
Q
  1. Hợp nhất sắp xếp
A
64
Q

Nhưng tiềm ẩn trong dòng cuối cùng đó, hợp nhất là một tính năng khá mạnh mẽ của loại này.

A
65
Q

If only one number
Quit
Else
Sort left half of numbers
Sort right half of numbers
Merge sorted halves

A

Mã giả

66
Q

Nếu chúng ta thấy mình có một danh sách, một mảng, có kích thước 1, thì rõ ràng mảng đó đã được sắp xếp.

A
67
Q

Nhưng mầm mống của một ý tưởng thực sự phân chia và chinh phục vấn đề,
1:54:59
không phải là bạn đang gặp vấn đề và chỉ giải quyết một nửa.
Rõ ràng, chúng ta đang sắp xếp một nửa và nửa còn lại
1:55:05
và hợp nhất chúng lại với nhau

A
68
Q
A

Bức tranh hợp nhất sắp xếp
https://imgur.com/uYT9mVu

69
Q

1:55:23 Cuối cùng, tôi đã chia danh sách cỡ 8 đó thành tám danh sách cỡ 1.

A
70
Q

Cuối cùng, tôi đã chia danh sách cỡ 8 đó thành tám danh sách cỡ 1.
1:55:28
Và đó là nơi trường hợp cơ bản bắt đầu và chỉ cần nói, OK, chúng tôi đã sắp xếp xong việc đó. Và sau đó, một cách hợp lý, tôi đã hợp nhất hai danh sách có kích thước 1
1:55:37
thành nhiều danh sách có kích thước 2 và các danh sách có kích thước 2 thành danh sách có kích thước 4. Và cuối cùng, danh sách có kích thước 4 thành một danh sách lớn được sắp xếp có kích thước 8.

A
71
Q

Vì vậy, vào cuối ngày, những khoảng thời gian chạy này liên quan đến sự đánh đổi.

A
72
Q

Trong thực tế, hầu hết các lập trình viên không tự thực hiện các thuật toán sắp xếp này. Kỳ lạ là, họ đang sử dụng một thư viện có sẵn
1:58:30
rằng chính họ đã đưa ra quyết định về việc sẽ thực hiện thuật toán nào trong số các thuật toán này.

A
73
Q
  1. Đánh đổi
A
73
Q
  1. Đánh đổi
A
74
Q

nếu bạn muốn cải thiện thời gian, chẳng hạn như sử dụng ít thời gian hơn, viết mã nhanh hơn, bạn phải trả giá.
1:58:42
Và đó có thể là thời gian của con người bạn, chỉ khiến bạn mất nhiều thời gian hơn để mã hóa thứ gì đó phức tạp hơn, khó thực hiện hơn.
1:58:49
Hoặc bạn cần phải dành một cái gì đó như không gian. Và như những giá sách này gợi ý, đó cũng là một trong những chi tiết chính của sắp xếp hợp nhất.

A