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 ფუნქცია მუშაობს \Theta, left parenthesis, n, right parenthesis დროში, როდესაც n ელემენტის შერწყმას ვაკეთებთ. როგორ ვაჩვენოთ, რომ mergeSort მუშაობს \Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis დროში? ვიწყებთ დაყავი-იბატონე-შეაჯერეს სამ ნაწილზე და იმაზე, თუ როგორ გამოვთვალოთ მათი სამუშაო დროები. დავუშვებთ, რომ ვასორტირებთ სულ n ელემენტს მთლიან მასივში.
  1. დაყოფის ნაბიჯს ესაჭიროება მუდმივი დრო ქვემასივის ზომის მიუხედავად. დაყოფის ნაბიჯი მხოლოდ q შუაწერტილს პოულობს p-სა და r-ს შორის. გავიხსენოთ, რომ დიდ-Θ ნოტაციაში ჩვენ მუდმივ დროს \Theta, left parenthesis, 1, right parenthesis-ით აღვნიშნავთ.
  2. ბატონობის ნაბიჯი, რომელშიც რეკურსიულად ვასორტირებთ ორ ქვემასივს, თითოეულ მათგანში n, slash, 2 ელემენტია, ამას გარკვეული დრო ესაჭიროება, მაგრამ ამას გავითვალისწინებთ ქვეამოცანების განხილვისას.
  3. შეჯერების ნაბიჯი აერთებს ჯამურად n ელემენტს, რასაც ესაჭიროება \Theta, left parenthesis, n, right parenthesis დრო.
