1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Insertion დალაგების]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [ჰარვარდის უნივერსიტეტის]

3
00:00:04,240 --> 00:00:07,290
[ეს არის CS50.TV]

4
00:00:07,290 --> 00:00:13,060
მოდით შევხედოთ Insertion დახარისხების, ალგორითმი აღების სიაში ნომრები და დახარისხება მათ.

5
00:00:13,060 --> 00:00:18,300
ალგორითმი, გახსოვდეთ, უბრალოდ ნაბიჯ ნაბიჯ პროცედურა განხორციელების ამოცანა.

6
00:00:18,300 --> 00:00:23,640
ძირითადი იდეა უკან Insertion დახარისხების, არის გაყავით ჩვენს სიაში შევიდა ორი ნაწილი, რომლებიც

7
00:00:23,640 --> 00:00:26,580
დახარისხებული ნაწილი და არასორტირებული ნაწილი.

8
00:00:26,580 --> 00:00:29,290
>> ყოველ ნაბიჯი ალგორითმი, ნომერი გადავიდა

9
00:00:29,290 --> 00:00:32,439
საწყისი არასორტირებული ნაწილი უნდა დალაგებულია ნაწილი

10
00:00:32,439 --> 00:00:35,680
სანამ საბოლოოდ მთელი სია დალაგებულია.

11
00:00:35,680 --> 00:00:43,340
აქ არის ჩამონათვალი ექვსი არასორტირებული ნომრები - 23, 42, 4, 16, 8 და 15.

12
00:00:43,340 --> 00:00:47,680
რადგან ეს ციფრები არ არის ყველა აღმავალი შეკვეთა, ისინი არასორტირებული.

13
00:00:47,680 --> 00:00:53,890
ვინაიდან ჩვენ არ დაწყებულა დახარისხება ჯერჯერობით, ჩვენ განიხილავს ექვსივე ელემენტები ჩვენი არასორტირებული ნაწილი.

14
00:00:53,890 --> 00:00:59,270
>> ერთხელ ჩვენ ვიწყებთ დახარისხება, ჩვენ დააყენა ამ დახარისხებული ნომრის მარცხენა ამათგანი.

15
00:00:59,270 --> 00:01:03,600
ასე რომ, დავიწყოთ 23, პირველი ელემენტია ჩვენს სიაში.

16
00:01:03,600 --> 00:01:06,930
ჩვენ არ გვაქვს რაიმე ელემენტების ჩვენი დახარისხებული ნაწილი მაინც,

17
00:01:06,930 --> 00:01:12,460
მოდით უბრალოდ განიხილოს 23 იქნება დაწყების და დასრულების ჩვენი დახარისხებული ნაწილი.

18
00:01:12,460 --> 00:01:16,510
ახლა ჩვენს დახარისხებული ნაწილი აქვს ერთი ნომერი, 23,

19
00:01:16,510 --> 00:01:20,260
და ჩვენი არასორტირებული ნაწილი აქვს ამ ხუთი ნომრები.

20
00:01:20,260 --> 00:01:27,320
მოდით ახლა ჩადეთ შემდეგი რაოდენობის ჩვენს არასორტირებული ნაწილი, 42, შევიდა დახარისხებული ნაწილი.

21
00:01:27,320 --> 00:01:35,930
>> ამისათვის ჩვენ უნდა შეადაროთ 42 დან 23 - მხოლოდ ელემენტს ჩვენს დახარისხებული ნაწილი ჯერჯერობით.

22
00:01:35,930 --> 00:01:41,980
ორმოცდაორ აღემატება 23, ასე რომ ჩვენ შეგვიძლია უბრალოდ დამატება 42 ბოლომდე

23
00:01:41,980 --> 00:01:45,420
საქართველოს დახარისხებული ნაწილი სიაში. მშვენიერია

24
00:01:45,420 --> 00:01:51,850
ახლა ჩვენი დახარისხებული ნაწილი აქვს ორი ელემენტები და ჩვენი არასორტირებული ნაწილი ოთხი ელემენტები.

25
00:01:51,850 --> 00:01:57,200
ასე რომ, მოდით, ახლა გადავა 4, შემდეგი ელემენტია არასორტირებული ნაწილი.

26
00:01:57,200 --> 00:02:00,230
ასე რომ, სადაც უნდა ამ განთავსდება დახარისხებული ნაწილი?

27
00:02:00,230 --> 00:02:04,220
>> გახსოვდეთ, ჩვენ გვინდა განათავსებს ამ რაოდენობის დახარისხებული მიზნით

28
00:02:04,220 --> 00:02:08,680
ამიტომ ჩვენი დახარისხებული ნაწილი რჩება სწორად დალაგებულია ნებისმიერ დროს.

