Dərs vəsaiti baki -2018 azərbaycan döVLƏt neft və SƏnaye universiteti

3)Birləşdirmə və yerləşdirmə üsullarının kombinasiyasından ibarət üsul (nizamlanmış alt çoxluğu böyütmə üsulu). Biz yuxarıda yerləşdirmə üsulunun iki variantı haqqında qeyd etmişdik. Yerləşdirmə üsulunun birinci variantı müfəssəl şərh olunmuşdu. Qeyd olunmuşdu ki, bu üsul yaddaşa və zamana qənaət etmədiyi üçün effektiv sayıla bilməz. İndi buna nisbətən effektiv olan bir üsula - birləşdirmə və yerləşdirmə üsullarının “simbioz”una baxaq. Bu üsulun mahiyyəti bundan ibarətdir ki, yeni yaradılan ardıcıllığa əlavə edilən elementi yerləşdirmək üçün hər dəfə bu element yeni ardıcıllığın elementləri ilə soldan başlayaraq (yaxud sağdan) bir-bir müqayisə edilmir. Yazılmalı element yeni ardıcıllığın “mərkəzi” elementi ilə müqayisə olunur, (burada elementlər tək saydadırsa, mərkəzi element var, məsələn, n=9 olduqda mərkəzi element 5-cidir, amma cüt sayda olduqda mərkəzə yaxın hansısa element “mərkəzi” olaraq qəbul edilə bilər, məsələn, n=10 olduqda şərtləşək ki, “mərkəzi” olaraq 6-cı element hesab olunacaq) vəziyyətdən asılı olaraq ya bunların arasına yazılır, ya ardıcıllığın sağ tərəfindəki hissə yenidən yarıya bölünür, ya da sol tərəfindəki hissə yarıya bölünür. Yəni yazılacaq elementin yeri ya sağda, ya da solda axtarılır.Göstərmək olar ki, bu yolla müqayisələrin sayını azaltmaq olar.Yenə c,b,a,v,h,d,x,e ardıcıllığının nizamlanmasına baxaq.

cc

c,b,a,v,h,d,x,e
1-ciaddımda müqayisə yoxdur.

bb

cc

b,a,v,h,d,x,e
2-ci addımda 1 müqayisə var: b ˂ c.

aa

b b

c c

a,v,h,d,x,e
3-cü addımda 2 müqayisə var:
a ˂ c, a˂ b

aa

bb

cc

vv

v,h,d,x,e
4-cü addımda
2 müqayisə var: v ˃b, v˃c

aa

bb

cc

vh

hv

h,d,x,e
5-ci addımda 2 müqayisə
var: h˃c, h˂v.

aa

bb

cc

dd

hh

vv

d,x,e
6-cı addımda
2 müqayisə var: d˃c, d ˂h.

aa

bb

cc

dd

hh

vv

xx

x,e
7-ci addımda 2 müqayisə var: x˃d, x˃v.

aa

bb

cc

dd

ee

hh

vv

xx

e
8-ci addımda 3 müqayisə var: e˃d, e˂v, e˂h.
Ümumi müqayisələrin sayı=14. Göstərmək olar ki, yerləşdirmə üsulunun birinci variantında müqayisələrin sayı 24-ə bərabərdir.
Bu üsulun effektivliyi o zaman yüksəlir ki, nizamlanmalı ardıcıllığın hansısa nizamlanmış alt ardıcıllığından başlanılsın. Belə alt ardıcıllıqlar bir neçə olarsa, bunlardan elementlərinin sayı daha çox olan seçilməlidir.


5.3.Nizamlama üsullarının mürəkkəbliyinin qiymətləndirilməsi

Alqoritmin praktiki mürəkkəbliyini qiymətləndirmək nəzəri mürəkkəbliyi qiymətləndirməkdən daha çətindir. Mürəkkəblik funksiyası əslində alqoritmin işləməsi üçün lazım olan zamanı dəqiq qiymətləndirməyə imkan verməsə də zamanın n-dən asılılığını ifadə etməyə imkan verir[8,15,18].

