Algorithmic complexity

Hi! Ang aralin ngayon ay bahagyang naiiba sa iba. Ito ay mag-iiba dahil ito ay hindi direktang nauugnay sa Java. Iyon ay sinabi, 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 ilang pagkakasunod-sunod ng mga aksyon na dapat kumpletuhin upang makamit ang ninanais na resulta . Madalas kaming gumagamit ng mga algorithm sa pang-araw-araw na buhay. Halimbawa, tuwing umaga mayroon kang isang partikular na gawain: pumunta sa paaralan o trabaho, at kasabay nito ay:

• Nakadamit
• Malinis
• Pinakain

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

1. Gumising gamit ang alarm clock.
2. Maligo ka at maghilamos.
3. Gumawa ng almusal at ilang kape o tsaa.
4. Kumain.
5. Kung hindi mo naplantsa ang iyong mga damit noong nakaraang gabi, pagkatapos ay plantsahin ang mga ito.
6. Magbihis.
7. Umalis sa bahay.

Ang pagkakasunud-sunod ng mga aksyon na ito ay tiyak na hahayaan kang makuha ang ninanais na resulta. Sa programming, patuloy kaming nagsusumikap upang makumpleto ang mga gawain. Ang isang makabuluhang bahagi ng mga gawaing ito ay maaaring isagawa gamit ang mga algorithm na alam na. Halimbawa, ipagpalagay na ang iyong gawain ay ito: pagbukud-bukurin ang isang listahan ng 100 mga pangalan sa isang array . Ang gawaing ito ay medyo simple, ngunit maaari itong malutas sa iba't ibang paraan. Narito ang isang posibleng solusyon: Algorithm para sa pag-uuri ng mga pangalan ayon sa alpabeto:

1. Bilhin o i-download ang 1961 na edisyon ng Webster's Third New International Dictionary.
2. Hanapin ang bawat pangalan mula sa aming listahan sa diksyunaryong ito.
3. Sa isang piraso ng papel, isulat ang pahina ng diksyunaryo kung saan matatagpuan ang pangalan.
4. Gamitin ang mga piraso ng papel upang pagbukud-bukurin ang mga pangalan.

