Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar

Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar

Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar.

Reja:

Algoritm murakkabligini statik va dinamik o‘lchovlari haqida.
Vaqt va xotira hajimi nima.
Algoritm murakkabligi bo‘yicha qiyinchiliklar.

• 
  Mavjud algoritmlarning ko’pchilig xotira va tezlik o’rtasida tanlovni taklif qiladi. Masala tez ishlashi va katta xotira egallashi yoki sekin ishlashi va kichik xotira hajmini egallashi mumkin. Bu holatda eng odatiy misollardan biri eng qisqa masofani topish masalasi bo’la oladi.
  
• 
  Bunda siz o’zaro bog’liq bo’lgan shahar orasidagi istalgan ikki nuqta orasidagi eng qisqa masofani topishingiz kerak bo’ladi. Bunda biz barcha nuqtalar orasidagi qisqa masofalarni aniqlab
  
• 
  ularni jadval shaklida saqlab qo’yishimiz mumkin. Va biz eng qisqa masofanianiqlashimizga to’g’ri kelganda shunchaki jadvaldan ma’lumotni olib qo’yishimiz mumkin bo’ladi.
  

Algoritmlarning murakkabligi odatda bajarilish vaqti yoki foydalanilgan xotiraga qarab baholanadi. Ikkala holatda ham murakkablik kiritilgan ma'lumotlarning hajmiga bog'liq: 100 ta elementdan iborat massiv 1000 ta o'xshashiga qaraganda tezroq qayta ishlanadi.

Shu bilan birga, kam odam aniq vaqt haqida qayg'uradi: bu protsessorga bog'liq, ma'lumotlar turi, dasturlash tili va boshqa ko'plab parametrlar. Faqat asimptotik murakkablik muhim, ya'ni kirishning o'lchami cheksizlikka moyil bo'lganligi sababli murakkablik.
Aytaylik, ba'zi bir algoritm n ta kiritilgan ma'lumotlar elementini qayta ishlash uchun 4n 3 + 7n shartli operatsiyalarni bajarishi kerak.
n ortishi bilan umumiy ish vaqti n ni kubga ko'tarish uni 4 ga ko'paytirish yoki 7n qo'shishdan ko'ra sezilarli darajada ko'proq ta'sir qiladi. Keyin biz aytamizki, bu algoritmning vaqt murakkabligi O(n 3) ga teng, ya'ni u kiritilgan ma'lumotlarning hajmiga kubik bog'liq.
O kapitalidan foydalanish (yoki O-notatsiyasi deb ataladigan) matematikadan kelib chiqadi, bu erda u funktsiyalarning asimptotik xatti-harakatlarini solishtirish uchun ishlatiladi.
Rasmiy ravishda O(f(n)) algoritmning ishlash vaqti (yoki band boʻlgan xotira miqdori) kiritilgan maʼlumotlar miqdoriga qarab f(n) ga koʻpaytiriladigan baʼzi bir doimiydan tezroq oʻsishini bildiradi.
Algoritmning vaqt murakkabligi T - uni bajarish uchun zarur bo'lgan vaqt. Bu elementar harakatlar sonining bitta harakatni bajarish uchun o'rtacha vaqtga ko'paytmasiga teng: T = kt.
Shu darajada t algoritmni amalga oshiruvchi ijrochiga bog'liq bo'lsa, algoritmning murakkabligi birinchi navbatda quyidagilarga bog'liq deb taxmin qilish tabiiydir. k. Shubhasiz, algoritmni bajarishdagi operatsiyalar soni ko'p jihatdan qayta ishlanadigan ma'lumotlar miqdoriga bog'liq.
Haqiqatan ham, 100 000 ta familiya ro'yxatini alifbo tartibida tartiblash uchun 100 000 ta familiya ro'yxatini tartiblashdan ko'ra ancha kam operatsiyalar talab etiladi. Shuning uchun algoritmning murakkabligi kiritilgan ma'lumotlar miqdorining funktsiyasi sifatida ifodalanadi.
Agar bitta halqa boshqasining ichiga o'rnatilgan bo'lsa va ikkala tsikl ham bir xil o'zgaruvchining o'lchamiga bog'liq bo'lsa, unda butun qurilish kvadratik murakkablik bilan tavsiflanadi. i uchun:=1 dan N gacha j uchun:=1 dan N gacha Boshlash ... oxiri; Ushbu dasturning murakkabligi O(N 2).
Bu algoritmning murakkabligi O(N), chunki sikl tanasi N marta bajariladi va sikl tanasining murakkabligi O(1) ga teng.


Algoritmning murakkabligini tahlil qilishning ikkita usuli: pastdan yuqoriga (ichki nazorat tuzilmalaridan tashqi boshqaruvga) va tushayotgan (tashqi va ichki tomondan).
Raqamlar bo'yicha tartiblash o'rniga, biz oddiygina massivni 2 qismga bo'lamiz va massivdagi o'rtacha sonni tekshiramiz. Biz 4-hujayrada joylashgan raqamni topamiz va uni tekshiramiz (rasmdagi ikkinchi qator). Bu raqam 16, biz esa 23 ni qidiramiz. Hozirgi raqam kamroq.
Bu nimani anglatadi? Nima oldingi barcha raqamlarni (ular 16 raqamidan oldin joylashgan) tekshirib bo'lmaydi: ular, albatta, biz izlayotgan narsadan kamroq bo'ladi, chunki bizning massivimiz tartiblangan!
Qolgan 5 ta element orasida qidirishni davom ettiramiz. E'tibor bering: biz faqat bitta tekshiruvni amalga oshirdik, ammo mumkin bo'lgan variantlarning yarmini allaqachon yo'q qildik. Bizda faqat 5 ta narsa qoldi.
http://hozir.org