1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar



Download 101,89 Kb.
bet18/19
Sana14.06.2022
Hajmi101,89 Kb.
#672007
1   ...   11   12   13   14   15   16   17   18   19
Bog'liq
1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va

Vaqtinchalik murakkablik - uzunlikdagi kirish ma'lumotlari bo'yicha algoritmning ishlash vaqtining asimptotik bahosi P. Shubhasiz, hisoblash protseduralarini parallellashtirish mavjud bo'lmaganda, algoritmning ishlash vaqti bajarilgan operatsiyalar soni bilan yagona aniqlanadi. Operatsiyalarning davomiyligini ifodalovchi doimiy koeffitsientlar vaqt murakkabligi tartibiga ta'sir qilmaydi, shuning uchun operatsion va vaqt murakkabligi uchun formulalar ko'pincha bir-biriga to'g'ri keladi.
Kapasitiv murakkablik - uzunlikdagi kirish ma'lumotlari bo'yicha algoritmni bajarishda bir vaqtning o'zida mavjud bo'lgan skalerlar sonining asimptotik bahosi P.
Strukturaviy murakkablik - algoritmdagi boshqaruv tuzilmalari sonining xarakteristikasi va ularning interpozitsiyasining o'ziga xosligi.
Kognitiv murakkablik - amaliy sohalardagi mutaxassislar tomonidan tushunish uchun algoritm mavjudligining xarakteristikasi.
Asimptotiklarning turlari va belgilanishi
Algoritmlarning asimptotik tahlilida matematik asimptotik tahlilning yozuvidan foydalanish odatiy holdir. Bunday holda, algoritmlarning murakkabligining uchta bahosi (asimptotikasi) ko'rib chiqiladi, ular quyidagicha belgilanadi:

  • 1) / (i) = O ^ (n))- murakkablik funksiyasining asimptotik aniq bahosi / («), yoki algoritmning operatsion murakkabligi;

  • 2) /(n) = 0 (§ (n)) - murakkablik funktsiyasi uchun asimptotik keskin yuqori chegara / ( P);

  • 3) / (n) =? 2 (# (n)) murakkablik funksiyasi uchun asimptotik aniq past bahodir / ( P).

Belgilash o'rniga C1 ^ (n)) juda tez-tez "o" harfi bilan oddiyroq o (^ (")) kichik kursivda ishlatiladi.
Formulalarning semantikasini misol orqali tushuntirib beraylik: agar u / (i) = 0 (^ 2 (l)) deb yozilsa, BU funksiyani bildiradi. g (n) = og2 (n) murakkablik funksiyasi uchun asimptotik aniq bahodir / (a). Aslida, bayonot shaklida ikki pozitsiyali ta'rif mavjud:
Agar f (n)= @ (jurnal 2 (")),
mo g (n)= log 2 (l) - f (n) uchun asimptotik keskin taxmin.
E'tibor bering, doimiy omil algoritmning murakkablik tartibiga ta'sir qilmaydi, shuning uchun logarifmik murakkablikni ko'rsatishda logarifm asosi o'tkazib yuboriladi va ular shunchaki / (n) = @ (log (n)) ni yozib, shuni nazarda tutadi. logarifm birdan katta ixtiyoriy asosga ega.
Asimptotiklarning rasmiy ta'riflari
Mehnat intensivligi funksiyasining asimptotik keskin bahosi Bilan, Bilan 2, n 0 shunday bo'lsinki, n> n 0 uchun f (n) funksiyasi o'zgarmas koeffitsientlargacha funksiyadan farq qilmaydi. g ( l), keyin funksiya g (n) f (x) funktsiyasi uchun asimptotik o'tkir taxmin deyiladi.

  • s], s 2 e F, x bilan > 0, 2> bilan 0:

    • (3 l 0 e K, l 0> 0: (/ l e K, l> l 0: 0 g (n) / (l) = 0 (? (L)),

bu yerda 9 ^, N mos ravishda barcha haqiqiy va natural sonlar to‘plamidir.
Murakkablik funksiyasi uchun asimptotik keskin yuqori chegara og'zaki ravishda quyidagicha aniqlanadi: agar ijobiy raqamlar bo'lsa Bilan va n 0 shunday bo'lsinki, n> n 0 uchun f (n) funksiya funktsiyadan tezroq o'smaydi. g (n) doimiy koeffitsient c gacha, keyin funksiya g (n) funksiya uchun asimptotik keskin yuqori chegara deyiladi Ap).
Ta'rifning aniqroq rasmiy belgisi quyidagicha:

  • Bilan e % s> 0:

    • (3 l 0 e X, l 0> 0: (/ l e K, l> l 0: 0 s? # (L))) 0 (g (n))

Murakkablik funktsiyasi uchun asimptotik keskin pastki chegara og'zaki ravishda quyidagicha aniqlanadi: agar ijobiy raqamlar bo'lsa Bilan va n 0 shunday bo'lsinki, n> n 0 uchun f (n) funksiya funksiyadan sekin o'smaydi. g (n) doimiy omilgacha Bilan, u holda funksiya?(l) funksiya uchun asimptotik keskin pastki chegara deyiladi
Ta'rifning aniqroq rasmiy belgisi quyidagicha:

  • Bilan e 9 ^, Bilan > 0:

    • (3 i 0 e X, i 0> 0: (/ i e K, i men 0: 0 s? g (n)

/(men) = 0. ^ (N))
Quyidagilarga e'tibor bering:

  • 1) asimptotikaning rasmiy ta'riflarida ko'rsatilgan tengsizliklar, umumiy holda, bir emas, balki ba'zi funktsiyalar to'plamini, ko'pincha cheksiz atamalar to'plamini qondirishi mumkin, shuning uchun konstruktsiyalar Q (g (n)), 0 ^ (n)) va 0. ^ (N)) ramziy qiladi ko'p funktsiyalar u bilan mehnat intensivligining tekshirilgan funktsiyasi f (i) solishtiriladi; shundan kelib chiqqan holda, f (x) = 0 (q (x)), f (f0 = 0 (q max (n)), d) = q 2 (q mn (x)) ko'rinishdagi asimptotikaning yozuvida. ) "=" belgisi o'rniga "e" belgisidan foydalanish oqilonaroq bo'ladi;

  • 2) konstruksiyalar (d ^ (n)), 0 ^ (n)) va ? 1 ^ (n)), Ba'zi miqdorlar uchun belgi sifatida qo'llaniladigan so'zlar mos ravishda quyidagicha o'qilishi kerak: mos keladigan har qanday funktsiya tezroq o'smaydi va sekinroq o'smaydi. g (n).


Download 101,89 Kb.

Do'stlaringiz bilan baham:
1   ...   11   12   13   14   15   16   17   18   19




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish