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

2
00:00:05,760 --> 00:00:08,900
>> Дъг LLOYD: Така че в CS50 сме научили за
разнообразие от сортиране и търсене

3
00:00:08,900 --> 00:00:09,442
алгоритми.

4
00:00:09,442 --> 00:00:11,400
И понякога то може да бъде
малко трудно да се запази

5
00:00:11,400 --> 00:00:14,161
следите какво алгоритъм какво прави.

6
00:00:14,161 --> 00:00:15,910
Имаме наистина само
обезмаслено повърхността прекалено,

7
00:00:15,910 --> 00:00:18,740
има много други търсене
и сортиране алгоритми.

8
00:00:18,740 --> 00:00:21,780
Така че в това видео нека
Просто отделете няколко минути,

9
00:00:21,780 --> 00:00:24,980
да се опита да дестилират всеки алгоритъм
надолу към нейните основни компоненти

10
00:00:24,980 --> 00:00:27,810
така че можете да се помни най-много
важна информация за тях

11
00:00:27,810 --> 00:00:31,970
и да може да артикулира
разлики, ако е необходимо.

12
00:00:31,970 --> 00:00:34,220
>> Първият е за избор на сортиране.

13
00:00:34,220 --> 00:00:38,210
Основната идея на подбора на сортиране
се намери най-малката е сортиран елемент

14
00:00:38,210 --> 00:00:42,890
в масив и да го сменяте с
Първият елемент от сортиран, че масив.

15
00:00:42,890 --> 00:00:46,620
Ние казахме, че в най-лошия случай
време на протичане на това е N квадрат.

16
00:00:46,620 --> 00:00:50,060
А ако искате да си припомним защо, вземете
Един поглед към избор на сортиране на видеото.

17
00:00:50,060 --> 00:00:54,560
Времето на най-добрия случай тече
и п е квадрат.

18
00:00:54,560 --> 00:00:58,910
>> Bubble сортиране, идеята зад това
едната е да суап съседни двойки.

19
00:00:58,910 --> 00:01:01,730
Така че това е ключът, който ви помага
не забравяйте разликата тук.

20
00:01:01,730 --> 00:01:04,920
Избор на подреждане е, че досега
намерите smallest-- балон

21
00:01:04,920 --> 00:01:06,790
Сортът е суап съседни двойки.

22
00:01:06,790 --> 00:01:08,710
Ние суап съседни двойки
на елементи, ако

23
00:01:08,710 --> 00:01:12,530
са извън строя, което ефективно
мехурчета по-големи елементи на правото,

24
00:01:12,530 --> 00:01:17,060
и в същото време тя започва също
да се движат по-малки елементи от ляво.

25
00:01:17,060 --> 00:01:20,180
Времето случай продължава, Най-лошият
на метод на мехурчето се п квадрат.

26
00:01:20,180 --> 00:01:23,476
Времето на най-добрия случай тече
на метод на мехурчето е п.

27
00:01:23,476 --> 00:01:25,350
Защото в тази ситуация
ние не actually--

28
00:01:25,350 --> 00:01:27,141
ние не може да се наложи да
прави никакви суапове на всички.

29
00:01:27,141 --> 00:01:31,026
Ние само трябва да се направи една
мине през всички наш елементи.

30
00:01:31,026 --> 00:01:34,600
>> В сортиране чрез вмъкване, на
основната идея тук се измества.

31
00:01:34,600 --> 00:01:36,630
Това е ключовата дума, за сортиране чрез вмъкване.

32
00:01:36,630 --> 00:01:39,630
Отиваме да се оттегли, след като през
масива от ляво на дясно.

33
00:01:39,630 --> 00:01:41,670
И както го правим, ние сме
ще измести елементи

34
00:01:41,670 --> 00:01:46,260
ние вече сме виждали да направи място за
по-малки такива, които трябва да се вмести някъде

35
00:01:46,260 --> 00:01:48,080
обратно в които сортирани порция.

36
00:01:48,080 --> 00:01:51,600
Така че ние се изгради сортиран масив една
елемент в даден момент, от ляво на дясно,

37
00:01:51,600 --> 00:01:54,740
и ние се измести неща, за да направи място.

38
00:01:54,740 --> 00:01:58,650
Времето най-лошия случай на изтичане на
сортиране чрез вмъкване е п квадрат.

39
00:01:58,650 --> 00:02:02,380
Времето на най-добрия случай тече, е п.

40
00:02:02,380 --> 00:02:05,380
>> Обединяване sort-- ключова дума
тук се разделя и се сливат.

41
00:02:05,380 --> 00:02:08,949
Разделяме предлага пълната гама, независимо дали
това е шест елемента, осем елемента,

42
00:02:08,949 --> 00:02:13,790
10000 elements-- ние ги разделим
определени от половината, от половината, от половината,

43
00:02:13,790 --> 00:02:17,720
докато имаме под масив
п един елемент масиви.

