|
1-ma’ruza. Algoritm tushunchasi. Algoritmni asosiy ta`riflari, xossalari va ularning turlari Oddiy klassik algoritmlar. Algoritm tushunchasi
|
| bet | 8/9 | | Sana | 17.05.2024 | | Hajmi | 48,86 Kb. | | #240309 |
Bog'liq 1-MavzuO (n2) - kvadratik murakkablik. Bunday murakkablik, masalan, element qoʻshilishi natijasida yangi saralash algoritmiga ega. Kanonik dasturda bu ikkita ichki sikldan iborat: biri butun massivni bosib oʻtish, ikkinchisi esa allaqachon ajratilgan qismdan keyingi element uchun joy topish. Shunday qilib, amallar soni n*n, ya’ni n2 kabi massiv oʻlchamiga bogʻliq boʻladi.
Murakkablikning boshqa koʻrinishlari ham mavjud, ammo ularning barchasi bir xil prinsipga asoslanadi.
Algoritmning ishlash vaqti umuman kiritilgan ma’lumotlarning hajmiga bogʻliq emasligi ham sodir boʻladi. Bu holda murakkablik O(1) bilan belgilanadi. Masalan, massivning uchinchi elementi qiymatini aniqlash uchun elementlarni eslab qolishingiz yoki ular orqali bir necha bor oʻtishingiz shart emas. Siz har doim ma’lumotlarni kiritish oqimidagi uchinchi elementni kutishingiz kerak va bu esa siz uchun natija boʻladi, bu har qanday ma’lumot uchun hisoblash uchun bir xil vaqtni oladi.
Baholash muhim boʻlgan taqdirda xotiradan xuddi shu tarzda amalga oshiriladi. Biroq, algoritmlar kirish ma’lumotlarining hajmi boshqalarga nisbatan kattalashganda sezilarli darajada koʻproq xotiradan foydalanishi mumkin, ammo ular tezroq ishlaydi va aksincha. Bu hozirgi sharoit va talablar asosida muammolarni hal qilishning eng yaxshi usullarini tanlashga yordam beradi.
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> n0 uchun c>0, n0> 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.
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
1-ma’ruza. Algoritm tushunchasi. Algoritmni asosiy ta`riflari, xossalari va ularning turlari Oddiy klassik algoritmlar. Algoritm tushunchasi
|
