|
Ushbu harakatlar ketma-ketligi muammomizni hal qilishga imkon beradimi? Ha, shunday boʻladi. Ushbu echim boʻladimi samarali? Zoʻrgʻa. Bu erda biz algoritmlarning yana bir muhim xususiyati - ularning samaradorlik... Muammoni hal qilishning turli usullari mavjud. Ammo dasturlashda va kundalik hayotda biz eng samarali usulni tanlaymiz. Agar sizning vazifangiz yog ʻsendvichini tayyorlash boʻlsa, siz, albatta, bugʻdoy ekish va sigir sogʻish bilan boshlashingiz mumkin. Ammo shunday boʻladi samarasiz qaror - bu juda uzoq vaqt talab etadi va koʻp pul sarflaydi. Oddiy muammoni hal qilish uchun siz shunchaki non va sariyog ʻsotib olishingiz mumkin. Bugʻdoy va sigir bilan algoritm, garchi bu muammoni hal qilishga imkon beradigan boʻlsa ham, amalda qoʻllash uchun juda murakkab. Dasturlashda algoritmlarning murakkabligini baholash uchun maxsus yozuv yaratildi Katta-O ("katta O"). Big-O algoritmning bajarilish vaqti unga uzatilgan maʻlumotlarga bogʻliqligini taxmin qilishga imkon beradi... Eng oddiy misolni koʻrib chiqamiz - maʻlumotlar uzatish. Tasavvur qiling, baʻzi maʻlumotlarni fayl shaklida uzoq masofaga (masalan, 5000 kilometr) uzatishingiz kerak. Qaysi algoritm eng samarali boʻladi? Bu u ishlashi kerak boʻlgan maʻlumotlarga bogʻliq. Masalan, bizda 10 megabaytli audio fayl mavjud. Bunday holda, faylni Internet orqali uzatish eng samarali algoritm boʻladi. Buning uchun bir necha daqiqa kerak boʻladi! Shunday qilib, yana bir bor algoritmimizga ovoz beraylik: “Agar siz maʻlumotni fayllar koʻrinishida 5000 kilometr masofaga uzatmoqchi boʻlsangiz, Internet orqali maʻlumotlar uzatishni ishlatishingiz kerak”. Yaxshi. Endi buni tahlil qilaylik. U bizning muammomizni hal qiladimi? Umuman olganda, ha. Ammo uning murakkabligi haqida nima deyish mumkin? Hmm, lekin bu erda hamma narsa qiziqroq. Haqiqat shundaki, bizning algoritmimiz kirish maʻlumotlariga, yaʻni fayllar hajmiga juda bogʻliq. Hozir bizda 10 megabayt bor va barchasi yaxshi. Agar 500 megabaytni oʻtkazishimiz kerak boʻlsa-chi? 20 gigabaytmi? 500 terabaytmi? 30 petabaytmi? Bizning algoritmimiz ishlamay qoladimi? Yoʻq, ushbu maʻlumotlarning barcha hajmlari hali ham uzatilishi mumkin. Yugurish uchun koʻproq vaqt kerak boʻladimi? Ha, shunday boʻladi! Endi biz algoritmimizning muhim xususiyatini bilamiz: uzatiladigan maʻlumotlarning hajmi qanchalik katta boʻlsa, algoritm shuncha koʻp vaqt talab etadi... Ammo biz ushbu munosabat qanday koʻrinishini aniqroq bilmoqchimiz (maʻlumotlar hajmi va uni uzatish uchun vaqt oʻrtasida). Bizning holatlarimizda algoritmning murakkabligi boʻladi chiziqli... "Lineer" maʻlumotlarning miqdori oshgani sayin, uzatish vaqti taxminan mutanosib ravishda koʻpayishini anglatadi. Agar maʻlumotlar 2 baravar koʻp boʻlsa va ularni uzatish uchun 2 barobar koʻproq vaqt kerak boʻlsa. Agar maʻlumotlar 10 baravar koʻp boʻlsa va uzatish vaqti 10 barobar koʻpaysa. Big-O notation yordamida algoritmimizning murakkabligi quyidagicha aniqlanadi O (N)... Ushbu yozuv kelajakda eng yaxshi esda qoladi - har doim chiziqli murakkablikka ega algoritmlar uchun ishlatiladi. Eʻtibor bering: biz bu erda turli xil "oʻzgaruvchan" narsalar haqida umuman gapirmayapmiz: Internet tezligi, kompyuterimiz kuchi va boshqalar. Algoritmning murakkabligini baholashda bu shunchaki mantiqqa toʻgʻri kelmaydi - har qanday holatda ham biz uni boshqara olmaymiz. Big-O algoritmni oʻzi ishlashi kerak boʻlgan "muhit" dan qatʻiy nazar oʻzi baholaydi. Keling, oʻz misolimiz bilan ishlashni davom ettiramiz. Aytaylik, oxirida fayllar hajmi 800 terabaytni tashkil etadi. Agar ularni Internet orqali uzatadigan boʻlsak, vazifa, albatta, hal qilinadi. Faqat bitta muammo bor: koʻpchiligimiz uyda foydalanadigan standart zamonaviy kanal (soniyasiga 100 megabit) orqali uzatish taxminan 708 kun davom etadi. Deyarli 2 yil! : O Shunday qilib, bizning algoritmimiz bu erda aniq mos emas. Boshqa echim kerak! Kutilmaganda, bizga IT giganti yordam beradi - Amazon! Uning Amazon Snowmobile xizmati sizga katta hajmdagi maʻlumotlarni mobil kassalarga yuklash va yuk mashinalari orqali manzilingizga etkazish imkonini beradi!
Shunday qilib bizda yangi algoritm mavjud! "Agar siz maʻlumotni fayllar koʻrinishida 5000 kilometr masofada uzatmoqchi boʻlsangiz va Internet orqali uzatishda bu jarayon 14 kundan koʻproq vaqtni talab qilsa, Amazon yuk mashinasi orqali maʻlumotlarni tashishdan foydalanishingiz kerak." Bu erda 14 kun raqami tasodifiy tanlangan: aytaylik, bu biz imkon beradigan maksimal muddat. Keling, algoritmimizni tahlil qilaylik. Tezlik haqida nima deyish mumkin? Yuk mashinasi atigi 50 km / soat tezlikda harakatlansa ham, 5000 kilometrni atigi 100 soat ichida bosib oʻtadi. Toʻrt kundan sal koʻproq vaqt! Bu internetni oqimlash imkoniyatidan ancha yaxshi. Ushbu algoritmning murakkabligi haqida nima deyish mumkin? U ham chiziqli boʻladimi, O (N)? Yoʻq, boʻlmaydi. Axir, yuk mashinasi qancha yuklaganingizning ahamiyati yoʻq - u baribir bir xil tezlikda yurib, oʻz vaqtida etib boradi. Bizda 800 terabayt boʻladimi yoki 10 baravar koʻp maʻlumot boʻladimi, yuk mashinasi 5 kun ichida belgilangan manzilga etib boradi. Boshqacha qilib aytganda, yuk mashinasi orqali maʻlumotlarni etkazib berish algoritmi doimiy murakkablik... "Doimiy" bu algoritmga uzatilgan maʻlumotlarga bogʻliq emasligini anglatadi. Yuk mashinasiga 1 Gb hajmli USB stikkani joylashtiring - u 5 kun ichida keladi. U erda 800 terabayt maʻlumotli disklarni joylashtiring - u 5 kun ichida keladi. Big-O dan foydalanilganda doimiy murakkablik quyidagicha belgilanadi O (1)... Biz uchrashganimizdan beri O (N) va O (1), endi koʻproq "dasturchi" misollarini koʻrib chiqamiz :) Aytaylik, sizga 100 ta raqamlar qatori berilgan va ularning har birini konsolga chiqarish vazifasi. Ushbu topshiriqni bajaradigan loop uchun odatiy yozasiz int numbers \u003d new int [100]; // .. qatorni raqamlar bilan toʻldiring uchun (int i: raqamlar) (System.out.println (i);) Yozilgan algoritmning murakkabligi nimada? Lineer, O (N). Dastur bajarishi kerak boʻlgan harakatlar soni unga qancha raqam berilganiga bogʻliq. Agar massivda 100 ta raqam boʻlsa, unda 100 ta amal boʻladi (ekranga chiqishlar) Agar massivda 10 000 ta raqam boʻlsa, 10 000 ta amalni bajarish kerak boʻladi. Bizning algoritmimiz yaxshilanishi mumkinmi? Yoʻq. Biz baribir majburiyat qilishimiz kerak N qatordan oʻtadi va konsolga N chiqishini bajaring. Keling, yana bir misolni koʻrib chiqaylik. public static void main (String args) (LinkedList < Integer> raqamlar \u003d yangi LinkedList< > (); raqamlar. qoʻshish (0, 20202); raqamlar. qoʻshish (0, 123); raqamlar. qoʻshish (0, 8283); ) Bizda boʻsh LinkedList mavjud, unga baʻzi raqamlarni kiritamiz. Biz oʻz misolimizda LinkedList-ga bitta raqamni kiritish algoritmining murakkabligini va uning roʻyxatdagi elementlar soniga bogʻliqligini baholashimiz kerak. Javob boʻladi O (1) - doimiy murakkablik... Nima uchun? Iltimos, har safar biz roʻyxatning boshiga raqam kiritganimizga eʻtibor bering. Bundan tashqari, siz eslayotganingizdek, LinkedList-ga raqam kiritishda elementlar hech qaerga siljimaydi - havolalar qayta belgilanadi (agar siz toʻsatdan LinkedList qanday ishlashini unutgan boʻlsangiz, biznikidan birini koʻrib chiqing). Agar hozir bizning roʻyxatimizdagi birinchi raqam x raqami boʻlsa va biz roʻyxatning boshiga y raqamini qoʻshsak, bizga faqat x kerak. oldingi \u003d y; y. oldingi \u003d null; y. keyingi \u003d x; Ushbu havolani bekor qiladi biz hozirda LinkedList-da qancha raqam borligiga ahamiyat bermaymiz - kamida bittasi, kamida milliard. Algoritmning murakkabligi doimiy boʻladi - O (1).
Do'stlaringiz bilan baham: |
