1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] ტომი: მოდით შევხედოთ შერჩევის დახარისხების, ალგორითმი

2
00:00:09,980 --> 00:00:12,800
აღების სიაში ნომრები და დახარისხება მათ.

3
00:00:12,800 --> 00:00:15,750
ალგორითმი, გახსოვდეთ, უბრალოდ ნაბიჯ ნაბიჯ

4
00:00:15,750 --> 00:00:18,370
პროცედურა განხორციელების ამოცანა.

5
00:00:18,370 --> 00:00:21,470
ძირითადი იდეა უკან შერჩევის დალაგების არის გაყავით

6
00:00:21,470 --> 00:00:23,390
ჩვენს სიაში შევიდა ორი ნაწილი -

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

8
00:00:26,810 --> 00:00:30,200
ყოველ ნაბიჯი ალგორითმი, ნომერი გადაინაცვლა

9
00:00:30,200 --> 00:00:33,800
არასორტირებული ნაწილი უნდა დალაგებულია ნაწილი სანამ საბოლოოდ

10
00:00:33,800 --> 00:00:35,880
მთელი სია დალაგებულია.

11
00:00:35,880 --> 00:00:38,510
ასე რომ აქ სიაში ექვსი ნომერი -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8 და 15.

13
00:00:44,010 --> 00:00:47,680
ახლავე სრული სია ითვლება არასორტირებული.

14
00:00:47,680 --> 00:00:51,770
მიუხედავად იმისა, რომ ხმების მოსწონს 16 შესაძლოა უკვე მისი სწორი

15
00:00:51,770 --> 00:00:56,040
საიდან, ჩვენი ალგორითმი აქვს არანაირად არ იცის, რომ სანამ

16
00:00:56,040 --> 00:00:57,980
მთელი სია დალაგებულია.

17
00:00:57,980 --> 00:01:01,355
ამიტომ ჩვენ განიხილოს ყველა ნომერი უნდა არასორტირებული სანამ ჩვენ დასალაგებლად

18
00:01:01,355 --> 00:01:03,800
იგი საკუთარ თავს.

19
00:01:03,800 --> 00:01:06,890
ჩვენ ვიცით, რომ ჩვენ გვინდა სია უნდა იყოს აღმავალი შეკვეთა.

20
00:01:06,890 --> 00:01:10,200
ასე რომ ჩვენ გვინდა, რომ დაამყარონ დახარისხებული ნაწილი ჩვენს სიაში

21
00:01:10,200 --> 00:01:13,280
მარცხნიდან მარჯვნივ, პატარა, რათა უმსხვილესი.

22
00:01:13,280 --> 00:01:17,970
ამისათვის, ჩვენ გვჭირდება, მინიმუმ არასორტირებული ელემენტს

23
00:01:17,970 --> 00:01:21,350
და განათავსოთ დასასრულს დახარისხებული ნაწილი.

24
00:01:21,350 --> 00:01:25,370
მას შემდეგ, რაც ამ სიაში არ არის დახარისხებული, ერთადერთი გზა ამის გაკეთება არის

25
00:01:25,370 --> 00:01:29,330
შეხედეთ თითოეულ ელემენტს არასორტირებული ნაწილი, დამახსოვრების

26
00:01:29,330 --> 00:01:32,010
რომელიც ელემენტს არის ყველაზე დაბალი და შედარებით

27
00:01:32,010 --> 00:01:33,770
ყოველ ელემენტს რომ.

28
00:01:33,770 --> 00:01:36,150
ასე რომ ჩვენ პირველი შევხედოთ 23.

29
00:01:36,150 --> 00:01:38,650
ეს არის პირველი ელემენტს ჩვენ ვნახეთ, ასე რომ ჩვენ გვახსოვს

30
00:01:38,650 --> 00:01:40,050
მას როგორც მინიმუმ.

31
00:01:40,050 --> 00:01:42,320
შემდეგი ჩვენ შევხედოთ 42.

32
00:01:42,320 --> 00:01:46,720
42 აღემატება 23, ასე 23 ჯერ კიდევ მინიმუმ.

33
00:01:46,720 --> 00:01:51,210
შემდეგი არის 4 ნაკლებია 23, ამიტომ ჩვენ გვახსოვს 4

34
00:01:51,210 --> 00:01:52,880
როგორც ახალი მინიმალური.

35
00:01:52,880 --> 00:01:56,380
შემდეგი არის 16 რომელიც აღემატება 4, ასე 4

36
00:01:56,380 --> 00:01:57,980
ჯერ კიდევ მინიმუმ.

