If you're seeing this message, it means we're having trouble loading external resources on our website.

თუ ვებფილტრს იყენებთ, დარწმუნდით, რომ *.kastatic.org და *.kasandbox.org დომენები არ არის დაბლოკილი.

ძირითადი მასალა

კომპიუტერული მეცნიერება

კურსი: კომპიუტერული მეცნიერება > თემა 1

გაკვეთილი 8: დალაგება შერწყმით
პროგრამირება
კომპიუტერული მეცნიერება
ალგორითმები
დალაგება შერწყმით
© 2023 Khan Academyგამოყენების პირობებიკონფიდენციალურობის პოლიტიკაშენიშვნა ქუქი-ჩანაწერებზე

შერწყმით დალაგების ანალიზი

Google–ის საკლასო ოთახი
ვიცით, რომ merge ფუნქცია მუშაობს Θ(n) დროში, როდესაც n ელემენტის შერწყმას ვაკეთებთ. როგორ ვაჩვენოთ, რომ mergeSort მუშაობს Θ(nlog2⁡n) დროში? ვიწყებთ დაყავი-იბატონე-შეაჯერეს სამ ნაწილზე და იმაზე, თუ როგორ გამოვთვალოთ მათი სამუშაო დროები. დავუშვებთ, რომ ვასორტირებთ სულ n ელემენტს მთლიან მასივში.
  1. დაყოფის ნაბიჯს ესაჭიროება მუდმივი დრო ქვემასივის ზომის მიუხედავად. დაყოფის ნაბიჯი მხოლოდ q შუაწერტილს პოულობს p-სა და r-ს შორის. გავიხსენოთ, რომ დიდ-Θ ნოტაციაში ჩვენ მუდმივ დროს Θ(1)-ით აღვნიშნავთ.
  2. ბატონობის ნაბიჯი, რომელშიც რეკურსიულად ვასორტირებთ ორ ქვემასივს, თითოეულ მათგანში n/2 ელემენტია, ამას გარკვეული დრო ესაჭიროება, მაგრამ ამას გავითვალისწინებთ ქვეამოცანების განხილვისას.
  3. შეჯერების ნაბიჯი აერთებს ჯამურად n ელემენტს, რასაც ესაჭიროება Θ(n) დრო.