Magagawa ba ng gayong pagkakasunod-sunod ng mga aksyon ang ating gawain? Oo, tiyak na mangyayari ito. Epektibo ba ang solusyong ito ? Halos hindi. Narito tayo sa isa pang napakahalagang aspeto ng mga algorithm: ang kanilang kahusayan . Mayroong ilang mga paraan upang magawa ang gawaing ito. Ngunit pareho sa programming at sa ordinaryong buhay, gusto naming piliin ang pinaka mahusay na paraan. Kung ang iyong gawain ay gumawa ng isang piraso ng mantikilya ng toast, maaari kang magsimula sa pamamagitan ng paghahasik ng trigo at paggatas ng baka. Ngunit iyon ay magiging isang hindi epektibosolusyon — aabutin ito ng maraming oras at gagastos ng malaking pera. Magagawa mo ang iyong simpleng gawain sa pamamagitan lamang ng pagbili ng tinapay at mantikilya. Bagama't hinahayaan ka nitong lutasin ang problema, ang algorithm na kinasasangkutan ng trigo at baka ay masyadong kumplikado upang magamit sa pagsasanay. Sa programming, mayroon kaming espesyal na notasyon na tinatawag na big O notation upang masuri ang pagiging kumplikado ng mga algorithm. Ginagawang posible ng Big O na masuri kung gaano kalaki ang tagal ng pagpapatupad ng algorithm sa laki ng data ng input . 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 milya). Anong algorithm ang magiging pinaka-epektibo? Depende ito sa data na pinagtatrabahuhan mo. Halimbawa, ipagpalagay na mayroon kaming isang audio file na 10 MB. Sa kasong ito, ang pinaka mahusay na algorithm ay ang ipadala ang file sa Internet. Hindi ito maaaring tumagal ng higit sa ilang minuto! Ipahayag muli ang aming algorithm: "Kung gusto mong maglipat ng impormasyon sa anyo ng mga file sa layong 5000 milya, dapat mong ipadala ang data sa pamamagitan ng Internet". Magaling. Ngayon ay pag-aralan natin ito. Nagagawa ba nito ang ating gawain?Well, oo, ito ay. Ngunit ano ang masasabi natin tungkol sa pagiging kumplikado nito? Hmm, ngayon ay nagiging mas kawili-wili ang mga bagay. Ang katotohanan ay ang aming algorithm ay nakasalalay sa data ng pag-input, ibig sabihin, ang laki ng mga file. Kung mayroon tayong 10 megabytes, kung gayon ang lahat ay maayos. Ngunit paano kung kailangan nating magpadala 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 talagang ilipat. Magtatagal pa ba? Oo, mangyayari ito! Ngayon ay alam na namin ang isang mahalagang feature ng aming algorithm: kung mas malaki ang dami ng data na ipapadala, mas magtatagal para patakbuhin ang algorithm. Ngunit gusto naming magkaroon ng mas tumpak na pag-unawa sa kaugnayang ito (sa pagitan ng laki ng data ng input at ang oras na kinakailangan upang ipadala ito). Sa aming kaso, ang pagiging kumplikado ng algorithm ay linear . Ang ibig sabihin ng "Linear" ay habang tumataas ang dami ng input data, tataas nang humigit-kumulang proporsyonal ang tagal ng pagpapadala nito. Kung doble ang dami ng data, ang oras na kinakailangan para ipadala ito ay magiging doble pa. Kung ang data ay tumaas ng 10 beses, ang oras ng paghahatid ay tataas ng 10 beses. Gamit ang malaking O notation, ang pagiging kumplikado ng aming algorithm ay ipinahayag bilang O(n). Dapat mong tandaan ang notasyong ito para sa hinaharap — palagi itong ginagamit para sa mga algorithm na may linear complexity. Tandaan na hindi namin pinag-uusapan ang ilang bagay na maaaring mag-iba dito: bilis ng Internet, kapangyarihan sa pag-compute ng aming computer, at iba pa. Kapag sinusuri ang pagiging kumplikado ng isang algorithm, walang saysay na isaalang-alang ang mga salik na ito — sa anumang kaganapan, wala sa aming kontrol ang mga ito. Ang Big O notation ay nagpapahayag ng pagiging kumplikado ng algorithm mismo, hindi ang "kapaligiran" kung saan ito tumatakbo. Ipagpatuloy natin ang ating halimbawa. Ipagpalagay na sa huli ay nalaman namin na kailangan naming magpadala ng mga file na may kabuuang 800 terabytes. Magagawa natin, siyempre, ang ating gawain sa pamamagitan ng pagpapadala sa kanila sa Internet. May isang problema lang: sa karaniwang mga rate ng paghahatid ng data ng sambahayan (100 megabits bawat segundo), aabutin ito ng humigit-kumulang 708 araw. Halos 2 taon! :O Ang aming algorithm ay malinaw na hindi angkop dito. Kailangan natin ng ibang solusyon! Sa hindi inaasahan, ang higanteng IT na Amazon ay dumating upang iligtas kami! Hinahayaan kami ng serbisyo ng Snowmobile ng Amazon na mag-upload ng malaking halaga ng data sa mobile storage at pagkatapos ay ihatid ito sa nais na address sa pamamagitan ng trak! Kaya, mayroon kaming bagong algorithm! "Kung gusto mong maglipat ng impormasyon sa anyo ng mga file sa layong 5000 milya at ang paggawa nito ay tatagal ng higit sa 14 na araw upang maipadala sa pamamagitan ng Internet, dapat mong ipadala ang data sa isang trak ng Amazon." Pinili namin ang 14 na araw nang arbitraryo dito. Sabihin na nating ito ang pinakamahabang panahon na maaari nating hintayin. Suriin natin ang aming algorithm. Paano ang bilis nito? Kahit na ang trak ay bumiyahe lamang sa 50 mph, ito ay sasaklaw ng 5000 milya sa loob lamang ng 100 oras. Mahigit apat na araw na ito! Ito ay mas mahusay kaysa sa opsyon ng pagpapadala ng data sa Internet. At ano ang tungkol sa pagiging kumplikado ng algorithm na ito? Linear din ba ito, ibig sabihin, O(n)? Hindi kaya. Pagkatapos ng lahat, ang trak ay walang pakialam kung gaano kabigat ang pagkarga mo dito — ito ay magda-drive pa rin sa halos parehong bilis at darating sa oras. Mayroon man tayong 800 terabytes, o 10 beses pa rin iyon, makakarating pa rin ang trak sa destinasyon nito sa loob ng 5 araw. Sa madaling salita, ang algorithm ng paglilipat ng data na nakabatay sa trak ay may palaging kumplikado. Dito, ang ibig sabihin ng "constant" ay hindi ito nakadepende sa laki ng data ng input. Maglagay ng 1GB flash drive sa trak, darating ito sa loob ng 5 araw. Ilagay sa mga disk na naglalaman ng 800 terabytes ng data, darating ito sa loob ng 5 araw. Kapag gumagamit ng malaking O notation, ang patuloy na pagiging kumplikado ay tinutukoy ng O(1) . Naging pamilyar tayo sa O(n) at O(1) , kaya ngayon tingnan natin ang higit pang mga halimbawa sa mundo ng programming :) Ipagpalagay na binigyan ka ng array ng 100 na numero, at ang gawain ay ipakita ang bawat isa sa kanila sa ang console. Sumulat ka ng isang ordinaryong forloop na nagsasagawa ng gawaing ito

