Kompleksitas algoritma

Hello! Kuliah dina iki bakal rada beda karo liyane. Bakal beda-beda amarga mung ora langsung ana hubungane karo Jawa. Nanging, topik iki penting banget kanggo saben programmer. Kita bakal ngomong babagan algoritma . Apa algoritma? Ing istilah sing prasaja, iki minangka urutan tumindak tartamtu sing kudu ditindakake kanggo entuk asil sing dikarepake . Kita asring nggunakake algoritma ing saben dinten. Contone, saben esuk sampeyan ngadhepi tugas: teka sekolah utawa kerja, lan ing wektu sing padha:

• Busana
• resik
• Apik-apik

Algoritma apa sing bakal ngidini sampeyan entuk asil iki?

1. Tangi karo jam weker.
2. Adus, cuci muka.
3. Siapke sarapan, gawe kopi/teh.
4. mangan.
5. Yen sampeyan durung nyetrika sandhangan wiwit sore, setrika.
6. Klamben.
7. Ninggalake omah.

Urutan tumindak iki mesthi bakal ngidini sampeyan entuk asil sing dikarepake. Ing pemrograman, kabeh tugas kita yaiku ngrampungake masalah kanthi terus-terusan. Bagean penting saka tugas kasebut bisa ditindakake kanthi nggunakake algoritma sing wis dikenal. Contone, sampeyan ngadhepi tugas: ngurutake dhaptar 100 jeneng ing larik . Tugas iki cukup prasaja, nanging bisa ditanggulangi kanthi cara sing beda-beda. Iki minangka salah sawijining solusi: Algoritma ngurutake jeneng miturut abjad:

1. Tuku utawa download ing Internet "Kamus Jeneng Pribadi Rusia" edisi 1966.
2. Temokake saben jeneng ing dhaptar kita ing kamus iki.
3. Tulis ing kertas sing ana ing kaca kamus sing jenenge.
4. Sijine jeneng kanthi urutan nggunakake cathetan ing kertas.