Praktiki olaraq alqoritmin iş vaxtı nəinki ilkin verilənlərin həcmindən, eyni zamanda onların düzülüşündən və qiymətlərindən asılıdır. Məsələn, bir sıra nizamlama alqoritmlərinin işi, əgər ilkin verilənlər hissə-hissə nizamlanmış olarsa, xeyli sürətlənə bilər. Lakin bu qənaəti hər bir nizamlama alqoritminə aid etmək olmaz. Praktikada nizamlama üsullarının aşağıdakı mürəkkəblik kateqoriyalarına baxılır.
1)Maksimal mürəkkəblik-yəni ən pis halda alqoritmin iş zamanının qiymətləndirilməsi;
2)Minimal mürəkkəblik- yəni ən yaxşı halda mürəkkəbliyin qiymətləndirilməsi;
3)Orta hesabla alqoritmin mürəkkəbliyinin qiymətləndirilməsi.
Tərif: Verilmiş n elementi hər hansı A üsulu ilə nizamlamaq üçün ən pis halda müqayisələrin sayına A üsulunun mürəkkəbliyi deyilir.
“Ən yaxşı hal”, “ən pis hal” dedikdə nizamlama üçün daxil olan informasiyada verilənlərin düzülüş qaydası nəzərdə tutulur. Buraya ilkin verilənlərin qismən nizamlanması, əks istiqamətdə nizamlanması və s. daxildir. Nizamlama üsullari üçün zaman mürəkkəbliyi funksiyaları olaraq adətən aşağıdakılardan istifadə olunur.
T(n²),T(nlogn),T(n). İxtiyari alqoritmin minimal mürəkkəbliyi T(n) funksiyasından kiçik ola bilməz. Müqayisə üsulu ilə qurulan alqoritmin mürəkkəbliliyi T(nlog (n)) funksiyasından böyük ola bilməz.
1) Seçmə üsulunun mürəkkəbliyinin qiymətləndirilməsi. Əgər massivdə n element olarsa bunlardan ən kiçiyini tapmaq üçün müqayisələrin sayı n-1-ə bərabər olacaq. Birinci elementi ilə işarə edək. İkinci elementi tapmaq üçün müqayisələrin sayı n-2-yə bərabər olacaq, bu elementi ilə işarə edək və s., nəticədə ,..., nizamlanmış ardıcıllığı qurulacaq.
Nizamlanmış massivi qurmaq üçün bütün müqayisələrin sayını qiymətləndirək:
T(n)=
n ədədinin böyük qiymətlərində yaza bilərik:
T(n) (5.1)
2) Nizamlanmış alt ardıcıllığı böyütmə üsulunun mürəkkəbliyinin qiymətləndirilməsi. Hər bir ardıcıllıqda nizamlanmış alt ardıcıllıq ola bilər. Bu üsulun mahiyyəti böyük ardıcıllığın nizamlanmamış hissəsinə aid olan elementləri bir-bir nizamlanmış alt ardıcıllıqda parçanı yarıya bölmə üsulu ilə yerləşdirməkdən ibarətdir. Hər dəfə nizamlanmış alt ardıcıllığı şərti olaraq iki bərabər hissəyə ayırmaq olar. Nizamlanmış hissədə elementlərin sayı cüt olduqda parşanı yarıya bölmə əməliyyatı dəqiqliklə yerinə yetirilir, amma tək olduqda bir hissədə elementlərin sayı digərindən vahid qədər artıq olur.
nizamlanmış alt ardıcıllıq olsun.
İki hala baxaq:
1) k - cüt ədəddir, onda:

2) k - tək ədəddir, onda p-ni qiymətləndirmək üçün
, və ya düsturlarından birini qəbul etmək olar.
Fərz edək, funksiyası yeni elementin k sayda elementi olan nizamlanmış alt ardıcıllığa əlavə edilməsi üçün müqayisələrin maksimal sayını qiymətləndirir. k-nın qiyməti artdıqca bu funksiyanın aldığı qiymətləri analiz edək. Fərz edək, k=1. Aydın məsələdir ki, bu halda cəmi bir müqayisə olacaq, ona görə də . k=2 olduqda müqayisələrin maksimal sayı 2-yə bərabərdir. Ümumiyətlə, analiz aşağıdakı
nəticələri verir:

