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
داگ لوید: خطی
جستجو، الگوریتم است

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
و پس از آن در ای اجرا می شود
N، در بدترین حالت.

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