Apa urutan tumindak kasebut ngidini kita ngrampungake masalah kita? Ya, iku bakal rampung ngidini. Apa solusi iki bakal efektif ? meh ora. Ing kene kita teka ing properti algoritma liyane sing penting banget - efisiensi . Masalah bisa ditanggulangi kanthi cara sing beda-beda. Nanging ing program lan ing saben dinten, kita milih cara sing paling efektif. Yen tugas sampeyan nggawe roti isi karo mentega, sampeyan bisa, mesthi, miwiti nyebar gandum lan milking sapi. Nanging iki bakal dadi solusi sing ora efektif - bakal entuk akeh wektu lan biaya akeh dhuwit. Kanggo ngatasi masalah sing prasaja, sampeyan mung bisa tuku roti lan mentega. Lan algoritma karo gandum lan sapi, sanajan ngijini sampeyan kanggo ngatasi masalah, banget Komplek kanggo aplikasi ing laku. Kanggo netepake kerumitan algoritma ing pemrograman, notasi khusus digawe sing diarani Big-O ("big O") . Big-O ngidini sampeyan ngira sepira wektu eksekusi algoritma gumantung saka data sing dilebokake . Ayo goleki conto sing paling gampang - transfer data. Mbayangno yen sampeyan kudu ngirim sawetara informasi ing wangun file ing jarak adoh (contone, 5000 kilometer). Algoritma endi sing paling efisien? Iku gumantung ing data sing kudu digarap. Contone, kita duwe file audio ukuran 10 megabyte. Ing kasus iki, algoritma sing paling efisien yaiku nransfer file liwat Internet. Iku mung bakal njupuk sawetara menit! Dadi, ayo ngucapake algoritma maneh: "Yen sampeyan kudu nransfer informasi ing bentuk file kanthi jarak 5000 kilometer, sampeyan kudu nggunakake transmisi data liwat Internet." Agung. Saiki ayo dianalisis. Apa ngrampungake masalah kita? Umumé, ya, rampung ngrampungake. Nanging apa sampeyan bisa ngomong babagan kerumitan? Hmm, saiki dadi menarik. Kasunyatane yaiku algoritma kita gumantung banget marang data sing mlebu, yaiku ukuran file. Saiki kita duwe 10 megabyte lan kabeh apik. Apa yen kita kudu nransfer 500 megabyte? 20 gigabyte? 500 terabyte? 30 petabyte? Apa algoritma kita bakal mandheg? Ora, kabeh jumlah data iki isih bisa ditransfer. Bakal njupuk maneh kanggo ngrampungake? Ya, iku bakal! Saiki kita ngerti fitur penting saka algoritma kita: luwih gedhe ukuran data sing bakal ditransfer, luwih suwe algoritma bakal rampung . Nanging kita pengin ngerti luwih tepat apa hubungan iki katon (antarane ukuran data lan wektu sing dibutuhake kanggo nransfer). Ing kasus kita, kerumitan algoritma bakal linear. "Linear" tegese yen volume data mundhak, wektu transmisi bakal saya tambah kanthi proporsional. Yen ana 2 kaping luwih data, lan bakal njupuk 2 kaping luwih wektu kanggo nransfer. Yen ana 10 kaping luwih data, wektu transfer bakal nambah 10 kaping. Nggunakake notasi Big-O, kerumitan algoritma kita ditetepake minangka O(N) . Notasi iki paling dieling-eling kanggo referensi ing mangsa ngarep; iki tansah digunakake kanggo algoritma kanthi kerumitan linier. Wigati dicathet: kita ora ngomong babagan macem-macem "variabel": kacepetan Internet, daya komputer, lan liya-liyane. Nalika netepake kerumitan algoritma, iki mung ora masuk akal - kita ora bisa ngontrol. Big-O ngevaluasi algoritma kasebut, preduli saka "lingkungan" sing kudu ditindakake. Ayo kita nerusake conto kita. Ayo kita ngomong pungkasane ternyata ukuran file sing bakal ditransfer yaiku 800 terabyte. Yen kita ngirim liwat Internet, masalah, mesthi, bakal ditanggulangi. Mung ana siji masalah: transmisi liwat link modern standar (ing 100 megabits per detik) sing umume digunakake ing omah-omah bakal njupuk kira-kira 708 dina. Meh 2 taun! :O Dadi, algoritma kita jelas ora cocok ing kene. We kudu sawetara solusi liyane! Dumadakan, raksasa IT Amazon nulungi kita! Layanan Amazon Snowmobile ngidini sampeyan mbukak akeh data menyang unit panyimpenan seluler lan ngirim menyang alamat sing dikarepake kanthi truk! Dadi, kita duwe algoritma anyar! "Yen sampeyan kudu nransfer informasi ing wangun file liwat jarak 5,000 kilometer, lan proses bakal njupuk luwih saka 14 dina nalika ditransfer liwat Internet, sampeyan kudu nggunakake transportasi truk Amazon." Angka 14 dina dipilih kanthi acak ing kene: ayo ngomong iki minangka periode maksimal sing bisa ditindakake. Ayo analisa algoritma kita. Kepiye babagan kacepetan? Sanajan truk kasebut lumaku kanthi kacepetan 50 km/jam, 5.000 kilometer mung 100 jam. Iku mung liwat patang dina! Iki luwih apik tinimbang pilihan transmisi Internet. Apa babagan kerumitan algoritma iki? Bakal uga linear, O(N)? Ora, ora bakal. Sawise kabeh, truk ora preduli sepira sampeyan mbukak - isih bakal nyopir kanthi kacepetan sing padha lan teka ing wektu sing tepat. Apa kita duwe 800 terabyte, utawa 10 kaping luwih data, truk isih bakal teka ing 5 dina. Ing tembung liya, algoritma kanggo ngirim data liwat truk nduweni kerumitan sing tetep . "Constant" tegese ora gumantung ing data sing dikirim menyang algoritma. Sijine flash drive 1GB ing truk lan bakal teka ing 5 dina. Sijine disk karo 800 terabyte data ana lan bakal teka ing 5 dina. Nalika nggunakake Big-O, kerumitan konstan dituduhake minangka O(1) . Awit kita wis dadi kenalan karo O(N) lanO (1) , ayo kang saiki katon ing liyane "programmer" conto :) Ayo dadi ngomong sampeyan diwenehi Uploaded 100 nomer, lan tugas kanggo print saben wong kanggo console. Sampeyan nulis daur ulang biasa forsing nindakake tugas iki

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

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

Apa kerumitan algoritma sing ditulis? Linear, O(N). Jumlah tumindak sing kudu ditindakake dening program kasebut gumantung saka jumlah nomer kasebut. Yen ana 100 nomer ing larik, bakal ana 100 tumindak (output ing layar) Yen ana 10.000 nomer ing larik, 10.000 tumindak kudu ditindakake. Apa algoritma kita bisa ditingkatake? Ora. Ing kasus apa wae, kita kudu nggawe N liwat array lan nindakake N output menyang console. Ayo goleki conto liyane.

