1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: دعونا نلقي نظرة على نوع الاختيار، خوارزمية

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، SO 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
لذلك دعونا مواصلة التكرار آخر.

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
الجزء مصنفة من قائمة تتألف من 8 و 4 و 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
دعونا الآن إضفاء الطابع الرسمي على خوارزمية لدينا مع بعض

108
00:05:32,100 --> 00:05:34,540
شبة الكود.

109
00:05:34,540 --> 00:05:37,760
على سطر واحد، يمكننا أن نرى أننا في حاجة إلى دمج أكثر من

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
على السطر الثاني، نرى أن العنصر الأول من لم يتم فرزها

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
ونحن نعلم أن بعد أن التكرار، الجزء مصنفة

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
على خط الأربعة، قارنا العنصر الحالي إلى الحد الأدنى

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
الحد الأدنى على السطر الخامس.

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 ن المربعة.

140
00:07:08,430 --> 00:07:12,050
أبحث في شبة الكود لدينا، لدينا أيضا حلقة متداخلة داخل

141
00:07:12,050 --> 00:07:14,420
آخر حلقة، الذي يبدو في الواقع وكأنه O

142
00:07:14,420 --> 00:07:16,480
ن عملية المربعة.

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، نحن في حاجة لجعل 5

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
يمكننا تمثيل هذا مع الجمع.

154
00:07:57,980 --> 00:07:59,910
ونحن لن نذهب إلى summations هنا.

155
00:07:59,910 --> 00:08:04,900
ولكن تبين أن هذا الجمع يساوي أضعاف ن

156
00:08:04,900 --> 00:08:07,540
ن ناقص 1 أكثر من 2.

157
00:08:07,540 --> 00:08:14,220
أو مكافئ، N تربيع ناقص أكثر من 2 ن أكثر من 2.

158
00:08:14,220 --> 00:08:18,860
عندما نتحدث عن وقت مقارب، وهذا المصطلح ن التربيعية

159
00:08:18,860 --> 00:08:22,070
سوف تهيمن على هذا المصطلح ن.

160
00:08:22,070 --> 00:08:27,850
ذلك النوع من الاختيار هو O ن المربعة.

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
ذلك نوع الاختيار لديه أداء أفضل حالة ن مربع،

168
00:08:51,470 --> 00:08:56,820
التي نمثلها مع أوميغا ن المربعة.

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.