Original subtitles

1 1

(موسيقى خفيفة) 2

2

(نقر لوحة المفاتيح) 3

3

حسنًا ، في بعض مقاطع الفيديو 4

4

سنبدأ في البحث في خوارزميات الفرز ، 5

5

وسيكون من المفيد حقًا أن نكون كذلك 6

6

قادرة على مقارنة أداء خوارزمية واحدة 7

7

ضد خوارزمية أخرى. 8

8

لذلك قد تعتقد أن طريقة واحدة يمكننا القيام بذلك 9

9

هو تنفيذ خوارزمية واحدة ثم وضع سطر من التعليمات البرمجية 10

10

يسجل وقت البدء ثم تشغيل التنفيذ 11

11

وبعد ذلك يكون لديك سطر من التعليمات البرمجية يسجل وقت الانتهاء 12

12

ويمكننا طرح وقت البدء من وقت الانتهاء 13

13

ونحصل على وقت تشغيل التنفيذ 14

14

من تلك الخوارزمية. 15

15

ثم نفعل الشيء نفسه مع خوارزمية أخرى 16

16

ونقارن بين الاثنين فقط. 17

17

يبدو رائعا من الناحية النظرية ولكن لسوء الحظ 18

18

هذه ليست طريقة جيدة للقيام بذلك بسبب الأجهزة. 19

19

ستؤثر الأجهزة على وقت التشغيل 20

20

من هذه الخوارزميات. 21

21

. أعني، فكر في ذلك 22

22

إذا أردنا تشغيل تنفيذ على كمبيوتر سطح المكتب 23

23

التي تم بناؤها في عام 2017 وقارن ذلك 24

24

إلى وقت تشغيل نفس التنفيذ بالضبط 25

25

على جهاز كمبيوتر مكتبي تم إنشاؤه قبل 20 عامًا 26

26

وربما كان كمبيوتر بنتيومًا قديمًا ، 27

27

أو حتى نذهب أبعد من ذلك ونركض 28

28

التنفيذ على Commodore 64 أو شيء من هذا القبيل ، 29

29

من الواضح أن التطبيقات ستعمل بشكل أبطأ 30

30

على الأجهزة القديمة. 31

31

وإذا أردنا تنفيذ تنفيذ على جهاز كمبيوتر فائق ، 32

32

ستعمل بسرعة كبيرة على الرغم من ذلك 33

33

قد تكون خوارزمية غير فعالة حقًا. 34

34

لذلك نحن بحاجة إلى مقياس أكثر موضوعية 35

35

من مجرد وقت التشغيل المباشر. 36

36

وما نفعله هو أن ننظر إلى عدد الخطوات 37

37

التي يتطلبها تنفيذ الخوارزمية. 38

38

ونسمي هذا تعقيد الوقت. 39

39

هناك نوعان من التعقيد: 40

40

هناك تعقيد زمني وهو العدد 41

41

من الخطوات المتبعة لتشغيل الخوارزمية ؛ 42

42

ثم هناك تعقيد الذاكرة وهو المقدار 43

43

من الذاكرة اللازمة لتشغيل خوارزمية. 44

44

الآن هذه الأيام ، لأن الذاكرة رخيصة جدًا ، 45

45

تعقيد الذاكرة ليس مثل هذه المشكلة. 46

46

لذلك نحن في هذه الأيام نهتم بأنفسنا بشكل رئيسي 47

47

مع تعقيد الوقت. 48

48

لذلك نحن مهتمون بعدد الخطوات التي يستغرقها ذلك 49

49

لتشغيل خوارزمية؟ 50

50

الآن عندما نفعل ذلك ، نود أن ننظر في أسوأ الحالات. 51

51

إن النظر إلى أفضل حالة لا يساعدنا لأنه 52

52

نادرًا ما تحصل على أفضل حالة. 53

53

الآن يمكننا أن نأخذ متوسط ​​الحالة 54

54

لكن هذا لن يخبرنا بالمطلق 55

55

أسوأ تعقيد زمني. 56

56

إذا أردنا معرفة الحد الأعلى ، 57

57

مثل ما هو أسوأ ما يمكن أن نتوقعه 58

58

من هذه الخوارزمية ، إنها مفيدة أكثر 59

59

للنظر في أسوأ الحالات. 60

60

لذلك من المفيد مقارنة السيناريو الأسوأ 61

