|
Algoritmlarning vaqt va hisoblash murakkabligi
|
| bet | 3/4 | | Sana | 30.07.2023 | | Hajmi | 21.76 Kb. | | #77669 |
Bog'liq 1 Algoritm murakkabligini statik va dinamik o‘lchovlari Vaqt va Boymamatova Rayhona Abduhalil qizi, erkin-iqtisodiy-hududlarni-tashkil-etishda-jahon-tajribasi, H , 1. Пул ва банклар НЎД, KOSMONAVTIKA KUNI, kllqNsMrYUpx59jvw5Q9TAFI6iBIlR1COmUr54Nc, Mavzu Jismoniy madaniyat nazariyasi va metodikasi fan sifatida, McDonald\'s kompaniyasi, Sayyoramizni asrang!, 1701192845, EVTANAZIYA VA PALLIATIV YORDAM ETIK MUAMMOLAR SIFATIDA, Talabalardagi psixologik stress holatini yengishning tarbiyaviy -fayllar.org, Talabalardagi psixologik stress holatini yengishning tarbiyaviy -fayllar.org (1), 1 Aylantiruvchi moment formulasini korsating?-fayllar.orgAlgoritmlarning vaqt va hisoblash murakkabligi.
Algoritmning vaqt murakkabligi (T(N) , qayerda N- topshiriqning o'lchami) - qadamlar bilan o'lchanadigan algoritmning bajarilish vaqti (natijaga erishish uchun bajarilishi kerak bo'lgan algoritm ko'rsatmalari). Ya'ni, bu muammoni hal qilish algoritmini tashkil etuvchi elementar operatsiyalar soni (: =,<>, =, +, -, *, /; va, yoki, emas, xor; qo'ng'iroq qilish, qaytish).
Muammoni hal qilishda kiritilgan ma'lumotlarning kombinatsiyasiga (ekvivalentligi, siyrakligi, tartibliligi va kiritilgan ma'lumotlarning boshqa xususiyatlari) bog'liq bo'lgan uch xil vaqt murakkabligi mavjud.
Bo‘lyapti T(N)= C* N2 kvadrat matritsa uchun amal qiladi.
Bu holda elementar operatsiyalar "+" va "*" kombinatsiyasi hisoblanadi.
Agar asl matritsa identifikatsiya bo'lsa, biz eng yaxshi holatni olamiz.
Agar matritsada elementlarning yarmi 0, yarmi 1 bo'lsa, biz O'rtacha holatni olamiz.
Doimiy BILAN, aniq ifodalab bo'lmaydigan, tashqi omillarning algoritmlarni bajarish vaqtiga ta'sirini tavsiflaydi (kompyuter tezligi, kompilyatsiya tezligi). Shuning uchun algoritmlarning vaqt murakkabligini baholash uchun vaqt birliklaridan foydalanish mutlaqo to'g'ri emas. Bu holda matritsa-vektorni ko'paytirish algoritmining vaqt murakkabligi ga proportsional deyiladi. N2 .
2.2 Ova Ō - belgilar.
Vaqt murakkabligining xulq-atvorining tabiati ortib borayotganida N (N® ¥ ) chaqirdi algoritmning asimptotik murakkabligi.
Asimptotik murakkablikning o'sish tezligini tavsiflash uchun biz foydalanamiz O-notatsiyasi. Algoritmning vaqt murakkabligi tartibida deyilganda N2 :
T(N)= O(N2 )= O(f(N)),
Keyin musbat konstantalar borligi taxmin qilinadi C, n0 =const (C>0), hamma uchun shunday N ³ N0 tengsizlik amal qiladi
T(N) £ C* f(N)
Bu murakkablik bahosining yuqori chegarasi.
Logarifmlar.
Rekursiya.
Algoritmik tuzilmalarni joylashtirish tufayli rekursiv algoritmlarning murakkabligini baholash oson emas.
f(n) Þ f(n* f(n-1))
Masalan, n algoritmini rekursiv baholash uchun! Murakkablik rekursiyaga kiritilgan har bir algoritmning murakkabligiga bog'liq bo'ladi.
Umuman T(n) ~ O(N).
Boshqa rekursiv algoritmlar odatda vaqt murakkabligiga ega T(n) ~ O(a) , qayerda a= const, bu bir xil masalani yechish uchun rekursiv bo'lmagan algoritmning murakkabligidan kattaroq umumiy murakkablikka olib keladi.
|
| |
