1
00:00:00,000 --> 00:00:05,760

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Vì vậy, trong CS50 chúng tôi đã học về
một loạt các phân loại và tìm kiếm

3
00:00:08,900 --> 00:00:09,442
các thuật toán.

4
00:00:09,442 --> 00:00:11,400
Và đôi khi nó có thể được
một chút khó khăn để giữ

5
00:00:11,400 --> 00:00:14,161
theo dõi của những thuật toán làm gì.

6
00:00:14,161 --> 00:00:15,910
Chúng tôi đã thực sự chỉ
sưa bề mặt quá,

7
00:00:15,910 --> 00:00:18,740
có rất nhiều tìm kiếm khác
và phân loại các thuật toán.

8
00:00:18,740 --> 00:00:21,780
Vì vậy, trong video này chúng ta hãy
chỉ mất một vài phút

9
00:00:21,780 --> 00:00:24,980
để cố gắng và chưng cất mỗi thuật toán
xuống đến các yếu tố cốt lõi của nó

10
00:00:24,980 --> 00:00:27,810
vì vậy bạn có thể nhớ nhất
thông tin quan trọng về họ

11
00:00:27,810 --> 00:00:31,970
và có thể trình bày rõ
sự khác biệt, nếu cần thiết.

12
00:00:31,970 --> 00:00:34,220
>> Việc đầu tiên là sắp xếp chọn.

13
00:00:34,220 --> 00:00:38,210
Ý tưởng cơ bản đằng sau sắp xếp chọn
đang tìm các phần tử nhỏ nhất không được phân loại

14
00:00:38,210 --> 00:00:42,890
trong một mảng và trao đổi nó với
yếu tố không được phân loại đầu tiên của mảng đó.

15
00:00:42,890 --> 00:00:46,620
Chúng tôi cho rằng, trường hợp xấu nhất
chạy thời điểm đó đã được n bình phương.

16
00:00:46,620 --> 00:00:50,060
Và nếu bạn muốn gọi lại lý do tại sao, mất
một nhìn vào video sắp xếp chọn.

17
00:00:50,060 --> 00:00:54,560
Các trường hợp tốt nhất thời gian chạy
cũng được n bình phương.

18
00:00:54,560 --> 00:00:58,910
>> Bubble sort, ý tưởng đằng sau đó
một là để trao đổi cặp liền kề.

19
00:00:58,910 --> 00:01:01,730
Vì vậy, đó là chìa khóa giúp bạn
nhớ sự khác biệt ở đây.

20
00:01:01,730 --> 00:01:04,920
Sắp xếp chọn là, cho đến nay,
tìm thấy những bong bóng smallest--

21
00:01:04,920 --> 00:01:06,790
loại là trao đổi cặp liền kề.

22
00:01:06,790 --> 00:01:08,710
Chúng tôi trao đổi cặp liền kề
của các nguyên tố nếu họ

23
00:01:08,710 --> 00:01:12,530
là ra lệnh, mà hiệu quả
Bong bóng yếu tố lớn hơn bên phải,

24
00:01:12,530 --> 00:01:17,060
và đồng thời nó cũng bắt đầu
để di chuyển các phần tử nhỏ hơn bên trái.

25
00:01:17,060 --> 00:01:20,180
Các trường hợp xấu nhất trường hợp thời gian chạy
các bong bóng sắp xếp được n bình phương.

26
00:01:20,180 --> 00:01:23,476
Các trường hợp tốt nhất thời gian chạy
các bong bóng sắp xếp là n.

27
00:01:23,476 --> 00:01:25,350
Bởi vì trong tình huống đó
chúng tôi không actually--

28
00:01:25,350 --> 00:01:27,141
chúng ta có thể không cần đến
thực hiện bất kỳ giao dịch hoán đổi ở tất cả.

29
00:01:27,141 --> 00:01:31,026
Chúng tôi chỉ phải làm một
vượt qua trên tất cả các yếu tố n.

