1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Merge Подреди]

2
00:00:02,000 --> 00:00:04,000
[Роб Бауден - Универзитетот Харвард]

3
00:00:04,000 --> 00:00:07,000
[Ова е CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Ајде да зборуваме за спојување вид.

5
00:00:09,000 --> 00:00:14,000
Досега сте виделе меур вид, вметнување вид, и селекција вид.

6
00:00:14,000 --> 00:00:17,000
Иако јас ќе вид на бран мојата рака во она што мислам со подобро,

7
00:00:17,000 --> 00:00:21,000
се спојат вид обично врши подобро од било кој од овие 3 видови.

8
00:00:22,000 --> 00:00:27,000
>> Но, пред да зборуваме за спојување вид, ајде да зборуваме за спојување 2 подредени листи.

9
00:00:27,000 --> 00:00:31,000
Ние ќе го наречеме процесот на преземање 2 подредени списоци, како овие,

10
00:00:31,000 --> 00:00:35,000
и правење еден подредени листа од нив - спојување на листи.

11
00:00:35,000 --> 00:00:37,750
Како можеме да го направите ова?

12
00:00:37,750 --> 00:00:41,290
Па, една идеја е само да се држи една листа кон крајот на другиот листа

13
00:00:41,290 --> 00:00:43,830
а потоа ги сортирате резултат листа.

14
00:00:43,830 --> 00:00:47,220
>> Иако ова функционира, тоа е многу непотребни работи.

15
00:00:47,220 --> 00:00:49,900
Ние можеме да го направи тоа побрзо отколку само сортирање.

16
00:00:49,900 --> 00:00:54,100
Забележете дека една погрешна идеја е само да се наизменични чаши од секоја листа.

17
00:00:54,100 --> 00:00:56,460
Иако тоа може да изгледа како тоа функционира на почетокот,

18
00:00:56,460 --> 00:01:05,760
прави тоа на крајот ќе заврши со 4, 8, 15, 23, 16 - напомена дека 16 и 23 се на место.

19
00:01:05,760 --> 00:01:09,380
Тоа е затоа што 2 елементи кои треба да се појави по ред во претпријатието листа

20
00:01:09,380 --> 00:01:11,720
се во иста почетна листа.

21
00:01:11,720 --> 00:01:14,850
Двете 15 и 16 се во листата на левата страна.

22
00:01:14,850 --> 00:01:19,810
Трикот е да ги искористат предностите на фактот дека двете листи веќе се подредени.

23
00:01:19,810 --> 00:01:23,320
Ова значи дека ако ние само погледнете во првите елементи на двете листи -

24
00:01:23,320 --> 00:01:29,580
тука, 4 и 8 - еден од нив, исто така, мора да биде првиот елемент на споеното листа.

25
00:01:29,580 --> 00:01:31,620
Па, зошто е тоа така?

26
00:01:31,620 --> 00:01:33,520
И двете од овие листи се веќе сортирани,

27
00:01:33,520 --> 00:01:38,410
и тоа или 4 или 8 мора да биде најмалата елемент кога се комбинираат 2 листи.

28
00:01:38,410 --> 00:01:41,770
Во овој случај, најмалата е 4,

29
00:01:41,770 --> 00:01:46,370
така што може да се извади 4 и да ја направат првиот елемент на нашата спои листа.

30
00:01:46,370 --> 00:01:50,710
Сега ние продолжуваме спојување на останатите 3 елементи на првата листа

31
00:01:50,710 --> 00:01:52,920
и 4 елементи на втората листа.

32
00:01:52,920 --> 00:01:57,150
>> Уште еднаш, ние треба само да се погледне на првиот елемент на двете листи.

33
00:01:57,150 --> 00:02:01,060
На помалата од 2 мора да биде вториот елемент на нашата спои листа.

34
00:02:01,060 --> 00:02:05,440
Овој пат, меѓу 8 и 15 од најмалите е 8, и така ние се вметне дека

35
00:02:05,440 --> 00:02:09,240
како втор елемент на нашата подредени листа.

36
00:02:09,240 --> 00:02:12,180
Можеме да продолжиме споредување на првите елементи на двете листи

37
00:02:12,180 --> 00:02:14,420
и отстранување на помали од 2.

38
00:02:14,420 --> 00:02:19,460
Споредба на 15 и 23, 15 е помал и така тоа е нашиот трет елемент.

39
00:02:21,000 --> 00:02:23,910
Сега споредување 16 и 23, 16 е помал.

40
00:02:23,910 --> 00:02:26,820
Значи тоа е четвртиот елемент.

41
00:02:26,820 --> 00:02:30,390
>> Забележете дека 2 елементи доаѓа од истата листа по ред.

42
00:02:30,390 --> 00:02:34,400
Ова е причината зошто на претпријатието листа не може само наизменично елементи од 2 листи.

43
00:02:34,400 --> 00:02:40,020
Споредба на 50 и 23, 23 е помала, па изберете тоа.

44
00:02:40,770 --> 00:02:44,070
Помеѓу 50 и 42, 42 е помал.

45
00:02:44,070 --> 00:02:48,290
Помеѓу 50 и 108, 50 е помал.

46
00:02:48,290 --> 00:02:52,330
И, конечно, треба само 108, па тоа мора да оди на крајот на нашата листа.

47
00:02:53,750 --> 00:02:56,180
Забележете дека ние имаме убаво, подредени листа.

48
00:02:56,180 --> 00:02:59,040
Секој пат кога ние во споредба првите 2 елементи на 2 листи

49
00:02:59,040 --> 00:03:02,730
ние бевме во можност да се утврди следниот елемент на споеното листа.

50
00:03:02,730 --> 00:03:08,070
Ова значи дека ако конечниот список содржи n број, каде што n тука е 8,

51
00:03:08,070 --> 00:03:12,610
тогаш ние треба најмногу n споредби да ги добиете сите од тие бројки во вистинското место.

52
00:03:13,230 --> 00:03:16,230
Како алгоритам се вели да се кандидира во линеарна време,

53
00:03:16,230 --> 00:03:18,090
но не грижете се за тоа тука.

54
00:03:18,570 --> 00:03:22,810
>> Користење на нашата алгоритам за спојување, ние може да се направи брзо спојување вид алгоритам.

55
00:03:22,810 --> 00:03:25,170
Значи, ајде да ги ресетирате нашите листи.

56
00:03:35,210 --> 00:03:37,750
Постојат 2 големи чекори во процесот на спојување вид.

57
00:03:37,750 --> 00:03:41,500
Прво, постојано се подели на листата на чаши во половини

58
00:03:41,500 --> 00:03:44,860
додека имаме еден куп на листи со само 1 чаша во нив.

59
00:03:44,860 --> 00:03:47,350
Не грижете се ако листа содржи непарен број

60
00:03:47,350 --> 00:03:49,880
и не може да се направи совршено чиста сече меѓу нив.

61
00:03:49,880 --> 00:03:53,750
Само произволно изберете која листа да се вклучат дополнителни чаша внатре

62
00:03:53,750 --> 00:03:56,240
Значи, ајде да се подели на овие листи.

63
00:03:58,140 --> 00:04:01,310
Сега имаме 2 листи.

64
00:04:04,120 --> 00:04:06,570
Сега имаме 4 листи.

65
00:04:10,350 --> 00:04:13,870
>> И сега ние имаме 8 листи со еден куп во секоја листа.

66
00:04:13,870 --> 00:04:16,630
Значи тоа е тоа за чекор 1.

67
00:04:16,630 --> 00:04:22,230
За чекор 2, ние постојано се спојат пара листи со користење на алгоритам логирате научивме досега.

68
00:04:22,230 --> 00:04:29,160
Спојување 108 и 15, ќе се заокружи со листа 15, 108.

69
00:04:30,330 --> 00:04:36,250
Спојување 50 и 4, на крајот ќе заврши со 4, 50.

70
00:04:36,960 --> 00:04:41,400
Спојување 8 и 42, на крајот ќе заврши со 8, 42.

71
00:04:42,790 --> 00:04:48,130
И спојување 23 и 16, на крајот ќе заврши со 16, 23.

72
00:04:49,740 --> 00:04:52,450
Сега сите наши листи се на големината 2.

73
00:04:53,020 --> 00:04:56,180
Забележете дека секоја од 4 листи се подредени.

74
00:04:56,180 --> 00:04:59,160
>> Значи можеме да започнеме спојување парови на листи повторно.

75
00:04:59,160 --> 00:05:03,240
Спојување 15 и 108 и 4 и 50 -

76
00:05:03,240 --> 00:05:11,170
Првиот преземе 4, потоа на 15, а потоа на 50, а потоа на 108.

77
00:05:11,170 --> 00:05:15,120
Спојување 8, 42 и 16, 23,

78
00:05:15,120 --> 00:05:22,440
ние прво се земе 8, потоа на 16, а потоа на 23, а потоа на 42.

79
00:05:22,440 --> 00:05:27,370
Така, сега имаме само 2 листи на големина од 4, од кои секоја е сортирана.

80
00:05:27,370 --> 00:05:30,980
Па сега ние се спојат овие 2 листи.

81
00:05:30,980 --> 00:05:33,440
Прво го земеме 4.

82
00:05:33,440 --> 00:05:36,580
Потоа земаме 8.

83
00:05:36,580 --> 00:05:50,700
Потоа земаме 15 и 16, потоа 23, па 42, потоа 50, па 108.

84
00:05:50,700 --> 00:05:52,220
И ние ќе завршиш.

85
00:05:52,220 --> 00:05:54,900
Сега имаме подредени листа.

86
00:05:54,900 --> 00:05:57,890
Значи колку брзо е тоа точно?

87
00:05:57,890 --> 00:06:02,000
Во технички термини, се спојат вид е О (n најавите л),

88
00:06:02,000 --> 00:06:07,380
додека сите на меурот вид, вметнување вид, и селекција вид се О (n ²).

89
00:06:07,380 --> 00:06:11,120
Всушност, како што ќе дознаете наскоро, вие не ќе биде во можност да излезе со еден вид

90
00:06:11,120 --> 00:06:14,820
која врши подобро од О (n најавите л) во општиот случај.

91
00:06:14,820 --> 00:06:19,120
Повторно, не грижете се за овој голем О нотација, ако не сте го виделе досега.

92
00:06:19,120 --> 00:06:23,490
>> Само знам дека ова значи дека ако сакавме да го решите навистина голема листа

93
00:06:23,490 --> 00:06:26,820
меур вид, вметнување вид, и селекција вид би можел да потрае

94
00:06:26,820 --> 00:06:29,500
значително подолго отколку спојат вид.

95
00:06:29,500 --> 00:06:33,210
Тоа не значи дека се спојат вид ќе биде побрз за сите листи

96
00:06:33,210 --> 00:06:36,220
или дури и за било единствен список под одредена големина.

97
00:06:36,220 --> 00:06:41,950
На пример, вметнување вид може да биде најбрз вид за сите листи помали од 5 елементи.

98
00:06:41,950 --> 00:06:47,360
Во пракса, се спојат вид е обично побрзо за листи како мали како 50 елементи.

99
00:06:47,360 --> 00:06:51,120
>> Но, ова екстра брзина не доаѓа без цена.

100
00:06:51,120 --> 00:06:54,770
За разлика од нашите други сорти, кои се на листа и да ја менувате на листата во место

101
00:06:54,770 --> 00:06:58,740
додека да добиеме подредени листата, се спојат вид треба некои дополнителни простор

102
00:06:58,740 --> 00:07:00,900
да се спојат 2 листи заедно.

103
00:07:00,900 --> 00:07:04,690
Ние не можат веднаш да го користите листи, кои се споени за чување на претпријатието листа

104
00:07:04,690 --> 00:07:08,880
бидејќи ние може да ја замени елементи кои допрва треба да бидат споени.

105
00:07:08,880 --> 00:07:13,540
Овој простор е малку на цена, но тоа обично не е неразумно.

106
00:07:13,540 --> 00:07:15,330
И тоа е тоа за спојување вид.

107
00:07:15,330 --> 00:07:18,490
>> Моето име е Роб Бауден, и ова е CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
- И селекција вид.

110
00:07:24,000 --> 00:07:25,880
[Се смее]

111
00:07:25,880 --> 00:07:31,480
О, мора да се земе дека премногу бидејќи јас вклучен како ми е тоа презентирање.

112
00:07:31,480 --> 00:07:35,680
Листа на левата страна. Тоа беше грешка.

113
00:07:35,680 --> 00:07:39,290
[Погрешно ја изговори] Јас ја зезнав -

114
00:07:39,290 --> 00:07:41,190
[Се смее]

115
00:07:41,190 --> 00:07:44,190
Не знам што -