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

2
00:00:05,760 --> 00:00:08,900
>> Даг Ллоид: Дакле, у ЦС50 смо научили о
низ сортирање и претраживање

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
Рекли смо да у најгорем случају
рун време које је н квадрат.

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
>> Буббле сорт, идеја иза тога
једна је да замени суседне парове.

19
00:00:58,910 --> 00:01:01,730
Дакле, то је кључ који ће вам помоћи
Сећам се разлика.

20
00:01:01,730 --> 00:01:04,920
Избор врсте је, до сада,
наћи смаллест-- мехур

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
Јер у тој ситуацији
не стварно--

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
>> Мерге сорт-- кључне речи
овде се дели и спојити.

41
00:02:05,380 --> 00:02:08,949
Делимо пуну низ, без обзира да ли
то је шест елемената, осам елемената,

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

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
Тако смо почели са једним
1.000 елемената низ,

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

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
У најгорем случају рун тиме је велики о н.

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
То је предуслов да користи то--
Низ да гледате кроз

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
лог н, што је значајно
боље од линеарног Сеарцх је н.

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
>> Ја сам Доуг Ллоид, ово је ЦС50.

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