>> [მუსიკის დაკვრა]
DOUG LLOYD: ხაზოვანი ძებნის ალგორითმი ჩვენ
შეგიძლიათ გამოიყენოთ ელემენტს მასივი.
ალგორითმი გაწვევას არის ნაბიჯ ნაბიჯ კომპლექტი
ინსტრუქციები დასრულების ამოცანა.
>> ხაზოვანი ძიება ალგორითმი მუშაობს შემდეგნაირად.
Iterate მასშტაბით მასივი მარცხნიდან მარჯვენა, ეძებს მითითებული ელემენტს.
>> In pseudocode, რომელიც უფრო გამოხდილი მობილური ეს წინადადება,
თუ პირველ ელემენტს არის ის, რაც თქვენ ეძებთ, შეგიძლიათ შეჩერება.
წინააღმდეგ შემთხვევაში, გადატანა მომდევნო ელემენტს და შენარჩუნება აპირებს მეტი და მეტი, სანამ თქვენთვის
ელემენტი, ან თქვენ არ.
ასე რომ, ჩვენ შეგვიძლია გამოვიყენოთ ხაზოვანი ძებნის ალგორითმი, მაგალითად,
მოვძებნოთ სამიზნე მნიშვნელობა ცხრა ამ მასივი.
ისე ჩვენ დაიწყება.
იმ შემთხვევაში, თუ ის, რაც ჩვენ ეძებს, შეიძლება შეწყდეს.
ეს არ არის, ჩვენ არ ვეძებთ 11.
ასე რომ, წინააღმდეგ შემთხვევაში, გადატანა მომდევნო ელემენტს.
>> ამიტომ, ჩვენ შევხედოთ 23.
23 ის, რასაც ჩვენ ვეძებთ?
ისე არ არის, ასე რომ, ჩვენ გადაადგილება, რათა მომდევნო ელემენტს, და მეორე ელემენტი,
და ჩვენ შენარჩუნება გადის ეს პროცესი და მეტი
და მეტი, სანამ ჩვენ მიწაზე on სიტუაცია მოსწონს ეს.
>> Nine არის ის, რაც ჩვენ ვეძებთ, და ამ ელემენტს მასივი
ის არის, რომ ის მნიშვნელობა ცხრა.
ამდენად, ჩვენ აღმოვაჩინეთ, რაც ჩვენ ეძებს, და ჩვენ ვერ შეაჩერებს.
ხაზოვანი ძებნის აქვს დასრულდა, წარმატებით.
>> მაგრამ რა შეიძლება ითქვას, თუ ჩვენ ვეძებთ ელემენტს, რომელიც არ არის ჩვენს მასივი.
ამჯამად ხაზოვანი ძებნა კიდევ მუშაობს?
ისე დარწმუნებული ვარ.
ასე რომ, ჩვენ ვიმეორებ ეს პროცესი დაწყებული პირველ ელემენტს.
იმ შემთხვევაში, თუ ის, რაც ჩვენ ეძებს, შეიძლება შეწყდეს.
ეს არ არის.
წინააღმდეგ შემთხვევაში, ჩვენ გადაადგილება, რათა მომდევნო ელემენტს.
>> მაგრამ ჩვენ შეგვიძლია შევინარჩუნოთ იმეორებს ამ პროცესში, შეისწავლა თითოეული ელემენტის თავის მხრივ,
იმ იმედით, რომ ჩვენ ნომერი 50.
მაგრამ ჩვენ არ ვიცით, თუ ჩვენ აღმოვაჩინეთ ნომერი 50
ან თუ ჩვენ არ, სანამ ჩვენ გადადგა მეტი თითოეული ელემენტის მასივი.
>> მხოლოდ ერთხელ, ჩვენ გავაკეთეთ რომ ამუშავება და მოკლე,
შეგვიძლია დავასკვნათ, რომ 50 არ არის მასივი.
ასე რომ, ხაზოვანი ძებნა ალგორითმი, ასევე ეს ვერ მოხერხდა, თავისთავად.
მაგრამ არა იმ გაგებით, რომ ის წარუმატებელი აღმოჩნდა კარგის
ჩვენ ვთხოვეთ მას ამის გაკეთება.
>> ეს იყო წარუმატებელი, როგორც იმდენად, რამდენადაც ეს არ იპოვოს 50,
მაგრამ 50 არ იყო მასივი.
მაგრამ ჩვენ ამომწურავად ჩხრეკა მეშვეობით თითოეული ელემენტი
და ა.შ., ხოლო ჩვენ ვერ არაფერი, ხაზოვანი ძებნა მაინც
გაამართლებს თუნდაც ელემენტი არ არის მასივი.
>> ასე რომ, რა უარეს შემთხვევაში სცენარი ხაზოვანი ძებნა?
ისე ჩვენ უნდა გაეცნონ თითოეული ელემენტის,
ან იმიტომ, რომ სამიზნე ელემენტი ბოლო ელემენტს მასივი,
ან ელემენტს ჩვენ ვეძებთ არ რეალურად არსებობს მასივი ყველა.
რა არის საუკეთესო სცენარი?
ისე, რომ ჩვენ შეიძლება იპოვოს ელემენტის დაუყოვნებლივ.
და რამდენი ელემენტები ჩვენ მაშინ უნდა ვეძებოთ
განთავსებულია საუკეთესო შემთხვევაში, თუ ჩვენ ვეძებთ მას
და ჩვენ ამას თავიდანვე?
ჩვენ შეგვიძლია შეწყდეს დაუყოვნებლივ.
>> რას გვეუბნება ეს შესახებ სირთულის ხაზოვანი ძებნა?
ისე, უარეს შემთხვევაში, ჩვენ გვაქვს შევხედოთ თითოეული ელემენტი.
ასე რომ, იგი ეშვება O of n, უარეს შემთხვევაში.
>> საუკეთესო შემთხვევაში, ჩვენ კარგად მოვძებნოთ ელემენტი დაუყოვნებლივ.
ასე რომ ეშვება omega 1.
>> მე Doug Lloyd.
ეს არის CS50.