Mavzu: Algoritmlarni loyihalash. Algoritm korrekt va samaradorligini baholash. Kvadrat tenglama ildizlarini aniqlash algoritmi. Uchburchak yuzasi uchun Geron formulasi, Gorner sxemasi

Mavzu: Algoritmlarni loyihalash. Algoritm korrekt va samaradorligini baholash. Kvadrat tenglama ildizlarini aniqlash algoritmi. Uchburchak yuzasi uchun Geron formulasi, Gorner sxemasi
Ishdan maqsad: Algoritmlarni samaradorligini baholash. Kvadrart tenglama ildizlarini hisoblash hamda uchburchak yuzini hisoblashda Geron formulasidan foydalanish algoritmini ishlab chiqish.


Hisoblash algoritmlarining to'g'riligi(korrektligi) va shartliligi
Hisoblash algoritmi - bu masalaning ixtiyoriy ruxsat etilgan boshlang'ich ma'lumotlari bo'yicha aniq tasvirlangan operatsiyalar ketma-ketligi bo'lib, uning natijasi masalaning raqamli yechimidir.
Agar hisoblash algoritmi to'g'ri(korrekt) algoritm deb ataladi

1. 
   hisoblash qurilmasi uchun elementar bo'lgan cheklangan miqdordagi operatsiyalarni bajargandan so'ng, o'zboshimchalik bilan ruxsat etilgan dastlabki ma'lumotlar muammoning echimiga aylantiriladi;
   
2. 
   dastlabki ma'lumotlarning kichik buzilishlariga nisbatan hisoblash natijasi barqaror, ya'ni. hisoblash xatosi bo'lmasa, natija doimiy ravishda dastlabki ma'lumotlarga bog'liq;
   
3. 
   natija hisoblash barqaror, ya'ni. agar natijaning hisoblash xatosi (yaxlitlash xatosi) nolga moyil bo'lsa, chunki mashina epsilon nolga intiladi.
   

Agar ushbu uchta shartdan kamida bittasi buzilgan bo'lsa, algoritm noto'g'ri deb ataladi.

Algoritm samaradorligi.
Algoritmni tahlil qilish uchun algoritmning vaqt murakkabligini tahlil qilish odatda kirish ma'lumotlarining o'lchamiga qarab ishlash vaqtini baholash uchun ishlatiladi . Natija odatda "O" katta shaklida ifodalanadi. Bu algoritmlarni solishtirish uchun, ayniqsa katta hajmdagi ma'lumotlarni qayta ishlashda foydalidir
Harakatlar ketma-ket bajarilgan taqdirda, algoritmning murakkabligi O(K + J) ga teng bo'ladi va shuning uchun O(max (K, J)) . Misol uchun, agar A n^2 va B n bo'lsa, u holda algoritmning murakkabligi O(n^2 + n) bo'ladi.
Ushbu ro'yxatdagi funktsiya qanchalik yuqori bo'lsa, bu taxmin bilan algoritm tezroq ishlaydi.
1. C doimiy
2. log(log(N))
3. log(N)
4. N^C, 05. N
6. N*log(N)
7. N^C, C > 1
8. C^N, C>1
9. N!
Agar biz murakkablik tenglamasi ushbu funktsiyalarning bir nechtasini o'z ichiga olgan algoritmning murakkabligini baholamoqchi bo'lsak, u holda tenglamani jadvalda quyidagi funktsiyaga qisqartirish mumkin. Masalan, O(log(N)+N!)=O(N!).
Algoritm samaradorligining asosiy sinflari
1 - doimiy. Kirish ma'lumotlarining hajmidan qat'iy nazar, belgilangan vaqt ichida ishlaydigan algoritmlarni tavsiflaydi.
log n logarifmikdir. Muammoning o'lchami har bir iteratsiyada doimiy miqdorga kamaytiriladigan algoritmlarga xosdir. Misol: ikkilik qidiruv algoritmi.
p - chiziqli. n ta element roʻyxatini skanerlovchi algoritmlarni tavsiflaydi. Misol: ketma-ket qidiruv algoritmi.
n log n - /7-log-n. Shaxsiy maqsadlar usuli bilan ishlab chiqilgan algoritmlar uchun odatiy. Misollar: birlashtirish, tez tartiblash.
n ~ kvadratikdir. Ikkita o'rnatilgan tsiklni o'z ichiga olgan algoritmlarni tavsiflaydi. Misollar: oddiy tartiblash algoritmlari, n * n matritsalarni qayta ishlash algoritmlari .
n ³ - kub. Uchta ichki halqani o'z ichiga olgan algoritmlar uchun odatiy. Misol: murakkab chiziqli algebra algoritmlari.
2 ⁿ - eksponensial. n ta elementdan iborat ba'zi bir to'plamning barcha kichik to'plamlarini qayta ishlovchi algoritmlarni tavsiflaydi . "Eksponensial" atamasi ko'pincha eksponensialdan tezroq o'sishning juda yuqori tartiblarini bildirish uchun erkin ishlatiladi.
Va! - faktorial. Ba'zi n elementlar to'plamining barcha almashtirishlarini qayta ishlaydigan algoritmlar uchun odatiy.

(1)T: algoritm samarali deb ataladi agar real kirish ma'lumotlari uchun u tezkor amalga oshirilsa.
(2)T: algoritm samarali deb ataladi agar u sifatli bajarilishni “to’liqqidirish”(полнiy перебор)ga nisbatan tezroq ta'minlasa."To'liq qidirish" usuliga qaraganda ancha yaxshi ishlashni ta'minlaydigan algoritmlar, deyarli har doim qimmatli evristik g'oyani o'z ichiga oladi, buning natijasida ushbu yaxshilanishga erishiladi; Bundan tashqari, ular ko'ribchiqilayotgan masalaning ichki tuzilishi va hisoblash qobiliyati haqida foydali ma'lumotlarni taqdim etadilar