«amaliy matematika va informatika» kafedrasi «Algoritmlar nazariyasi» fanidan Mustaqil ish

O‘ZBEKISTON RESPUBLIKASI

OLIY VA O‘RTA MAXSUS TA’LIM VAZIRLIGI

FARG‘ONA DAVLAT UNIVERSITETI

«AMALIY MATEMATIKA VA INFORMATIKA»

KAFEDRASI

«Algoritmlar nazariyasi» fanidan

Mustaqil ish

Mavzu: Asosiy hisoblash algoritmlarining murakkabligi

Bajardi: 19.08-gurux talabasi B. Turg’unov

Raxbar: K.Karimov

Farg‘ona– 2021 y.

.

Algoritmni bajarishning vaqt turlari

Doimiy vaqt

Algoritm algoritm deyiladi doimiy vaqt (vaqt sifatida qayd etilgan O (1)) agar qiymat T(n) kirish hajmiga bogʻliq boʻlmagan qiymat bilan cheklangan. Masalan, massivda bitta elementni olish doimiy vaqtni talab qiladi, chunki uni topish uchun bitta buyruq bajariladi. Biroq, saralanmagan massivda minimal qiymatni topish doimiy ish emas, chunki biz massivning har bir elementini skanerlashimiz kerak. Shunday qilib, bu operatsiya O (n) chiziqli vaqtni oladi. Agar elementlar 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 ishlash vaqtining yuqori chegarasi boʻlmasligi kerak. Masalan, vazifa «qiymatlarni almashish a va bagar kerak boʻlsa, natijada biz buni qoʻlga kiritamiz a≤b"doimiy vaqt muammosi hisoblanadi, garchi algoritmning ishlash muddati tengsizlikning mavjudligiga bogʻliq boʻlishi mumkin a ≤ b yoki yoʻq. Biroq, maʻlum bir doimiy mavjud tbuning uchun vazifani bajarish vaqti har doim boʻladi oshmaydi t.

Quyida doimiy vaqt ichida ishlaydigan kodning baʻzi bir misollari keltirilgan:

Int indeks \u003d 5; int element \u003d roʻyxat; agar (shart toʻgʻri) keyinboshqa doimiy ish vaqti bilan baʻzi operatsiyalarni bajaring uchun i \u003d 1 ga 100 uchun j \u003d 1 ga 200 kishi doimiy ish vaqti bilan baʻzi operatsiyalarni bajaradi

Agar a T(n) O ( baʻzi bir doimiy qiymat), bu tengdir T(n) O (1) dir.