1-amaliy mashg’ulot. Ma’lumotlar tuzilmalari ustida bajariladigan amallar. Ma’lumotlarning strukturlashganligi va dasturlash texnologiyasi algoritmlarning murakkabligi

Algoritmlar murakkabligining oʻsish tartibi
Murakkablikning oʻsish tartibi (yoki aksiomatik murakkablik) katta kirish hajmi uchun algoritmning murakkablik funksiyasining taxminiy xatti-harakatini tavsiflaydi. Bundan kelib chiqadiki, vaqt murakkabligini baholashda elementar amallarni koʻrib chiqishning hojati yoʻq, algoritm qadamlarini koʻrib chiqish kifoya.
Algoritm qadami – bu ketma-ket joylashtirilgan elementar amallar toʻplami, uning bajarilish vaqti kirish qadamiga bogʻliq emas, ya’ni yuqoridan qandaydir doimiy bilan chegaralangan.
Asimptotik baholashning koʻrinishlari. F(n)>0 murakkabligini, bir xil tartibdagi g(n)>0 funksiyasini, kirish n>0 oʻlchamini koʻrib chiqaylik.
A
gar f(n) = O (g(n)) va n> n₀ uchun c>0, n₀> 0 konstantalar mavjud boʻlsa, u holda 0

Bu holda g(n) funksiyasi f(n) uchun asimptotik-aniq baho hisoblanadi. Agar f(n) algoritmning murakkablik funksiyasi boʻlsa, unda murakkablik tartibi f(n) uchun - O(g(n)) deb belgilanadi. Ushbu ibora doimiy koeffitsiyentgacha g(n) dan tez oʻsmaydigan funksiyalar sinfini belgilaydi.

Funksional va imperativ dasturlashda ma’lumotlar strukturalarini taqqoslash. Kamida ikkita sababga koʻra funksional tillar uchun ma’lumotlar tuzilmalarini loyihalash imperativ tillarga qaraganda ancha qiyin:

1. 
   Deyarli barcha ma’lumotlar strukturalari aniq funksional uslubda ishlatilmaydigan oʻzlashtirishlardan ogʻir foydalanadilar;
   

2. Ma’lumotlarning funksional strukturalari yanada moslashuvchan, shuning uchun imperativ dasturlashda eski versiya yoʻqoladi, shunchaki yangisi bilan almashtiriladi, funksional ravishda u avtomatik ravishda mavjud boʻlib qoladi. Boshqacha qilib aytganda, imperativ dasturlashda (agar siz dasturni jiddiy ravishda murakkablashtirishi mumkin boʻlgan maxsus choralarni koʻrmasangiz) ma’lumotlar strukturalari vaqtinchalik (ing. ephemeral), funksional dasturlarda ular odatda doimiydir.