|
O’zbekistan respublikasi raqamli texnologiyalar vazirligi muhammad Al-Xorazmiynomidagi Toshkent Axborot texnologiyalari universiteti Nukus filiali Telekommunikatsiya texnologiyalari va kasbiy ta’lim»fakulteti «Axborat qavfsixligi»
|
| bet | 1/4 | | Sana | 21.10.2023 | | Hajmi | 0.88 Mb. | | #89628 |
Bog'liq Abdiganiev Jandos (2) 4-1-5399 илова, 3 kurs ped psox ish reja, Mavzu Induktorli generatorlar Reja, Mavzu Payvandlash transformatorlari, Krassword, python mustaqil ish, Python asoslari (O\'zbekcha), Fonetika va fonologiya111, Tarmoq 1-mustaqil, sun-iy-intellekt-va-uning-insoniyat-faoliyatida-tutgan-o-rni, Baǵıt boyınsha tuwındı, 1-Amaliy topshiriq(KTE), MUSTAQIL, 13.Toplam. 1-
O’ZBEKISTAN RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI
Muhammad Al-Xorazmiynomidagi Toshkent Axborot
texnologiyalari universiteti Nukus filiali
Telekommunikatsiya texnologiyalari va kasbiy ta’lim»fakulteti «Axborat qavfsixligi»yo’nalishi 105-22 guruh talabasi Abdiganiev Jandosning Algoritmlerdi Joybarlaw fanidan
MUSTAQIL ISHI
Mavzu:Algoritmlarni vaqt va hajm bo'yicha baholash.
NUKUS 2023
TOPSHIRDI: __________ J.Abdiganiev
QABUL QILDI: __________ B.Jubanova
Algoritmlarni vaqt va hajm bo'yicha baholash. REJA: 1) Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar. 2) Algoritmlarni eng yomon va o‘rtacha xolatlarda baholash 3) Algoritmlarni vaqt va hajmiy marakkabligini baholashda tekis va logorifmik solishtirma mezonlari. Algoritmning vaqt murakkabligini baholash. Algoritmlar murakkabligi funksiyalarining turlari - Doimiy vaqt Algoritmga algoritm deyiladi doimiy vaqt(vaqt sifatida qayd etilgan O (1)) qiymat bo'lsa T(n) kirish hajmiga bog'liq bo'lmagan qiymat bilan cheklangan. Masalan, massivda bitta elementni olish doimiy vaqtni oladi, chunki uni topish uchun bitta buyruq bajariladi. Biroq, tartiblanmagan massivda minimal qiymatni topish doimiy vaqtdagi operatsiya emas, chunki biz massivning har bir elementini skanerlashimiz kerak. Shunday qilib, bu operatsiya chiziqli vaqtni oladi, O (n). Agar elementlarning soni oldindan ma'lum bo'lsa va o'zgarmasa, bunday algoritmni doimiy vaqt algoritmi deb atash mumkin. "Doimiy vaqt" nomiga qaramay, ish vaqti vazifa hajmidan mustaqil bo'lishi shart emas, lekin ish vaqtining yuqori chegarasi bo'lmasligi kerak. Masalan, "qiymatlarni almashish" vazifasi a va b, zarur bo'lsa, natijada biz olamiz a≤b", doimiy vaqt muammosi hisoblanadi, garchi algoritmning ishlash vaqti tengsizlikning mavjudligiga bog'liq bo'lishi mumkin. a ≤ b yoki yo'q. Biroq, ma'lum bir doimiylik mavjud t, ular uchun vazifani bajarish vaqti har doim oshmaydi t. Quyida doimiy vaqtda ishlaydigan ba'zi kod misollari keltirilgan: Int indeksi = 5; int element = ro'yxat; agar(shart to'g'ri) keyinboshqa doimiy ish vaqti bilan ba'zi operatsiyalarni bajarish uchun i = 1 uchun 100 uchun j = 1 uchun 200 doimiy ish vaqti bilan ba'zi operatsiyalarni bajaradi Agar T(n) bu O ( ba'zi doimiy qiymat), bu ga teng T(n) O (1) dir.
Logarifmik vaqt logarifmik vaqt, agar T(n) = O (log n) ... Kompyuterlar ikkilik tizimdan foydalanganligi sababli, logarifmning asosi sifatida 2 ishlatiladi (ya'ni log 2). n). Biroq, bilan bazani almashtirish logaritmalar log a n va jurnal b n faqat doimiy koeffitsient bilan farqlanadi, bu esa O-katta belgisida bekor qilinadi. Shunday qilib, O (log n) - logarifm asosidan qat'iy nazar, logarifmik vaqt algoritmlari uchun standart belgi. Logarifmik vaqt algoritmlari odatda binar daraxt operatsiyalarida yoki ikkilik qidiruvdan foydalanganda topiladi. O (log n) algoritmlari yuqori samarali hisoblanadi, chunki har bir elementning bajarilish vaqti elementlar sonining ko'payishi bilan kamayadi. Bunday algoritmning juda oddiy misoli qatorni ikkiga bo'lish, ikkinchi yarmini yana yarmiga bo'lish va hokazo. Bu O (log n) vaqtni oladi (bu erda n - satr uzunligi, biz bu erda taxmin qilamiz console.log va str.substring doimiy vaqt talab qiladi). Bu shuni anglatadiki, nashrlar sonini ko'paytirish uchun chiziq uzunligi ikki barobarga oshirilishi kerak. // Chiziqning o'ng yarmini rekursiv chop etish funksiyasi var o'ng = funktsiya (str) (var uzunligi = ko'cha uzunligi; // yordamchi funksiya var help = funktsiya (indeks) ( // Rekursiya: o'ng yarmini chop eting agar (indeks< length ) { // Belgilarni indeksdan satr oxirigacha chop etish konsol. log (str. substring (indeks, uzunlik)); // rekursiv chaqiruv: o'ng tomoni bilan yordamchi funksiyani chaqiring yordam (Math.ceil ((uzunlik + indeks) / 2)); )) yordam (0); )
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
O’zbekistan respublikasi raqamli texnologiyalar vazirligi muhammad Al-Xorazmiynomidagi Toshkent Axborot texnologiyalari universiteti Nukus filiali Telekommunikatsiya texnologiyalari va kasbiy ta’lim»fakulteti «Axborat qavfsixligi»
|