61

لخوارزمية واحدة ضد السيناريو الأسوأ 62

62

للخوارزمية الأخرى. 63

63

وهذه هي الطريقة التي نقوم بها. 64

64

لذلك دعونا نلقي نظرة على الخوارزمية 65

65

التي أعرضها على هذه الشاشة. 66

66

لقد بحثنا بالفعل في خوارزمية لصنع الشاي 67

67

لذا سننظر الآن في خطوة واحدة صغيرة. 68

68

ولدينا خوارزمية لإضافة السكر إلى الشاي. 69

69

لذا في هذه الخوارزمية ، الخطوة الأولى هي الحصول على الوعاء 70

70

تحتوي على السكر. 71

71

الخطوة الثانية هي الحصول على ملعقة. 72

72

لذلك نفترض أن لدينا سكرًا سائبًا هنا. 73

73

الخطوة الثالثة هي استخلاص السكر باستخدام الملعقة ، 74

74

والخطوة الرابعة هي صب السكر 75

75

من الملعقة إلى الشاي. 76

76

وطبعا إذا كنت تريد أكثر من ملعقة شاي 77

77

ثم عليك أن تكرر الخطوتين الثالثة والرابعة 78

78

حتى تضيف الكمية المرغوبة من السكر. 79

79

يمكننا الآن أن نرى من هذا أن عدد الخطوات 80

80

أنه سيتطلب إضافة السكر إلى الشاي الخاص بك 81

81

ستعتمد على عدد السكريات التي تريدها. 82

82

إذا كنت تريد سكرًا واحدًا فقط ، 83

83

ثم ستعمل هذه الخوارزمية بأربع خطوات. 84

84

ولكن إذا كنت تريد سكرين ، 85

85

سوف يستغرق ست خطوات لأن 86

86

سيتعين عليك تكرار الخطوتين الثالثة والرابعة. 87

87

لذلك دعونا نلقي نظرة على ما يحدث 88

88

لعدد السكريات. 89

89

لذلك إذا كان لديك سكر واحد ، ما عليك سوى القيام بأربع خطوات. 90

90

إذا كان لديك نوعان من السكر ، فستحتاج إلى ست خطوات. 91

91

إذا كنت تريد ثلاثة أنواع من السكريات في الشاي 92

92

ستحتاج إلى ثماني خطوات لأنك ستفعل 93

93

يجب أن تكرر الخطوتين الثالثة والرابعة ثلاث مرات. 94

94

وإذا كنت تريد أربعة سكريات في الشاي الخاص بك ، 95

95

أنا متأكد من أن معظمنا كان سيخرج بكفالة الآن ، 96

96

لكن لدي صديق أقول أنه يأخذ 97

97

الشاي مع السكر لها وليس العكس. 98

98

لذلك قد تصل إلى الصف الرابع. 99

99

إذا كنت تريد أربعة سكريات في الشاي الخاص بك ، 100

100

ثم سيتعين عليك التكرار 101

101

الخطوتين الثالثة والرابعة أربع مرات. 102

102

ولذا سوف تتخذ 10 خطوات 103

103

لوضع السكر في الشاي الخاص بك. 104

104

هكذا يمكننا أن نرى عدد الخطوات 105

105

أو التعقيد الزمني لخوارزمية السكر لدينا 106

106

يعتمد على عدد السكريات التي يريدها شخص ما في الشاي. 107

107

إذا كانوا يريدون سكرًا واحدًا فقط ، 108

108

يستغرق الأمر منهم أربع خطوات فقط. 109

109

لكن إذا أرادوا أربعة أنواع من السكريات ، فسيتخذون 10 خطوات. 110

110

لذا فإن تعقيد الوقت يعطينا فكرة 111

111

حول كيفية أداء الخوارزمية كعدد العناصر 112

112

عليه أن يتعامل مع النمو كما نرى 113

113

كعدد السكريات التي يجب أن تضيفها هذه الخوارزمية 114

114

إلى الشاي ، يزداد عدد الخطوات المطلوبة. 115

115

طريقة أخرى لقول هذا هو أنه يخبرنا 116

116

مدى جودة الخوارزمية. 117

117

إذن ما مدى نجاحها عندما يتعين عليها التعامل 118

118

مع 100 عنصر مقابل 1،00 عنصر مقابل مليون عنصر؟ 119

119

