Algoritm çylşyrymlylygy

Salam! Şu günki leksiýa beýlekilerden birneme tapawutlanar. Diňe Java bilen gytaklaýyn baglanyşyklydygy bilen tapawutlanar. Şeýle-de bolsa, bu mowzuk her bir programmist üçin gaty möhümdir. Algoritmler hakda gürleşeris . Algoritm näme? Simpleönekeý sözler bilen aýdylanda, bu islenýän netijäni gazanmak üçin edilmeli hereketleriň belli bir yzygiderliligi . Gündelik durmuşda algoritmleri köplenç ulanýarys. Mysal üçin, her gün irden bir mesele bilen ýüzbe-ýüz bolýarsyňyz: mekdebe ýa-da işe gelmek we şol bir wagtyň özünde:

• Geýinen
• Arassa
• Gowy iýmitlenýär

Bu netijäni gazanmaga haýsy algoritm mümkinçilik berer?

1. Jaň sagadyna oýan.
2. Suwa düşüň, ýüzüňizi ýuwuň.
3. Ertirlik taýýarlaň, kofe / çaý taýýarlaň.
4. Iýiň.
5. Agşamdan bäri eşikleriňizi demirlemedik bolsaňyz, demirläň.
6. Geýinmek.
7. Öýden çykyň

Hereketleriň yzygiderliligi hökman islenýän netijäni almaga mümkinçilik berer. Programmirlemekde işimiziň ähli nokady hemişe problemalary çözmekdir. Bu meseleleriň ep-esli bölegi eýýäm belli algoritmleri ulanyp ýerine ýetirilip bilner. Mysal üçin, bir mesele bilen ýüzbe-ýüz bolarsyňyz: bir massiwde 100 atyň sanawyny tertipläň . Bu mesele gaty ýönekeý, ýöne ony dürli ýollar bilen çözüp bolýar. Ine, bir çözgüt: Atlary elipbiý boýunça tertiplemek algoritmi:

1. Internetde “Rus şahsy atlaryň sözlügi” 1966-njy ýyldaky neşirini satyn alyň ýa-da göçürip alyň.
2. Sanawymyzdaky her bir aty şu sözlükden tapyň.
3. Adyň sözlügiň haýsy sahypasynda bardygyny kagyz ýüzüne ýazyň.
4. Bellikleri kagyz ýüzüne ulanyp, atlary tertipläň.