public static void main(String[] args) {

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

Kita duwe siji kosong LinkedListsing dilebokake sawetara nomer. Kita kudu ngira kerumitan algoritma kanggo nglebokake nomer siji menyang LinkedListconto, lan carane gumantung saka jumlah unsur ing dhaptar. Jawaban iki O(1) - kerumitan konstan . Kenging punapa? Wigati dicathet: saben kita nglebokake nomer ing wiwitan dhaptar. Kajaba iku, nalika sampeyan ngelingi, nalika nglebokake angka menyang LinkedListunsur, dheweke ora dipindhah menyang endi wae - pranala didefinisikan maneh (yen sampeyan tiba-tiba lali cara kerja LinkedList, deleng salah sawijining ceramah lawas ). Yen saiki nomer pisanan ing dhaptar kita yaiku nomer х, lan kita masang nomer y ing wiwitan dhaptar, kabeh sing dibutuhake yaiku:

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

Kanggo redefinisi referensi iki, ora dadi masalah kanggo kita pira nomer saikiLinkedList - paling ora siji, paling ora milyar. Kompleksitas algoritma bakal tetep - O(1).

Kompleksitas logaritma

Aja geger! :) Yen tembung "logaritmik" nggawe sampeyan pengin nutup kuliah lan ora maca maneh, ngenteni sawetara menit. Ora bakal ana kesulitan matematika ing kene (ana akeh panjelasan kasebut ing papan liya), lan kita bakal nganalisa kabeh conto "ing driji". Bayangake yen tugas sampeyan yaiku nemokake nomer tartamtu ing susunan 100 nomer. Luwih tepate, priksa manawa ana ing kono. Sanalika nomer sing dibutuhake ditemokake, telusuran kudu mandheg, lan entri "Nomer sing dibutuhake wis ditemokake!" kudu ditampilake ing konsol. Indeks ing larik = ....” Kepiye carane ngatasi masalah kasebut? Ing kene, solusi kasebut jelas: sampeyan kudu ngubengi unsur-unsur array siji-sijine, diwiwiti kanthi pisanan (utawa pungkasan) lan priksa manawa nomer saiki pas karo sing dikarepake. Dadi, jumlah tumindak langsung gumantung saka jumlah unsur ing array. Yen kita duwe 100 nomer, banjur kita kudu pindhah menyang unsur sabanjuré 100 kaping lan mriksa nomer kanggo cocog 100 kaping. Yen ana 1000 nomer, banjur bakal ana langkah mriksa 1000. Iki temenan kerumitan linear, O(N) . Saiki kita bakal nambah siji klarifikasi kanggo conto kita: array sing sampeyan kudu nemokake nomer diurutake ing urutan munggah . Apa iki ngganti apa wae kanggo tugas kita? Kita isih bisa nggoleki nomer sing dikarepake kanthi brute force. Nanging kita bisa nggunakake algoritma telusuran binar sing kondhang tinimbang . Ing baris ndhuwur gambar kita ndeleng array diurutake. Ing kita kudu golek nomer 23. Tinimbang iterating liwat nomer, kita mung dibagi Uploaded menyang 2 bagean lan mriksa nomer rata-rata ing Uploaded. Kita nemokake nomer sing ana ing sel 4 lan mriksa (baris kapindho ing gambar). Iki nomer 16, lan kita looking for 23. Jumlah saiki kurang. Apa tegese iki? Sing kabeh nomer sadurunge (sing dumunung nganti nomer 16) ora perlu dicenthang : padha mesthi bakal kurang saka siji kita looking for, amarga array kita wis diurutake! Ayo nerusake panelusuran ing antarane 5 unsur sing isih ana. Pay manungsa waé:Kita wis rampung mung siji mriksa, nanging kita wis ngilangi setengah saka opsi bisa. Kita mung duwe 5 unsur sing isih ana. Kita bakal mbaleni langkah - maneh dibagi array sing isih ana kanthi 2 lan maneh njupuk unsur tengah (baris 3 ing gambar). Nomer iki 56, lan luwih gedhe tinimbang sing kita goleki. Apa tegese iki? Sing kita discard 3 opsi liyane - nomer 56 dhewe, lan loro nomer sawise iku (padha mesthi luwih saka 23, amarga Uploaded diurutake). We kudu mung 2 nomer kiwa kanggo mriksa (baris pungkasan ing tokoh) - nomer karo indeks Uploaded 5 lan 6. Kita mriksa pisanan mau, lan iki apa kita padha looking for - nomer 23! Indeks = 5! Ayo ndeleng asil algoritma kita, banjur kita bakal ngerti kerumitan. (Oalah, saiki sampeyan ngerti kenapa diarani biner: intine yaiku terus-terusan mbagi data kanthi 2). Asil nyengsemaken! Yen kita nggoleki nomer sing dikarepake nggunakake telusuran linear, kita butuh 10 mriksa, nanging kanthi panelusuran binar kita nindakake ing 3! Ing kasus sing paling awon, bakal ana 4, yen ing langkah pungkasan nomer sing dibutuhake dadi nomer loro, lan dudu sing pertama. Kepiye babagan kerumitan? Iki minangka titik sing menarik banget :) Algoritma telusuran binar gumantung banget karo jumlah unsur ing array tinimbang algoritma telusuran linier (yaiku, enumerasi sing prasaja). Kanthi 10 unsur ing larik, telusuran linear mbutuhake maksimal 10 pamriksa, lan telusuran binar mbutuhake maksimal 4 pamriksaan. Bentenipun punika 2,5 kaping. Nanging kanggo macem-macem 1000 unsur, telusuran linear mbutuhake 1000 mriksa, lan telusuran binar mung butuh 10 ! Bentenipun wis 100 kaping! Pay manungsa waé:jumlah unsur ing array tambah 100 kaping (saka 10 kanggo 1000), lan jumlah mriksa perlu kanggo panelusuran binar tambah mung 2,5 kaping - saka 4 kanggo 10. Yen kita tekan 10.000 unsur , prabédan malah luwih nyengsemaken: 10.000 mriksa panelusuran linear, lan total 14 mriksa kanggo binar. Lan maneh: jumlah unsur tambah 1000 kaping (saka 10 kanggo 10000), nanging jumlah mriksa tambah mung 3,5 kaping (saka 4 kanggo 14). Kompleksitas algoritma telusuran binar yaiku logaritmik , utawa, ing notasi Big-O, O(log n) . Kok diarani ngono? Logaritma minangka kebalikan saka eksponensial. Logaritma biner digunakake kanggo ngetung daya 2. Contone, kita duwe 10.000 unsur sing kudu ditindakake kanthi nggunakake telusuran binar. Saiki sampeyan duwe gambar sadurunge mata, lan sampeyan ngerti yen iki mbutuhake maksimum 14 mriksa. Nanging apa yen ora ana gambar sadurunge mata, lan sampeyan kudu ngetung jumlah pas perlu mriksa? Cukup kanggo njawab pitakonan sing prasaja: apa daya kudu diunggahake nomer 2 supaya asil sing dipikolehi > = jumlah unsur sing dipriksa? Kanggo 10000 bakal dadi daya kaping 14. 2 kanggo daya kaping 13 cilik banget (8192) Nanging 2 kanggo daya kaping 14 = 16384 , nomer iki nyukupi kawontenan kita (iku > = jumlah unsur ing array). Kita nemokake logaritma - 14. Sepira akeh cek sing dibutuhake! :) Algoritma lan kerumitan kasebut minangka topik sing akeh banget kanggo dilebokake ing siji kuliah. Nanging ngerti penting banget: ing akeh wawancara sampeyan bakal nampa masalah algoritma. Kanggo teori, aku bisa menehi rekomendasi sawetara buku. Panggonan sing apik kanggo miwiti yaiku " Algoritma Grocking ": sanajan conto ing buku kasebut ditulis nganggo Python, basa lan conto buku kasebut gampang banget. Pilihan sing paling apik kanggo pamula, lan uga volume cilik. Wacan sing luwih serius: buku dening Robert Laforet lan Robert Sedgwick . Loro-lorone ditulis ing basa Jawa, sing bakal nggawe sinau luwih gampang kanggo sampeyan. Sawise kabeh, sampeyan wis ngerti basa iki! :) Kanggo siswa kanthi latar mburi matematika sing apik, pilihan sing paling apik yaiku buku dening Thomas Corman . Nanging sampeyan ora bakal wareg karo mung teori! "Ngerti" ! = "bisa" Sampeyan bisa latihan ngatasi masalah algoritma ing HackerRank lan Leetcode . Masalah saka kono asring digunakake sanajan wawancara ing Google lan Facebook, dadi sampeyan mesthi ora bakal bosen :) Kanggo nguatake materi kuliah, aku menehi saran supaya nonton video sing apik babagan Big-O ing YouTube. Sampai jumpa lagi ing kuliah sabanjure! :)