როგორ გამოითვლება შერწყმის დახარისხების სირთულე?

2024 ავტორი: Lynn Donovan | [email protected]. ბოლოს შეცვლილი: 2023-12-15 23:49

2 პასუხი. A[L, R] კვანძის ორ კვანძად გაყოფას სჭირდება R−L+1 დრო და შემდეგ შერწყმა ორ შვილობილ კვანძს A[L, M] და A[M+1, R] ისევ A[R−L+1] დრო სჭირდება. ამრიგად, თითოეული კვანძისთვის, ოპერაციების რაოდენობაა ალგორითმი performs უდრის ამ კვანძის შესაბამისი მასივის ორჯერ ზომას.

ამასთან დაკავშირებით, როგორ მუშაობს შერწყმის დალაგება?

აი, როგორ იყენებს შერწყმის დალაგებას გაყოფა და დაბადება:

1. გაყოფა პოზიციის q რიცხვის იპოვით p-სა და r-ს შორის.
2. დაიპყროთ ქვემასივების რეკურსიულად დალაგებით თითოეულ ორ ქვეპრობლემში, რომლებიც შექმნილია გაყოფის ნაბიჯით.
3. გააერთიანეთ ორი დალაგებული ქვემაივი უკან შერწყმით ერთ დახარისხებულ ქვემასივში[გვ.

ასევე, რა არის დიდი O სირთულე შერწყმის დახარისხებისთვის? შერწყმა დახარისხება არის სტაბილური დალაგება რაც ნიშნავს, რომ მასივის ერთი და იგივე ელემენტი ინარჩუნებს თავდაპირველ პოზიციებს ერთმანეთის მიმართ. საერთო დრო სირთულის დან შერწყმა დახარისხება არის ო (nLogn). ეს უფრო ეფექტურია, რადგან უარეს შემთხვევაში ასევე არის მუშაობის დრო ო (nlogn) სივრცე სირთულის დან შერწყმა დახარისხება არის ო (n).

რა არის შერწყმის დახარისხების სირთულე უარეს შემთხვევაში?

n*log(n)

რამდენ შედარებას ახდენს შერწყმის დალაგება?

როდესაც ერთ-ერთ სიაში ელემენტები ამოიწურება, დანარჩენ ელემენტებს ვათავსებთ ბოლო სლოტებში დალაგებულია სია. Როგორც შედეგი, შერწყმა ორი სია, რომელსაც აქვს სულ n ელემენტი, მოითხოვს მაქსიმუმ n-1-ს შედარებები.