37
00:01:57,980 --> 00:02:03,670
8 აღემატება 4 და 15 აღემატება 4, ისე 4 უნდა იყოს

38
00:02:03,670 --> 00:02:05,980
ყველაზე პატარა არასორტირებული ელემენტს.

39
00:02:05,980 --> 00:02:09,350
ასე რომ მიუხედავად იმისა, რომ როგორც ადამიანები შეგვიძლია დაუყოვნებლივ ვხედავთ, რომ 4 არის

40
00:02:09,350 --> 00:02:12,300
მინიმალური ელემენტის, ჩვენი ალგორითმი სჭირდება შევხედოთ

41
00:02:12,300 --> 00:02:15,710
ყველა არასორტირებული ელემენტს შემდეგაც კი, ჩვენ ნაპოვნია 4 -

42
00:02:15,710 --> 00:02:16,860
მინიმალური ელემენტს.

43
00:02:16,860 --> 00:02:19,900
ახლა რომ ჩვენ ი მინიმალური ელემენტს, 4, ჩვენ გვინდა

44
00:02:19,900 --> 00:02:23,410
მისი გადატანა შევიდა დახარისხებული ნაწილი სიაში.

45
00:02:23,410 --> 00:02:27,320
რადგან ეს არის პირველი ნაბიჯი, ეს იმას ნიშნავს, რომ ჩვენ გვინდა დააყენა 4 საათზე

46
00:02:27,320 --> 00:02:29,680
დასაწყისში სიაში.

47
00:02:29,680 --> 00:02:33,040
ახლავე 23 არის დასაწყისში სიაში, ასე

48
00:02:33,040 --> 00:02:36,080
მოდით სვოპ 4 და 23.

49
00:02:36,080 --> 00:02:38,870
ახლა ჩვენს სიაში ასე გამოიყურება.

50
00:02:38,870 --> 00:02:42,710
ჩვენ ვიცით, რომ 4 უნდა იყოს საბოლოო საიდან, რადგან ეს

51
00:02:42,710 --> 00:02:45,890
ორივე პატარა ელემენტს და ელემენტს დასაწყისში

52
00:02:45,890 --> 00:02:46,960
სიის.

53
00:02:46,960 --> 00:02:50,650
ასე რომ, ეს იმას ნიშნავს, რომ ჩვენ არ გვჭირდება ოდესმე მისი გადატანა კიდევ ერთხელ.

54
00:02:50,650 --> 00:02:53,910
მოდით ვიმეორებ, რომ ეს პროცესი დაამატოთ კიდევ ერთი ელემენტი

55
00:02:53,910 --> 00:02:55,910
დახარისხებული ნაწილი სიაში.

56
00:02:55,910 --> 00:02:58,950
ჩვენ ვიცით, რომ ჩვენ არ უნდა შევხედოთ 4, იმიტომ რომ

57
00:02:58,950 --> 00:03:00,000
უკვე დახარისხებული.

58
00:03:00,000 --> 00:03:03,540
ასე რომ ჩვენ შეგვიძლია იწყება 42, რომელიც ჩვენ გვახსოვს, როგორც

59
00:03:03,540 --> 00:03:05,290
მინიმალური ელემენტს.

60
00:03:05,290 --> 00:03:08,700
ასე რომ შემდეგი ჩვენ შევხედოთ 23 ნაკლებია 42, ამიტომ ჩვენ

61
00:03:08,700 --> 00:03:11,620
გვახსოვდეს 23 არის ახალი მინიმალური.

62
00:03:11,620 --> 00:03:14,870
შემდეგი ჩვენ ვხედავთ 16 ნაკლებია 23, ისე

63
00:03:14,870 --> 00:03:16,800
16 არის ახალი მინიმალური.

64
00:03:16,800 --> 00:03:19,720
ახლა ჩვენ შევხედოთ 8 ნაკლებია 16, ისე

65
00:03:19,720 --> 00:03:21,130
8 არის ახალი მინიმალური.

66
00:03:21,130 --> 00:03:25,900
და ბოლოს 8 ნაკლებია, ვიდრე 15, ასე რომ, ჩვენ ვიცით, რომ 8 არის მინიმუმი

67
00:03:25,900 --> 00:03:27,780
არასორტირებული ელემენტს.

68
00:03:27,780 --> 00:03:30,660
ასე რომ, რაც იმას ნიშნავს, რომ ჩვენ უნდა დამატება 8 დან დახარისხებული

69
00:03:30,660 --> 00:03:32,450
ნაწილი სიაში.