int[] numbers = new int[100];
// ...fill the array with numbers

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

Ano ang pagiging kumplikado ng algorithm na ito? Linear, ibig sabihin, O(n). Ang bilang ng mga aksyon na dapat gawin ng programa ay depende sa kung gaano karaming mga numero ang ipinapasa dito. Kung mayroong 100 numero sa array, magkakaroon ng 100 aksyon (mga pahayag upang ipakita ang mga string sa screen). Kung mayroong 10,000 na numero sa array, 10,000 na aksyon ang dapat gawin. Maaari bang mapabuti ang aming algorithm sa anumang paraan? Hindi. Anuman ang mangyari, kailangan nating gumawa ng N pass sa array at magsagawa ng N statement para magpakita ng mga string sa console. Isaalang-alang 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 suriin ang pagiging kumplikado ng algorithm ng pagpasok ng isang numero sa sa LinkedListaming halimbawa, at kung paano ito nakadepende sa bilang ng mga elemento sa listahan. Ang sagot ay O(1), ibig sabihin, pare-pareho ang pagiging kumplikado . Bakit? Tandaan na ipinapasok namin ang bawat numero sa simula ng listahan. Bilang karagdagan, maaalala mo na kapag nagpasok ka ng isang numero sa isang LinkedList, ang mga elemento ay hindi gumagalaw kahit saan. Ang mga link (o mga sanggunian) ay ina-update (kung nakalimutan mo kung paano gumagana ang LinkList, tingnan ang isa sa aming mga lumang aralin ). Kung ang unang numero sa aming listahan ay x, at ilalagay namin ang numerong y sa harap ng listahan, ang kailangan lang naming gawin ay ito:

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

Kapag na-update namin ang mga link, wala kaming pakialam kung ilang numero na ang nasaLinkedList , isa man o isang bilyon. Ang pagiging kumplikado ng algorithm ay pare-pareho, ibig sabihin, O(1).

Ang pagiging kumplikado ng logarithmic