(5.2)
Yuxarıdakı düsturda yazılışı k-nın 2-yə nisbətinin tam qiymətini göstərir. Nizamlanmış alt ardıcıllığı böyütmə üsulunun mürəkkəbliyini qiymətləndirilmək üçün T₂(n) funksiyasını daxil edək. Burada n nizamlanmalı massıvin elementlərinin sayını göstərir. T(n) və T₂(n) funksiyalarının qiymətlərini müqayisə etməyə çalışaq. T(n)-in qiymətləndirilməsi haqqında təsəvvürümüz var. Nizamlanmalı massıvin ən əlverişsiz halı üçün T₂(n) funksiyasını qiymətləndirək. Fərz edək, nizamlanmalı massivin nizamlanmış fraqmenti, yəni alt ardıcıllığı mövcud deyil. Bu halda ardıcıllığın ixtiyari bir elementini nizamlanmış ardıcıllıq kimi qəbul edib bunu parçanı yarıya bölmə üsulu ilə addım-addım böyütmək olar. Belə olan halda maksimal müqayisələrin sayını qiymətləndirmək üçün aşağıdakı düsturdan istifadə olunmalıdır:
T₂(n) U(1)+ U(2)+...+ U(n-1) (5.3)
Məsələn, n=5 olduqda alınır:

olduqda seçmə üsulu ilə müqayisələrin sayı 10-a bərabər olacaq:

və qiymətlərinin müqayisəsi göstərir ki, nizamlanmış alt çoxluğu böyütmə üsulu daha əlverişlidir. n ədədi böyüdükcə ikinci üsulun effektivliyi daha da qabarıq surətdə nəzərə çarpır, məsələn n=10 olduqda alınır:
T(10) =
n= 20 olduqda:

Вir daha qeyd edək ki, nizamlanmış alt ardıcıllığı böyütmə üsulunun ən əlverışsiz halı nəzərdən keçirildi. Əlverişli halda üsulun effektivliyi daha da qabarıq surətdə nəzərə çarpacaq.

1
n
1

Şək.5.2. n/2 və +1 funksiyalarının qrafiklərinin müqayisəsi

İndi də ümumi halda olduğunu analitik qaydada isbat edək.

bərabərsizliyinin isbatında nəzərə alındı ki, n-in çox böyük qiymətlərində n/2 bərabərsizliyi doğrudur. Aşağıdakı cədvəldən göründüyü kimi n-in 8-dən böyük qiymətlərindən sonra n/2 bərabərsizliyi doğrudur və n artdıqca işarəsi tədricən işarəsinə çevrilir.

n	2	4	8	16	32	64
n/2	1	2	4	8	16	32
	2	3	4	5	6	7

Nizamlama üsullarının mürəkkəbliyini qiymətləndirmə üsullarından biri də nizamlama ağacının hündürlüyü əsasında yerinə yetirilir. Budaqlanma ağacının kökündən onun ən uzaq yarpağına qədər yolun tillərinin sayına ağacın hündürlüyü deyilir. Ağacın mühüm göstəricilərindən biri də onun enidir, bu göstərici ağacın şaxələnmə dərəcəsi haqqında təsəvvür yaradır və qurulan variantların sayı ilə qiymətləndirilir. Məsələn, ədədi çoxluğunun elementlərini nizamalamaq üçün binar ağac qursaq, bu ağacın eni S=3!=6-ya bərabər olar (bax: şəkil 5.3).

Hər qurulan variant ağacın yarpaqlarına (son düyünlərinə) uyğun gəlir.

Lemma: Binar ağacın hündürlüyü h-dan böyük deyilsə, yarpaqlarının sayı S= -dan böyük deyil, yəni S_max= .
Binar ağacın hündürlüyünün aşağı həddini qiymətləndirək.


Qeyd edək ki, nizamlama üsullarının nəzəri mürəkkəbliyi əsasında müəyyən bir üsulun mütləq mənada əlverişli olması qənaətinə gəlmək olmaz. Praktiki nizamlama zamanı bir çox hallarda əlverişli nizamlama üsulunun seçilməsi nizamlanmalı ardıcıllığın özündən asılıdır. Məsələn, seçmə və qabarcıqlı üsullarla 9,8,7,6,5,4,3,2,1 tipli ardıcıllığın artma sırası ilə nizamlanması ən əlverişsiz hesab olunur. Sürətli nizamlama və yerləşdirmə üsullarının tətbiqi üçün, əksinə, 1,2,3,4,5,6,7,8,9 tipli ardıcıllıq daha əlverişsiz hesab olunur.

Şək.5.3. Üç fərqli ədədlərini nizamlamaq üçün qurulan ağac