29
00:02:08,680 --> 00:02:14,380
თუ ჩვენ განათავსებს 4 მარჯვნივ 42, მაშინ ჩვენი სიიდან იქნება მწყობრიდან.

30
00:02:14,380 --> 00:02:18,380
ასე რომ, მოდით, გავაგრძელოთ მოძრავი უფლება-ის მარცხენა ჩვენს დალაგების ნაწილი.

31
00:02:18,380 --> 00:02:23,260
როგორც ჩვენ გადავა, მოდით გადაეტანა თითოეული ნომრის ქვემოთ ადგილი, რათა ოთახის ახალი ნომერი.

32
00:02:25,440 --> 00:02:31,740
Okay, 4 ასევე ნაკლები 23, ამიტომ ჩვენ ვერ შეძლებს აქ არც.

33
00:02:31,740 --> 00:02:34,480
მოდით გადაადგილება 23 უფლება ერთ ადგილას.

34
00:02:36,500 --> 00:02:43,120
>> ეს იმას ნიშნავს, ჩვენ გვინდა განვათავსოთ 4 შევიდა პირველი სლოტი წელს დახარისხებული ნაწილი.

35
00:02:43,120 --> 00:02:46,300
შეამჩნევთ, თუ როგორ ამ სივრცეში სიაში იყო უკვე დაცარიელდა,

36
00:02:46,300 --> 00:02:51,120
იმიტომ, რომ ჩვენ უკვე მოძრავი დახარისხებული ელემენტების ქვემოთ როგორც ჩვენ შეექმნა მათ.

37
00:02:51,120 --> 00:02:52,740
ყველა უფლება. ასე რომ, ჩვენ შუა ნაწილამდე იყვნენ იქ.

38
00:02:52,740 --> 00:02:57,990
მოდით გავაგრძელოთ ალგორითმი მიერ ჩასმა 16 შევიდა დახარისხებული ნაწილი.

39
00:02:59,260 --> 00:03:03,820
თექვსმეტი ნაკლებია, ვიდრე 42, მოდით გადაეტანა 42 მარჯვნივ.

40
00:03:05,700 --> 00:03:10,190
თექვსმეტი ასევე ნაკლები 23, მოდით ასევე გადაეტანა, რომ ელემენტს.

41
00:03:11,790 --> 00:03:20,820
>> ახლა, 16 მეტია 4. ასე რომ, როგორც ჩანს მინდა ჩადეთ 16 შორის 4 და 23.

42
00:03:20,820 --> 00:03:24,620
მიუხედავად იმისა, მოძრავი მეშვეობით დახარისხებული ნაწილი სიაში მარჯვნიდან მარცხნივ,

43
00:03:24,620 --> 00:03:29,160
4 არის პირველი ნომერი ჩვენ ვნახეთ, რომ მცირეა ნომერი

44
00:03:29,160 --> 00:03:31,540
ჩვენ ვცდილობთ ჩასასმელად.

45
00:03:31,540 --> 00:03:35,820
ასე რომ, ახლა ჩვენ ჩადეთ 16 ამ ცარიელ ჭრილში,

46
00:03:35,820 --> 00:03:40,520
რომელიც, გახსოვდეთ, ჩვენ მიერ შექმნილი მოძრავი ელემენტების დალაგების ნაწილი დასრულდა

47
00:03:40,520 --> 00:03:43,340
როგორც ჩვენ შეექმნა მათ.

48
00:03:43,340 --> 00:03:47,900
>> ყველა უფლება. ახლა ჩვენ გვყავს ოთხი დახარისხებული ელემენტები და ორი არასორტირებული ელემენტებს.

49
00:03:47,900 --> 00:03:51,600
ასე რომ, მოდით, გადაადგილება 8 შევიდა დახარისხებული ნაწილი.

50
00:03:51,600 --> 00:03:55,010
რვა ნაკლებია, ვიდრე 42.

51
00:03:55,010 --> 00:03:56,940
რვა ნაკლებია, ვიდრე 23.

52
00:03:56,940 --> 00:04:00,230
და 8 ნაკლებია, ვიდრე 16.

53
00:04:00,230 --> 00:04:03,110
მაგრამ 8 მეტია 4.

54
00:04:03,110 --> 00:04:07,280
ასე რომ, მინდა ჩადეთ 8 შორის 4 და 16.

55
00:04:09,070 --> 00:04:13,650
და ახლა ჩვენ უბრალოდ კიდევ ერთი ელემენტს დაუტოვებიათ დასალაგებლად - 15.

56
00:04:13,950 --> 00:04:16,589
თხუთმეტი ნაკლებია, ვიდრე 42,

57
00:04:16,589 --> 00:04:19,130
თხუთმეტი ნაკლებია, ვიდრე 23.

58
00:04:19,130 --> 00:04:21,750
და 15 ზე ნაკლებია 16.

