Ang pagiging kumplikado ng algorithm

Kamusta! Magiging iba ang lecture ngayon sa iba. Ito ay mag-iiba dahil ito ay hindi direktang nauugnay sa Java. Gayunpaman, ang paksang ito ay napakahalaga para sa bawat programmer. Pag-uusapan natin ang tungkol sa mga algorithm . Ano ang isang algorithm? Sa simpleng mga termino, ito ay isang tiyak na pagkakasunud-sunod ng mga aksyon na dapat gawin upang makamit ang ninanais na resulta . Madalas kaming gumagamit ng mga algorithm sa pang-araw-araw na buhay. Halimbawa, tuwing umaga ay nahaharap ka sa isang gawain: pumunta sa paaralan o trabaho, at sa parehong oras ay:

• Nakabihis
• Malinis
• Busog na busog

Anong algorithm ang magpapahintulot sa iyo na makamit ang resultang ito?

1. Gumising sa alarm clock.
2. Maligo ka, maghugas ng mukha.
3. Maghanda ng almusal, magtimpla ng kape/tsa.
4. Kumain.
5. Kung hindi mo pa naplantsa ang iyong mga damit mula noong gabi, plantsahin ang mga ito.
6. Magbihis.
7. Umalis sa bahay.

Ang pagkakasunud-sunod ng mga aksyon na ito ay tiyak na magbibigay-daan sa iyo upang makuha ang ninanais na resulta. Sa programming, ang buong punto ng aming trabaho ay ang patuloy na paglutas ng mga problema. Ang isang mahalagang bahagi ng mga gawaing ito ay maaaring isagawa gamit ang mga kilalang algorithm. Halimbawa, nahaharap ka sa isang gawain: pagbukud-bukurin ang isang listahan ng 100 mga pangalan sa isang array . Ang problemang ito ay medyo simple, ngunit maaari itong malutas sa iba't ibang paraan. Narito ang isang solusyon: Algorithm para sa pag-uuri ng mga pangalan ayon sa alpabeto:

1. Bumili o mag-download sa Internet na "Dictionary of Russian Personal Names" 1966 na edisyon.
2. Hanapin ang bawat pangalan sa aming listahan sa diksyunaryong ito.
3. Isulat sa isang piraso ng papel kung aling pahina ng diksyunaryo ang pangalan.
4. Ayusin ang mga pangalan gamit ang mga tala sa isang piraso ng papel.

