1
00:00:00,000 --> 00:00:02,892
>> [عزف الموسيقى]

2
00:00:02,892 --> 00:00:05,347

3
00:00:05,347 --> 00:00:07,180
DOUG لويد: الخطي
البحث هو أننا خوارزمية

4
00:00:07,180 --> 00:00:09,840
يمكن استخدامها للعثور على عنصر في صفيف.

5
00:00:09,840 --> 00:00:11,990
إستدعاء خوارزمية
هو عبارة عن مجموعة خطوة بخطوة

6
00:00:11,990 --> 00:00:15,030
من تعليمات لإكمال المهمة.

7
00:00:15,030 --> 00:00:17,480
>> البحث الخطي
الخوارزمية يعمل على النحو التالي.

8
00:00:17,480 --> 00:00:22,200
تكرار عبر مجموعة من اليسار إلى
الحق، وتبحث عن عنصر المحدد.

9
00:00:22,200 --> 00:00:26,380
>> في شبة الكود، وهو أكثر
نسخة المقطر من هذه الجملة،

10
00:00:26,380 --> 00:00:29,840
إذا كان العنصر الأول هو ما
كنت تبحث عنه، يمكنك التوقف.

11
00:00:29,840 --> 00:00:33,930
خلاف ذلك، والانتقال إلى العنصر التالي و
الاستمرار مرارا وتكرارا حتى تجد

12
00:00:33,930 --> 00:00:36,389
العنصر، أو لم تقم.

13
00:00:36,389 --> 00:00:38,680
حتى نتمكن من استخدام خطي
خوارزمية البحث، على سبيل المثال،

14
00:00:38,680 --> 00:00:42,330
العثور على القيمة المستهدفة
تسعة في هذه المجموعة.

15
00:00:42,330 --> 00:00:43,870
حسنا نبدأ في البداية.

16
00:00:43,870 --> 00:00:45,970
إذا كان ما نحن
تبحث عن، فإننا يمكن أن تتوقف.

17
00:00:45,970 --> 00:00:47,890
انها ليست، نحن لا نبحث عن 11.

18
00:00:47,890 --> 00:00:50,220
لذلك على خلاف ذلك، والانتقال إلى العنصر التالي.

19
00:00:50,220 --> 00:00:51,510
>> لذلك نحن ننظر إلى 23.

20
00:00:51,510 --> 00:00:52,730
هو 23 ما كنت تبحث عنه؟

21
00:00:52,730 --> 00:00:55,614
حسنا لا، حتى ننتقل الى المرحلة التالية
عنصر، والعنصر التالي،

22
00:00:55,614 --> 00:00:57,780
ونبقى يمر
هذه العملية مرارا وتكرارا

23
00:00:57,780 --> 00:01:01,030
وأكثر، حتى أننا الأرض
في مثل هذا الوضع.

24
00:01:01,030 --> 00:01:03,910
>> تسعة هو ما نبحث عنه،
وهذا عنصر من المصفوفة

25
00:01:03,910 --> 00:01:05,787
هو، انها القيمة تسعة.

26
00:01:05,787 --> 00:01:08,120
ولذلك وجدنا ما نحن عليه
تبحث عنها، ونحن يمكن أن تتوقف.

27
00:01:08,120 --> 00:01:11,910
البحث الخطي له
الانتهاء، بنجاح.

28
00:01:11,910 --> 00:01:15,370
>> ولكن ماذا عن إذا كنا نبحث عن
أحد العناصر التي ليست في مجموعة لدينا.

29
00:01:15,370 --> 00:01:17,040
هل البحث الخطي لا تزال تعمل؟

30
00:01:17,040 --> 00:01:17,540
تأكد جيدا.

31
00:01:17,540 --> 00:01:19,947
لذلك نكرر هذه العملية
بدءا من العنصر الأول.

32
00:01:19,947 --> 00:01:21,780
إذا كان ما نحن
تبحث عن، فإننا يمكن أن تتوقف.

33
00:01:21,780 --> 00:01:22,800
ليست كذلك.