وسنرى أن بعض الخوارزميات ستتوسع بشكل جيد حقًا 120

120

والبعض الآخر ليس جيدًا. 121

121

كلما زاد عدد العناصر ، 122

122

كلما انخفض أداء الخوارزمية. 123

123

الآن تدوين O الكبير هو وسيلة للتعبير 124

124

التعقيد المرتبط بعدد العناصر 125

125

أن الخوارزمية يجب أن تتعامل معها. 126

126

وهي مكتوبة برأس مال O 127

127

متبوعًا بتعبير بين قوسين. 128

128

لذلك دعونا نحسب قيمة O الكبيرة لخوارزمية السكر لدينا. 129

129

لذلك من المعتاد تحديد عدد العناصر بواسطة N. 130

130

لذلك في حالتنا ، فإن عدد السكريات المرغوبة سوف يساوي N. 131

131

وكما نرى من طاولتنا 132

132

ومن خوارزميتنا هنا ، 133

133

عدد الخطوات سيكون مرتين في N زائد اثنين. 134

134

والسبب في ذلك هو أن عليك التكرار 135

135

الخطوتين الثالثة والرابعة لعدد السكريات التي لديك ، 136

136

لذلك هذا هو اثنان N. 137

137

ثم زائد اثنين هو الخطوتين واحد واثنين. 138

138

الآن كما رأينا عندما ينمو N ، يزداد عدد الخطوات. 139

139

الآن لاحظ أن الاثنين ، 140

140

سيكون من الصعب علي أن أقول ، 141

141

لكن الاثنين في اثنين N زائد اثنين ، 142

142

تظل ثابتة. 143

143

لا تتغير مع تغير عدد السكريات. 144

144

وبسبب ذلك فإننا لا نعتبرهم 145

145

عندما نتوصل إلى قيمة O الكبيرة. 146

146

إن N هو الذي يؤثر على عدد الخطوات. 147

147

ولذا في هذه الحالة نقول أن الوقت معقد 148

148

لهذه الخوارزمية هي O لـ N. 149

149

ولأن التعقيد الزمني لهذه الخوارزمية 150

150

يزيد بشكل خطي ، 151

151

نحن نعتبر هذا تعقيدًا زمنيًا خطيًا. 152

152

لذا فإن التعقيد الزمني لـ O لـ N هو تعقيد زمني خطي. 153

153

وإذا عدنا إلى طاولتنا ، 154

154

سنرى أننا نذهب أربعة ، ستة ، ثمانية ، 10 155

155

وبالطبع سنستمر ، 12 ، 14 ، 16 ، 18. 156

156

هذا تسلسل خطي ، إنه تسلسل خطي. 157

157

وبالتالي التعقيد الزمني للسكريات المضافة 158

158

إلى خوارزمية الشاي هي O من N. 159

159

هذه هي قيم O الكبيرة 160

160

سنرى بشكل أساسي في هذه الدورة. 161

161

لديك O من واحد وهو تعقيد زمني مستمر ، 162

162

O من لوغاريتم N أي تعقيد زمني لوغاريتمي ، 163

163

وهذا هو log للأساس اثنين وليس للأساس 10. 164

164

إذن فهو لوغاريتم ن للأساس اثنين. 165

165

O لـ N وهو تعقيد زمني خطي. 166

166

ثم لدينا O لـ N log N 167

167

وهو N مرات لوغاريتم القاعدة اثنين N ، 168

168

وهذا التعقيد الزمني لنجوم تسجيل نون ن. 169

169

ولدينا O لـ N تربيع 170

170

وهو تعقيد زمني من الدرجة الثانية. 171

171

ستلاحظ أنه عندما ننظر إلى خوارزميات الفرز ، 172

172

في الواقع ، ستكون المراتب القليلة الأولى التي ننظر إليها تربيعية. 173

173

والترتيب في الجدول من الأفضل إلى الأسوأ. 174

174

لذلك إذا كان بإمكانك استخدام خوارزمية وقت ثابت 175

175

هذه طريقة أفضل من خوارزمية الوقت التربيعية. 176

176

الآن كما قلت ، سمعتني أقول: O of one and O of N، 177

177

هكذا تقولها. 178

178

O ثم القيمة الموجودة بين قوسين. 179

179

الآن عندما تعلمت عن تدوينات O الكبيرة ، 180

180

لسبب ما الشخص الذي يقوم بتدريس المعلومات 181