თუ დაყოფისა და შეერთების (შეჯერების) ნაბიჯებს განვიხილავთ ერთად, დაყოფის \Theta, left parenthesis, 1, right parenthesis სამუშაო დრო არის უფრო დაბალი თანრიგის წევრი შეერთების \Theta, left parenthesis, n, right parenthesis-ის სამუშაო დროსთან შედარებით. ასე რომ, ვიფიქროთ დაყოფისა და შეერთების ნაბიჯებზე ერთად, როგორც ჯამში \Theta, left parenthesis, n, right parenthesis დროში მომუშავე ნაბიჯებად. უფრო რომ დავაკონკრეტოთ, ვთქვათ, რომ დაყოფისა და შეჯერების ნაბიჯებს ერთად ესაჭიროება c, n დრო რაიმე მუდმივა c-სთვის.
სიმარტივისთვის, დავუშვათ, რომ თუ n, is greater than, 1, მაშინ n ყოველთვის ლუწია, ასე რომ, n, slash, 2, მთელი რიცხვი იქნება. (n-ის კენტი შემთხვევის განხილვა არ ცვლის შედეგს დიდ-Θ ნოტაციაში.) ასე რომ, n ელემენტიან მასივზე mergeSort-ის სამუშაო დრო არის ორი გამრავლებული mergeSort-ის სამუშაო დროზე left parenthesis, n, slash, 2, right parenthesis ელემენტიან ქვემასივზე (ბატონობის ნაბიჯისთვის) პლუს c, n (დაყოფისა და შეჯერების ნაბიჯებისთვის — რეალურად, მხოლოდ შერწყმისთვის).
ახლა უნდა გავარკვიოთ ორი რეკურსიული გამოძახების სამუშაო დრო n, slash, 2 ელემენტზე. ამ რეკურსიული გამოძახებებიდან თითოეულს ესაჭიროება ორი გამრავლებული mergeSort-ის სამუშაო დროზე left parenthesis, n, slash, 4, right parenthesis ელემენტიან ქვემასივზე (რადგან უნდა გავანახევროთ n, slash, 2) პლუს c, n, slash, 2 შერწყმისათვის. გვაქვს n, slash, 2 ორი ქვეამოცანა და თითოეულს ესაჭიროება c, n, slash, 2 დრო შერწყმისათვის და, შესაბამისად, n, slash, 2 ზომის ქვეამოცანების შერწყმისათვის საჭირო ჯამური დრო არის 2, dot, c, n, slash, 2, equals, c, n.
შერწყმის დროები დავხატოთ „ხეში“:
დიაგრამა, რომელზეც მარცხნივ არის ხე და მარჯვნივ არის შერწყმის დროები. ხეს აწერია „ქვეამოცანის ზომა“ და მარჯვენა მხარეს აწერია „ამ ზომის ქვეამოცანების შერწყმის ჯამური დრო“. ხის პირველი დონე აჩვენებს ერთ წვერო n-ს შესაბამის შერწყმის დროს c*n-ს. ხის მეორე დონე აჩვენებს ორ წვეროს, თითოეული მათგანი 1/2 n და შერწყმის დროს 2 * c * 1/2 n, იგივე, რაც c * n.
კომპიუტერული მეცნიერები ხეს უკუღმა ხატავენ. ხე არის გრაფი უციკლოდ (გზები, რომლებიც იწყება და მთავრდება ერთსა და იმავე ადგილზე). ხის წერტილებს წვეროებს ვუწოდებთ. ფუძე არის ყველაზე ზემოთ მყოფი წვერო; აქ ფუძეს აწერია n ქვემასივის ზომა თავდაპირველი n-ელემენტიანი მასივისთვის. ფუძის ქვემოთ არის ორი შვილობილი წვერო, თითოეულს აწერია n, slash, 2, რაც აღნიშნავს ქვემასივის ზომებს n, slash, 2 ზომის ქვეამოცანებისთვის.
n, slash, 2 ზომის თითოეული ქვეამოცანა რეკურსიულად ასორტირებს left parenthesis, n, slash, 2, right parenthesis, slash, 2 ზომის ქვემასივებს, იგივე n, slash, 4. ვინაიდან n, slash, 2 ზომის ორი ქვეამოცანაა, n, slash, 4 ზომის ოთხი ქვეამოცანა გვექნება. ამ ოთხიდან თითოეული ქვემასივი ასორტირებს n, slash, 4 ელემენტს და, შესაბამისად, შერწყმის დროები თითოეული მათგანისთვის არის c, n, slash, 4. ვკრებთ ოთხივე ქვეამოცანისთვის, შედეგად ვხედავთ, რომ შერწყმის ჯამური დრო n, slash, 4 ზომის ქვეამოცანებისთვის არის 4, dot, c, n, slash, 4, equals, c, n:
დიაგრამა, რომელზეც მარცხნივ არის ხე და მარჯვნივ არის შერწყმის დროები. ხეს აწერია „ქვეამოცანის ზომა“ და მარჯვენა მხარეს აწერია „ამ ზომის ქვეამოცანების შერწყმის ჯამური დრო“. ხის პირველი დონე აჩვენებს ერთ წვერო 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, slash, 8 ზომის ქვეამოცანების შემთხვევაში? ასეთი 8 გვექნება და თითოეულის შერწყმის დრო იქნება c, n, slash, 8, რაც მოგვცემს შერწყმის ჯამურ დროს 8, dot, c, n, slash, 8, equals, c, n:
დიაგრამა, რომელზეც მარცხნივ არის ხე და მარჯვნივ არის შერწყმის დროები. ხეს აწერია „ქვეამოცანის ზომა“ და მარჯვენა მხარეს აწერია „ამ ზომის ქვეამოცანების შერწყმის ჯამური დრო“. ხის პირველი დონე აჩვენებს ერთ წვერო 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.
რაც უფრო პატარავდება ქვეამოცანები, ქვეამოცანების რაოდენობა ორჯერ იზრდება თითოეულ რეკურსიის „დონეზე“, მაგრამ შერწყმის დროები ნახევრდება. გაორმაგება და განახევრება აბათილებს ერთმანეთს და შერწყმის ჯამური დრო რეკურსიის თითოეულ დონეზე გამოდის c, n. საბოლოოდ ჩამოვდივართ 1 ზომის ქვეამოცანებზე: ბაზისი. გვიწევს \Theta, left parenthesis, 1, right parenthesis დროის დახარჯვა 1 ზომის მასივების დასასორტირებლად, რადგან უნდა შევამოწმოთ p, is less than, r და ამ ტესტს სჭირდება დრო. 1 ზომის რამდენი ქვემასივია? ვინაიდან დავიწყეთ n ელემენტით, უნდა იყოს ასეთი n ქვესიმრავლე. ვინაიდან თითოეულ ბაზისს ესაჭიროება \Theta, left parenthesis, 1, right parenthesis დრო, ვთქვათ, რომ ჯამში ბაზისებს მიაქვთ c, n დრო:
დიაგრამა, რომელზეც მარცხნივ არის ხე და მარჯვნივ არის შერწყმის დროები. ხეს აწერია „ქვეამოცანის ზომა“ და მარჯვენა მხარეს აწერია „ამ ზომის ქვეამოცანების შერწყმის ჯამური დრო“. ხის პირველი დონე აჩვენებს ერთ წვერო 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, dot, c, n. რისი ტოლია l? ჩვენ ვიწყებთ n ზომის ქვეამოცანებით და ყოველ ჯერზე ვანახევრებთ მანამ, სანამ 1 ზომის ქვეამოცანებამდე არ დავალთ. ეს თვისება ვნახეთ მაშინ, როცა ვაანალიზებდით ორობით ძებნას და პასუხი არის l, equals, log, start base, 2, end base, n, plus, 1. მაგალითად, თუ n, equals, 8, მაშინ log, start base, 2, end base, n, plus, 1, equals, 4 და, სწორედაც რომ, ხეს აქვს 4 დონე: n, equals, 8, comma, 4, comma, 2, comma, 1. mergeSort-ის ჯამური დრო მაშინ გამოდის c, n, left parenthesis, log, start base, 2, end base, n, plus, 1, right parenthesis. როდესაც ვიყენებთ დიდ-Θ ნოტაციას სამუშაო დროის აღსაწერად, შეგვიძლია, დაბალი თანრიგის წევრი (plus, 1) და მუდმივი კოეფიციენტი (c) უგულებელვყოთ, რაც გვაძლევს \Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis სამუშაო დროს, როგორც დაგპირდით.
შერწყმით სორტირების კიდევ ერთი რამ იმსახურებს აღნიშვნას. შერწყმის დროს ის აკოპირებს მთლიან დასასორტირებელ მასივს, ნახევარს lowHalf-ში და მეორე ნახევარს highHalf-ში. ვინაიდან ის მუდმივ რაოდენობაზე მეტ ელემენტს აკოპირებს კონკრეტულ დროს, ვამბობთ, რომ შერწყმით სორტირება ვერ მუშაობს ადგილზე. ამის საპირისპიროდ, შერჩევითი სორტირებაც და ჩასმით სორტირებაც ადგილზევე მუშაობენ, რადგან ისინი არც ერთ კონკრეტულ მომენტში არ აკოპირებენ მუდმივ რაოდენობაზე მეტ ელემენტს. კომპიუტერულ მეცნიერებს უყვართ იმის განხილვა, ალგორითმი მუშაობს თუ არა ადგილზე, რადგან არსებობს სისტემები, რომლებშიც თავისუფალი ადგილის უკმარისობაა და, შესაბამისად, ასეთ შემთხვევებში ადგილზე მომუშავე ალგორითმებს ენიჭებათ უპირატესობა.
ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.

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

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