70
00:03:32,450 --> 00:03:35,990
ახლავე 4 არის მხოლოდ დახარისხებული ელემენტს, ამიტომ ჩვენ გვინდა განათავსებს

71
00:03:35,990 --> 00:03:38,410
8 შემდეგი 4.

72
00:03:38,410 --> 00:03:41,920
მას შემდეგ, რაც 42 არის პირველი ელემენტია არასორტირებული ნაწილი

73
00:03:41,920 --> 00:03:47,260
სია, ჩვენ გვინდა, რომ სვოპ 42 და 8.

74
00:03:47,260 --> 00:03:49,680
ახლა ჩვენს სიაში ასე გამოიყურება.

75
00:03:49,680 --> 00:03:53,830
4 და 8 წარმოადგენენ დახარისხებული ნაწილი სიაში, და

76
00:03:53,830 --> 00:03:56,440
დარჩენილი ციფრები წარმოადგენენ არასორტირებული

77
00:03:56,440 --> 00:03:58,260
ნაწილი სიაში.

78
00:03:58,260 --> 00:04:00,630
მოდით გავაგრძელოთ სხვა iteration.

79
00:04:00,630 --> 00:04:03,850
ჩვენ დავიწყებთ 23 ამ დროს, რადგან ჩვენ არ გვჭირდება შევხედოთ

80
00:04:03,850 --> 00:04:05,770
4 და 8 უქმნით რადგან ისინი

81
00:04:05,770 --> 00:04:07,660
უკვე დახარისხებული.

82
00:04:07,660 --> 00:04:10,270
16 ნაკლებია, ვიდრე 23, ამიტომ ჩვენ გვახსოვს

83
00:04:10,270 --> 00:04:12,070
16 როგორც მინიმუმ ახალი.

84
00:04:12,070 --> 00:04:18,149
16 ნაკლებია, ვიდრე 42, მაგრამ 15 ზე ნაკლებია 16, ისე 15 უნდა იყოს

85
00:04:18,149 --> 00:04:20,480
მინიმალური არასორტირებული ელემენტს.

86
00:04:20,480 --> 00:04:24,580
ახლა ჩვენ გვინდა სვოპ 15 და 23 დან

87
00:04:24,580 --> 00:04:26,310
მოგვცეს ამ სიაში.

88
00:04:26,310 --> 00:04:30,500
დახარისხებული ნაწილი სია შედგება 4, 8 და 15, და

89
00:04:30,500 --> 00:04:33,210
ამ ელემენტების კვლავ არასორტირებული.

90
00:04:33,210 --> 00:04:36,900
მაგრამ ეს ასე მოხდება, რომ შემდეგი არასორტირებული ელემენტს, 16,

91
00:04:36,900 --> 00:04:38,480
უკვე დახარისხებული.

92
00:04:38,480 --> 00:04:42,060
თუმცა, არ არსებობს გზა ჩვენს ალგორითმი, რათა იცოდეს, რომ 16

93
00:04:42,060 --> 00:04:45,230
უკვე მისი სწორი მდებარეობა, ამიტომ ჩვენ კვლავ უნდა

94
00:04:45,230 --> 00:04:47,870
ვიმეორებ ზუსტად იგივე პროცესი.

95
00:04:47,870 --> 00:04:53,750
ასე რომ, ჩვენ ვხედავთ, რომ 16 ნაკლებია, ვიდრე 42 და 16 არის ნაკლები ვიდრე 23, ისე

96
00:04:53,750 --> 00:04:56,230
16 უნდა იყოს მინიმუმ ელემენტს.

97
00:04:56,230 --> 00:04:59,010
შეუძლებელია სვოპ ამ ელემენტს საკუთარ თავთან, რათა

98
00:04:59,010 --> 00:05:01,780
უბრალოდ დატოვეთ ამ ადგილას.

99
00:05:01,780 --> 00:05:04,660
ამიტომ, ჩვენ გვჭირდება კიდევ ერთი უღელტეხილი ჩვენი ალგორითმი.

100
00:05:04,660 --> 00:05:09,370
42 მეტია 23, ისე 23 უნდა იყოს

101
00:05:09,370 --> 00:05:10,970
მინიმალური არასორტირებული ელემენტს.

102
00:05:10,970 --> 00:05:17,410
ერთხელ ჩვენ სვოპ 23 და 42, ჩვენ დასრულდება მდე ჩვენს საბოლოო

103
00:05:17,410 --> 00:05:18,530
დახარისხებული სია -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
ჩვენ ვიცით, 42 უნდა იყოს სწორი ადგილი, რადგან ეს

