[Грає музика] ДАГ Lloyd: Лінійний Пошук алгоритм ми можна використовувати для пошуку елемента в масиві. Алгоритм відгук це крок за кроком набір інструкцій для виконання завдання. 

Лінійний пошук Алгоритм працює таким чином. Ітерації по масиву зліва Право, дивлячись на зазначеному елементі. 

У псевдокоді, який є більш дистильована версія цієї пропозиції, Якщо перший елемент що Ви шукаєте, ви можете зупинитися. В іншому випадку, перейти до наступного елементу і продовжувати знову і знову до тих пір, поки не знайдете елемент, або ви не робите. Таким чином, ми можемо використовувати лінійну Алгоритм пошуку, наприклад, знайти цільове значення дев'ять у цьому масиві. Ну, ми почнемо з самого початку. Якщо це те, що ми шукаєте, ми можемо зупинити. Це не так, ми не шукаємо 11. Так в іншому випадку, перейти до наступного елементу. 

Таким чином, ми дивимося на 23. 23 те, що ми шукаємо? Ну ні, так що ми перейдемо до наступного елемент, а наступний елемент, і ми продовжуємо переживає Цей процес знову і знову, і більше, поки ми не приземлитися по ситуації, як це. 

Дев'ять те, що ми шукаємо, і цей елемент масиву Тобто, це значення становить дев'ятій. І таким чином, ми знайшли те, що ми шукаєте, і ми можемо зупинитися. Лінійний пошук має завершено успішно. 

Але що, якщо ми шукаємо елемент, який не в масиві. Будь-яка лінійний пошук все ще працює? Ну звичайно. Таким чином, ми повторюємо цей процес починаючи з першого елемента. Якщо це те, що ми шукаєте, ми можемо зупинити. Це не. В іншому випадку, ми переходимо до наступного елементу. 

Але ми можемо повторювати цей процес, розглядаючи кожен елемент, у свою чергу, сподіваючись, що ми знаходимо числа 50. Але ми не будете знати, якщо ми знайшли номер 50 або якщо ми не зробили, поки ми не вийшов над кожним одного елемента масиву. 

Тільки один раз ми зробили що і придумати короткий, ми можемо зробити висновок, що 50 не перебуває у масиві. І тому лінійний пошук Алгоритм, також він не по собі. Але не в тому сенсі, що це була невдалою в цьому, що ми попросили його зробити. 

Це було невдалим, як скільки він не знайшов 50, але 50 не в масиві. Але ми вичерпно шукали через кожен окремий елемент і так, поки ми не знайшли що-небудь, лінійний пошук ще успішно, навіть якщо елемент не в масиві. 

Так що в гіршому випадку Сценарій з лінійним пошуком? Ну, ми повинні дивитися через кожен елемент, або тому, що цільовий елемент це останній елемент масиву, або елемент, ми шукаємо НЕ насправді існує в масиві на всіх. Який найкращий сценарій? Ну, ми могли б знайти елемент негайно. І скільки елементів Отже, ми повинні дивитися на, в кращому випадку, якщо ми шукаємо для нього і ми знаходимо його на самому початку? Ми можемо зупинити негайно. 

Що це говорить про Складність лінійного пошуку? Ну в гіршому випадку, у нас є подивитися на кожен окремий елемент. І так він працює в O з N, в гіршому випадку. 

У кращому випадку, ми збираємося відразу знайти елемент. І так працює омега 1. 

Я Дуг Ллойд. Це CS50.