59
00:04:21,750 --> 00:04:24,810
მაგრამ 15 მეტია 8.

60
00:04:24,810 --> 00:04:27,440
>> ასე რომ, აქ არის, სადაც ჩვენ გვინდა, რომ ჩვენი საბოლოო Insertion.

61
00:04:28,770 --> 00:04:30,330
და ჩვენ გავაკეთეთ.

62
00:04:30,330 --> 00:04:33,540
ჩვენ არ გვაქვს მეტი ელემენტების არასორტირებული ნაწილი,

63
00:04:33,540 --> 00:04:36,670
და ჩვენი დახარისხებული ნაწილი არის სწორი მიზნით.

64
00:04:36,670 --> 00:04:40,270
ციფრები დავალება ყველაზე პატარა რომ უდიდესი.

65
00:04:40,270 --> 00:04:44,330
ასე რომ, მოდით შევხედოთ ზოგიერთი pseudocode რომელიც ასახავს ნაბიჯებით ჩვენ მხოლოდ შესრულებული.

66
00:04:46,760 --> 00:04:51,740
>> On line 1, ვხედავთ, რომ ჩვენ გვჭირდება iterate მეტი თითოეული ელემენტის სიაში

67
00:04:51,740 --> 00:04:57,060
გარდა პირველი, რადგან პირველი ელემენტია არასორტირებული ნაწილი უბრალოდ გახდეს

68
00:04:57,060 --> 00:05:00,220
პირველი ელემენტია დახარისხებული ნაწილი.

69
00:05:00,220 --> 00:05:06,320
On ხაზები 2 და 3, ჩვენ შენახვა ტრეკზე ჩვენი დღევანდელი ადგილი არასორტირებული ნაწილი.

70
00:05:06,320 --> 00:05:10,450
Element წარმოადგენს პუნქტების ჩვენ გაკეთებული მოძრავი შევიდა დახარისხებული ნაწილი,

71
00:05:10,450 --> 00:05:15,600
და კ წარმოადგენს ჩვენი ინდექსი შევიდა არასორტირებული ნაწილი.

72
00:05:15,600 --> 00:05:20,980
>> On line 4, ჩვენ iterating მეშვეობით დახარისხებული ნაწილი მარჯვნიდან მარცხნივ.

73
00:05:20,980 --> 00:05:26,010
ჩვენ გვინდა, რომ შეწყვიტოს iterating ერთხელ ელემენტს მარცხნივ ჩვენი მიმდინარე თანამდებობა

74
00:05:26,010 --> 00:05:30,050
ნაკლებია, ვიდრე ელემენტს ვცდილობთ ჩადეთ.

75
00:05:30,050 --> 00:05:35,600
On line 5, ჩვენ გადავიდა ყოველ ელემენტს ვხვდებით ერთ სივრცეში უფლება.

76
00:05:35,600 --> 00:05:40,950
ამ გზით, ჩვენ გვექნება ნათელი სივრცე INSERT INTO როდესაც ჩვენ პირველად ელემენტს

77
00:05:40,950 --> 00:05:44,080
ნაკლებია, ვიდრე ელემენტს ჩვენ მოძრავი.

78
00:05:44,080 --> 00:05:50,800
On line 6, ჩვენ განახლებაზე ჩვენი Counter გააგრძელოს გადაადგილება დაუტოვებიათ მეშვეობით დახარისხებული ნაწილი.

79
00:05:50,800 --> 00:05:56,860
საბოლოოდ, on line 7, ჩვენ ჩასმა ელემენტს შევიდა დახარისხებული ნაწილი სიაში.

80
00:05:56,860 --> 00:06:00,020
>> ჩვენ ვიცით, რომ ეს okay ჩასასმელად შევიდა პოზიცია j,

81
00:06:00,020 --> 00:06:05,360
იმიტომ, რომ ჩვენ უკვე გადავიდა ელემენტს, რომლებიც იქ ერთ სივრცეში უფლება.

82
00:06:05,360 --> 00:06:09,460
გახსოვდეთ, ჩვენ მოძრავი მეშვეობით დახარისხებული ნაწილი მარჯვნიდან მარცხნივ,

83
00:06:09,460 --> 00:06:13,960
მაგრამ ჩვენ მოძრავი მეშვეობით არასორტირებული ნაწილი მარცხნიდან მარჯვნივ.

84
00:06:13,960 --> 00:06:19,090
ყველა უფლება. მოდით ახლა შეხედეთ, რამდენი ხანი გაშვებული რომ ალგორითმი აიღო.

85
00:06:19,090 --> 00:06:25,300
ჩვენ ვთხოვთ პირველი კითხვა, რამდენი ხანი სჭირდება ამ ალგორითმის გასაშვებად ყველაზე ცუდ შემთხვევაში.