106
00:05:26,830 --> 00:05:30,210
მხოლოდ ელემენტს დაუტოვებიათ, და ეს შერჩევის ჯიშია.

107
00:05:30,210 --> 00:05:32,100
მოდით ახლა formalize ჩვენი ალგორითმი რამდენიმე

108
00:05:32,100 --> 00:05:34,540
pseudocode.

109
00:05:34,540 --> 00:05:37,760
On line ერთი, ჩვენ ვხედავთ, რომ ჩვენ გვჭირდება ინტეგრაცია ზე მეტი

110
00:05:37,760 --> 00:05:39,530
ყოველ ელემენტს სიაში.

111
00:05:39,530 --> 00:05:42,150
გარდა ბოლო ელემენტს, რადგან 1 ელემენტს

112
00:05:42,150 --> 00:05:44,230
სიაში უკვე დახარისხებული.

113
00:05:44,230 --> 00:05:48,100
On line ორი, მიგვაჩნია პირველი ელემენტს არასორტირებული

114
00:05:48,100 --> 00:05:51,080
ნაწილი სიაში უნდა იყოს მინიმალური, როგორც გავაკეთეთ ჩვენს

115
00:05:51,080 --> 00:05:53,750
მაგალითად, ასე გვაქვს რაიმე შედარებით.

116
00:05:53,750 --> 00:05:57,260
ხაზი სამი იწყება მეორე მარყუჟის, რომელშიც ჩვენ iterate მეტი

117
00:05:57,260 --> 00:05:59,170
ყოველ არასორტირებული ელემენტს.

118
00:05:59,170 --> 00:06:02,150
ჩვენ ვიცით, რომ მას შემდეგ, რაც მე iterations, დახარისხებული ნაწილი

119
00:06:02,150 --> 00:06:05,330
ჩვენი სიაში უნდა ჰქონდეს მე ელემენტების იგი წლიდან ყოველი ნაბიჯი

120
00:06:05,330 --> 00:06:06,890
ჯიშები ერთ ელემენტს.

121
00:06:06,890 --> 00:06:11,770
ამიტომ პირველ არასორტირებული ელემენტს უნდა იყოს პოზიცია მე პლუს 1.

122
00:06:11,770 --> 00:06:15,440
On line ოთხი, შევადარებთ მიმდინარე ელემენტი მინიმალური

123
00:06:15,440 --> 00:06:17,750
ელემენტს, რომ ჩვენ ვნახეთ ჯერჯერობით.

124
00:06:17,750 --> 00:06:20,560
თუ მიმდინარე ელემენტს მცირეა მინიმალური

125
00:06:20,560 --> 00:06:23,870
ელემენტს, მაშინ ჩვენ გვახსოვს მიმდინარე ელემენტს როგორც ახალი

126
00:06:23,870 --> 00:06:26,250
მინიმალური on line ხუთი.

127
00:06:26,250 --> 00:06:29,900
ბოლოს, ხაზების ექვსი და შვიდი, ჩვენ სვოპ მინიმალური

128
00:06:29,900 --> 00:06:33,080
ელემენტს პირველი არასორტირებული ელემენტს, რითაც

129
00:06:33,080 --> 00:06:36,990
დასძინა, რომ მას დახარისხებული ნაწილი სიაში.

130
00:06:36,990 --> 00:06:40,030
ერთხელ ჩვენ გვყავს ალგორითმი, მნიშვნელოვანი საკითხის ვთხოვო

131
00:06:40,030 --> 00:06:43,370
საკუთარ თავს, როგორც პროგრამისტები არის რამდენ ხანს საერთოდ რომ მიიღოს?

132
00:06:43,370 --> 00:06:46,970
ჩვენ ვთხოვთ პირველი კითხვა, რამდენი ხანი სჭირდება ამ

133
00:06:46,970 --> 00:06:50,070
ალგორითმი გასაშვებად ყველაზე ცუდ შემთხვევაში?

134
00:06:50,070 --> 00:06:51,640
გავიხსენოთ წარმოვადგენთ ამ გაშვებული

135
00:06:51,640 --> 00:06:55,060
ახლა დიდი O ნოტაცია.

136
00:06:55,060 --> 00:06:58,650
დასადგენად მინიმალური არასორტირებული ელემენტს, ჩვენ

137
00:06:58,650 --> 00:07:01,880
არსებითად ჰქონდა შედარების თითოეულ ელემენტს სია

138
00:07:01,880 --> 00:07:04,040
ყველა სხვა ელემენტს სიაში.

139
00:07:04,040 --> 00:07:08,430
ინტუიციურად, ამ ჟღერს O of n კვადრატში ოპერაცია.