30
00:01:31,026 --> 00:01:34,600
>> Trong sắp xếp chèn, các
Ý tưởng cơ bản ở đây đang dịch chuyển.

31
00:01:34,600 --> 00:01:36,630
Đó là các từ khóa cho các sắp xếp chèn.

32
00:01:36,630 --> 00:01:39,630
Chúng ta sẽ bước qua một lần
các mảng từ trái sang phải.

33
00:01:39,630 --> 00:01:41,670
Và như chúng tôi, chúng tôi
sẽ thay đổi các yếu tố

34
00:01:41,670 --> 00:01:46,260
chúng ta đã thấy để nhường chỗ cho
những cái nhỏ hơn cần để phù hợp với một nơi nào đó

35
00:01:46,260 --> 00:01:48,080
trở lại trong đó phần được sắp xếp.

36
00:01:48,080 --> 00:01:51,600
Vì vậy, chúng tôi xây dựng các mảng được sắp xếp một
yếu tố tại một thời gian, trái sang phải,

37
00:01:51,600 --> 00:01:54,740
và chúng tôi thay đổi mọi thứ để làm cho căn phòng.

38
00:01:54,740 --> 00:01:58,650
Thời gian chạy trường hợp xấu nhất của
sắp xếp chèn được n bình phương.

39
00:01:58,650 --> 00:02:02,380
Các trường hợp tốt nhất thời gian chạy là n.

40
00:02:02,380 --> 00:02:05,380
>> Merge sort-- từ khóa
ở đây được phân chia và hợp nhất.

41
00:02:05,380 --> 00:02:08,949
Chúng tôi chia các mảng đầy đủ, cho dù
đó là sáu yếu tố, tám yếu tố,

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- chúng tôi chia nó
xuống một nửa, một nửa, một nửa,

43
00:02:13,790 --> 00:02:17,720
cho đến khi chúng tôi có theo mảng
của n một mảng phần tử.

44
00:02:17,720 --> 00:02:19,470
Một tập hợp của n một mảng phần tử.

45
00:02:19,470 --> 00:02:22,640
Vì vậy, chúng ta bắt đầu với một
1.000 phần tử mảng,

46
00:02:22,640 --> 00:02:26,550
và chúng tôi nhận được đến điểm mà chúng ta
có 1.000 mảng một phần tử.

47
00:02:26,550 --> 00:02:30,990
Sau đó, chúng ta bắt đầu kết hợp những mảng phụ
trở lại với nhau theo thứ tự đúng.

48
00:02:30,990 --> 00:02:34,860
Vì vậy, chúng tôi mất hai mảng một phần tử
và tạo ra một mảng hai yếu tố.

49
00:02:34,860 --> 00:02:38,180
Chúng tôi có hai mảng hai phần tử
và tạo ra một mảng bốn phần tử

50
00:02:38,180 --> 00:02:43,900
và như vậy và như vậy cho đến khi chúng tôi đã
một lần nữa xây dựng lại một mảng n phần tử.

51
00:02:43,900 --> 00:02:48,410
>> Thời gian chạy trường hợp xấu nhất của
hợp nhất phân loại là n lần log n.

52
00:02:48,410 --> 00:02:52,390
Chúng tôi có n phần tử, nhưng
quá trình tái hợp này

53
00:02:52,390 --> 00:02:56,960
mất log n bước để có được
sao để một mảng đầy đủ.

54
00:02:56,960 --> 00:03:01,160
Các trường hợp tốt nhất thời gian chạy cũng là n log
n bởi vì quá trình này không thực sự

55
00:03:01,160 --> 00:03:04,090
quan tâm cho dù mảng là
sắp xếp hay không để bắt đầu.

56
00:03:04,090 --> 00:03:07,590
Quá trình này là giống nhau, có
không có cách nào để mọi thứ ngắn mạch.

57
00:03:07,590 --> 00:03:11,610
Vì vậy, n log n trong trường hợp xấu nhất,
n log n trong trường hợp tốt nhất.

