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

Algoritmni bajarish vaqti uchun soddalashtirishlar

D.Knutning ishlarida algoritmlarning bajarilish vaqtini tahlil qilish uchun quyidagi yondashuv taklif qilingan: umumiy vaqt har bir asosiy operatsiya uchun qiymati * chastota qiymatlari yigʻindisidir. Asosiy operatsiyalarga qoʻshish, koʻpaytirish, boʻlish, massivdan indeks boʻyicha element olish, butun sonlarni taqqoslash va hk kiradi. Bu holda algoritmni bajarish vaqtini hisoblash juda zerikarli ekanligini koʻrish oson. Shuning uchun A. Turing algoritmlarning bajarilish vaqti taxminlarining taxminiy taxminlaridan ham foydalanish qulay: algoritmning ishlashi paytida ularning paydo boʻlish chastotasiga qarab har xil operatsiyalarga ogʻirliklarni belgilash mumkin va faqat eng katta ogʻirliklarga mos keladigan operatsiyalar. Masalan, matritsalarni koʻpaytirishda siz faqat koʻpaytirish va raqamlarni yozish kabi amallarni koʻrib chiqishingiz kerak, chunki bu eng keng tarqalgan operatsiyalar.Faqat eng koʻpini hisobga olgan holdatez-tez sodir boʻladigan operatsiyalar - birinchi soddalashtirishalgoritmlarning bajarilish vaqtini taxminiy hisoblash uchun taklif qilingan.

Ikkinchi soddalashtirish algoritmni bajarish vaqtini yakuniy baholashga ozgina hissa qoʻshadigan quyi tartibli atamalarni (yaʻni, atamalarni) bekor qilishdan iborat. Masalan, (bundan keyin N raqami kirish maʻlumotlarining hajmini tavsiflaydi),

\\ (1/6 N ^ 3 + 20N + 16 \\ sim 1 / 6N ^ 3 \\),

\\ (1 / 6N ^ 3 \\) oʻrniga "bu algoritmning murakkabligi bor (O (N ^ 3) \\), oʻrniga \\ (3N ^ 4 \\) yozing" bu algoritmning murakkabligi bor \\ (O (N ^ 4) ))).

O-katta taʻrif

Ular \\ (f \\) \\ "g \\" dan \\ (x \\ dan x_0 \\) gacha "O katta", agar \\ (C\u003e 0 \\) doimiy mavjud boʻlsa, hamma uchun \\ (x \\) \\ (x_0 \\) nuqtaning mahallasidan \\ (| f (x) | \\ leq C | g (x) | \\) tengsizlik bajariladi. Quyida taʻrifning illyustratsiyasi keltirilgan (\\ (x \\) oʻqi kirish maʻlumotlarining kattaligi, \\ (y \\) oʻqi algoritmning bajarilish vaqti). Maʻlum bir nuqtadan boshlab, kirish maʻlumotlarining hajmi \\ (\\ propto \\) \\ (f (n) \\) ga intilgandan soʻng, \\ (g (n) \\) ga nisbatan sekin oʻsib borishini va umuman \\ (g (n) \\) goʻyo uni yuqoridan cheklab qoʻygandek.

Misollar. \\ (1 \u003d O (N), N \u003d O (N ^ 2). \\)

\\ (O (N) \\) shaklini baholash bilan bir qatorda, \\ (\\ Omega (N) \\) (katta omega) bahosi ishlatiladi. Bu funktsiya oʻsishining pastki chegarasini bildiradi. Masalan, algoritmning amallar soni \\ (f (N) \u003d \\ Omega (N ^ 2) \\) funktsiyasi bilan tavsiflansin. Bu shuni anglatadiki, hatto eng muvaffaqiyatli holatda ham kamida \\ (N ^ 2 \\) harakatlar bajariladi. \\ (O (N ^ 3) \\) smetasi eng yomon holatda \\ (N ^ 3 \\) harakatlar tartibidan koʻproq boʻlmasligini kafolatlaydi. Bundan tashqari, \\ (\\ Theta (N) \\) (teta) bahosi ishlatiladi, bu esa yuqori va pastki asimptotik taxmin hisoblanadi.\\ (O (N) \\) va \\ (\\ Omega (N) \\) oʻyini.Shunday qilib, \\ (O (N) \\) - bu eng yomon kirish maʻlumotlari boʻyicha algoritmning taxminiy bahosi,\\ (\\ Omega (N) \\) - eng yaxshi maʻlumot,\\ (\\ Theta (N) \\) - xuddi shu narsa uchun stenografiya\\ (O (N) \\) va \\ (\\ Omega (N) \\).