140
00:07:08,430 --> 00:07:12,050
ეძებს ჩვენს pseudocode, ჩვენ ასევე გვაქვს loop წყობილი შიგნით

141
00:07:12,050 --> 00:07:14,420
სხვა loop, რომელიც მართლაც ჟღერს O

142
00:07:14,420 --> 00:07:16,480
საქართველოს N კვადრატში ოპერაცია.

143
00:07:16,480 --> 00:07:19,250
თუმცა გახსოვდეთ, რომ ჩვენ არ უნდა გამოიყურებოდეს მეტი

144
00:07:19,250 --> 00:07:23,460
მთელი სია, როდესაც განმსაზღვრელი მინიმალური არასორტირებული ელემენტს?

145
00:07:23,460 --> 00:07:26,600
ერთხელ ჩვენ ვიცოდით, რომ 4 იყო დახარისხებული, მაგალითად, ჩვენ არ

146
00:07:26,600 --> 00:07:28,170
უნდა შევხედოთ ამას კიდევ ერთხელ.

147
00:07:28,170 --> 00:07:31,020
ასე რომ ჯერ ეს ქვედა ქრონომეტრაჟი?

148
00:07:31,020 --> 00:07:34,510
ჩვენი ჩამონათვალი სიგრძე 6, გვჭირდებოდა, რათა ხუთი

149
00:07:34,510 --> 00:07:37,990
შედარებები პირველად ელემენტს, ოთხი შედარებები ამისთვის

150
00:07:37,990 --> 00:07:40,750
მეორე ელემენტს, და ასე შემდეგ.

151
00:07:40,750 --> 00:07:44,690
ეს იმას ნიშნავს, რომ საერთო რაოდენობის ნაბიჯების თანხა

152
00:07:44,690 --> 00:07:49,160
მთელი რიცხვები 1 დან სიგრძე სიის მინუს 1.

153
00:07:49,160 --> 00:07:51,005
ჩვენ შეგვიძლია წარმოადგენენ ამ summation.

154
00:07:57,980 --> 00:07:59,910
ჩვენ არ წასვლას summations აქ.

155
00:07:59,910 --> 00:08:04,900
მაგრამ აღმოჩნდება, რომ ამ summation უდრის N ჯერ

156
00:08:04,900 --> 00:08:07,540
N მინუს 1 ზე 2.

157
00:08:07,540 --> 00:08:14,220
ან equivalently, N კვადრატში მეტი 2 მინუს N ზე 2.

158
00:08:14,220 --> 00:08:18,860
როდესაც ვსაუბრობთ asymptotic runtime, ამ N კვადრატში ვადა

159
00:08:18,860 --> 00:08:22,070
აპირებს დომინირება ამ N ვადით.

160
00:08:22,070 --> 00:08:27,850
ამიტომ შერჩევას დალაგების არის O of n კვადრატში.

161
00:08:27,850 --> 00:08:31,460
შეგახსენებთ, რომ ჩვენს მაგალითში, შერჩევის დალაგების მაინც საჭიროა

162
00:08:31,460 --> 00:08:33,850
შეამოწმეთ თუ ნომერი, რომელიც უკვე დახარისხებული

163
00:08:33,850 --> 00:08:35,450
საჭირო გადავიდა.

164
00:08:35,450 --> 00:08:38,929
ასე რომ, რაც იმას ნიშნავს, რომ თუ ჩვენ გაიქცა შერჩევის დალაგების მეტი უკვე

165
00:08:38,929 --> 00:08:43,070
დახარისხებული სია, ამას სჭირდება იგივე რაოდენობის ნაბიჯები ისე, როგორც ეს

166
00:08:43,070 --> 00:08:46,340
რომ როდესაც გაშვებული მეტი მთლიანად არასორტირებული სიაში.

167
00:08:46,340 --> 00:08:51,470
ამიტომ შერჩევას დალაგების აქვს საუკეთესო შემთხვევაში შესრულება N კვადრატში,

168
00:08:51,470 --> 00:08:56,820
რომელსაც ჩვენ წარმოვადგენთ ერთად omega N კვადრატში.

169
00:08:56,820 --> 00:08:58,600
და ამით ყველაფერი შერჩევის ჯიშია.

170
00:08:58,600 --> 00:09:00,630
მხოლოდ ერთი ბევრი ალგორითმები შეგვიძლია

171
00:09:00,630 --> 00:09:02,390
გამოყენება დასალაგებლად სიაში.

172
00:09:02,390 --> 00:09:05,910
ჩემი სახელი არის ტომი, და ეს არის cs50.