58
00:03:11,610 --> 00:03:13,960
>> Chúng tôi nói về hai
tìm kiếm các thuật toán.

59
00:03:13,960 --> 00:03:16,230
Vì vậy, tìm kiếm tuyến tính là khoảng iterating.

60
00:03:16,230 --> 00:03:19,500
Chúng tôi tiến hành trên mảng
một lần, từ trái sang phải,

61
00:03:19,500 --> 00:03:21,950
cố gắng để tìm số
mà chúng ta đang tìm kiếm.

62
00:03:21,950 --> 00:03:24,550
Lần trường hợp xấu nhất chạy là O lớn của n.

63
00:03:24,550 --> 00:03:27,610
Nó có thể đưa chúng ta lặp
qua mọi yếu tố duy nhất

64
00:03:27,610 --> 00:03:30,660
để tìm các phần tử chúng tôi đang tìm kiếm
cho, hoặc là ở vị trí cuối cùng,

65
00:03:30,660 --> 00:03:31,630
hoặc không gì cả.

66
00:03:31,630 --> 00:03:34,720
Nhưng chúng tôi không thể xác nhận rằng cho đến khi
chúng tôi đã xem xét tất cả mọi thứ.

67
00:03:34,720 --> 00:03:36,730
m là trường hợp tốt nhất, chúng tôi tìm thấy ngay lập tức.

68
00:03:36,730 --> 00:03:41,060
Thời gian chạy nhất trường hợp của
tìm kiếm tuyến tính là omega của 1.

69
00:03:41,060 --> 00:03:43,689
>> Cuối cùng, có tìm kiếm nhị phân,
trong đó yêu cầu các loại mảng.

70
00:03:43,689 --> 00:03:45,605
Hãy nhớ rằng một rất
xem xét quan trọng

71
00:03:45,605 --> 00:03:47,155
khi làm việc với tìm kiếm nhị phân.

72
00:03:47,155 --> 00:03:50,180
Đó là một điều kiện tiên quyết để sử dụng it--
mảng mà bạn đang tìm kiếm thông qua

73
00:03:50,180 --> 00:03:52,160
phải được sắp xếp.

74
00:03:52,160 --> 00:03:54,500
Nếu không, các từ khóa
là phân chia và chinh phục.

75
00:03:54,500 --> 00:03:58,310
Chia mảng thành một nửa và
loại bỏ một nửa của các yếu tố

76
00:03:58,310 --> 00:04:00,780
mỗi khi bạn tiến hành thông qua.

77
00:04:00,780 --> 00:04:04,330
Vì sự ngăn cách và chinh phục
và tách thứ trong nửa phương pháp tiếp cận,

78
00:04:04,330 --> 00:04:07,450
trường hợp xấu nhất thời gian chạy
tìm kiếm nhị phân là

79
00:04:07,450 --> 00:04:11,730
log n, đó là đáng kể
tốt hơn so với n tìm kiếm tuyến tính của.

80
00:04:11,730 --> 00:04:13,570
Các trường hợp tốt nhất chạy thời gian vẫn là một.

81
00:04:13,570 --> 00:04:17,010
>> Chúng tôi có thể tìm thấy nó ngay lập tức
Lần đầu tiên chúng tôi làm cho một bộ phận, nhưng,

82
00:04:17,010 --> 00:04:19,339
một lần nữa, hãy nhớ rằng
mặc dù tìm kiếm nhị phân là

83
00:04:19,339 --> 00:04:24,030
tốt hơn đáng kể so với tìm kiếm tuyến tính
nhờ được log n so n,

84
00:04:24,030 --> 00:04:27,110
bạn có thể phải đi qua công việc
phân loại mảng đầu tiên của bạn, mà

85
00:04:27,110 --> 00:04:32,010
có thể làm cho nó kém hiệu quả phụ thuộc
vào kích thước của iterating sắp xếp.

86
00:04:32,010 --> 00:04:35,250
>> Tôi Doug Lloyd, đây là CS50.

87
00:04:35,250 --> 00:04:36,757