ძირითადი მასალა
კომპიუტერული მეცნიერება
კურსი: კომპიუტერული მეცნიერება > თემა 1
გაკვეთილი 8: დალაგება შერწყმითშერწყმით დალაგების ანალიზი
ვიცით, რომ დროში, როდესაც ელემენტის შერწყმას ვაკეთებთ. როგორ ვაჩვენოთ, რომ დროში? ვიწყებთ დაყავი-იბატონე-შეაჯერეს სამ ნაწილზე და იმაზე, თუ როგორ გამოვთვალოთ მათი სამუშაო დროები. დავუშვებთ, რომ ვასორტირებთ სულ ელემენტს მთლიან მასივში.
merge
ფუნქცია მუშაობს mergeSort
მუშაობს - დაყოფის ნაბიჯს ესაჭიროება მუდმივი დრო ქვემასივის ზომის მიუხედავად. დაყოფის ნაბიჯი მხოლოდ
შუაწერტილს პოულობს -სა და -ს შორის. გავიხსენოთ, რომ დიდ-Θ ნოტაციაში ჩვენ მუდმივ დროს -ით აღვნიშნავთ. - ბატონობის ნაბიჯი, რომელშიც რეკურსიულად ვასორტირებთ ორ ქვემასივს, თითოეულ მათგანში
ელემენტია, ამას გარკვეული დრო ესაჭიროება, მაგრამ ამას გავითვალისწინებთ ქვეამოცანების განხილვისას. - შეჯერების ნაბიჯი აერთებს ჯამურად
ელემენტს, რასაც ესაჭიროება დრო.
თუ დაყოფისა და შეერთების (შეჯერების) ნაბიჯებს განვიხილავთ ერთად, დაყოფის სამუშაო დრო არის უფრო დაბალი თანრიგის წევრი შეერთების -ის სამუშაო დროსთან შედარებით. ასე რომ, ვიფიქროთ დაყოფისა და შეერთების ნაბიჯებზე ერთად, როგორც ჯამში დროში მომუშავე ნაბიჯებად. უფრო რომ დავაკონკრეტოთ, ვთქვათ, რომ დაყოფისა და შეჯერების ნაბიჯებს ერთად ესაჭიროება დრო რაიმე მუდმივა -სთვის.
სიმარტივისთვის, დავუშვათ, რომ თუ , მაშინ ყოველთვის ლუწია, ასე რომ, , მთელი რიცხვი იქნება. ( -ის კენტი შემთხვევის განხილვა არ ცვლის შედეგს დიდ-Θ ნოტაციაში.) ასე რომ, ელემენტიან მასივზე ელემენტიან ქვემასივზე (ბატონობის ნაბიჯისთვის) პლუს (დაყოფისა და შეჯერების ნაბიჯებისთვის — რეალურად, მხოლოდ შერწყმისთვის).
mergeSort
-ის სამუშაო დრო არის ორი გამრავლებული mergeSort
-ის სამუშაო დროზე ახლა უნდა გავარკვიოთ ორი რეკურსიული გამოძახების სამუშაო დრო ელემენტზე. ამ რეკურსიული გამოძახებებიდან თითოეულს ესაჭიროება ორი გამრავლებული ელემენტიან ქვემასივზე (რადგან უნდა გავანახევროთ ) პლუს შერწყმისათვის. გვაქვს ორი ქვეამოცანა და თითოეულს ესაჭიროება დრო შერწყმისათვის და, შესაბამისად, ზომის ქვეამოცანების შერწყმისათვის საჭირო ჯამური დრო არის .
mergeSort
-ის სამუშაო დროზე შერწყმის დროები დავხატოთ „ხეში“:
კომპიუტერული მეცნიერები ხეს უკუღმა ხატავენ. ხე არის გრაფი უციკლოდ (გზები, რომლებიც იწყება და მთავრდება ერთსა და იმავე ადგილზე). ხის წერტილებს წვეროებს ვუწოდებთ. ფუძე არის ყველაზე ზემოთ მყოფი წვერო; აქ ფუძეს აწერია ქვემასივის ზომა თავდაპირველი -ელემენტიანი მასივისთვის. ფუძის ქვემოთ არის ორი შვილობილი წვერო, თითოეულს აწერია , რაც აღნიშნავს ქვემასივის ზომებს ზომის ქვეამოცანებისთვის.
როგორ ფიქრობთ, რა მოხდებოდა ზომის ქვეამოცანების შემთხვევაში? ასეთი 8 გვექნება და თითოეულის შერწყმის დრო იქნება , რაც მოგვცემს შერწყმის ჯამურ დროს :
რაც უფრო პატარავდება ქვეამოცანები, ქვეამოცანების რაოდენობა ორჯერ იზრდება თითოეულ რეკურსიის „დონეზე“, მაგრამ შერწყმის დროები ნახევრდება. გაორმაგება და განახევრება აბათილებს ერთმანეთს და შერწყმის ჯამური დრო რეკურსიის თითოეულ დონეზე გამოდის . საბოლოოდ ჩამოვდივართ 1 ზომის ქვეამოცანებზე: ბაზისი. გვიწევს დროის დახარჯვა 1 ზომის მასივების დასასორტირებლად, რადგან უნდა შევამოწმოთ და ამ ტესტს სჭირდება დრო. 1 ზომის რამდენი ქვემასივია? ვინაიდან დავიწყეთ ელემენტით, უნდა იყოს ასეთი ქვესიმრავლე. ვინაიდან თითოეულ ბაზისს ესაჭიროება დრო, ვთქვათ, რომ ჯამში ბაზისებს მიაქვთ დრო:
ახლა ვიცით, რამდენი დროა საჭირო თითოეული ქვეამოცანის ზომისთვის. დონე, მაშინ შერწყმის ჯამური დრო არის . რისი ტოლია ? ჩვენ ვიწყებთ ზომის ქვეამოცანებით და ყოველ ჯერზე ვანახევრებთ მანამ, სანამ 1 ზომის ქვეამოცანებამდე არ დავალთ. ეს თვისება ვნახეთ მაშინ, როცა ვაანალიზებდით ორობით ძებნას და პასუხი არის . მაგალითად, თუ , მაშინ და, სწორედაც რომ, ხეს აქვს 4 დონე: . . როდესაც ვიყენებთ დიდ-Θ ნოტაციას სამუშაო დროის აღსაწერად, შეგვიძლია, დაბალი თანრიგის წევრი ( ) და მუდმივი კოეფიციენტი ( ) უგულებელვყოთ, რაც გვაძლევს სამუშაო დროს, როგორც დაგპირდით.
mergeSort
-ის ჯამური დრო არის შერწყმის დროების ჯამი თითოეული დონისთვის. თუ ხეში არის mergeSort
-ის ჯამური დრო მაშინ გამოდის შერწყმით სორტირების კიდევ ერთი რამ იმსახურებს აღნიშვნას. შერწყმის დროს ის აკოპირებს მთლიან დასასორტირებელ მასივს, ნახევარს
lowHalf
-ში და მეორე ნახევარს highHalf
-ში. ვინაიდან ის მუდმივ რაოდენობაზე მეტ ელემენტს აკოპირებს კონკრეტულ დროს, ვამბობთ, რომ შერწყმით სორტირება ვერ მუშაობს ადგილზე. ამის საპირისპიროდ, შერჩევითი სორტირებაც და ჩასმით სორტირებაც ადგილზევე მუშაობენ, რადგან ისინი არც ერთ კონკრეტულ მომენტში არ აკოპირებენ მუდმივ რაოდენობაზე მეტ ელემენტს. კომპიუტერულ მეცნიერებს უყვართ იმის განხილვა, ალგორითმი მუშაობს თუ არა ადგილზე, რადგან არსებობს სისტემები, რომლებშიც თავისუფალი ადგილის უკმარისობაა და, შესაბამისად, ასეთ შემთხვევებში ადგილზე მომუშავე ალგორითმებს ენიჭებათ უპირატესობა.ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.
გსურთ, შეუერთდეთ დისკუსიას?
პოსტები ჯერ არ არის.