Şeýle hereketleriň yzygiderliligi meselämizi çözmäge mümkinçilik berermi? Hawa, muňa doly rugsat berer. Bu çözgüt täsirli bolarmy ? Gaty kyn. Bu ýerde algoritmleriň başga bir möhüm häsiýetine - olaryň netijeliligine gelýäris . Meseläni dürli ýollar bilen çözüp bolýar. Emma programmirlemekde-de, gündelik durmuşda-da iň täsirli usuly saýlaýarys. Siziň işiňiz ýag bilen sendwiç ýasamak bolsa, elbetde bugdaý ekip, sygyr süýt bermekden başlap bilersiňiz. Emma bu netijesiz çözgüt bolar - köp wagt we köp pul gerek bolar. Simpleönekeý meseläňizi çözmek üçin diňe çörek we ýag satyn alyp bilersiňiz. Bugdaý we sygyr bilen algoritm, meseläni çözmäge mümkinçilik berse-de, ony iş ýüzünde ulanmak gaty çylşyrymly. Programmirlemekde algoritmleriň çylşyrymlylygyna baha bermek üçin Big-O (“uly O”) atly ýörite bellik döredildi . Big-O, algoritmiň ýerine ýetiriliş wagtynyň oňa berlen maglumatlara nä derejede baglydygyny çaklamaga mümkinçilik berýär . Iň ýönekeý mysal - maglumatlary geçirmek meselesine seredeliň. Käbir maglumatlary faýl görnüşinde uzak aralyga (mysal üçin 5000 kilometre) geçirmelidigini göz öňüne getiriň. Haýsy algoritm iň täsirli bolar? Bu onuň bilen işlemeli maglumatlara baglydyr. Mysal üçin, 10 megabaýtlyk ses faýly bar. Bu ýagdaýda iň täsirli algoritm faýly internete geçirmek bolar. Diňe birnäçe minut gerek bolar! Şeýlelik bilen, algoritmimize ýene bir gezek ses bereliň: “5000 kilometr aralykda faýl görnüşinde maglumat geçirmek zerur bolsa, internet arkaly maglumat geçirişini ulanmaly bolarsyňyz.” Gowy. Indi analiz edeliň. Bu biziň meselämizi çözýärmi? Umuman, hawa, ony doly çözýär. Itsöne onuň çylşyrymlylygy barada näme aýdyp bilersiňiz? Hmm, indi zatlar gyzykly bolýar. Hakykat, algoritmimiziň gelýän maglumatlara, ýagny faýllaryň ululygyna baglydyr. Indi 10 megabaýt bar we hemme zat gowy. 500 megabaýt geçirmeli bolsa näme etmeli? 20 gigabaýt? 500 terabaýt? 30 petabaýt? Algoritmimiz işlemezmi? , Ok, bu mukdarda maglumatlaryň hemmesi geçirilip bilner. Tamamlamak üçin has köp wagt gerek bolarmy? Hawa, bolar! Indi algoritmimiziň möhüm aýratynlygyny bilýäris: geçirilmeli maglumatlaryň göwrümi näçe uly bolsa, algoritmiň tamamlanmagy üçin şonça köp wagt gerek bolar . Thisöne bu gatnaşyklaryň görnüşine has takyk düşünmek isleýäris (maglumatlaryň ululygy bilen ony geçirmek üçin wagtyň arasynda). Biziň ýagdaýymyzda algoritmiň çylşyrymlylygy çyzykly bolar. “Çyzykly”, maglumatlaryň göwrüminiň artmagy bilen, geçiriş wagtynyň takmynan proporsional artjakdygyny aňladýar. 2 esse köp maglumat bar bolsa we ony geçirmek üçin 2 esse köp wagt gerek bolar. 10 esse köp maglumat bar bolsa, geçiriş wagty 10 esse artar. Big-O belligini ulanyp, algoritmimiziň çylşyrymlylygy O (N) hökmünde kesgitlenýär . Bu bellik geljekki salgylanma üçin iň gowy ýatda saklanýar, hemişe çyzykly çylşyrymly algoritmler üçin ulanylýar. Üns beriň: bu ýerde dürli “üýtgeýän” zatlar hakda asla gürleşemzok: internet tizligi, kompýuterimiziň güýji we ş.m. Algoritmiň çylşyrymlylygyna baha berlende, munuň manysy ýok - her niçigem bolsa oňa gözegçilik edip bilmeris. Big-O, işlemeli “gurşawyna” garamazdan algoritmiň özüne baha berýär. Mysalymyzy dowam etdireliň. Iň soňunda geçiriljek faýllaryň göwrüminiň 800 terabaýtdygyny aýdalyň. Olary internet arkaly ýaýratsak, mesele elbetde çözüler. Diňe bir mesele bar: köpümiziň öýlerimizde ulanýan adaty döwrebap baglanyşykdan (sekuntda 100 megabit) geçmek takmynan 708 gün dowam eder. 2 ýyl töweregi! : O Diýmek, algoritmimiz bu ýerde laýyk däl. Başga bir çözgüt gerek! Birden IT ägirdi Amazon kömege gelýär! “Amazon Snowmobile” hyzmaty size köp mukdarda maglumatlary ykjam ammar bölümlerine ýüklemäge we ýük awtoulaglary bilen gerekli adrese ýetirmäge mümkinçilik berýär! Şeýlelik bilen bizde täze algoritm bar! "5000 kilometr aralykda faýl görnüşinde maglumat geçirmek zerur bolsa we internet arkaly geçirilende 14 günden gowrak wagt gerek bolsa, Amazon awtoulag ulaglaryny ulanmaly bolarsyňyz." 14 günüň şekili bu ýerde tötänleýin saýlandy: geliň, bu iň ýokary döwür. Algoritmimizi seljereliň. Tizlik hakda näme? Truckük awtoulagy sagatda bary-ýogy 50 km tizlik bilen geçse-de, bary-ýogy 100 sagadyň dowamynda 5000 kilometri geçer. Bu dört günden gowrak! Bu, internet geçiriş opsiýasyndan has gowy. Bu algoritmiň çylşyrymlylygy barada näme aýdyp bilersiňiz? O (N) çyzykly bolarmy? .Ok, bolmaz. Galyberse-de, ýük awtoulagynyň näçeräk ýükländigiňiziň aladasy ýok - henizem şol bir tizlikde sürer we wagtynda geler. 800 terabaýt barmy ýa-da 10 esse köp maglumat bolsun, ýük awtoulagy 5 günüň içinde henizem barar. Başgaça aýdylanda, ýük awtoulagynyň üsti bilen maglumat bermek algoritmi hemişe çylşyrymly . “Dowamly”, algoritmlere berlen maglumatlara bagly däldigini aňladýar. Truckük awtoulagyna 1GB fleş disk goýuň we 5 günden geler. 800 terabaýt maglumatly diskleri şol ýere goýuň we 5 günüň içinde geler. Big-O ulanylanda hemişelik çylşyrymlylyk O (1) diýilýär . O (N ) weO (1) , indi has “programmist” mysallara seredeliň :) Geliň, size 100 belgili massiw berildi diýeliň we wezipe olaryň hersini konsola çap etmekdir. forBu meseläni ýerine ýetirýän yzygiderli aýlaw ýazýarsyňyz