181

بدلاً من ذلك قال O للواحد ، O لـ N. 182

182

وهكذا تم حفر ذلك في رأسي 183

183

وهي عادة يصعب التخلص منها. 184

184

تدوين O الكبير ، إنه نوع من الأشياء 185

185

ليس عليك قولها معظم الوقت 186

186

أنت تقرأه أو تكتبه. 187

187

لذا فإن الطريقة الصحيحة لقولها هي O of one، O of N، 188

188

O من السجل N ، وما إلى ذلك. 189

189

لكنني سأخطئ في بعض الأحيان 190

190

ونقول يا لأن هذا ما كان 191

191

حفرت في رأسي عندما تعلمت هذه المادة. 192

192

ولذا إذا سمعتني أقول ذلك ، 193

193

إذا سمعتني أقول O للواحد ، 194

194

O إلى مربع N ، وما إلى ذلك ، 195

195

فقط قم بتحويل ذلك إلى O في عقلك. 196

196

هناك احتمالات أنك لن تحصل عليه أبدًا في الواقع 197

197

لقول هذا من أي وقت مضى. 198

198

طوال مسيرتي المهنية بالكامل لم أضطر أبدًا إلى قول "O" من أي شيء. 199

199

في الواقع ، لم نناقش مرة واحدة في حياتي المهنية بأكملها 200

200

تدوين كبير يا. 201

201

أنا متأكد من أن اعتمادًا على نوع ملفات 202

202

التطبيق الذي تعمل عليه ، 203

203

قد يكون ذلك مختلفًا بالنسبة لك. 204

204

لكن في مسيرتي المهنية ، كانت تدوينات O الكبيرة نوعًا ما ليست مشكلة. 205

205

لم يكن أبدًا شيئًا نحتاج إلى القلق بشأنه. 206

206

ولذا إذا كنت تتحدث إلى شخص ما 207

207

ويسألونك عن تدوين O الكبير 208

208

أو قيم O الكبيرة تقول O من. 209

209

وإذا سمعتني أقول "أوه" في هذه الدورة ، 210

210

فقط قم بتحويل ذلك إلى O لـ. 211

211

فلننتقل الآن إلى ويكيبيديا 212

212

حتى نتمكن بالفعل من رؤية قيم O الكبيرة 213

213

على رسم بياني حتى نتمكن من الحصول على فكرة بصرية 214

214

الاختلافات بين قيم O الكبيرة المختلفة. 215

215

أنا هنا في ويكيبيديا وستجد هذه الصورة 216

216

في مقالة ويكيبيديا حول تدوين O الكبير 217

217

وقمت أيضًا بتضمين رابط مباشر لهذه الصورة 218

218

في قسم الموارد. 219

219

تم إنشاء هذه الصورة بواسطة المستخدم Cmglee. 220

220

وهذا رسم بياني لبعض قيم O الكبيرة ، 221

221

وهذا يمثل كيفية تدهور الخوارزمية. 222

222

على طول المحور X لدينا حجم الإدخال ، 223

223

وبالتالي فإن عدد العناصر ؛ 224

224

وعلى طول المحور ص لدينا عدد الخطوات. 225

225

لذلك يمكنك أن ترى خوارزمية ثابتة ، 226

226

يا من واحد في هذا اللون البنفسجي ، 227

227

مع زيادة عدد العناصر 228

228

عدد الخطوات يبقى كما هو. 229

229

هذا مجرد خط أفقي مستقيم. 230

230

إذن هذا هو عدد الخطوات. 231

231

وهذا الخط لا يتسلق على الإطلاق 232

232

مع زيادة عدد العناصر. 233

233

هذا هو أفضل حال. 234

234

إذا كان بإمكانك الحصول على خوارزمية ثابتة ، 235

235

هذا إلى حد كبير أفضل ما يمكنك القيام به. 236

236

ثاني أفضل شيء هو اللوغاريتمي. 237

237

ولاحظ أنه لوغاريتم للأساس اثنين. 238

238

وسنرى بعض الخوارزميات 239

239

التي لديها تعقيد هذا الوقت. 240

240

هذا باللون الأزرق الغامق. 241

241

وكما نرى ، يبدأ نوع من التسلق. 242

242

لذلك كلما زاد عدد العناصر ، 243

243

عدد الخطوات يرتفع. 244

