>> [Мусиц плаиинг]
Даг Ллоид: Пуни Претрага је алгоритам смо
Можете користити да пронађе елемент у низу.
Алгоритам опозив је корак-по-корак комплет
упутстава за завршетак задатка.
>> Линеарни претрага алгоритам ради на следећи начин.
Посматрајте преко низа са лева на Добро, у потрази за одређени елемент.
>> У псеудокоду, што је више дестилована верзија ове реченице,
уколико је први елемент је шта тражите, можете зауставити.
У супротном, пређите на следећи елемент и наставити изнова и изнова док не пронађете
елемент, или не.
Дакле, можемо користити линеарни претраживачки алгоритам, на пример,
да пронађе циљну вредност девет у овом низу.
Па да почнемо од почетка.
Ако је то оно што смо лоокинг фор, можемо зауставити.
Није, ми не тражимо 11.
Тако у супротном, пређите на наредни елемент.
>> Дакле, гледамо 23.
Да ли је 23 оно што тражите?
Па не, па смо прешли на следећи елеменат, а следећи елемент,
и ми наставимо путем Овај процес изнова и изнова
и изнова, док не слети на оваквој ситуацији.
>> Девет је оно што тражите, а тај елемент низа
јесте, то је вредност је девет.
И тако смо пронашли оно што смо тражите, и можемо зауставити.
Линеарни Претрага има завршен успешно.
>> Али шта би било да смо у потрази за елемент који није у нашем низу.
Да ли линеарна претрага још ради?
Па да.
Дакле, понављам овај процес почев од првог елемента.
Ако је то оно што смо лоокинг фор, можемо зауставити.
Није.
У супротном, идемо на следећи елемент.
>> Али можемо понављати тај процес, испитивања сваки елемент заузврат,
у нади да ћемо наћи број 50.
Али нећемо знати да ли ми смо пронашли број 50
или ако нисмо, док смо закорачио преко сваког елемента низа.
>> Само једном смо урадили да и дошао кратак,
можемо закључити да 50 није у низу.
И тако је линеарна претрага алгоритам, али то није успело, само по себи.
Али не у смислу да био неуспешан у оно што раде
ми то тражили.
>> То је био неуспешан у као колико је нису нашли 50,
али 50 није био у низу.
Али ми смо тражили исцрпно кроз сваки елемент
и тако док нисмо нашли ништа, линеарна претрага даље
успијева чак и ако елемент није у низу.
>> Дакле, оно што је најгори случај сценарио са линеарном претраге?
Па морамо да погледамо кроз Сваки елемент,
или зато што је мета елемента је последњи елемент низа,
или елемент тражимо не заиста постоје у низу уопште.
Шта је најбољи сценарио?
Па могли бисмо пронашли Елемент одмах.
А колико елемената ми онда морамо да погледамо
се у најбољем случају, ако смо у потрази за њега
а ми га наћи на самом почетку?
Можемо одмах зауставити.
>> Шта то говори о Сложеност линеарне претраге?
Па, у најгорем случају, имамо да погледате сваки елемент.
И тако ради у Ø н у најгорем случају.
>> У најбољем случају, ми ћемо одмах наћи елемент.
И тако ради у омега 1.
>> Ја сам Доуг Лојд.
Ово је ЦС50.