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
Мы сказалі, што ў горшым выпадку
запусціць час, што быў н квадраце.

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
Выбар роду ёсць, да гэтага часу,
знайсці 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
Набор N Адзін масіваў элементаў.

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
Час горшы запусціць вялікі вываду п.

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
увайсці н, які, па сутнасці
лепш, чым лінейны пошук у п.

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
значна лепш, чым лінейны пошук
у сілу таго, часопіс N у параўнанні з п,

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