თუ დაყოფისა და შეერთების (შეჯერების) ნაბიჯებს განვიხილავთ ერთად, დაყოფის Θ(1) სამუშაო დრო არის უფრო დაბალი თანრიგის წევრი შეერთების Θ(n)-ის სამუშაო დროსთან შედარებით. ასე რომ, ვიფიქროთ დაყოფისა და შეერთების ნაბიჯებზე ერთად, როგორც ჯამში Θ(n) დროში მომუშავე ნაბიჯებად. უფრო რომ დავაკონკრეტოთ, ვთქვათ, რომ დაყოფისა და შეჯერების ნაბიჯებს ერთად ესაჭიროება cn დრო რაიმე მუდმივა c-სთვის.
სიმარტივისთვის, დავუშვათ, რომ თუ n>1, მაშინ n ყოველთვის ლუწია, ასე რომ, n/2, მთელი რიცხვი იქნება. (n-ის კენტი შემთხვევის განხილვა არ ცვლის შედეგს დიდ-Θ ნოტაციაში.) ასე რომ, n ელემენტიან მასივზე mergeSort-ის სამუშაო დრო არის ორი გამრავლებული mergeSort-ის სამუშაო დროზე (n/2) ელემენტიან ქვემასივზე (ბატონობის ნაბიჯისთვის) პლუს cn (დაყოფისა და შეჯერების ნაბიჯებისთვის — რეალურად, მხოლოდ შერწყმისთვის).
ახლა უნდა გავარკვიოთ ორი რეკურსიული გამოძახების სამუშაო დრო n/2 ელემენტზე. ამ რეკურსიული გამოძახებებიდან თითოეულს ესაჭიროება ორი გამრავლებული mergeSort-ის სამუშაო დროზე (n/4) ელემენტიან ქვემასივზე (რადგან უნდა გავანახევროთ n/2) პლუს cn/2 შერწყმისათვის. გვაქვს n/2 ორი ქვეამოცანა და თითოეულს ესაჭიროება cn/2 დრო შერწყმისათვის და, შესაბამისად, n/2 ზომის ქვეამოცანების შერწყმისათვის საჭირო ჯამური დრო არის 2⋅cn/2=cn.
შერწყმის დროები დავხატოთ „ხეში“:
დიაგრამა, რომელზეც მარცხნივ არის ხე და მარჯვნივ არის შერწყმის დროები. ხეს აწერია „ქვეამოცანის ზომა“ და მარჯვენა მხარეს აწერია „ამ ზომის ქვეამოცანების შერწყმის ჯამური დრო“. ხის პირველი დონე აჩვენებს ერთ წვერო n-ს შესაბამის შერწყმის დროს c*n-ს. ხის მეორე დონე აჩვენებს ორ წვეროს, თითოეული მათგანი 1/2 n და შერწყმის დროს 2 * c * 1/2 n, იგივე, რაც c * n.
კომპიუტერული მეცნიერები ხეს უკუღმა ხატავენ. ხე არის გრაფი უციკლოდ (გზები, რომლებიც იწყება და მთავრდება ერთსა და იმავე ადგილზე). ხის წერტილებს წვეროებს ვუწოდებთ. ფუძე არის ყველაზე ზემოთ მყოფი წვერო; აქ ფუძეს აწერია n ქვემასივის ზომა თავდაპირველი n-ელემენტიანი მასივისთვის. ფუძის ქვემოთ არის ორი შვილობილი წვერო, თითოეულს აწერია n/2, რაც აღნიშნავს ქვემასივის ზომებს n/2 ზომის ქვეამოცანებისთვის.
n/2 ზომის თითოეული ქვეამოცანა რეკურსიულად ასორტირებს (n/2)/2 ზომის ქვემასივებს, იგივე n/4. ვინაიდან n/2 ზომის ორი ქვეამოცანაა, n/4 ზომის ოთხი ქვეამოცანა გვექნება. ამ ოთხიდან თითოეული ქვემასივი ასორტირებს n/4 ელემენტს და, შესაბამისად, შერწყმის დროები თითოეული მათგანისთვის არის cn/4. ვკრებთ ოთხივე ქვეამოცანისთვის, შედეგად ვხედავთ, რომ შერწყმის ჯამური დრო n/4 ზომის ქვეამოცანებისთვის არის 4⋅cn/4=cn:
დიაგრამა, რომელზეც მარცხნივ არის ხე და მარჯვნივ არის შერწყმის დროები. ხეს აწერია „ქვეამოცანის ზომა“ და მარჯვენა მხარეს აწერია „ამ ზომის ქვეამოცანების შერწყმის ჯამური დრო“. ხის პირველი დონე აჩვენებს ერთ წვერო n-ს შესაბამის შერწყმის დროს c*n-ს. ხის მეორე დონე აჩვენებს ორ წვეროს, თითოეული მათგანი 1/2 n და შერწყმის დროს 2 * c * 1/2 n, იგივე, რაც c * n. ხის მესამე დონეზეა 4 წვერო, 1/4 n-იდან თითოეული, და შერწყმის დრო 4-ჯერ c გამრავლებული1/4 n-ზე, იგივე, რაც c გამრავლებული n-ზე.
როგორ ფიქრობთ, რა მოხდებოდა n/8 ზომის ქვეამოცანების შემთხვევაში? ასეთი 8 გვექნება და თითოეულის შერწყმის დრო იქნება cn/8, რაც მოგვცემს შერწყმის ჯამურ დროს 8⋅cn/8=cn:
დიაგრამა, რომელზეც მარცხნივ არის ხე და მარჯვნივ არის შერწყმის დროები. ხეს აწერია „ქვეამოცანის ზომა“ და მარჯვენა მხარეს აწერია „ამ ზომის ქვეამოცანების შერწყმის ჯამური დრო“. ხის პირველი დონე აჩვენებს ერთ წვერო n-ს შესაბამის შერწყმის დროს c*n-ს. ხის მეორე დონე აჩვენებს ორ წვეროს, თითოეული მათგანი 1/2 n და შერწყმის დროს 2 * c * 1/2 n, იგივე, რაც c * n. ხის მესამე დონეზეა 4 წვერო, 1/4 n-იდან თითოეული, და შერწყმის დრო 4-ჯერ c გამრავლებული1/4 n-ზე, იგივე, რაც c გამრავლებული n-ზე. მეოთხე დონეზე ნაჩვენებია 8 წვერო, 1/8 n-იდან თითოეული, და შერწყმის დრო: 8 გამრავლებული c-ჯერ 1/8 n-ზე, იგივე, რაც c-ჯერ n.
რაც უფრო პატარავდება ქვეამოცანები, ქვეამოცანების რაოდენობა ორჯერ იზრდება თითოეულ რეკურსიის „დონეზე“, მაგრამ შერწყმის დროები ნახევრდება. გაორმაგება და განახევრება აბათილებს ერთმანეთს და შერწყმის ჯამური დრო რეკურსიის თითოეულ დონეზე გამოდის cn. საბოლოოდ ჩამოვდივართ 1 ზომის ქვეამოცანებზე: ბაზისი. გვიწევს Θ(1) დროის დახარჯვა 1 ზომის მასივების დასასორტირებლად, რადგან უნდა შევამოწმოთ p<r და ამ ტესტს სჭირდება დრო. 1 ზომის რამდენი ქვემასივია? ვინაიდან დავიწყეთ n ელემენტით, უნდა იყოს ასეთი n ქვესიმრავლე. ვინაიდან თითოეულ ბაზისს ესაჭიროება Θ(1) დრო, ვთქვათ, რომ ჯამში ბაზისებს მიაქვთ cn დრო:
დიაგრამა, რომელზეც მარცხნივ არის ხე და მარჯვნივ არის შერწყმის დროები. ხეს აწერია „ქვეამოცანის ზომა“ და მარჯვენა მხარეს აწერია „ამ ზომის ქვეამოცანების შერწყმის ჯამური დრო“. ხის პირველი დონე აჩვენებს ერთ წვერო n-ს შესაბამის შერწყმის დროს c*n-ს. ხის მეორე დონე აჩვენებს ორ წვეროს, თითოეული მათგანი 1/2 n და შერწყმის დროს 2 * c * 1/2 n, იგივე, რაც c * n. ხის მესამე დონეზეა 4 წვერო, 1/4 n-იდან თითოეული, და შერწყმის დრო 4-ჯერ c გამრავლებული1/4 n-ზე, იგივე, რაც c გამრავლებული n-ზე. მეოთხე დონეზე ნაჩვენებია 8 წვერო, 1/8 n-იდან თითოეული, და შერწყმის დრო: 8 გამრავლებული c-ჯერ 1/8 n-ზე, იგივე, რაც c-ჯერ n. ამ დონის ქვემოთ ნაჩვენებია წერტილები, რაც გვამცნობს, რომ ხე ამ ლოგიკით გრძელდება. ბოლო დონეზე არის ერთიანების n ცალი წვერო და შერწყმის დრო n-ჯერ c, იგივე, რაც c-ჯერ n.
ახლა ვიცით, რამდენი დროა საჭირო თითოეული ქვეამოცანის ზომისთვის. mergeSort-ის ჯამური დრო არის შერწყმის დროების ჯამი თითოეული დონისთვის. თუ ხეში არის l დონე, მაშინ შერწყმის ჯამური დრო არის l⋅cn. რისი ტოლია l? ჩვენ ვიწყებთ n ზომის ქვეამოცანებით და ყოველ ჯერზე ვანახევრებთ მანამ, სანამ 1 ზომის ქვეამოცანებამდე არ დავალთ. ეს თვისება ვნახეთ მაშინ, როცა ვაანალიზებდით ორობით ძებნას და პასუხი არის l=log2⁡n+1. მაგალითად, თუ n=8, მაშინ log2⁡n+1=4 და, სწორედაც რომ, ხეს აქვს 4 დონე: n=8,4,2,1. mergeSort-ის ჯამური დრო მაშინ გამოდის cn(log2⁡n+1). როდესაც ვიყენებთ დიდ-Θ ნოტაციას სამუშაო დროის აღსაწერად, შეგვიძლია, დაბალი თანრიგის წევრი (+1) და მუდმივი კოეფიციენტი (c) უგულებელვყოთ, რაც გვაძლევს Θ(nlog2⁡n) სამუშაო დროს, როგორც დაგპირდით.
შერწყმით სორტირების კიდევ ერთი რამ იმსახურებს აღნიშვნას. შერწყმის დროს ის აკოპირებს მთლიან დასასორტირებელ მასივს, ნახევარს lowHalf-ში და მეორე ნახევარს highHalf-ში. ვინაიდან ის მუდმივ რაოდენობაზე მეტ ელემენტს აკოპირებს კონკრეტულ დროს, ვამბობთ, რომ შერწყმით სორტირება ვერ მუშაობს ადგილზე. ამის საპირისპიროდ, შერჩევითი სორტირებაც და ჩასმით სორტირებაც ადგილზევე მუშაობენ, რადგან ისინი არც ერთ კონკრეტულ მომენტში არ აკოპირებენ მუდმივ რაოდენობაზე მეტ ელემენტს. კომპიუტერულ მეცნიერებს უყვართ იმის განხილვა, ალგორითმი მუშაობს თუ არა ადგილზე, რადგან არსებობს სისტემები, რომლებშიც თავისუფალი ადგილის უკმარისობაა და, შესაბამისად, ასეთ შემთხვევებში ადგილზე მომუშავე ალგორითმებს ენიჭებათ უპირატესობა.
ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.

გსურთ, შეუერთდეთ დისკუსიას?

შესვლა
პოსტები ჯერ არ არის.
გესმით ინგლისური? დააწკაპუნეთ აქ და გაეცანით განხილვას ხანის აკადემიის ინგლისურენოვან გვერდზე.