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

Mürəkkəblik haqqında teoremlər.
Teorem1: Fərz edək ki, f funksiyasının yuxarı asimptotu g-yə bərabərdir, onda cf(n) funksiyasının da yuxarı asimptotu həmin funksiyaya bərabərdir. Burada c hər hansı sabitdir.

İsbatı:

Şərtə görə:

│cf(n)│ │c││f(n)│ │c││k││g(n)│=c₁│g(n)│
Deməli,
Teoem 2: Əgər f(n) və h(n) funksiyalarının hər birinin yuxarı asimptotu g(n)-ə bərabər olarsa, onda bunların cəmindən ibarət olan funksiyanın yuxarı asimptotu da g(n) funksiyasına bərabər olar.
İsbatı:
=(c₁+c₂) g(n) = c g(n)
Teorem3: Əgər və olarsa, olar. İsbatı: c₁ g(n) c₂ e(n) =c g(n) e(n) . Burada c=c₁c₂.
Teorem 4: İxtiyari 1 natural və r həqiqi ədədləri üçün n^{r s}, yəni n^r= O(n^s).
İsbatı: Doğurdan da r bərabərsizliyinin hər iki tərəfini ln n-ə vursaq, r ln n ln n. Buradan ln n^r ln n^s ,yəni n^r n^s.
Teorem 5: Tutaq ki, P(n)=a_k n^k +a_k-1 n^k-1+...+a₁ n+a₀ n-dən asılı olan çoxhədlidir. Onda: P(n)=O (n^k) .
İsbatı:│p(n)│ │a_kn^k+a_k-1n^k-1+...+a₁n +a₀│ │a_kn^k│+
│a_k-1n^k-1│+...+│a₁n│+│ a₀│ │a_k│n^k+│a_k-1│n^k-1 +...+│a₁│n+
│ a₀│ (│a_k│+│a_k-1│ +...+│a₁│+│a₀│) n^k =cn^k.
Deməli, P(n)=O (n^k) .
Bu teorem göstərir ki, P(n) çoxhədlisinin majorantı onun ən yüksək dərəcəli birhədlisinin majorantına, yəni n^k ifadəsinə bərabərdir.
Teorem 6:1-dən böyük olan ixtiyari a və b tam ədədləri üçün aşağıdakı münüsibət doğrudur:
log_an=O(log_bn).
İsbatı: log_an= =clog_b n
Teorem 7: İxtiyari n natural ədədi üçün aşağıdakı münüsibət doğrudur:
n=O(2ⁿ).
İsbatı riyazi induksiya ilkə yerinə yetirək:
n=0 olduqda o 2⁰=1 alınır, bu doğrudur;
n=1 olduqda 1 2¹=2 alınır, bu da doğrudur;
n=k olduqda k 2^k olduğunu qəbul edək;
k+1 k+k 2^k+2^k=2^k+1