int[] numbers = new int[100];
// ..заполняем массив числами

for (int i: numbers) {
   System.out.println(i);
}

Writtenazuw algoritminiň çylşyrymlylygy näme? Çyzykly, O (N). Programmanyň ýerine ýetirmeli hereketleriniň sany, näçeräk mukdarda geçendigine baglydyr. Eger massiwde 100 san bar bolsa, 100 hereket bolar (ekranda çykyşlar). Eger massiwde 10,000 san bar bolsa, 10 000 hereket edilmeli. Algoritmimizi gowulandyryp bolarmy? No.ok. Her niçigem bolsa, N massiwden geçmeli we N netijelerini konsola ýerine ýetirmeli bolarys . Başga bir meselä seredeliň.

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

LinkedListBizde birnäçe san goýýan boş bir zat bar . Mysal üçin ýekeje san girizmek üçin algoritmiň çylşyrymlylygyny LinkedListwe sanawdaky elementleriň sanyna näderejede baglydygyny bahalandyrmalydyrys. Jogap O (1) - hemişelik çylşyrymlylyk . Näme üçin? Üns beriň: her gezek sanawyň başyna san goýanymyzda. Mundan başga-da, ýadyňyzda bolsa, sanlary elementlere salanyňyzda , olar hiç ýere geçirilmeýär - baglanyşyklar täzeden kesgitlenýär (eger LinkedList-iň işleýşini birden ýatdan çykaran bolsaňyz, köne leksiýalarymyzyňLinkedList birine göz aýlaň ). Indi sanawymyzdaky birinji san san bolsa we sanawyň başyna y belgisini goýsak, zerur zat: х

x.previous  = y;
y.previous = null;
y.next = x;

Bu salgylanmany kesgitlemek üçin, häzirki wagtda näçe sanynyň bolmagy möhüm dälLinkedList - iň bolmanda bir, azyndan bir milliard. Algoritmiň çylşyrymlylygy hemişelik bolar - O (1).

Logarifmiki çylşyrymlylyk