44
00:02:17,720 --> 00:02:19,470
Набор от п един елемент масиви.

45
00:02:19,470 --> 00:02:22,640
Така че ние започнахме с една
1000-масив,

46
00:02:22,640 --> 00:02:26,550
и стигнем до точката, където ние
имаме 1000 един елемент масиви.

47
00:02:26,550 --> 00:02:30,990
След това ние започваме да се слеят тези под масиви
отново заедно в правилния ред.

48
00:02:30,990 --> 00:02:34,860
Така че ние се две една-елементни масиви
и създаде две масив.

49
00:02:34,860 --> 00:02:38,180
Ние приемаме два дву-елементни масиви
и да се създаде четири елемент на масив

50
00:02:38,180 --> 00:02:43,900
и така нататък и така нататък, докато ние сме
отново възстановен една п масив.

51
00:02:43,900 --> 00:02:48,410
>> Времето най-лошия случай на изтичане на
сортиране чрез сливане е п пъти вляза п.

52
00:02:48,410 --> 00:02:52,390
Имаме наш елементи, но
този процес рекомбиниране

53
00:02:52,390 --> 00:02:56,960
отнема влезте п стъпки, за да получите
резервно до пълен спектър.

54
00:02:56,960 --> 00:03:01,160
В най-добрия случай тече време е и п дневник
п, защото този процес не е така наистина

55
00:03:01,160 --> 00:03:04,090
интересува дали масива е
сортирано или не да се започне с.

56
00:03:04,090 --> 00:03:07,590
Методът е същият, има
Няма начин да кратки неща верига.

57
00:03:07,590 --> 00:03:11,610
Така че п п влезте в най-лошия случай,
п п влезете в най-добрия случай.

58
00:03:11,610 --> 00:03:13,960
>> Ние говорихме за двама
търсите алгоритми.

59
00:03:13,960 --> 00:03:16,230
Така линейно търсене е около итерации.

60
00:03:16,230 --> 00:03:19,500
Изхождаме от другата страна на масива
веднъж, от ляво на дясно,

61
00:03:19,500 --> 00:03:21,950
опитвайки се да намери броя
че ние не търсим.

62
00:03:21,950 --> 00:03:24,550
В най-лошия случай тече времето е голям O от п.

63
00:03:24,550 --> 00:03:27,610
Тя може да ни отнеме итерации
през всеки един елемент

64
00:03:27,610 --> 00:03:30,660
да намерите елемент, което търсим
за, или на последна позиция,

65
00:03:30,660 --> 00:03:31,630
или не на всички.

66
00:03:31,630 --> 00:03:34,720
Но ние не можем да потвърдим, че до
след като видяхме всичко.

67
00:03:34,720 --> 00:03:36,730
съм най-добрия случай, ние веднага намери.

68
00:03:36,730 --> 00:03:41,060
Времето на най-добрия случай на изтичане на
линейно търсене е омега на 1.

69
00:03:41,060 --> 00:03:43,689
>> На последно място, не е двоично търсене,
която изисква разнообразни масив.

70
00:03:43,689 --> 00:03:45,605
Не забравяйте, че е много
Важно съображение

71
00:03:45,605 --> 00:03:47,155
при работа с двоично търсене.

72
00:03:47,155 --> 00:03:50,180
Това е предпоставка за използване на it--
масива, че търсите чрез

73
00:03:50,180 --> 00:03:52,160
трябва да бъдат сортирани.

74
00:03:52,160 --> 00:03:54,500
В противен случай, ключовата дума
е разделяй и владей.

75
00:03:54,500 --> 00:03:58,310
Разделяне на масива в половината и
премахване на половината от елементите

76
00:03:58,310 --> 00:04:00,780
всеки път, като придвижването ви през.

77
00:04:00,780 --> 00:04:04,330
Поради това разделяй и владей
и разделяне неща в половината подход,

78
00:04:04,330 --> 00:04:07,450
времето на най-лошия случай продължава
на двоично търсене е

79
00:04:07,450 --> 00:04:11,730
влизане N, който е по същество
по-добре от п линейно търсене на.

80
00:04:11,730 --> 00:04:13,570
Времето на най-добрия случай тече все още е един.

81
00:04:13,570 --> 00:04:17,010
>> Бихме могли да го намерят веднага
Първият път, когато се направи разделение, но,

82
00:04:17,010 --> 00:04:19,339
отново, не забравяйте, че
въпреки двоично търсене е

83
00:04:19,339 --> 00:04:24,030
значително по-добре от линеен търсене
по силата на това дневник п спрямо п,

84
00:04:24,030 --> 00:04:27,110
може да се наложи да мине през работата
на сортиране вашия масив първата, която

85
00:04:27,110 --> 00:04:32,010
може да го направи по-малко ефективни в зависимост
от размера на итерации сортирани.

86
00:04:32,010 --> 00:04:35,250
>> Аз съм Дъг Лойд, това е CS50.

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