244

ولكن بعد ذلك يتم إيقافه وهو إلى حد كبير 245

245

تقريبا وقت ثابت. 246

246

إذا كنت تستطيع تحقيق السجل 247

247

إلى التعقيد الزمني الأساسي اثنين N ، هذا رائع. 248

248

لن نرى أي شيء مع 249

249

أعتقد أن هذا هو الجذر التربيعي ، الجذر التربيعي لـ N 250

250

لكننا سنرى بعض الخوارزميات الخطية. 251

251

لقد ناقشنا بالفعل الوقت الخطي. 252

252

وهذا هو الرسم البياني باللون الأخضر. 253

253

لذلك إذا كان لديك 10 عناصر ، فستتخذ 10 خطوات ، 254

254

20 عنصرًا ، 20 خطوة. 255

255

لا يجب أن تكون مطابقة تامة كهذه. 256

256

إنه نمط أكثر للنمو. 257

257

لذلك إذا كان نمط النمو خطيًا ، 258

258

إنه تسلسل خطي ، ثم الرسم البياني 259

259

سيبدو هكذا. 260

260

وهذا ما بدا عليه بالنسبة لنا 261

261

إضافة السكر إلى خوارزمية الشاي. 262

262

لم نبدأ من الصفر. 263

263

إذا كنت لا تريد السكريات ، فمن الواضح أنه لا توجد خطوات ، 264

264

لكن خوارزميتنا هي إضافة السكر إلى الشاي الخاص بك ، 265

265

بحيث يفترض أنه سيكون هناك سكر مضاف. 266

266

وبالتالي ، فإن الحد الأدنى لعدد الخطوات لسكر واحد هو أربعة. 267

267

لذلك سنبدأ في الواقع من أربعة 268

268

ولكن بعد ذلك نذهب ستة ، ثمانية ، 10 ، وما إلى ذلك. 269

269

ولذا فهو تقدم خطي. 270

270

هذا الخط البرتقالي الآن هو N log للأساس اثنين N. 271

271

إذن نضرب هنا اللوغاريتمات في القاعدة اثنين N 272

272

بعدد العناصر. 273

273

وسنرى بعض الخوارزميات 274

274

التي لديها تعقيد هذا الوقت. 275

275

هذا أسوأ من الخطي لأنه كما ترون 276

276

عدد الخطوات المطلوبة يرتفع بشكل أكثر حدة. 277

277

ومن ثم بالطبع أسوأ من ذلك هو التربيعي 278

278

وسنبدأ في البحث عن خوارزميات الفرز 279

279

التي تحتوي في الواقع على تعقيد زمني للوقت التربيعي. 280

280

وهذا تسلق أكثر حدة. 281

281

هذا هو الخط الأحمر المتقطع. 282

282

وبالتالي ، إذا كان لديك 10 عناصر ، فسيستغرق الأمر 100 خطوة 283

283

لأن هذا سيكون 10 تربيع. 284

284

وبالتالي ، إذا كانت لديك خوارزمية تربيعية ، 285

285

هذا يتحلل بسرعة. 286

286

1000 عنصر هو بالفعل مليون خطوة. 287

287

لذا ضع هذا الرسم البياني في الاعتبار عندما ننظر 288

288

في الخوارزميات المختلفة. 289

289

الأفضل المطلق هو الوقت الثابت. 290

290

إذا لم تتمكن من الحصول على ذلك ، فأنت تريد وقتًا لوغاريتميًا ، 291

291

سجل إلى الأساس الثاني N. 292

292

لا يزال الوقت الخطي جيدًا 293

293

بمجرد أن تبدأ في الصعود إلى N log N و N تربيع. 294

294

يمكنك أن ترى أن عدد الخطوات المطلوبة 295

295

يرتفع بشكل حاد مع زيادة عدد العناصر. 296

296

في الختام ، هذا ما يجب أن تتذكره حقًا ، 297

297

تعطينا علامة O الكبيرة طريقة للمقارنة 298

298

التعقيد الزمني للخوارزميات المختلفة 299

299

بطريقة موضوعية ، بطريقة مستقلة عن الأجهزة. 300

300

حسنًا ، هذا كل شيء الآن بالنسبة لتدوين O الكبير. 301

301

سنعيد النظر في هذا أثناء مرورنا بالدورة. 302

302

لذلك سأراك في الفيديو التالي.