Analysis of Algorithms

Output maximum element of A
currentMax  A[0]
for i  1 to n  1 do
if A[i]  currentMax then
currentMax  A[i]
return currentMax

Psevdokod tafsilotlari

• Nazorat oqimi
• if … then … [else …]
• while … do …
• repeat … until …
• for … do …
• Qavslar o'rnini bosadi
• Usul deklaratsiyasi

Algoritm usuli ( arg [, arg …])

Kiritish …

Chiqish …

• Method call

var.method (arg [, arg…])

• Return value

return expression

• Expressions
• Assignment (like  in Java)
• Equality testing (like  in Java)

n2 Superscripts and other mathematical formatting allowed

RAM

• CPU _
• Har birida ixtiyoriy raqam yoki belgi bo'lishi mumkin bo'lgan potentsial cheklanmagan xotira yadrolari banki

0
1
2

• Xotira yadrolari raqamlangan va xotiradagi istalgan yadroga kirish birlik vaqtni oladi.

Primitiv operatsiyalar

• Algoritm orqali bajariladigan asosiy hisoblar
• Psevdokodda aniqlanishi mumkin
• Dasturlash tilidan ko'p jihatdan mustaqil
• Operativ xotira modelida doimiy vaqt talab qilinadi

• Misollar:
• Ifodani baholash
• O'zgaruvchiga qiymat berish
• Massivga indekslash
• Usulni chaqirish
• Usuldan qaytish

Primitiv operatsiyalarni hisoblash

• Psevdokodni tekshirish orqali biz kirish hajmiga bog'liq holda algoritm tomonidan bajariladigan primitiv operatsiyalarning maksimal sonini aniqlashimiz mumkin.

Algorithm arrayMax(A, n)
# operations
currentMax  A[0] 2
for i  1 to n  1 do 2n
if A[i]  currentMax then 2(n  1)
currentMax  A[i] 2(n  1)
{ increment counter i } 2(n  1)
return currentMax 1
Total 8n  2

Ishlash vaqtini hisoblash

• Algoritm arrayMax 8 n ni bajaradi  eng yomon holatda 2 ta primitiv amal. Belgilang:

a = Eng tez primitiv operatsiya tomonidan olingan vaqt

b = Eng sekin primitiv operatsiya tomonidan qabul qilingan vaqt

• T ( n ) arrayMax ning eng yomon vaqti bo‘lsin . Keyin a (8 n  2)  T ( n )  b (8 n  2)
• Demak, ish vaqti T ( n ) ikkita chiziqli funksiya bilan chegaralangan

Ishlash vaqtining o'sish sur'ati

• Uskuna/dasturiy muhitni o'zgartirish
• T ( n ) ga doimiy omil bilan ta'sir qiladi , lekin
• T(n) ning o'sish tezligini o'zgartirmaydi
• T(n) ish vaqtining chiziqli o'sish tezligi arrayMax algoritmining o'ziga xos xususiyatidir.

Yetti muhim funksiya

• Algoritm tahlilida tez-tez paydo bo'ladigan yetti funktsiya:
• Constant  1
• Logarithmic  log n
• Linear  n
• N-Log-N  n log n
• Quadratic  n2
• Cubic  n3
• Exponential  2n

• Log-log diagrammasida chiziqning qiyaligi funktsiyaning o'sish tezligiga mos keladi

Doimiy omillar

• O'sish sur'ati ta'sir qilmaydi
• doimiy omillar yoki
• pastki tartibli shartlar
• Misollar
• 10 2 n + 10 5 chiziqli funksiya hisoblanadi
• 10 5 n 2 + 10 8 n kvadratik funktsiyadir

Big-Oh belgisi

• Berilgan f ( n ) va g ( n ) funksiyalari f ( n ) O ( g ( n )) deb aytamiz. c va n 0 musbat konstantalar mavjud bo'lsa shunday

f(n)  cg(n) for n  n0

• Misol: 2 n + 10 - O ( n )
• 2 n + 10  cn
• ( c  2) n  10
• n  10 / ( c  2)
• c = 3 va n 0 = 10 ni