Ang ganitong pagkakasunud-sunod ng mga aksyon ay magbibigay-daan sa amin upang malutas ang aming problema? Oo, ito ay ganap na pahihintulutan ito. Magiging epektibo ba ang solusyong ito ? Halos hindi. Narito tayo sa isa pang napakahalagang katangian ng mga algorithm - ang kanilang kahusayan . Ang problema ay maaaring malutas sa iba't ibang paraan. Ngunit pareho sa programming at sa pang-araw-araw na buhay, pipiliin namin ang paraan na magiging pinaka-epektibo. Kung ang iyong gawain ay gumawa ng sandwich na may mantikilya, maaari mong, siyempre, magsimula sa pamamagitan ng paghahasik ng trigo at paggatas ng baka. Ngunit ito ay magiging isang hindi epektibong solusyon - kakailanganin ito ng maraming oras at nagkakahalaga ng maraming pera. Upang malutas ang iyong simpleng problema, maaari kang bumili lamang ng tinapay at mantikilya. At ang algorithm na may trigo at baka, bagaman pinapayagan ka nitong malutas ang problema, ay masyadong kumplikado upang mailapat ito sa pagsasanay. Upang masuri ang pagiging kumplikado ng mga algorithm sa programming, nilikha ang isang espesyal na notasyon na tinatawag na Big-O (“big O”) . Binibigyang-daan ka ng Big-O na tantyahin kung gaano nakadepende ang oras ng pagpapatupad ng isang algorithm sa data na ipinasa dito . Tingnan natin ang pinakasimpleng halimbawa - paglilipat ng data. Isipin na kailangan mong magpadala ng ilang impormasyon sa anyo ng isang file sa isang mahabang distansya (halimbawa, 5000 kilometro). Aling algorithm ang magiging pinakamabisa? Depende ito sa data na kailangan niyang magtrabaho. Halimbawa, mayroon kaming audio file na 10 megabytes ang laki. Sa kasong ito, ang pinaka mahusay na algorithm ay ang paglipat ng file sa Internet. Tatagal lang ng ilang minuto! Kaya, ipahayag muli ang aming algorithm: "Kung kailangan mong maglipat ng impormasyon sa anyo ng mga file sa layong 5000 kilometro, kailangan mong gumamit ng pagpapadala ng data sa Internet." Malaki. Ngayon ay pag-aralan natin ito. Nalulutas ba nito ang ating problema? Sa pangkalahatan, oo, ito ay ganap na malulutas ito. Ngunit ano ang masasabi mo tungkol sa pagiging kumplikado nito? Hmm, ngayon dito nagiging kawili-wili ang mga bagay. Ang katotohanan ay ang aming algorithm ay lubos na nakasalalay sa papasok na data, lalo na ang laki ng mga file. Ngayon ay mayroon na tayong 10 megabytes at maayos ang lahat. Paano kung kailangan nating maglipat ng 500 megabytes? 20 gigabytes? 500 terabytes? 30 petabytes? Hihinto ba sa paggana ang aming algorithm? Hindi, lahat ng mga halagang ito ng data ay maaari pa ring ilipat. Magtatagal ba ito upang makumpleto? Oo, mangyayari ito! Ngayon ay alam na namin ang isang mahalagang feature ng aming algorithm: mas malaki ang laki ng data na ililipat, mas matagal ang algorithm upang makumpleto . Ngunit gusto naming maunawaan nang mas tumpak kung ano ang hitsura ng relasyon na ito (sa pagitan ng laki ng data at ang oras na kinakailangan upang ilipat ito). Sa aming kaso, ang pagiging kumplikado ng algorithm ay magiging linear. Ang ibig sabihin ng "Linear" ay habang tumataas ang dami ng data, tataas nang humigit-kumulang proporsyonal ang oras para sa paghahatid nito. Kung mayroong 2 beses na mas maraming data, at aabutin ng 2 beses na mas maraming oras upang mailipat ito. Kung mayroong 10 beses na higit pang data, ang oras ng paglipat ay tataas ng 10 beses. Gamit ang Big-O notation, ang pagiging kumplikado ng aming algorithm ay tinukoy bilang O(N) . Ang notasyong ito ay pinakamahusay na natatandaan para sa sanggunian sa hinaharap; ito ay palaging ginagamit para sa mga algorithm na may linear na kumplikado. Pakitandaan: hindi namin pinag-uusapan dito ang tungkol sa iba't ibang "variable" na bagay: bilis ng Internet, kapangyarihan ng aming computer, at iba pa. Kapag tinatasa ang pagiging kumplikado ng isang algorithm, ito ay walang katuturan - wala kaming kontrol dito. Sinusuri ng Big-O ang algorithm mismo, anuman ang "kapaligiran" kung saan ito gagana. Ipagpatuloy natin ang ating halimbawa. Sabihin nating sa kalaunan ay lumalabas na ang laki ng mga file na ililipat ay 800 terabytes. Kung ipapadala natin ang mga ito sa Internet, ang problema, siyempre, ay malulutas. May isang problema lang: ang paghahatid sa isang karaniwang modernong link (sa 100 megabits bawat segundo) na ginagamit ng karamihan sa atin sa ating mga tahanan ay tatagal ng humigit-kumulang 708 araw. Halos 2 taon! :O Kaya, ang aming algorithm ay malinaw na hindi angkop dito. Kailangan natin ng ibang solusyon! Biglang tumulong sa amin ang higanteng IT na Amazon! Nagbibigay-daan sa iyo ang serbisyong Amazon Snowmobile nito na mag-load ng malaking halaga ng data sa mga mobile storage unit at ihatid ang mga ito sa nais na address sa pamamagitan ng trak! Kaya mayroon kaming bagong algorithm! "Kung kailangan mong maglipat ng impormasyon sa anyo ng mga file sa layong 5,000 kilometro, at ang proseso ay tatagal ng higit sa 14 na araw kapag inilipat sa Internet, kailangan mong gumamit ng Amazon truck transport." Ang bilang ng 14 na araw ay pinili dito nang random: sabihin nating ito ang maximum na panahon na maaari nating bayaran. Suriin natin ang aming algorithm. Paano ang tungkol sa bilis? Kahit 50 km/h lang ang byahe ng truck, 5,000 kilometers na ang sasakyan nito sa loob lang ng 100 oras. Mahigit apat na araw lang yan! Ito ay mas mahusay kaysa sa opsyon sa paghahatid ng Internet. Paano naman ang pagiging kumplikado ng algorithm na ito? Magiging linear din ba ito, O(N)? Hindi maaari. Pagkatapos ng lahat, ang trak ay walang pakialam kung gaano mo ito ikarga - ito ay magda-drive pa rin sa humigit-kumulang sa parehong bilis at darating sa oras. Mayroon man tayong 800 terabytes, o 10 beses na mas maraming data, makakarating pa rin ang trak doon sa loob ng 5 araw. Sa madaling salita, ang algorithm para sa paghahatid ng data sa pamamagitan ng trak ay palaging kumplikado . Ang ibig sabihin ng "Constant" ay hindi ito nakadepende sa data na ipinasa sa algorithm. Maglagay ng 1GB flash drive sa trak at darating ito sa loob ng 5 araw. Maglagay ng mga disk na may 800 terabytes ng data doon at darating ito sa loob ng 5 araw. Kapag gumagamit ng Big-O, ang patuloy na pagiging kumplikado ay tinutukoy bilang O(1) . Simula ng makilala natin si O(N) atO(1) , tingnan natin ngayon ang higit pang mga halimbawa ng “programmer” :) Sabihin nating bibigyan ka ng hanay ng 100 numero, at ang gawain ay i-print ang bawat isa sa kanila sa console. Sumulat ka ng isang regular na loop forna nagsasagawa ng gawaing ito

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

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

