>> DOUG LLOYD: ასე CS50 გავიგეთ სხვადასხვა დახარისხება და ძიების
ალგორითმები.
და ზოგჯერ ეს შეიძლება იყოს ცოტა სახიფათო შენარჩუნება
სიმღერა რა ალგორითმი აკეთებს რა.
ჩვენ ნამდვილად მხოლოდ ნაწილობრივ შევეხეთ ძალიან,
არსებობს მრავალი სხვა სამძებრო და დახარისხება ალგორითმები.
ასე რომ, ამ ვიდეო მოდით მხოლოდ რამდენიმე წუთი
ცდილობენ და გამოიხადოს თითოეულ ალგორითმი ქვემოთ მისი ძირითადი ელემენტები
ასე რომ თქვენ შეგიძლიათ გვახსოვდეს, რომ ყველაზე მნიშვნელოვანი ინფორმაცია მათ შესახებ
და შეძლებს მივიტანოთ განსხვავებები, საჭიროების შემთხვევაში.
>> პირველი არის ის, შერჩევა ერთგვარი.
ძირითადი იდეა უკან შერჩევის დალაგების მოვძებნოთ ყველაზე პატარა არასორტირებული ელემენტს
მასივი და სვოპ იგი პირველი არასორტირებული ელემენტს რომ მასივი.
ჩვენ ვთქვით, რომ ყველაზე უარეს აწარმოებს დრო, რომ n კვადრატში.
და თუ გინდათ გავიხსენოთ, რატომ, მიიღოს შევხედოთ შერჩევის დალაგების ვიდეო.
საუკეთესო შემთხვევაში პერსპექტივაში დრო ასევე n კვადრატში.
>> Bubble დალაგების, იდეა, რომ ერთი სვოპ მიმდებარე წყვილი.
ასე რომ, ეს არის გასაღები, რომელიც დაგეხმარებათ მახსოვს განსხვავება აქ.
შერჩევა დალაგების არის, ჯერჯერობით, მოვძებნოთ smallest-- bubble
დალაგების არის სვოპ მიმდებარე წყვილი.
ჩვენ სვოპ მიმდებარე წყვილი ელემენტების, თუ ისინი
მწყობრიდან გამოსულია, რომელიც ეფექტურად ბუშტები დიდი ელემენტები უფლება,
და, ამავე დროს, ის ასევე იწყება გადაადგილება პატარა ელემენტები მარცხენა.
უარესი შემთხვევაში პერსპექტივაში დრო of bubble sort არის n კვადრატში.
საუკეთესო შემთხვევაში პერსპექტივაში დრო of bubble sort არის n.
იმის გამო, რომ სიტუაცია ჩვენ არ რეალურად
ჩვენ შეიძლება არ უნდა მიიღოს ნებისმიერი სვოპების ყველა.
ჩვენ მხოლოდ უნდა მიიღოს ერთი გაივლის მთელი n ელემენტებს.
>> In ჩასმა სახის, ძირითადი იდეა აქ გადავიდა.
სწორედ სიტყვით Insertion დალაგების.
ჩვენ ვაპირებთ, რომ გადადგას ერთხელ მეშვეობით მასივი მარცხნიდან მარჯვნივ.
და როგორც ჩვენ ვაკეთებთ, ჩვენ აპირებს გადასვლას ელემენტები
ჩვენ უკვე დავინახეთ, რათა ოთახი მცირე პირობა, რომ უნდა მოერგოს სადღაც
უკან რომ დახარისხებული ნაწილი.
ასე რომ, ჩვენ ავაშენოთ დახარისხებული მასივი ერთი ელემენტს დროს, მარცხნიდან მარჯვნივ,
და ჩვენ გადაეტანა რამ, რათა ოთახში.
უარესი პერსპექტივაში დრო Insertion დალაგების არის n კვადრატში.
საუკეთესო შემთხვევაში აწარმოებს დრო n.
>> შერწყმა დალაგების სიტყვით აქ არის გაყოფილი და შერწყმა.
ჩვენ გაყოფილი სრული მასივი, თუ არა ეს ექვსი ელემენტები, რვა ელემენტებს,
10,000 ელემენტებს ჩვენ გაყოფილი იგი ქვემოთ ნახევარი, ნახევარი, ნახევარი,
სანამ ჩვენ გვაქვს ქვეშ მასივი ო-ერთი ელემენტია მასივები.
კომპლექტი n ერთ ელემენტს მასივები.
ასე რომ, ჩვენ დავიწყეთ ერთი 1000-ელემენტს მასივი,
და მივიღებთ იმ წერტილში, სადაც ჩვენ 1,000 ერთი ელემენტი მასივები.
მაშინ ჩვენ ვიწყებთ შერწყმა იმ ქვე კოლექტორები უკან ერთად სწორი მიზნით.
ასე რომ, ჩვენ ვიღებთ ორი ერთი ელემენტი კოლექტორები და შექმნა ორი ელემენტს მასივი.
ჩვენ ვიღებთ ორი ორ ელემენტს კოლექტორები და შექმნას ოთხი ელემენტს მასივი
და ასე შემდეგ და ასე შემდეგ, სანამ ჩვენ ერთხელ გადაკეთებული ერთ n ელემენტს მასივი.
>> უარესი პერსპექტივაში დრო შერწყმა დალაგების არის N ჯერ შესვლა n.
ჩვენ გვყავს n ელემენტები, მაგრამ ამ recombining პროცესი
იღებს შესვლა N ნაბიჯები მისაღებად უკან სრული მასივი.
საუკეთესო შემთხვევაში აწარმოებს დროს ასევე n შესვლა n რადგან ეს პროცესი ნამდვილად არ
მაინტერესებს თუ არა მასივი დახარისხებული ან არ უნდა დაიწყოს.
პროცესი იგივე, არსებობს არავითარ შემთხვევაში არ უნდა მოკლე ჩართვა რამ.
ასე რომ, N შესვლა N უარეს შემთხვევაში, N შესვლა N საუკეთესო შემთხვევაში.
>> ჩვენ ვისაუბრეთ ორი ძიების ალგორითმები.
ასე რომ წრფივი ძიება დაახლოებით iterating.
ჩვენ გაგრძელება მასშტაბით მასივი ერთხელ, მარცხნიდან მარჯვნივ,
ცდილობს იპოვოს ნომერი ჩვენ ვეძებთ.
უარესი აწარმოებს დრო არის დიდი ო ო.
ეს შეიძლება მიიღოს ჩვენთვის iterating მასშტაბით თითოეული ელემენტის
იპოვონ ელემენტს ჩვენ ვეძებთ ამისთვის, არც ბოლო თანამდებობა,
ან საერთოდ არ.
მაგრამ ჩვენ ვერ ადასტურებენ, რომ სანამ ჩვენ შევხედე ყველაფერი.
ვარ საუკეთესო შემთხვევაში, ჩვენ დაუყოვნებლივ.
საუკეთესო შემთხვევაში პერსპექტივაში დრო ხაზოვანი ძებნა omega 1.
>> და ბოლოს, ორობითი ძებნა, რომელიც მოითხოვს ასორტი მასივი.
გახსოვდეთ, რომ ეს არის ძალიან მნიშვნელოვანი განხილვის
როდესაც მუშაობა ორობითი ძებნა.
ეს არის წინაპირობა გამოყენებით it-- მასივი, რომ თქვენ გადახედეთ
უნდა იყოს დახარისხებული.
წინააღმდეგ შემთხვევაში, სიტყვით არის გათიშე და დაიპყროთ.
გაყოფილი მასივი ნახევარი და აღმოფხვრას ნახევარში ელემენტები
ყოველ ჯერზე, როგორც თქვენ მიიღოს მეშვეობით.
იმის გამო, რომ ამ გათიშე და დაიპყროთ და გაყოფა რამ ნახევარი მიდგომა,
უარესი პერსპექტივაში დრო ორობითი ძებნა არის
შესვლა N, რომელიც არსებითად უკეთესად ხაზოვანი ძებნა ს ო.
საუკეთესო პერსპექტივაში დრო არის კიდევ ერთი.
>> ჩვენ, შეიძლება, მაშინვე პირველად ჩვენ დაედოთ, მაგრამ,
ერთხელ, მახსოვს, რომ მიუხედავად იმისა, რომ ორობითი ძებნა არის
გაცილებით უკეთესია, ვიდრე ხაზოვანი ძებნა ძალით მყოფი log n წინააღმდეგ n,
თქვენ უნდა გაიაროს მუშაობა დახარისხება თქვენი მასივი პირველი, რომელიც
შესაძლოა ეს ნაკლებად ეფექტური დამოკიდებულია on ზომა iterating გადანაწილებული.
>> მე Doug Lloyd, ეს არის CS50.