Aljyrama! :) "Logarifmiki" sözi leksiýany ýapmak we mundan beýläk okamazlyk isleýän bolsa, birnäçe minut garaşyň. Bu ýerde matematiki kynçylyklar bolmaz (beýleki ýerlerde şeýle düşündirişler kän) we ähli mysallary “barmaklarda” seljereris. Siziň wezipäňiz 100 san massiwinde belli bir san tapmakdygyny göz öňüne getiriň. Has takygy, onuň bardygyny ýa-da ýokdugyny barlaň. Talap edilýän nomer tapylan badyna gözleg bes edilmeli we konsolda “Gerekli belgisi tapyldy!” Entryazgysy görkezilmelidir. Onuň massiwindäki görkezijisi = .... ”Şeýle meseläni nädip çözüp bilersiňiz? Bu ýerde çözgüt düşnüklidir: birinji (ýa-da soňky) -dan başlap, massiw elementleriniň üsti bilen birin-birin gaýtalamaly we häzirki sanyň islenýän san bilen gabat gelýändigini barlamaly. Şoňa laýyklykda hereketleriň sany, massiwdäki elementleriň sanyna gönüden-göni baglydyr. 100 sany belgimiz bar bolsa, indiki elemente 100 gezek baryp, oýny 100 gezek barlamaly. 1000 san bar bolsa, 1000 barlag ädimi bolar. Bu çyzykly çylşyrymlylyk, O (N) . Indi mysalymyza bir düşündiriş goşarys: san tapmaly massiw ýokarlanýan tertipde tertiplenýär . Bu biziň wezipämiz üçin bir zady üýtgedýärmi? Gerekli belgini zalym güýç bilen gözläp bileris. Insteadöne munuň ýerine belli ikilik gözleg algoritmini ulanyp bileris . Suratyň ýokarky hatarynda tertipli bir massiw görýäris. Onda 23-nji belgini tapmalydyrys. Sanlaryň üstünde gaýtalamagyň ýerine, massiwi 2 bölege bölýäris we massiwdäki ortaça sanlary barlaýarys. 4-nji öýjükde ýerleşýän belgini tapýarys we barlaýarys (suratdaky ikinji hatar). Bu san 16, biz 23 gözleýäris. Häzirki san az. Bu näme many berýär? Öňki sanlaryň hemmesiniň (16-njy belgä çenli) barlanmagynyň zerurlygy ýok : hökman gözleýänimizden az bolar, sebäbi massiwimiz tertiplenen! Galan 5 elementiň arasynda gözlegi dowam etdireliň. Üns beriň:Diňe bir barlag etdik, ýöne mümkin bolan wariantlaryň ýarysyny ýok etdik. Bizde diňe 5 element galdy. Stepdimimizi gaýtalarys - galan massiwleri ýene 2-ä bölýäris we orta elementi alarys (suratda 3-nji setir). Bu san 56, gözleýänimizden has uludyr. Bu näme many berýär? Moreene-de 3 warianty - 56 belginiň özi we ondan soň iki san (bu 23-den uly bolmaly, sebäbi massiw tertiplenendir). Barlamak üçin bary-ýogy 2 san galdy (suratda iň soňky hatar) - 5 we 6 massiw görkezijileri bolan sanlar, olaryň birinjisini barlaýarys we gözleýän zadymyz - 23 belgisi! Onuň görkezijisi = 5! Algoritmimiziň netijelerine seredeliň, soň bolsa onuň çylşyrymlylygyna düşüneris. (Theeri gelende aýtsak, näme üçin ikilik diýilýändigine indi düşünýärsiňiz: onuň manysy maglumatlary yzygiderli 2-ä bölmekdir). Netije täsirli! Çyzykly gözleg arkaly islenýän belgini gözleýän bolsak, 10 barlag gerek bolar, ýöne ikilik gözleg bilen 3-de etdik! Iň erbet ýagdaýda, iň soňky ädimde zerur san birinji däl-de, ikinji bolup çyksa, olardan 4-si bolardy. Onuň çylşyrymlylygy barada näme aýdyp bilersiňiz? Bu gaty gyzykly bir nokat :) Ikitaraplaýyn gözleg algoritmi, çyzykly gözleg algoritmine (ýagny ýönekeý sanama) garanyňda massiwdäki elementleriň sanyna has az baglydyr. Toplumda 10 element bilen çyzykly gözleg üçin iň köp 10 barlag, ikilik gözleginde bolsa iň köp 4 barlag gerek bolar. Tapawut 2,5 esse. 1000öne 1000 elementden ybarat bolan çyzykly gözleg üçin 1000 barlag, ikilik gözlegine bolsa diňe 10 gerek bolar ! Tapawut eýýäm 100 gezek! Üns beriň:massiwdäki elementleriň sany 100 esse artdy (10-dan 1000-e çenli), ikilik gözlegi üçin zerur barlaglaryň sany bary-ýogy 2,5 esse köpeldi - 4-den 10-a çenli. 10,000 elemente ýetsek, tapawut hasam täsirli : 10,000 çyzykly gözleg üçin barlaglar we ikilik üçin jemi 14 barlag . Againene-de: elementleriň sany 1000 esse köpeldi (10-dan 10000-e çenli), ýöne barlaglaryň sany bary-ýogy 3,5 esse artdy (4-den 14-e çenli). Ikilik gözleg algoritminiň çylşyrymlylygy logarifmiki ýa-da Big-O belliginde O (log n) . Näme üçin beýle diýilýär? Logarifm eksponentasiýanyň tersidir. Ikilik logarifm 2-iň güýjüni hasaplamak üçin ulanylýar. Mysal üçin, ikilik gözlegini ulanyp geçmeli 10,000 elementimiz bar. Indi gözüňiziň öňünde surat bar we munuň iň köp 14 barlagyň zerurdygyny bilýärsiňiz. Eyesöne gözüňiziň öňünde surat ýok bolsa we zerur barlaglaryň takyk sanyny sanamaly bolsa näme etmeli? Simpleönekeý soraga jogap bermek ýeterlikdir: alnan netije> = barlanylýan elementleriň sany bolar ýaly 2-nji belgini haýsy güýç bilen ýokarlandyrmaly? 10000 üçin 14-nji güýç bolar. 2-den 13-nji güýje gaty az (8192) 2öne 14-den 14-e çenli güýç = 16384 , bu san biziň şertimizi kanagatlandyrýar (bu> = massiwdäki elementleriň sany). Logarifmi tapdyk - 14. Ine, näçe barlag gerek! :) Algoritmler we olaryň çylşyrymlylygy, bir leksiýa girip bolmajak gaty giň mowzuk. Itöne munuň gaty möhümdigini bilmek: köp söhbetdeşliklerde algoritmiki problemalary alarsyňyz. Nazaryýet üçin size birnäçe kitap maslahat berip bilerin. Başlamak üçin gowy ýer “ Grocking algoritmleri ”: kitapdaky mysallar Pythonda ýazylan hem bolsa, kitabyň dili we mysallary gaty ýönekeý. Bir öwrenje üçin iň oňat warianty, göwrümi hem az. Has çynlakaý okamak: Robert Laforet we Robert Sedgwikiň kitaplary . Ikisi hem Java-da ýazylan, bu size öwrenmegi birneme aňsatlaşdyrar. Galyberse-de, siz bu dil bilen gaty tanyş! :) Matematiki taýdan gowy bilim alan talyplar üçin iň oňat warianty Tomas Kormanyň kitaby bolar . Justöne diňe teoriýa bilen kanagatlanmarsyňyz! “Bil”! = “Başar” HackerRank we Leetcode -da algoritm meselelerini çözüp bilersiňiz . Ol ýerdäki meseleler köplenç Google we Facebook-da geçirilen söhbetdeşliklerde-de ulanylýar, şonuň üçin hökman ýadamazsyňyz :) Leksiýa materiallaryny güýçlendirmek üçin, YouTube-da Big-O hakda ajaýyp wideo görmegiňizi maslahat berýärin . Indiki leksiýalarda görüşeris! :)