Ano ang pagiging kumplikado ng nakasulat na algorithm? Linear, O(N). Ang bilang ng mga aksyon na dapat gawin ng programa ay depende sa eksaktong bilang ng mga numero ang naipasa dito. Kung mayroong 100 numero sa array, magkakaroon ng 100 aksyon (mga output sa screen). Kung mayroong 10,000 na numero sa array, 10,000 aksyon ang kailangang isagawa. Maaari bang mapabuti ang aming algorithm? Hindi. Sa anumang kaso, kailangan nating gumawa ng N pass sa array at magsagawa ng N output sa console. Tingnan natin ang isa pang halimbawa.

public static void main(String[] args) {

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

Mayroon kaming isang walang laman LinkedListkung saan nagpasok kami ng ilang mga numero. Kailangan nating tantyahin ang pagiging kumplikado ng algorithm para sa pagpasok ng isang numero sa LinkedListating halimbawa, at kung paano ito nakadepende sa bilang ng mga elemento sa listahan. Ang sagot ay O(1) - constant complexity . Bakit? Pakitandaan: sa tuwing maglalagay kami ng numero sa simula ng listahan. Bilang karagdagan, tulad ng naaalala mo, kapag naglalagay ng mga numero sa LinkedListmga elemento, hindi sila inililipat kahit saan - ang mga link ay muling tinukoy (kung bigla mong nakalimutan kung paano gumagana ang LinkList, tingnan ang isa sa aming mga lumang lecture ). Kung ngayon ang unang numero sa aming listahan ay ang numero х, at ipinasok namin ang numerong y sa simula ng listahan, ang kailangan lang ay:

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

Para sa redefinition ng reference na ito, hindi mahalaga sa amin kung gaano karaming mga numero ang mayroon ngayonLinkedList - kahit isa, kahit isang bilyon. Ang pagiging kumplikado ng algorithm ay magiging pare-pareho - O(1).

Ang pagiging kumplikado ng logarithmic

Huwag mag-panic! :) Kung gusto mong isara ng salitang "logarithmic" ang lecture at huwag nang magbasa pa, maghintay ng ilang minuto. Hindi magkakaroon ng mga paghihirap sa matematika dito (maraming ganoong mga paliwanag sa ibang mga lugar), at susuriin namin ang lahat ng mga halimbawa "sa mga daliri". Isipin na ang iyong gawain ay maghanap ng isang partikular na numero sa hanay ng 100 numero. Mas tiyak, suriin kung naroroon ba ito. Sa sandaling mahanap ang kinakailangang numero, dapat ihinto ang paghahanap, at ang entry na "Nahanap na ang kinakailangang numero!" ay dapat na ipakita sa console. Ang index nito sa array = ....” Paano mo malulutas ang ganoong problema? Narito ang solusyon ay halata: kailangan mong umulit sa pamamagitan ng mga elemento ng array nang paisa-isa, simula sa una (o huli) at suriin kung ang kasalukuyang numero ay tumutugma sa nais na isa. Alinsunod dito, ang bilang ng mga aksyon ay direktang nakasalalay sa bilang ng mga elemento sa array. Kung mayroon tayong 100 numero, kailangan nating pumunta sa susunod na elemento ng 100 beses at suriin ang numero para sa isang tugma ng 100 beses. Kung mayroong 1000 na numero, magkakaroon ng 1000 na hakbang sa pagsusuri. Ito ay malinaw na linear complexity, O(N) . Ngayon ay magdaragdag kami ng isang paglilinaw sa aming halimbawa: ang array kung saan kailangan mong maghanap ng numero ay pinagsunod-sunod sa pataas na pagkakasunud-sunod . May pagbabago ba ito para sa ating gawain? Maaari pa rin nating hanapin ang nais na numero sa pamamagitan ng brute force. Ngunit maaari naming gamitin ang kilalang binary search algorithm sa halip . Sa tuktok na hilera ng larawan ay nakikita namin ang isang pinagsunod-sunod na hanay. Sa loob nito kailangan nating hanapin ang numerong 23. Sa halip na umulit sa mga numero, hinahati lang natin ang array sa 2 bahagi at suriin ang average na numero sa array. Hinahanap namin ang numero na matatagpuan sa cell 4 at suriin ito (pangalawang hilera sa larawan). Ang numerong ito ay 16, at hinahanap namin ang 23. Ang kasalukuyang numero ay mas mababa. Ano ang ibig sabihin nito? Na ang lahat ng mga nakaraang numero (na matatagpuan hanggang sa numero 16) ay hindi kailangang suriin : tiyak na mas mababa ang mga ito kaysa sa hinahanap namin, dahil ang aming array ay pinagsunod-sunod! Ipagpatuloy natin ang paghahanap sa natitirang 5 elemento. Bigyang-pansin:Isang pagsusuri lang ang ginawa namin, ngunit naalis na namin ang kalahati ng mga posibleng opsyon. Mayroon na lang tayong 5 elemento na natitira. Uulitin namin ang aming hakbang - muling hatiin ang natitirang array sa pamamagitan ng 2 at muling kunin ang gitnang elemento (linya 3 sa figure). Ang numerong ito ay 56, at mas malaki ito kaysa sa hinahanap namin. Ano ang ibig sabihin nito? Na itapon namin ang 3 higit pang mga pagpipilian - ang numero 56 mismo, at dalawang numero pagkatapos nito (tiyak na mas malaki sila sa 23, dahil ang array ay pinagsunod-sunod). Mayroon na lang kaming 2 numero na natitira upang suriin (ang huling hilera sa figure) - mga numero na may mga indeks ng array 5 at 6. Sinusuri namin ang una sa mga ito, at ito ang aming hinahanap - ang numerong 23! Ang index nito = 5! Tingnan natin ang mga resulta ng ating algorithm, at pagkatapos ay mauunawaan natin ang pagiging kumplikado nito. (Sa pamamagitan ng paraan, ngayon naiintindihan mo kung bakit ito ay tinatawag na binary: ang kakanyahan nito ay ang patuloy na hatiin ang data sa 2). Ang resulta ay kahanga-hanga! Kung naghahanap kami ng nais na numero gamit ang linear na paghahanap, kakailanganin namin ng 10 tseke, ngunit sa binary na paghahanap ginawa namin ito sa 3! Sa pinakamasamang kaso, magkakaroon ng 4 sa kanila, kung sa huling hakbang ang numero na kailangan namin ay naging pangalawa, at hindi ang una. Paano naman ang pagiging kumplikado nito? Ito ay isang napaka-kagiliw-giliw na punto :) Ang binary search algorithm ay higit na nakadepende sa bilang ng mga elemento sa array kaysa sa linear search algorithm (iyon ay, simpleng enumeration). Sa 10 elemento sa array, ang linear na paghahanap ay mangangailangan ng maximum na 10 na pagsusuri, at ang binary na paghahanap ay mangangailangan ng maximum na 4 na pagsusuri. Ang pagkakaiba ay 2.5 beses. Ngunit para sa hanay ng 1000 elemento, ang linear na paghahanap ay mangangailangan ng 1000 na pagsusuri, at ang binary na paghahanap ay mangangailangan lamang ng 10 ! Ang pagkakaiba ay 100 beses na! Bigyang-pansin:ang bilang ng mga elemento sa array ay tumaas ng 100 beses (mula 10 hanggang 1000), at ang bilang ng mga kinakailangang pagsusuri para sa binary na paghahanap ay tumaas lamang ng 2.5 beses - mula 4 hanggang 10. Kung umabot tayo ng 10,000 elemento , ang pagkakaiba ay mas kahanga-hanga: 10,000 mga pagsusuri para sa linear na paghahanap, at isang kabuuang 14 na pagsusuri para sa binary. At muli: ang bilang ng mga elemento ay tumaas ng 1000 beses (mula 10 hanggang 10000), ngunit ang bilang ng mga tseke ay tumaas lamang ng 3.5 beses (mula 4 hanggang 14). Ang pagiging kumplikado ng binary search algorithm ay logarithmic , o, sa Big-O notation, O(log n) . Bakit ito tinawag? Ang logarithm ay ang kabaligtaran ng exponentiation. Ang binary logarithm ay ginagamit upang kalkulahin ang kapangyarihan ng 2. Halimbawa, mayroon tayong 10,000 elemento na kailangan nating pagdaanan gamit ang binary search. Ngayon ay mayroon kang isang larawan sa harap ng iyong mga mata, at alam mo na nangangailangan ito ng maximum na 14 na pagsusuri. Ngunit paano kung walang larawan sa harap ng iyong mga mata, at kailangan mong bilangin ang eksaktong bilang ng mga kinakailangang pagsusuri? Ito ay sapat na upang sagutin ang isang simpleng tanong: sa anong kapangyarihan dapat itaas ang numero 2 upang ang resulta na nakuha ay >= ang bilang ng mga elemento na sinusuri? Para sa 10000 ito ang magiging ika-14 na kapangyarihan. 2 sa ika-13 kapangyarihan ay masyadong maliit (8192) Ngunit 2 sa ika-14 na kapangyarihan = 16384 , ang numerong ito ay nakakatugon sa aming kondisyon (ito ay >= ang bilang ng mga elemento sa array). Natagpuan namin ang logarithm - 14. Gaano karaming mga tseke ang kailangan namin! :) Ang mga algorithm at ang kanilang pagiging kumplikado ay isang paksang napakalawak upang maisama sa isang panayam. Ngunit ang pag-alam na ito ay napakahalaga: sa maraming mga panayam makakatanggap ka ng mga problema sa algorithm. Para sa teorya, maaari kong irekomenda sa iyo ang ilang mga libro. Ang isang magandang lugar upang magsimula ay " Grocking Algorithms ": kahit na ang mga halimbawa sa aklat ay nakasulat sa Python, ang wika at mga halimbawa ng aklat ay napakasimple. Ang pinakamahusay na pagpipilian para sa isang baguhan, at ito ay maliit din sa dami. Mas seryosong pagbabasa: mga aklat ni Robert Laforet at Robert Sedgwick . Parehong nakasulat sa Java, na gagawing mas madali ang pag-aaral para sa iyo. Pagkatapos ng lahat, pamilyar ka sa wikang ito! :) Para sa mga mag-aaral na may magandang background sa matematika, ang pinakamagandang opsyon ay ang aklat ni Thomas Corman . Ngunit hindi ka makuntento sa teorya lamang! “Alamin” != “makakaya” Maaari kang magsanay sa paglutas ng mga problema sa algorithm sa HackerRank at Leetcode . Ang mga problema mula doon ay madalas na ginagamit kahit na sa mga panayam sa Google at Facebook, kaya tiyak na hindi ka magsasawa :) Upang mapalakas ang materyal ng panayam, ipinapayo ko sa iyo na manood ng isang mahusay na video tungkol sa Big-O sa YouTube. Magkita-kita tayo sa susunod na mga lecture! :)