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

Teorem 8: Əgər .
Teorem 9: 1-dən böyük olan ixtiyari a tam ədədi üçün aşağıdakı münüsibət doğrudur:
log_an=O(n).
İsbatı: teorem 7-yə görə: n 2ⁿ. Buradan alınır ki,
log₂ n log₂2ⁿ= n. Deməli, log₂n=O(n),digər tərəfdən teorem 6-ya əsasən log_an=O(log₂n).Teorem 8-dən alınır ki, log_an=O(n).
Teorem 10: İxtiyari n natural ədədi üçün aşağıdakı münüsibət doğrudur: n!= O(nⁿ)
İsbatı riyazi induksiya ilkə yerinə yetirək:
n=1 olduqda 1 1¹=1 alınır,
n=2 olduqda 2 2²=4 alınır,
n=k olduqda k k^k olduğunu qəbul edək;
(k+1)! k!(k+1) k^k(k+1) (k+1)^k(k+1)= (k+1)^k+1
Teorem 11: İxtiyari a 1və n natural ədədi üçün aşağıdakı münüsibət doğrudur: log_a (n!)= O(nlog_an)

4.2. Mürəkkəbliyinə görə məsələlərin təsnifatı.

Praktikada qarşımıza çıxan bəzi məsələlərin mürəkkəbliyini qiymətləndirək[16,22,23 ].

1. Matrislərin toplanması alqoritminin mürəkkəbliyinin qiymətləndirilməsi. A[1:m,1:k]+B[1:m,1:k] əməliyytını yerinə yetirmək üçün mk sayda elementar əməliyyat yerinə yetirmək lazımdır; max(m,k) = n ilə işarə edək, onda mk n² , yəni bu alqoritmin mürəkkəbliyinin yuxarı həddi O(n²) düsturu ilə qiymətləndirilir. min(m,k) = n ilə işarə etsək, onda o(n²) – bu da mürəkkəbliyin aşağı həddini göstərir.
2.Matrislərin vurulması alqoritminin mürəkkəbliyinin qiymətləndirilməsi. A[1:m,1:k]+B[1:k,1:p] əməliyytını yerinə yetirən zaman mp sayda xanası olan C[1:m,1:p] matrisinin hər xanasını qurmaq üçün k sayda vurma və k-1 sayda toplama əməliyyatını yerinə yetirmək lazımdır. Beləliklə elementar hesab əməllərinin sayı mp(2k-1) olacaq. max(m,p,k)=n işarə etsək, mp(2k-1) 2n³-n²=O(n³).
3.Matrisin transponirə edilməsi alqoritminin mürəkkəbliyinin qiymətləndirilməsi. A[1:m,1:k] matrisi transponirə olunanda yeni qurulan C[1:k,1:m] matrisin elementlərinin sayı A matrisininki qədər olacaq. Sonuncunun hər xanası qurulanda yalnız bir elementar əmıəliyyattdan-mənimsətmə əməliyyatından istifadə olunacaq. Deməli, bu alqoritmin mürəkkəbliyini qiymətləndirəndə mk n² düsturundan istifadə olunmalıdır, buruda n =max(m,k).
4.Çoxhədlinin verilmiş nöqtədə qiymətinin ümumi qaydada hesablanması alqoritminin mürəkkəbliyinin qiymətləndirilməsi. çoxhədlisinin qiymətini ixtiyari c nöqtəsində hesablamaq üçün tələb olunan elementar əməliyyatların sayını qiymətləndirək. birhədlisini hesablamaq üçün n-1 sayda vurma əməliyyatını icra edərək xⁿ ifadəsini hesablamalıyıq, alınan cavabı isə bir dəfə a₀ əmsalına vurmalıyıq. Nəticədə hesab əməllərinin sayı n-ə bərabər olacaq. Hər bir birhədlisini hesablamaq üçün istifadə olunan əməliyyatların sayı n-i ədədinə bərabər olacaq. Alınan birhədliləri toplamaq üçün istifadə olunan toplama əməliyyatlarının sayı n-ə bərabərdir. Deməli, bütün hesab əməliyyatlarının sayı:
n+(n-1)+(n-2)+...+2+1+n= +n=0,5n²+1,5n=O(n²) düsturu ilə qiymətləndirilir.
5. Çoxhədlinin verilmiş nöqtədə qiymətinin Horner sxemi ilə hesablanması alqoritminin mürəkkəbliyinin qiymətləndirilməsi. Göstərək ki, bu alqoritm işləyəndə hesab əməllərinin sayı xeyli azala bilir. Məsələn üç dərəcəli çoxhədlini Horner sxemi ilə hesablasaq, istifadə olunan elementar əməliyyatların sayını qiymətləndirək:

Göründüyü kimi, üç toplama və üç vurmadan ibarət hesablama aparmaq lazımdır. Eyni qayda ilə belə qənaətə gəlmək olar ki, çoxhədlinin dərəcəsi n-ə bərabər olanda n toplama və n vurmadan ibarət hesablama aparmaq lazımdır. Ümumilikdə istifadə olunan əməliyyatların sayı 2n ifadəsi ilə, bu alqoritmin mürəkkəbliyi O(n) düsturu ilə qiymətləndiriləcək. Bu nəticə onu göstərir ki, çoxhədlinin verilmiş nöqtədə qiymətinin Horner sxemi ilə hesablanması alqoritminin mürəkkəbliyi çoxhədlinin verilmiş nöqtədə qiymətinin birbaşa üsulla hesablanması alqoritminin mürəkkəbliyindən kiçikdir.
6.Yüklərin yerləşdirilməsi məsələsinin alqoritminin mürəkkəbliyinin qiymətləndirilməsi.Bir sıra məsələlərin dəqiq həlli həddən artıq hesablama tələb etdiyi üçün bunu praktiki olaraq etmək qeyri-mümkündür. Hətta kompüterin köməyilə hesablama aparsaq, bəzən on illərlə vaxt lazımdır. Məsələn, yüklərin yerləşdirilməsi məsələsinə baxaq. Tutaq ki, 3 adda məhsulu 10000 kq yük tutan maşına yerləşdirmək lazımdır. Bu zaman elə etmək lazımdır ki, yüklənənən məhsulların ümumi çəkisi mümkün olduğu qədər 10000 kq-a yaxın olsun, ancaq bu həddi aşmasın. Müxtəlif variantları qiymətləndirən seçmə məsələsi qarşıya çıxır.

S(20) S(30)

G(50) G(100) G(70 ) G(90)

K(85) K(10) K(35) K(5)