Hi! Pawulangan dina iki bakal rada beda karo liyane. Bakal beda-beda amarga mung ora langsung ana hubungane karo Jawa. Yen ngandika, topik iki penting banget kanggo saben programmer. Kita bakal ngomong babagan algoritma . Apa algoritma? Ing istilah prasaja, iku sawetara urutan tumindak sing kudu rampung kanggo entuk asil sing dikarepake . Kita asring nggunakake algoritma ing saben dinten. Contone, saben esuk sampeyan duwe tugas tartamtu: menyang sekolah utawa kerja, lan ing wektu sing padha:
Sandhangan
resik
dipakani
Algoritma apa sing ngidini sampeyan entuk asil iki?
Tangi nganggo jam weker.
Adus lan adus.
Nggawe sarapan lan sawetara kopi utawa teh.
mangan.
Yen sampeyan ora nyetrika sandhangan ing wayah sore, banjur disetrika.
Klamben.
Ninggalake omah.
Urutan tumindak iki mesthi bakal ngidini sampeyan entuk asil sing dikarepake. Ing pemrograman, kita terus-terusan kerja kanggo ngrampungake tugas. Bagean penting saka tugas kasebut bisa ditindakake kanthi nggunakake algoritma sing wis dikenal. Contone, umpamane tugas sampeyan yaiku: ngurutake dhaptar 100 jeneng ing larik . Tugas iki cukup prasaja, nanging bisa ditanggulangi kanthi cara sing beda-beda. Iki minangka salah sawijining solusi sing bisa ditindakake: Algoritma ngurutake jeneng miturut abjad:
Tuku utawa download edisi 1961 saka Webster's Third New International Dictionary.
Temokake saben jeneng saka dhaptar kita ing kamus iki.
Ing kertas, tulisake kaca kamus sing jenenge.
Gunakake potongan kertas kanggo ngurutake jeneng.
Apa urutan tumindak kasebut bakal ngrampungake tugas kita? Ya, mesthi bakal. Apa solusi iki efisien ? meh ora. Ing kene kita teka menyang aspek algoritma liyane sing penting banget: efisiensi . Ana sawetara cara kanggo ngrampungake tugas iki. Nanging ing program lan ing urip biasa, kita pengin milih cara sing paling efisien. Yen tugas sampeyan nggawe roti panggang sing diolesi mentega, sampeyan bisa miwiti kanthi nyebar gandum lan nyusoni sapi. Nanging sing bakal dadi ora efisiensolusi - iku bakal njupuk akèh wektu lan bakal biaya akèh dhuwit. Sampeyan bisa ngrampungake tugas prasaja kanthi mung tuku roti lan mentega. Sanajan ngidini sampeyan ngatasi masalah kasebut, algoritma sing nglibatake gandum lan sapi banget rumit kanggo digunakake ing praktik. Ing pemrograman, kita duwe notasi khusus sing diarani notasi O gedhe kanggo netepake kerumitan algoritma. Big O ndadekake iku bisa kanggo netepke pinten wektu eksekusi algoritma gumantung ing ukuran data input . Ayo goleki conto sing paling gampang: transfer data. Mbayangno yen sampeyan kudu ngirim sawetara informasi ing wangun file ing jarak adoh (contone, 5000 mil). Algoritma apa sing paling efisien? Iku gumantung ing data sing digunakake karo. Contone, umpamane kita duwe file audio sing ukurane 10 MB. Ing kasus iki, algoritma sing paling efisien yaiku ngirim file liwat Internet. Ora bisa njupuk luwih saka sawetara menit! Ayo nyatakake maneh algoritma kita: "Yen sampeyan pengin nransfer informasi ing wangun file ing jarak 5000 mil, sampeyan kudu ngirim data liwat Internet". Banget. Saiki ayo dianalisis. Apa iku ngrampungake tugas kita?Inggih, inggih punika. Nanging apa sing bisa kita ucapake babagan kerumitan kasebut? Hmm, saiki dadi luwih menarik. Kasunyatane yaiku algoritma kita gumantung banget marang data input, yaiku ukuran file. Yen kita duwe 10 megabyte, mula kabeh apik. Nanging apa yen kita kudu ngirim 500 megabyte? 20 gigabyte? 500 terabyte? 30 petabyte? Apa algoritma kita bakal mandheg? Ora, kabeh jumlah data kasebut pancen bisa ditransfer. Bakal njupuk maneh? Ya, iku bakal! Saiki kita ngerti fitur penting saka algoritma kita: luwih gedhe jumlah data sing bakal dikirim, luwih suwe kanggo mbukak algoritma kasebut.. Nanging kita pengin duwe pangerten sing luwih tepat babagan hubungan iki (antarane ukuran data input lan wektu sing dibutuhake kanggo ngirim). Ing kasus kita, kerumitan algoritma linear . "Linear" tegese yen jumlah data input mundhak, wektu sing dibutuhake kanggo ngirim bakal saya tambah kanthi proporsional. Yen jumlah data tikel kaping pindho, wektu sing dibutuhake kanggo ngirim bakal kaping pindho. Yen data mundhak 10 kaping, wektu transmisi bakal nambah 10 kaping. Nggunakake notasi O gedhe, kerumitan algoritma kita ditulis minangka O (n). Sampeyan kudu ngelingi notasi iki kanggo masa depan - mesthi digunakake kanggo algoritma kanthi kerumitan linier. Elinga yen kita ora ngomong babagan sawetara perkara sing beda-beda ing kene: kacepetan Internet, daya komputasi komputer, lan liya-liyane. Nalika ngevaluasi kerumitan algoritma, ora ana gunane kanggo nimbang faktor kasebut - ing acara apa wae, ora ana ing kontrol kita. Notasi Big O nyatakake kerumitan algoritma kasebut dhewe, dudu "lingkungan" sing ditindakake. Ayo kita nerusake conto kita. Upaminipun kita pungkasanipun sinau sing kita kudu ngirim file total 800 terabyte. Kita bisa, mesthi, ngrampungake tugas kita kanthi ngirim liwat Internet. Mung ana siji masalah: ing tingkat transmisi data kluwarga standar (100 megabits per detik), iku bakal njupuk kira-kira 708 dina. Meh 2 taun! : O Algoritma kita temenan ora cocok ing kene. We kudu sawetara solusi liyane! Ora sengaja, raksasa IT Amazon teka kanggo ngluwari kita! Layanan Snowmobile Amazon ngidini kita ngunggah data akeh menyang panyimpenan seluler banjur dikirim menyang alamat sing dikarepake kanthi truk! Dadi, kita duwe algoritma anyar! "Yen sampeyan pengin nransfer informasi ing wangun file liwat kadohan saka 5000 mil lan mengkono bakal njupuk luwih saka 14 dina kanggo ngirim liwat Internet, sampeyan kudu ngirim data ing truk Amazon." Kita milih 14 dina kanthi sewenang-wenang ing kene. Ayo ngomong iki wektu paling dawa kita bisa ngenteni. Ayo analisa algoritma kita. Kepiye babagan kacepetan? Sanajan truk kasebut mlaku kanthi kacepetan mung 50 mph, bakal nutupi 5000 mil sajrone 100 jam. Iki luwih saka patang dina! Iki luwih apik tinimbang pilihan ngirim data liwat Internet. Lan babagan kerumitan algoritma iki? Apa uga linear, yaiku O(n)? Ora, ora. Sawise kabeh, truk ora preduli sepira abote sampeyan mbukak - isih bakal nyopir kanthi kacepetan sing padha lan teka ing wektu sing tepat. Apa kita duwe 800 terabyte, utawa kaping 10, truk isih bakal tekan tujuane sajrone 5 dina. Ing tembung liya, algoritma transfer data adhedhasar truk nduweni kerumitan konstan. Ing kene, "konstan" tegese ora gumantung ing ukuran data input. Sijine flash drive 1GB ing truk, bakal teka ing 5 dina. Sijine ing disk sing ngemot 800 terabyte data, bakal teka ing 5 dina. Nalika nggunakake notasi O gedhe, kerumitan konstan dilambangake O(1) . Kita wis kenal karo O(n) lan O(1) , mula saiki ayo ndeleng conto liyane ing jagad pemrograman :) Upaminipun sampeyan diwenehi array 100 nomer, lan tugase yaiku nampilake saben-saben ing. konsol. Sampeyan nulis loop biasa forsing nindakake tugas iki
int[] numbers =newint[100];// ...fill the array with numbersfor(int i: numbers){System.out.println(i);}
Apa kerumitan algoritma iki? Linear, yaiku O(n). Jumlah tumindak sing kudu ditindakake program kasebut gumantung saka jumlah nomer sing diterusake. Yen ana 100 nomer ing array, bakal ana 100 tumindak (statements kanggo nampilake strings ing layar). Yen ana 10.000 nomer ing larik, banjur 10.000 tumindak kudu ditindakake. Apa algoritma kita bisa ditingkatake kanthi cara apa wae? Ora ana prakara apa, kita kudu nggawe N liwat Uploaded lan nglakokaké N statements kanggo tampilan strings ing console. Coba conto liyane.
We duwe kosong LinkedListmenyang kang kita masang sawetara nomer. Kita kudu ngevaluasi kerumitan algoritma kanggo nglebokake nomer siji ing LinkedListconto kita, lan carane gumantung saka jumlah unsur ing dhaptar. Jawabane yaiku O(1), yaiku kompleksitas konstan . Kenging punapa? Elinga yen kita masang saben nomer ing awal dhaftar. Kajaba iku, sampeyan bakal kelingan yen sampeyan masang nomer menyang a LinkedList, unsur ora pindhah ngendi wae. Link (utawa referensi) dianyari (yen sampeyan kelalen cara kerja LinkedList, deleng salah sawijining pelajaran lawas ). Yen nomer pisanan ing dhaftar kita x, lan kita masang nomer y ing ngarep dhaftar, banjur kabeh kita kudu nindakake iki:
x.previous = y;
y.previous =null;
y.next = x;
Nalika kita nganyari pranala, kita ora Care carane akeh nomer wis ingLinkedList , apa siji utawa siji milyar. Kompleksitas algoritma punika pancet, yaiku O(1).
Kompleksitas logaritma
Aja geger! :) Yen tembung "logaritmik" nggawe sampeyan pengin nutup pelajaran iki lan mandheg maca, tahan sawetara menit. Ora bakal ana matematika edan ing kene (ana akeh panjelasan kaya ing papan liya), lan kita bakal milih saben conto. Bayangake yen tugas sampeyan yaiku nemokake nomer tartamtu ing susunan 100 nomer. Luwih tepate, sampeyan kudu mriksa manawa ana utawa ora. Sanalika nomer sing dibutuhake ditemokake, telusuran rampung, lan sampeyan nampilake ing ngisor iki ing konsol: "Nomer sing dibutuhake ditemokake! Indeks ing array = ...." Kepiye carane sampeyan ngrampungake tugas iki? Ing kene, solusi kasebut jelas: sampeyan kudu ngulang unsur-unsur array siji-sijine, diwiwiti saka sing pertama (utawa saka sing pungkasan) lan priksa manawa nomer saiki cocog karo sing sampeyan goleki. Pramila, jumlah tumindak langsung gumantung ing nomer unsur ing Uploaded. Yen kita duwe 100 nomer, kita bisa uga kudu pindhah menyang unsur sabanjure kaping 100 lan nindakake 100 mbandhingake. Yen ana 1000 nomer, mula bisa uga ana 1000 mbandhingake. Iki jelas kerumitan linier, yaikuO(n) . Lan saiki kita bakal nambah siji refinement kanggo conto kita: larik ngendi sampeyan kudu nemokake nomer diurutake ing urutan munggah . Apa iki ngganti apa wae babagan tugas kita? Kita isih bisa nindakake panelusuran brute-force kanggo nomer sing dikarepake. Nanging minangka alternatif, kita bisa nggunakake algoritma telusuran binar sing kondhang . Ing baris ndhuwur ing gambar, kita ndeleng array diurutake. Kita kudu golek nomer 23 ing. Tinimbang iterasi liwat nomer, kita mung dibagi array dadi 2 bagean lan mriksa nomer tengah ing Uploaded. Temokake nomer sing ana ing sel 4 lan priksa (baris kapindho ing gambar). Iki nomer 16, lan kita looking for 23. Jumlah saiki kurang saka apa kita looking for. Apa tegese? Iku tegesekabeh nomer sadurunge (sing dumunung sadurunge nomer 16) ora perlu dicenthang : padha dijamin bakal kurang saka siji kita looking for, amarga array kita diurutake! Kita nerusake panelusuran ing antarane 5 unsur sing isih ana. Cathetan:kita wis dileksanakake mung siji comparison, nanging kita wis ngilangi setengah saka opsi bisa. Kita mung duwe 5 unsur sing isih ana. Kita bakal mbaleni langkah sadurunge kanthi misahake subarray sing isih ana ing setengah lan maneh njupuk unsur tengah (baris kaping 3 ing gambar). Jumlahe 56, lan luwih gedhe tinimbang sing kita goleki. Apa tegese? Iku tegese kita wis ngilangi liyane 3 kemungkinan: nomer 56 dhewe uga loro nomer sawise iku (amarga padha dijamin luwih saka 23, amarga Uploaded diurutake). Kita mung duwe 2 nomer kiwa kanggo mriksa (baris pungkasan ing gambar) - nomer karo indeks Uploaded 5 lan 6. Kita mriksa pisanan mau, lan golek apa kita padha looking for - nomer 23! Indekse 5! Ayo ndeleng asil algoritma kita, banjur kita ' bakal nganalisa kerumitan. Miturut cara, saiki sampeyan ngerti kenapa iki diarani telusuran binar: gumantung ing bola-bali mbagi data ing setengah. Asil nyengsemaken! Yen kita nggunakake telusuran linear kanggo nggoleki nomer kasebut, kita butuh nganti 10 mbandhingake, nanging kanthi telusuran binar, kita bisa ngrampungake tugas kasebut kanthi mung 3! Ing kasus paling awon, bakal ana 4 bandingaken (yen ing langkah pungkasan nomer kita wanted minangka kaloro saka kemungkinan isih, tinimbang pisanan. Dadi apa bab kerumitan sawijining? Iki titik menarik banget :) Algoritma telusuran binar kurang gumantung marang jumlah unsur ing array tinimbang algoritma telusuran linier (yaiku, iterasi prasaja). Kanthi 10 unsur ing larik, telusuran linear mbutuhake maksimal 10 mbandhingake, nanging telusuran binar mbutuhake maksimal 4 mbandhingake. Sing beda karo faktor 2,5. Nanging kanggo macem-macem 1000 unsur , telusuran linear mbutuhake nganti 1000 mbandhingake, nanging telusuran binar mung mbutuhake 10 ! Bentenipun saiki 100 tikel! Cathetan:nomer unsur ing Uploaded wis tambah 100 kaping (saka 10 kanggo 1000), nanging nomer bandingaken dibutuhake kanggo search binar wis tambah dening faktor mung 2,5 (saka 4 kanggo 10). Yen kita entuk 10.000 unsur , prabédan bakal luwih nyengsemake: 10.000 mbandhingake kanggo telusuran linear, lan total 14 mbandhingake kanggo panelusuran binar. Lan maneh, yen jumlah unsur mundhak 1000 kaping (saka 10 kanggo 10000), banjur nomer mbandhingaké mundhak dening faktor mung 3,5 (saka 4 kanggo 14). Kompleksitas algoritma telusuran binar yaiku logaritmik , utawa, yen kita nggunakake notasi O gedhe, O(log n). Kok diarani ngono? Logaritma minangka kebalikan saka eksponensial. Logaritma biner yaiku kekuwatan sing nomer 2 kudu diunggahake kanggo entuk nomer. Contone, kita duwe 10.000 unsur sing kudu digoleki nggunakake algoritma telusuran binar. Saiki, sampeyan bisa ndeleng tabel nilai kanggo ngerti yen nindakake iki mbutuhake maksimal 14 mbandhingake. Nanging kepiye yen ora ana sing nyedhiyakake tabel kasebut lan sampeyan kudu ngetung jumlah perbandingan maksimal sing tepat? Sampeyan mung kudu njawab pitakonan sing prasaja: apa daya sampeyan kudu ngunggahake nomer 2 supaya asil luwih gedhe tinimbang utawa padha karo jumlah unsur sing kudu dicenthang? Kanggo 10.000, iku daya kaping 14. 2 kanggo daya kaping 13 cilik banget (8192), nanging 2 kanggo daya kaping 14 = 16384, lan nomer iki nyukupi kondisi kita (luwih gedhe tinimbang utawa padha karo jumlah unsur ing array). Kita nemokake logaritma: 14. Semono uga akeh perbandingan sing dibutuhake! :) Algoritma lan kerumitan algoritmik minangka topik sing amba banget kanggo pas karo siji pelajaran. Nanging ngerti iku penting banget: akeh wawancara proyek bakal ndherek pitakonan nglibatno algoritma. Kanggo teori, aku bisa menehi rekomendasi sawetara buku kanggo sampeyan. Sampeyan bisa miwiti karo " Algoritma Grokking ". Conto ing buku iki ditulis nganggo Python, nanging buku kasebut nggunakake basa lan conto sing gampang banget. Iku pilihan sing paling apik kanggo pamula lan, apa maneh, iku ora amba banget. Antarane maca sing luwih serius, kita duwe buku dening Robert Lafore lan Robert Sedgewick. Loro-lorone ditulis ing basa Jawa, sing bakal nggawe sinau luwih gampang kanggo sampeyan. Sawise kabeh, sampeyan wis ngerti basa iki! :) Kanggo siswa sing duwe katrampilan matematika sing apik, pilihan sing paling apik yaiku buku Thomas Cormen . Nanging teori mung ora bakal ngisi weteng! Kawruh != Kemampuan . Sampeyan bisa latihan ngrampungake masalah sing nglibatake algoritma ing HackerRank lan LeetCode . Tugas saka situs web iki asring digunakake sanajan nalika wawancara ing Google lan Facebook, mula sampeyan mesthi ora bosen :) Kanggo nguatake materi pelajaran iki, aku nyaranake sampeyan nonton video sing apik babagan notasi O gedhe ing YouTube. Ditemokake ing wulangan sabanjure! :)
Yen ngandika, topik iki penting banget kanggo saben programmer. Kita bakal ngomong babagan algoritma . Apa algoritma? Ing istilah prasaja, iku sawetara urutan tumindak sing kudu rampung kanggo entuk asil sing dikarepake . Kita asring nggunakake algoritma ing saben dinten. Contone, saben esuk sampeyan duwe tugas tartamtu: menyang sekolah utawa kerja, lan ing wektu sing padha:
Ing kasus iki, algoritma sing paling efisien yaiku ngirim file liwat Internet. Ora bisa njupuk luwih saka sawetara menit! Ayo nyatakake maneh algoritma kita: "Yen sampeyan pengin nransfer informasi ing wangun file ing jarak 5000 mil, sampeyan kudu ngirim data liwat Internet". Banget. Saiki ayo dianalisis. Apa iku ngrampungake tugas kita?Inggih, inggih punika. Nanging apa sing bisa kita ucapake babagan kerumitan kasebut? Hmm, saiki dadi luwih menarik. Kasunyatane yaiku algoritma kita gumantung banget marang data input, yaiku ukuran file. Yen kita duwe 10 megabyte, mula kabeh apik. Nanging apa yen kita kudu ngirim 500 megabyte? 20 gigabyte? 500 terabyte? 30 petabyte? Apa algoritma kita bakal mandheg? Ora, kabeh jumlah data kasebut pancen bisa ditransfer. Bakal njupuk maneh? Ya, iku bakal! Saiki kita ngerti fitur penting saka algoritma kita: luwih gedhe jumlah data sing bakal dikirim, luwih suwe kanggo mbukak algoritma kasebut.. Nanging kita pengin duwe pangerten sing luwih tepat babagan hubungan iki (antarane ukuran data input lan wektu sing dibutuhake kanggo ngirim). Ing kasus kita, kerumitan algoritma linear . "Linear" tegese yen jumlah data input mundhak, wektu sing dibutuhake kanggo ngirim bakal saya tambah kanthi proporsional. Yen jumlah data tikel kaping pindho, wektu sing dibutuhake kanggo ngirim bakal kaping pindho. Yen data mundhak 10 kaping, wektu transmisi bakal nambah 10 kaping. Nggunakake notasi O gedhe, kerumitan algoritma kita ditulis minangka O (n). Sampeyan kudu ngelingi notasi iki kanggo masa depan - mesthi digunakake kanggo algoritma kanthi kerumitan linier. Elinga yen kita ora ngomong babagan sawetara perkara sing beda-beda ing kene: kacepetan Internet, daya komputasi komputer, lan liya-liyane. Nalika ngevaluasi kerumitan algoritma, ora ana gunane kanggo nimbang faktor kasebut - ing acara apa wae, ora ana ing kontrol kita. Notasi Big O nyatakake kerumitan algoritma kasebut dhewe, dudu "lingkungan" sing ditindakake. Ayo kita nerusake conto kita. Upaminipun kita pungkasanipun sinau sing kita kudu ngirim file total 800 terabyte. Kita bisa, mesthi, ngrampungake tugas kita kanthi ngirim liwat Internet. Mung ana siji masalah: ing tingkat transmisi data kluwarga standar (100 megabits per detik), iku bakal njupuk kira-kira 708 dina. Meh 2 taun! : O Algoritma kita temenan ora cocok ing kene. We kudu sawetara solusi liyane! Ora sengaja, raksasa IT Amazon teka kanggo ngluwari kita! Layanan Snowmobile Amazon ngidini kita ngunggah data akeh menyang panyimpenan seluler banjur dikirim menyang alamat sing dikarepake kanthi truk! 
Dadi, kita duwe algoritma anyar! "Yen sampeyan pengin nransfer informasi ing wangun file liwat kadohan saka 5000 mil lan mengkono bakal njupuk luwih saka 14 dina kanggo ngirim liwat Internet, sampeyan kudu ngirim data ing truk Amazon." Kita milih 14 dina kanthi sewenang-wenang ing kene. Ayo ngomong iki wektu paling dawa kita bisa ngenteni. Ayo analisa algoritma kita. Kepiye babagan kacepetan? Sanajan truk kasebut mlaku kanthi kacepetan mung 50 mph, bakal nutupi 5000 mil sajrone 100 jam. Iki luwih saka patang dina! Iki luwih apik tinimbang pilihan ngirim data liwat Internet. Lan babagan kerumitan algoritma iki? Apa uga linear, yaiku O(n)? Ora, ora. Sawise kabeh, truk ora preduli sepira abote sampeyan mbukak - isih bakal nyopir kanthi kacepetan sing padha lan teka ing wektu sing tepat. Apa kita duwe 800 terabyte, utawa kaping 10, truk isih bakal tekan tujuane sajrone 5 dina. Ing tembung liya, algoritma transfer data adhedhasar truk nduweni kerumitan konstan. Ing kene, "konstan" tegese ora gumantung ing ukuran data input. Sijine flash drive 1GB ing truk, bakal teka ing 5 dina. Sijine ing disk sing ngemot 800 terabyte data, bakal teka ing 5 dina. Nalika nggunakake notasi O gedhe, kerumitan konstan dilambangake O(1) . Kita wis kenal karo O(n) lan O(1) , mula saiki ayo ndeleng conto liyane ing jagad pemrograman :) Upaminipun sampeyan diwenehi array 100 nomer, lan tugase yaiku nampilake saben-saben ing. konsol. Sampeyan nulis loop biasa 
Ing baris ndhuwur ing gambar, kita ndeleng array diurutake. Kita kudu golek nomer 23 ing. Tinimbang iterasi liwat nomer, kita mung dibagi array dadi 2 bagean lan mriksa nomer tengah ing Uploaded. Temokake nomer sing ana ing sel 4 lan priksa (baris kapindho ing gambar). Iki nomer 16, lan kita looking for 23. Jumlah saiki kurang saka apa kita looking for. Apa tegese? Iku tegesekabeh nomer sadurunge (sing dumunung sadurunge nomer 16) ora perlu dicenthang : padha dijamin bakal kurang saka siji kita looking for, amarga array kita diurutake! Kita nerusake panelusuran ing antarane 5 unsur sing isih ana. Cathetan:kita wis dileksanakake mung siji comparison, nanging kita wis ngilangi setengah saka opsi bisa. Kita mung duwe 5 unsur sing isih ana. Kita bakal mbaleni langkah sadurunge kanthi misahake subarray sing isih ana ing setengah lan maneh njupuk unsur tengah (baris kaping 3 ing gambar). Jumlahe 56, lan luwih gedhe tinimbang sing kita goleki. Apa tegese? Iku tegese kita wis ngilangi liyane 3 kemungkinan: nomer 56 dhewe uga loro nomer sawise iku (amarga padha dijamin luwih saka 23, amarga Uploaded diurutake). Kita mung duwe 2 nomer kiwa kanggo mriksa (baris pungkasan ing gambar) - nomer karo indeks Uploaded 5 lan 6. Kita mriksa pisanan mau, lan golek apa kita padha looking for - nomer 23! Indekse 5! Ayo ndeleng asil algoritma kita, banjur kita ' bakal nganalisa kerumitan. Miturut cara, saiki sampeyan ngerti kenapa iki diarani telusuran binar: gumantung ing bola-bali mbagi data ing setengah. Asil nyengsemaken! Yen kita nggunakake telusuran linear kanggo nggoleki nomer kasebut, kita butuh nganti 10 mbandhingake, nanging kanthi telusuran binar, kita bisa ngrampungake tugas kasebut kanthi mung 3! Ing kasus paling awon, bakal ana 4 bandingaken (yen ing langkah pungkasan nomer kita wanted minangka kaloro saka kemungkinan isih, tinimbang pisanan. Dadi apa bab kerumitan sawijining? Iki titik menarik banget :) Algoritma telusuran binar kurang gumantung marang jumlah unsur ing array tinimbang algoritma telusuran linier (yaiku, iterasi prasaja). Kanthi 10 unsur ing larik, telusuran linear mbutuhake maksimal 10 mbandhingake, nanging telusuran binar mbutuhake maksimal 4 mbandhingake. Sing beda karo faktor 2,5. Nanging kanggo macem-macem 1000 unsur , telusuran linear mbutuhake nganti 1000 mbandhingake, nanging telusuran binar mung mbutuhake 10 ! Bentenipun saiki 100 tikel! Cathetan:nomer unsur ing Uploaded wis tambah 100 kaping (saka 10 kanggo 1000), nanging nomer bandingaken dibutuhake kanggo search binar wis tambah dening faktor mung 2,5 (saka 4 kanggo 10). Yen kita entuk 10.000 unsur , prabédan bakal luwih nyengsemake: 10.000 mbandhingake kanggo telusuran linear, lan total 14 mbandhingake kanggo panelusuran binar. Lan maneh, yen jumlah unsur mundhak 1000 kaping (saka 10 kanggo 10000), banjur nomer mbandhingaké mundhak dening faktor mung 3,5 (saka 4 kanggo 14). Kompleksitas algoritma telusuran binar yaiku logaritmik , utawa, yen kita nggunakake notasi O gedhe, O(log n). Kok diarani ngono? Logaritma minangka kebalikan saka eksponensial. Logaritma biner yaiku kekuwatan sing nomer 2 kudu diunggahake kanggo entuk nomer. Contone, kita duwe 10.000 unsur sing kudu digoleki nggunakake algoritma telusuran binar. 
Saiki, sampeyan bisa ndeleng tabel nilai kanggo ngerti yen nindakake iki mbutuhake maksimal 14 mbandhingake. Nanging kepiye yen ora ana sing nyedhiyakake tabel kasebut lan sampeyan kudu ngetung jumlah perbandingan maksimal sing tepat? Sampeyan mung kudu njawab pitakonan sing prasaja: apa daya sampeyan kudu ngunggahake nomer 2 supaya asil luwih gedhe tinimbang utawa padha karo jumlah unsur sing kudu dicenthang? Kanggo 10.000, iku daya kaping 14. 2 kanggo daya kaping 13 cilik banget (8192), nanging 2 kanggo daya kaping 14 = 16384, lan nomer iki nyukupi kondisi kita (luwih gedhe tinimbang utawa padha karo jumlah unsur ing array). Kita nemokake logaritma: 14. Semono uga akeh perbandingan sing dibutuhake! :) Algoritma lan kerumitan algoritmik minangka topik sing amba banget kanggo pas karo siji pelajaran. Nanging ngerti iku penting banget: akeh wawancara proyek bakal ndherek pitakonan nglibatno algoritma. Kanggo teori, aku bisa menehi rekomendasi sawetara buku kanggo sampeyan. Sampeyan bisa miwiti karo " Algoritma Grokking ". Conto ing buku iki ditulis nganggo Python, nanging buku kasebut nggunakake basa lan conto sing gampang banget. Iku pilihan sing paling apik kanggo pamula lan, apa maneh, iku ora amba banget. Antarane maca sing luwih serius, kita duwe buku dening Robert Lafore lan Robert Sedgewick. Loro-lorone ditulis ing basa Jawa, sing bakal nggawe sinau luwih gampang kanggo sampeyan. Sawise kabeh, sampeyan wis ngerti basa iki! :) Kanggo siswa sing duwe katrampilan matematika sing apik, pilihan sing paling apik yaiku buku Thomas Cormen . Nanging teori mung ora bakal ngisi weteng! Kawruh != Kemampuan . Sampeyan bisa latihan ngrampungake masalah sing nglibatake algoritma ing HackerRank lan LeetCode . Tugas saka situs web iki asring digunakake sanajan nalika wawancara ing Google lan Facebook, mula sampeyan mesthi ora bosen :) Kanggo nguatake materi pelajaran iki, aku nyaranake sampeyan nonton video sing apik babagan notasi O gedhe ing YouTube. Ditemokake ing wulangan sabanjure! :)