Big-Oh misoli

• n 2 funksiyasi O ( n ) emas
• n 2  cn
• n  c
• Yuqoridagi tengsizlikni qondirish mumkin emas, chunki c doimiy bo'lishi kerak

Ko'proq Big-Oh misollari

• 7n-2

7n-2 is O(n)
need c > 0 and n0  1 such that 7n-2  c•n for n  n0
this is true for c = 7 and n0 = 1

• 3n3 + 20n2 + 5

3n3 + 20n2 + 5 is O(n3)
need c > 0 and n0  1 such that 3n3 + 20n2 + 5  c•n3 for n  n0
this is true for c = 4 and n0 = 21

• 3 log n + 5

3 log n + 5 is O(log n)
need c > 0 and n0  1 such that 3 log n + 5  c•log n for n  n0
this is true for c = 8 and n0 = 2

Asimptotik algoritmlarni tahlil qilish

• Algoritmning asimptotik tahlili big-Oh yozuvida ishlash vaqtini aniqlaydi
• Asimptotik tahlilni o'tkazish uchun
• Biz kirish hajmiga bog'liq holda bajarilgan primitiv operatsiyalarning eng yomon sonini topamiz.
• Biz bu funktsiyani big-Oh belgisi bilan ifodalaymiz
• Misol:
• arrayMax algoritmi ko'pi bilan 8 n ni bajarishini aniqlaymiz  2 ta primitiv amal
• arrayMax algoritmi “ O ( n ) vaqtida ishlaydi ” deymiz.
• Doimiy omillar va pastki tartibli atamalar oxir-oqibatda olib tashlanganligi sababli, biz primitiv operatsiyalarni hisoblashda ularni e'tiborsiz qoldirishimiz mumkin.

Hisoblash prefiksining o'rtacha ko'rsatkichlari

• Biz asimptotik tahlilni o'rtacha prefikslar uchun ikkita algoritm bilan ko'rsatamiz
• X massivning o'rtacha i - prefiksi birinchisining o'rtacha ( i + 1) X ning elementlari :

A [ i ] = ( X [0] + X [1] + … + X [ i ])/( i +1)

O'rtacha prefiks (kvadrat)

• Quyidagi algoritm ta'rifni qo'llash orqali kvadratik vaqtda o'rtacha prefikslarni hisoblaydi

Algorithm prefixAverages1(X, n)
Input array X of n integers
Output array A of prefix averages of X #operations
A  new array of n integers n
for i  0 to n  1 do n
s  X[0] n
for j  1 to i do 1 + 2 + …+ (n  1)
s  s + X[j] 1 + 2 + …+ (n  1)
A[i]  s / (i + 1) n
return A 1

Arifmetik progressiya

• PrefiksAverages1 ning ishlash vaqti O (1 + 2 + … + n )
• Birinchi n ta butun sonning yig'indisi n ( n + 1) / 2
• Bu haqiqatning oddiy vizual isboti mavjud
• Shunday qilib, prefiksAverages1 algoritmi O ( n 2 ) vaqtida ishlaydi

Prefiks o'rtachalari (chiziqli)

• Quyidagi algoritm amaldagi summani saqlab, chiziqli vaqtda o'rtacha prefikslarni hisoblaydi

• Algoritm prefiksiAverages2 O ( n ) vaqtida ishlaydi

Algorithm prefixAverages2(X, n)
Input array X of n integers
Output array A of prefix averages of X #operations
A  new array of n integers n
s  0 1
for i  0 to n  1 do n
s  s + X[i] n
A[i]  s / (i + 1) n
return A 1

Matematikani ko'rib chiqishingiz kerak

• Logarifmlarning xususiyatlari:

log b (xy) = log b x + log b y

log b (x/y) = log b x - log b y

log b xa = alog b x

log b a = log x a/log x b

• eksponensial xossalari :

a (b+c) = a b a c

a bc = (a b ) c

a b / a c = a (bc)

b = a log a b

b c = a c*log a b

• Xulosa
• Logarifmlar va darajalar
• Tasdiqlash texnikasi
• Asosiy ehtimollik