34
00:01:22,800 --> 00:01:25,020
خلاف ذلك، ننتقل إلى العنصر التالي.

35
00:01:25,020 --> 00:01:29,050
>> لكننا يمكن أن تبقي تكرار هذه العملية،
دراسة كل عنصر بدوره،

36
00:01:29,050 --> 00:01:31,720
على أمل أن نجد العدد 50.

37
00:01:31,720 --> 00:01:33,750
لكننا لن نعرف إذا
وجدنا أن عدد 50

38
00:01:33,750 --> 00:01:38,290
أو إذا لم نفعل، حتى لقد صعدت
على كل عنصر واحد من مجموعة.

39
00:01:38,290 --> 00:01:40,440
>> فقط مرة واحدة فعلناه
أن والخروج قصيرة،

40
00:01:40,440 --> 00:01:43,040
يمكننا أن نستنتج أن
50 ليس في المصفوفة.

41
00:01:43,040 --> 00:01:46,410
وبالتالي فإن البحث الخطي
الخوارزمية، إضافة إلى أنه فشل في حد ذاتها.

42
00:01:46,410 --> 00:01:49,181
ولكن ليس بمعنى أنه
لم يوفق في فعل ما

43
00:01:49,181 --> 00:01:49,930
طلبنا أن تفعله.

44
00:01:49,930 --> 00:01:52,390
>> وكانت ناجحة في النحو
بقدر ما لم يجد 50،

45
00:01:52,390 --> 00:01:54,070
ولكن 50 لم يكن في المصفوفة.

46
00:01:54,070 --> 00:01:57,310
ولكننا قد بحثت باستفاضة
من خلال كل عنصر واحد

47
00:01:57,310 --> 00:02:00,550
وهكذا، في حين أننا لم نجد
أي شيء، بحث خطي لا يزال

48
00:02:00,550 --> 00:02:05,230
ينجح حتى لو كان
العنصر غير موجود في المصفوفة.

49
00:02:05,230 --> 00:02:07,507
>> إذن ما هو أسوأ حالة
السيناريو مع البحث الخطي؟

50
00:02:07,507 --> 00:02:09,590
كذلك علينا أن ننظر من خلال
كل عنصر واحد،

51
00:02:09,590 --> 00:02:14,590
إما لأن العنصر المستهدف
هو العنصر الأخير للصفيف،

52
00:02:14,590 --> 00:02:18,510
أو العنصر الذي نبحث عنه لا
موجودة بالفعل في مجموعة على الإطلاق.

53
00:02:18,510 --> 00:02:19,760
ما هو أفضل سيناريو؟

54
00:02:19,760 --> 00:02:22,430
كذلك فإننا قد نجد ل
العنصر فورا.

55
00:02:22,430 --> 00:02:24,360
وعدد العناصر
هل لدينا بعد ذلك للبحث

56
00:02:24,360 --> 00:02:26,859
في في أفضل الأحوال،
إذا كنا نبحث عن ذلك

57
00:02:26,859 --> 00:02:28,400
ونجد أنه في البداية؟

58
00:02:28,400 --> 00:02:29,850
نحن يمكن أن تتوقف على الفور.

59
00:02:29,850 --> 00:02:32,984
>> ماذا يعني هذا القول عن
تعقيد البحث الخطي؟

60
00:02:32,984 --> 00:02:35,650
كذلك في أسوأ الأحوال، لدينا
أن ننظر إلى كل عنصر واحد.

61
00:02:35,650 --> 00:02:38,930
وبحيث يتم تشغيله في O ل
ن، في أسوأ الأحوال.

62
00:02:38,930 --> 00:02:41,540
>> في أفضل الأحوال، نحن ستعمل
العثور على العنصر فورا.

63
00:02:41,540 --> 00:02:44,750
وهكذا يعمل في أوميغا 1.

64
00:02:44,750 --> 00:02:45,780
>> أنا دوغ ويد.

65
00:02:45,780 --> 00:02:48,020
هذا هو CS50.

66
00:02:48,020 --> 00:02:49,876