86
00:06:25,300 --> 00:06:29,040
შეგახსენებთ, რომ წარმოვადგენთ ამ გაშვებული დროის დიდი O ნოტაცია.

87
00:06:32,530 --> 00:06:38,500
იმისათვის, რომ დასალაგებლად ჩვენს სიაში, მოგვიწია iterate მეტი ელემენტების არასორტირებული ნაწილი,

88
00:06:38,500 --> 00:06:43,430
და თითოეული იმ ელემენტებს, პოტენციურად ყველა ელემენტების დახარისხებული ნაწილი.

89
00:06:43,430 --> 00:06:47,950
ინტუიციურად, ამ ჟღერს O (N ^ 2) ოპერაცია.

90
00:06:47,950 --> 00:06:51,840
>> ეძებს ჩვენს pseudocode, ჩვენ გვაქვს loop წყობილი შიგნით კიდევ ერთი მარყუჟი,

91
00:06:51,840 --> 00:06:55,290
რაც, რა თქმა უნდა, ჟღერს O (N ^ 2) ოპერაცია.

92
00:06:55,290 --> 00:07:01,590
თუმცა, დახარისხებული ნაწილი სიაში არ შეიცავს მთელ სიაში, სანამ ბოლომდე.

93
00:07:01,590 --> 00:07:06,920
მიუხედავად ამისა, ჩვენ შესაძლოა ჩადეთ ახალ ელემენტს დროს ძალიან დასაწყისში დახარისხებული ნაწილი

94
00:07:06,920 --> 00:07:09,320
ყოველ iteration of ალგორითმი,

95
00:07:09,320 --> 00:07:14,500
რაც იმას ნიშნავს, რომ ჩვენ გვინდა უნდა შევხედოთ თითოეული ელემენტის ამჟამად დახარისხებული ნაწილი.

96
00:07:14,500 --> 00:07:20,090
ასე რომ, ეს ნიშნავს, რომ ჩვენ შესაძლოა ერთი შედარებით მეორე ელემენტს,

97
00:07:20,090 --> 00:07:24,660
ორი შედარებები მესამე ელემენტს, და ასე შემდეგ.

98
00:07:24,660 --> 00:07:32,480
ასე რომ, სულ რამდენიმე ისეთი ნაბიჯი არის თანხა რიცხვებით 1 დან სიგრძე სიის მინუს 1.

99
00:07:32,480 --> 00:07:35,240
ჩვენ შეგვიძლია წარმოადგენენ ამ summation.

100
00:07:41,170 --> 00:07:47,270
>> ჩვენ არ წასვლას summations აქ, მაგრამ აღმოჩნდება, რომ ამ summation უდრის

101
00:07:47,270 --> 00:07:57,900
n (n - 1) მეტი 2, რომელიც უდრის N ^ 2/2 - N / 2.

102
00:07:57,900 --> 00:08:00,800
როდესაც ვსაუბრობთ asymptotic Runtime,

103
00:08:00,800 --> 00:08:05,170
ამ N ^ 2 ვადით აპირებს დომინირება ამ N ვადით.

104
00:08:05,170 --> 00:08:11,430
ასე რომ, Insertion დალაგების არის დიდი O (N ^ 2).

105
00:08:11,430 --> 00:08:16,150
რა მოხდება, თუ ჩვენ გაიქცა Insertion დალაგების შესახებ უკვე დახარისხებული სია.

106
00:08:16,150 --> 00:08:20,960
ამ შემთხვევაში, ჩვენ გვინდა უბრალოდ დაამყარონ დახარისხებული ნაწილი მარცხნიდან მარჯვნივ.

107
00:08:20,960 --> 00:08:25,050
ასე რომ, ჩვენ მხოლოდ უნდა ბრძანებით N ნაბიჯები.

108
00:08:25,050 --> 00:08:29,740
>> ეს იმას ნიშნავს, რომ Insertion დალაგების აქვს საუკეთესო შემთხვევაში შესრულება N,

109
00:08:29,740 --> 00:08:34,130
რომელსაც ჩვენ წარმოვადგენთ ერთად Ω (N).

110
00:08:34,130 --> 00:08:36,190
სწორედ ეს Insertion დახარისხების,

111
00:08:36,190 --> 00:08:40,429
მხოლოდ ერთი ბევრი ალგორითმები ჩვენ შეგვიძლია გამოვიყენოთ დასალაგებლად სიაში.

112
00:08:40,429 --> 00:08:43,210
ჩემი სახელი არის ტომი, და ეს არის CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
ოჰ, თქვენ უბრალოდ ვერ შეაჩერებს, რომ ერთხელ იწყება.

115
00:09:01,620 --> 00:09:04,760
ოჰ, ჩვენ რომ - >> BooM!