Huwag mag-panic! :) Kung gusto mong isara ng salitang "logarithmic" ang araling ito at huminto sa pagbabasa, kumapit lang ng ilang minuto. Walang anumang mabaliw na matematika dito (mayroong maraming mga paliwanag na tulad niyan sa ibang lugar), at pipiliin namin ang bawat halimbawa. Isipin na ang iyong gawain ay maghanap ng isang partikular na numero sa hanay ng 100 numero. Mas tiyak, kailangan mong suriin kung ito ay naroroon o wala. Sa sandaling mahanap ang kinakailangang numero, magtatapos ang paghahanap, at ipapakita mo ang sumusunod sa console: "Nahanap ang kinakailangang numero! Ang index nito sa array = ...." Paano mo magagawa ang gawaing ito? Narito ang solusyon ay halata: kailangan mong ulitin ang mga elemento ng array nang paisa-isa, simula sa una (o mula sa huli) at suriin kung ang kasalukuyang numero ay tumutugma sa iyong hinahanap. Alinsunod dito, ang bilang ng mga aksyon ay direktang nakasalalay sa bilang ng mga elemento sa array. Kung mayroon tayong 100 numero, maaaring kailanganin nating pumunta sa susunod na elemento ng 100 beses at magsagawa ng 100 paghahambing. Kung mayroong 1000 na numero, maaaring mayroong 1000 na paghahambing. Ito ay malinaw na linear kumplikado, ibig sabihinO(n) . At ngayon ay magdaragdag kami ng isang pagpipino sa aming halimbawa: ang array kung saan kailangan mong hanapin ang numero ay pinagsunod-sunod sa pataas na pagkakasunud-sunod . May pagbabago ba ito tungkol sa ating gawain? Maaari pa rin kaming magsagawa ng brute-force na paghahanap para sa gustong numero. Ngunit bilang kahalili, maaari naming gamitin ang kilalang binary search algorithm . Sa itaas na hilera sa larawan, nakikita namin ang isang pinagsunod-sunod na hanay. Kailangan nating hanapin ang numerong 23 dito. Sa halip na umulit sa mga numero, hinahati lang namin ang array sa 2 bahagi at suriin ang gitnang numero sa array. Hanapin ang numero na matatagpuan sa cell 4 at suriin ito (pangalawang row sa larawan). Ang numerong ito ay 16, at hinahanap namin ang 23. Ang kasalukuyang numero ay mas mababa kaysa sa hinahanap namin. Anong ibig sabihin niyan? Ibig sabihin nito aylahat ng mga naunang numero (mga nasa unahan ng numero 16) ay hindi kailangang suriin : ang mga ito ay garantisadong mas mababa kaysa sa hinahanap namin, dahil ang aming array ay pinagsunod-sunod! Ipinagpapatuloy namin ang paghahanap sa natitirang 5 elemento. Tandaan:nagsagawa kami ng isang paghahambing, ngunit naalis na namin ang kalahati ng mga posibleng opsyon. Mayroon na lamang tayong 5 elemento na natitira. Uulitin namin ang aming nakaraang hakbang sa pamamagitan ng muling paghahati sa natitirang subarray sa kalahati at muling pagkuha sa gitnang elemento (ang ika-3 hilera sa larawan). Ang numero ay 56, at ito ay mas malaki kaysa sa isa na hinahanap namin. Anong ibig sabihin niyan? Nangangahulugan ito na inalis namin ang isa pang 3 posibilidad: ang numero 56 mismo pati na rin ang dalawang numero pagkatapos nito (dahil ang mga ito ay garantisadong mas malaki sa 23, dahil ang array ay pinagsunod-sunod). Mayroon na lang kaming 2 numero na natitira upang suriin (ang huling hilera sa larawan) — ang mga numero na may mga indeks ng array 5 at 6. Sinusuri namin ang una sa mga ito, at nakita namin kung ano ang aming hinahanap — ang numerong 23! Ang index nito ay 5! Tingnan natin ang mga resulta ng aming algorithm, at pagkatapos ay Susuriin ang pagiging kumplikado nito. Sa pamamagitan ng paraan, ngayon naiintindihan mo kung bakit ito ay tinatawag na binary search: umaasa ito sa paulit-ulit na paghahati ng data sa kalahati. Ang resulta ay kahanga-hanga! Kung gumamit kami ng linear na paghahanap upang hanapin ang numero, kakailanganin namin ng hanggang 10 paghahambing, ngunit sa isang binary na paghahanap, nagawa namin ang gawain na may 3 lang! Sa pinakamasamang kaso, magkakaroon ng 4 na paghahambing (kung sa huling hakbang ang numero na gusto namin ay ang pangalawa sa natitirang mga posibilidad, sa halip na ang una. Kaya paano ang pagiging kumplikado nito? Ito ay isang napaka-interesante na punto :) Ang binary search algorithm ay hindi gaanong nakadepende sa bilang ng mga elemento sa array kaysa sa linear search algorithm (iyon ay, simpleng pag-ulit). Sa 10 elemento sa array, ang isang linear na paghahanap ay mangangailangan ng maximum na 10 paghahambing, ngunit ang binary na paghahanap ay mangangailangan ng maximum na 4 na paghahambing. Iyon ay isang pagkakaiba sa pamamagitan ng isang kadahilanan na 2.5. Ngunit para sa isang hanay ng 1000 elemento , ang isang linear na paghahanap ay mangangailangan ng hanggang 1000 paghahambing, ngunit ang isang binary na paghahanap ay mangangailangan lamang ng 10 ! Ang pagkakaiba ay 100 ulit na! Tandaan:ang bilang ng mga elemento sa array ay tumaas ng 100 beses (mula 10 hanggang 1000), ngunit ang bilang ng mga paghahambing na kinakailangan para sa isang binary na paghahanap ay tumaas ng isang kadahilanan na 2.5 lamang (mula 4 hanggang 10). Kung makakarating tayo sa 10,000 elemento , magiging mas kahanga-hanga ang pagkakaiba: 10,000 paghahambing para sa linear na paghahanap, at kabuuang 14 na paghahambing para sa binary na paghahanap. At muli, kung ang bilang ng mga elemento ay tumaas ng 1000 beses (mula 10 hanggang 10000), kung gayon ang bilang ng mga paghahambing ay tataas ng isang kadahilanan na 3.5 lamang (mula 4 hanggang 14). Ang pagiging kumplikado ng binary search algorithm ay logarithmic , o, kung gagamit tayo ng malaking O notation, O(log n). Bakit ito tinawag? Ang logarithm ay parang kabaligtaran ng exponentiation. Ang binary logarithm ay ang kapangyarihan kung saan ang numero 2 ay dapat na itaas upang makakuha ng isang numero. Halimbawa, mayroon kaming 10,000 elemento na kailangan naming hanapin gamit ang binary search algorithm. Sa kasalukuyan, maaari mong tingnan ang talahanayan ng mga halaga upang malaman na ang paggawa nito ay mangangailangan ng maximum na 14 na paghahambing. Ngunit paano kung walang nagbigay ng ganoong talahanayan at kailangan mong kalkulahin ang eksaktong maximum na bilang ng mga paghahambing? Kailangan mo lang sagutin ang isang simpleng tanong: sa anong kapangyarihan kailangan mong itaas ang numero 2 upang ang resulta ay mas malaki kaysa o katumbas ng bilang ng mga elemento na susuriin? Para sa 10,000, ito ang ika-14 na kapangyarihan. 2 sa ika-13 na kapangyarihan ay masyadong maliit (8192), ngunit 2 sa ika-14 na kapangyarihan = 16384, at ang bilang na ito ay nakakatugon sa aming kundisyon (ito ay mas malaki kaysa o katumbas ng bilang ng mga elemento sa array). Natagpuan namin ang logarithm: 14. Gaano karaming mga paghahambing ang maaaring kailanganin namin! :) Ang mga algorithm at algorithmic complexity ay masyadong malawak na paksa upang magkasya sa isang aralin. Ngunit ang pag-alam na ito ay napakahalaga: maraming mga panayam sa trabaho ang magsasangkot ng mga tanong na kinasasangkutan ng mga algorithm. Para sa teorya, maaari akong magrekomenda ng ilang mga libro para sa iyo. Maaari kang magsimula sa " Grokking Algorithms ". Ang mga halimbawa sa aklat na ito ay nakasulat sa Python, ngunit ang aklat ay gumagamit ng napakasimpleng wika at mga halimbawa. Ito ang pinakamagandang opsyon para sa isang baguhan at, higit pa, hindi ito masyadong malaki. Sa mas seryosong pagbabasa, mayroon kaming mga aklat nina Robert Lafore at Robert Sedgewick. 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 mahusay na kasanayan sa matematika, ang pinakamagandang opsyon ay ang aklat ni Thomas Cormen . Ngunit ang teorya lamang ay hindi pupunuin ang iyong tiyan! Kaalaman != Kakayahan . Maaari kang magsanay sa paglutas ng mga problemang kinasasangkutan ng mga algorithm sa HackerRank at LeetCode . Ang mga gawain mula sa mga website na ito ay madalas na ginagamit kahit na sa panahon ng mga panayam sa Google at Facebook, kaya tiyak na hindi ka magsasawa :) Upang mapalakas ang materyal ng aralin na ito, inirerekomenda kong panoorin mo ang mahusay na video na ito tungkol sa big O notation sa YouTube. Magkita-kita tayo sa susunod na mga aralin! :)