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
ДАГ Lloyd: Лінійний
Пошук алгоритм ми

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 з
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