MERHABA! Bugünün dersi diğerlerinden biraz farklı olacak. Java ile yalnızca dolaylı olarak ilişkili olması bakımından farklılık gösterecektir. Bununla birlikte, bu konu her programcı için çok önemlidir. Algoritmalar hakkında konuşacağız . Algoritma nedir? Basit bir ifadeyle, istenen bir sonuca ulaşmak için tamamlanması gereken bir dizi eylemdir . Algoritmaları günlük hayatta sıklıkla kullanırız. Örneğin, her sabah belirli bir göreviniz var: okula veya işe gidin ve aynı zamanda:
giyinik
Temiz
Besledi
Hangi algoritma bu sonuca ulaşmanızı sağlar?
Çalar saat kullanarak uyanın.
Duş al ve kendini yıka.
Kahvaltı ve biraz kahve veya çay yapın.
Yemek yemek.
Giysilerinizi bir önceki akşam ütülemediyseniz, ütüleyin.
Giyinmek.
Evi terk et.
Bu eylem dizisi kesinlikle istenen sonucu almanıza izin verecektir. Programlamada, görevleri tamamlamak için sürekli çalışıyoruz. Bu görevlerin önemli bir kısmı zaten bilinen algoritmalar kullanılarak gerçekleştirilebilir. Örneğin, görevinizin şu olduğunu varsayalım: bir dizideki 100 isimden oluşan bir liste sıralamak . Bu görev oldukça basittir, ancak farklı şekillerde çözülebilir. İşte olası bir çözüm: Adları alfabetik olarak sıralamak için algoritma:
Webster's Third New International Dictionary'nin 1961 baskısını satın alın veya indirin.
Listemizdeki her adı bu sözlükte bulun.
Bir kağıda, adın bulunduğu sözlüğün sayfasını yazın.
Adları sıralamak için kağıt parçalarını kullanın.
Böyle bir eylemler dizisi görevimizi yerine getirecek mi? Evet, kesinlikle olacak. Bu çözüm verimli mi ? Zorlu. Algoritmaların çok önemli başka bir yönüne geldik: verimlilikleri . Bu görevi gerçekleştirmenin birkaç yolu vardır. Ama hem programlamada hem de günlük hayatta en verimli yolu seçmek isteriz. Göreviniz tereyağlı bir tost yapmaksa, buğday ekerek ve bir inek sağarak başlayabilirsiniz. Ama bu verimsiz olurduçözüm — çok zaman alacak ve çok paraya mal olacak. Basit görevinizi sadece ekmek ve tereyağı alarak başarabilirsiniz. Sorunu çözmenize izin verse de, buğday ve bir ineği içeren algoritma pratikte kullanılamayacak kadar karmaşıktır. Programlamada, algoritmaların karmaşıklığını değerlendirmek için büyük O notasyonu adı verilen özel bir notasyona sahibiz. Big O, bir algoritmanın yürütme süresinin girdi veri boyutuna ne kadar bağlı olduğunu değerlendirmeyi mümkün kılar . En basit örneğe bakalım: veri aktarımı. Bazı bilgileri dosya biçiminde uzun bir mesafeye (örneğin 5000 mil) göndermeniz gerektiğini düşünün. Hangi algoritma en verimli olur? Çalıştığınız verilere bağlıdır. Örneğin, 10 MB'lık bir ses dosyamız olduğunu varsayalım. Bu durumda, en verimli algoritma dosyayı İnternet üzerinden göndermektir. Birkaç dakikadan fazla sürmedi! Algoritmamızı yeniden ifade edelim: "Bilgileri 5000 mil mesafeye dosya biçiminde aktarmak istiyorsanız, verileri İnternet üzerinden göndermelisiniz". Harika. Şimdi onu analiz edelim. Görevimizi yerine getiriyor mu?Evet, öyle. Ancak karmaşıklığı hakkında ne söyleyebiliriz? Hmm, şimdi işler daha da ilginçleşiyor. Gerçek şu ki, algoritmamız girdi verilerine, yani dosyaların boyutuna çok bağlıdır. 10 megabaytımız varsa, her şey yolunda demektir. Peki ya 500 megabayt göndermemiz gerekirse? 20 gigabayt mı? 500 terabayt mı? 30 petabayt mı? Algoritmamız çalışmayı durduracak mı? Hayır, tüm bu miktarda veri gerçekten aktarılabilir. Daha uzun sürer mi? Evet, olacak! Artık algoritmamızın önemli bir özelliğini biliyoruz: gönderilecek veri miktarı ne kadar büyükse, algoritmayı çalıştırmak o kadar uzun sürer. Ancak bu ilişkiyi (girdi veri boyutu ile onu göndermek için gereken süre arasındaki) daha kesin bir şekilde anlamak istiyoruz. Bizim durumumuzda, algoritmik karmaşıklık doğrusaldır . "Doğrusal", girdi verisi miktarı arttıkça, onu göndermek için gereken sürenin yaklaşık olarak orantılı olarak artacağı anlamına gelir. Veri miktarı iki katına çıkarsa, göndermek için gereken süre iki katına çıkacaktır. Veri 10 kat artarsa, iletim süresi 10 kat artacaktır. Büyük O notasyonu kullanılarak, algoritmamızın karmaşıklığı O(n) olarak ifade edilir.. Bu gösterimi gelecekte hatırlamanız gerekir - her zaman doğrusal karmaşıklığa sahip algoritmalar için kullanılır. Burada değişebilecek birkaç şeyden bahsetmediğimize dikkat edin: İnternet hızı, bilgisayarımızın hesaplama gücü vb. Bir algoritmanın karmaşıklığını değerlendirirken, bu faktörleri dikkate almak mantıklı değildir - her halükarda bunlar bizim kontrolümüz dışındadır. Büyük O gösterimi, içinde çalıştığı "ortamı" değil, algoritmanın kendisinin karmaşıklığını ifade eder. Örneğimizle devam edelim. En sonunda toplam 800 terabaytlık dosyalar göndermemiz gerektiğini öğrendiğimizi varsayalım. Elbette bunları internet üzerinden göndererek görevimizi yerine getirebiliriz. Tek bir sorun var: standart ev veri iletim hızlarında (saniyede 100 megabit), yaklaşık 708 gün sürecek. Neredeyse 2 yıl! :O Algoritmamız açıkçası buraya pek uygun değil. Başka bir çözüme ihtiyacımız var! Beklenmedik bir şekilde imdadımıza bilişim devi Amazon yetişiyor! Amazon'un Snowmobile hizmeti, büyük miktarda veriyi mobil depolamaya yüklememizi ve ardından kamyonla istenen adrese teslim etmemizi sağlıyor! Demek yeni bir algoritmamız var! "Bilgileri 5000 millik bir mesafeye dosya biçiminde aktarmak istiyorsanız ve bunu yapmak İnternet üzerinden 14 günden fazla sürecekse, verileri bir Amazon kamyonuyla göndermelisiniz." Burada keyfi olarak 14 gün seçtik. Diyelim ki bekleyebileceğimiz en uzun süre bu. Algoritmamızı analiz edelim. Peki ya hızı? Kamyon saatte sadece 50 mil hızla gitse bile, 5000 mili sadece 100 saatte katedecektir. Bu dört günden biraz fazla! Bu, verileri İnternet üzerinden gönderme seçeneğinden çok daha iyidir. Peki ya bu algoritmanın karmaşıklığı? Aynı zamanda doğrusal mı, yani O(n)? Hayır öyle değil. Ne de olsa kamyon, onu ne kadar yüklediğinizi umursamaz — yine de aynı hızda gidecek ve zamanında varacaktır. İster 800 terabaytımız olsun ister bunun 10 katı olsun, kamyon yine de hedefine 5 gün içinde ulaşacaktır. Başka bir deyişle, kamyon tabanlı veri aktarım algoritması sürekli karmaşıklığa sahiptir.. Burada "sabit", girdi veri boyutuna bağlı olmadığı anlamına gelir. Kamyona 1GB flash sürücü koyun, 5 gün içinde gelir. 800 terabayt veri içeren disklere koyun, 5 gün içinde gelir. Büyük O gösterimi kullanılırken, sabit karmaşıklık O(1) ile gösterilir . O(n) ve O(1) 'e aşina olduk , şimdi programlama dünyasından daha fazla örneğe bakalım :) Diyelim ki size 100 sayılık bir dizi verildi ve görev her birini ekranda göstermek. konsol. forBu görevi yerine getiren sıradan bir döngü yazarsınız.
int[] numbers =newint[100];// ...fill the array with numbersfor(int i: numbers){System.out.println(i);}
Bu algoritmanın karmaşıklığı nedir? Doğrusal, yani O(n). Programın gerçekleştirmesi gereken eylem sayısı, kendisine kaç sayı iletildiğine bağlıdır. Dizide 100 sayı varsa, 100 eylem olacaktır (ekranda dizeleri görüntülemek için ifadeler). Dizide 10.000 sayı varsa, 10.000 eylem gerçekleştirilmelidir. Algoritmamız herhangi bir şekilde geliştirilebilir mi? Hayır. Ne olursa olsun, diziden N tane geçiş yapmamız ve dizileri konsolda görüntülemek için N ifadeleri çalıştırmamız gerekecek . Başka bir örnek düşünün.
LinkedListİçine birkaç sayı eklediğimiz bir boşluğumuz var . LinkedListÖrneğimize tek bir sayı eklemenin algoritmik karmaşıklığını ve bunun listedeki öğe sayısına nasıl bağlı olduğunu değerlendirmemiz gerekiyor . Cevap O(1), yani sabit karmaşıklıktır . Neden? Her sayıyı listenin başına eklediğimize dikkat edin. LinkedListEk olarak, a'ya bir sayı eklediğinizde öğelerin hiçbir yere taşınmadığını hatırlayacaksınız . Bağlantılar (veya referanslar) güncellenir (LinkedList'in nasıl çalıştığını unuttuysanız, eski derslerimizden birine bakın ). Listemizdeki ilk sayı ise xve y sayısını listenin başına yerleştirirsek, o zaman tek yapmamız gereken şudur:
x.previous = y;
y.previous =null;
y.next = x;
Bağlantıları güncellediğimizde, ister bir ister bir milyar olsun, içinde zaten kaç sayı olduğu umurumuzda değilLinkedList . Algoritmanın karmaşıklığı sabittir, yani O(1).
logaritmik karmaşıklık
Panik yapma! :) "Logaritmik" kelimesi bu dersi bitirmek ve okumayı bırakmak istemenize neden oluyorsa, birkaç dakika bekleyin. Burada herhangi bir çılgın matematik olmayacak (başka yerlerde bunun gibi pek çok açıklama var) ve her örneği ayrı ayrı seçeceğiz. Görevinizin 100 sayılık bir dizide belirli bir sayıyı bulmak olduğunu hayal edin. Daha doğrusu, orada olup olmadığını kontrol etmeniz gerekiyor. İstenen sayı bulunur bulunmaz arama sona erer ve konsolda şunu görüntülersiniz: "Gereken sayı bulundu! Dizindeki dizini = ...." Bu görevi nasıl gerçekleştirirsiniz? Burada çözüm açıktır: dizinin öğelerini ilkinden (veya sondan) başlayarak birer birer yinelemeniz ve mevcut sayının aradığınız sayıyla eşleşip eşleşmediğini kontrol etmeniz gerekir. Buna göre, eylemlerin sayısı doğrudan dizideki öğelerin sayısına bağlıdır. 100 numaramız varsa, potansiyel olarak 100 kez bir sonraki öğeye gitmemiz ve 100 karşılaştırma yapmamız gerekebilir. 1000 sayı varsa, 1000 karşılaştırma olabilir. Bu açıkça doğrusal karmaşıklıktır, yaniO(n) . Ve şimdi örneğimize bir iyileştirme ekleyeceğiz: sayıyı bulmanız gereken dizi artan düzende sıralanmıştır . Bu, görevimizle ilgili herhangi bir şeyi değiştirir mi? İstenen sayı için yine de kaba kuvvet araması yapabiliriz. Ancak alternatif olarak, iyi bilinen ikili arama algoritmasını kullanabiliriz . Görüntünün üst satırında sıralanmış bir dizi görüyoruz. İçindeki 23 sayısını bulmamız gerekiyor. Sayılar üzerinde yineleme yapmak yerine, diziyi 2 parçaya böleriz ve dizideki ortadaki sayıyı kontrol ederiz. 4. hücrede bulunan sayıyı bulun ve kontrol edin (resmin ikinci satırı). Bu sayı 16 ve biz 23'ü arıyoruz. Mevcut sayı bizim aradığımızdan daha az. Bu ne anlama gelir? Bu demektirönceki tüm sayıların (16 sayısından önce bulunanlar) kontrol edilmesine gerek yoktur : dizimiz sıralandığından, aradığımızdan daha az olmaları garanti edilir! Kalan 5 element arasından aramaya devam ediyoruz. Not:sadece bir karşılaştırma yaptık, ancak olası seçeneklerin yarısını zaten eledik. Sadece 5 elementimiz kaldı. Kalan alt diziyi tekrar ikiye bölerek ve yine ortadaki elemanı (resimdeki 3. sıra) alarak bir önceki adımımızı tekrarlayacağız. Sayı 56 ve aradığımızdan daha büyük. Bu ne anlama gelir? Bu, 3 olasılığı daha elediğimiz anlamına gelir: 56 sayısının kendisi ve ondan sonraki iki sayı (çünkü dizi sıralandığı için 23'ten büyük olmaları garanti edilir). Kontrol edilecek sadece 2 numaramız kaldı (resimdeki son satır) — dizi indeksleri 5 ve 6 olan sayılar. İlkini kontrol edip aradığımızı buluyoruz — 23 sayısı! Endeksi 5! Algoritmamızın sonuçlarına bakalım ve sonra karmaşıklığını analiz edeceğiz. Bu arada, buna neden ikili arama dendiğini şimdi anladınız: verileri tekrar tekrar ikiye bölmeye dayanır. Sonuç etkileyici! Sayıyı aramak için doğrusal bir arama kullansaydık, 10 adede kadar karşılaştırmaya ihtiyacımız olurdu, ancak ikili arama ile görevi yalnızca 3 ile başardık! En kötü ihtimalle 4 karşılaştırma olurdu (son adımda istediğimiz sayı kalan olasılıklardan birincisi değil de ikincisi olsaydı. Peki ya karmaşıklığı? Bu çok ilginç bir nokta :) İkili arama algoritması, dizideki öğelerin sayısına doğrusal arama algoritmasına (yani basit yineleme) göre çok daha az bağımlıdır. Dizideki 10 öğeyle , doğrusal arama maksimum 10 karşılaştırmaya ihtiyaç duyacaktır, ancak ikili arama maksimum 4 karşılaştırmaya ihtiyaç duyacaktır. Bu 2,5 kat fark demek. Ancak 1000 öğelik bir dizi için , doğrusal bir arama 1000'e kadar karşılaştırma gerektirecektir, ancak ikili arama yalnızca 10 gerektirecektir ! Fark şimdi 100 kat! Not:dizideki öğelerin sayısı 100 kat arttı (10'dan 1000'e), ancak ikili arama için gereken karşılaştırma sayısı yalnızca 2,5 kat arttı (4'ten 10'a). 10.000 öğeye ulaşırsak , fark daha da etkileyici olacaktır: doğrusal arama için 10.000 karşılaştırma ve ikili arama için toplam 14 karşılaştırma . Ve yine, öğe sayısı 1000 kat artarsa (10'dan 10000'e), karşılaştırma sayısı yalnızca 3,5 kat artar (4'ten 14'e). İkili arama algoritmasının karmaşıklığı logaritmiktir veya büyük O gösterimi kullanırsak, O(log n). Neden buna denir? Logaritma, üstel almanın tersi gibidir. İkili logaritma, bir sayı elde etmek için 2 sayısının yükseltilmesi gereken kuvvettir. Örneğin, ikili arama algoritmasını kullanarak aramamız gereken 10.000 öğemiz var. Şu anda, bunu yapmanın en fazla 14 karşılaştırma gerektireceğini bilmek için değerler tablosuna bakabilirsiniz. Peki ya hiç kimse böyle bir tablo sağlamadıysa ve tam olarak maksimum karşılaştırma sayısını hesaplamanız gerekiyorsa? Basit bir soruyu yanıtlamanız yeterlidir: sonucun kontrol edilecek öğe sayısından büyük veya ona eşit olması için 2 sayısını hangi güce yükseltmeniz gerekir? 10.000 için, 14. kuvvettir. 2'nin 13'üncü kuvveti çok küçük (8192), ancak 2'nin 14'üncü kuvveti = 16384, ve bu sayı koşulumuzu karşılar (dizideki öğe sayısından büyük veya ona eşittir). Logaritmayı bulduk: 14. İşte bu kadar karşılaştırmaya ihtiyacımız olabilir! :) Algoritmalar ve algoritmik karmaşıklık, bir derse sığmayacak kadar geniş bir konu. Ancak bunu bilmek çok önemlidir: birçok iş görüşmesi, algoritmaları içeren sorular içerecektir. Teorik olarak size birkaç kitap önerebilirim. " Grokking Algoritmaları " ile başlayabilirsiniz . Bu kitaptaki örnekler Python ile yazılmış ancak kitap çok basit bir dil ve örnekler kullanıyor. Yeni başlayanlar için en iyi seçenek ve dahası, çok büyük değil. Daha ciddi okumalar arasında Robert Lafore ve Robert Sedgewick'in kitapları var.. Her ikisi de Java'da yazılmıştır, bu da öğrenmeyi sizin için biraz daha kolaylaştıracaktır. Sonuçta, bu dile oldukça aşinasınız! :) İyi matematik becerisine sahip öğrenciler için en iyi seçenek Thomas Cormen'in kitabıdır . Ama teori tek başına karnını doyurmaz! Bilgi != Yetenek . HackerRank ve LeetCode'da algoritma içeren problem çözme alıştırmaları yapabilirsiniz . Bu web sitelerindeki görevler genellikle Google ve Facebook'taki röportajlarda bile kullanılıyor, bu yüzden kesinlikle sıkılmayacaksınız :) Bu ders materyalini pekiştirmek için YouTube'da büyük O notasyonu ile ilgili bu mükemmel videoyu izlemenizi tavsiye ederim. Sonraki derslerde görüşmek üzere! :)
Bununla birlikte, bu konu her programcı için çok önemlidir. Algoritmalar hakkında konuşacağız . Algoritma nedir? Basit bir ifadeyle, istenen bir sonuca ulaşmak için tamamlanması gereken bir dizi eylemdir . Algoritmaları günlük hayatta sıklıkla kullanırız. Örneğin, her sabah belirli bir göreviniz var: okula veya işe gidin ve aynı zamanda:
Bu durumda, en verimli algoritma dosyayı İnternet üzerinden göndermektir. Birkaç dakikadan fazla sürmedi! Algoritmamızı yeniden ifade edelim: "Bilgileri 5000 mil mesafeye dosya biçiminde aktarmak istiyorsanız, verileri İnternet üzerinden göndermelisiniz". Harika. Şimdi onu analiz edelim. Görevimizi yerine getiriyor mu?Evet, öyle. Ancak karmaşıklığı hakkında ne söyleyebiliriz? Hmm, şimdi işler daha da ilginçleşiyor. Gerçek şu ki, algoritmamız girdi verilerine, yani dosyaların boyutuna çok bağlıdır. 10 megabaytımız varsa, her şey yolunda demektir. Peki ya 500 megabayt göndermemiz gerekirse? 20 gigabayt mı? 500 terabayt mı? 30 petabayt mı? Algoritmamız çalışmayı durduracak mı? Hayır, tüm bu miktarda veri gerçekten aktarılabilir. Daha uzun sürer mi? Evet, olacak! Artık algoritmamızın önemli bir özelliğini biliyoruz: gönderilecek veri miktarı ne kadar büyükse, algoritmayı çalıştırmak o kadar uzun sürer. Ancak bu ilişkiyi (girdi veri boyutu ile onu göndermek için gereken süre arasındaki) daha kesin bir şekilde anlamak istiyoruz. Bizim durumumuzda, algoritmik karmaşıklık doğrusaldır . "Doğrusal", girdi verisi miktarı arttıkça, onu göndermek için gereken sürenin yaklaşık olarak orantılı olarak artacağı anlamına gelir. Veri miktarı iki katına çıkarsa, göndermek için gereken süre iki katına çıkacaktır. Veri 10 kat artarsa, iletim süresi 10 kat artacaktır. Büyük O notasyonu kullanılarak, algoritmamızın karmaşıklığı O(n) olarak ifade edilir.. Bu gösterimi gelecekte hatırlamanız gerekir - her zaman doğrusal karmaşıklığa sahip algoritmalar için kullanılır. Burada değişebilecek birkaç şeyden bahsetmediğimize dikkat edin: İnternet hızı, bilgisayarımızın hesaplama gücü vb. Bir algoritmanın karmaşıklığını değerlendirirken, bu faktörleri dikkate almak mantıklı değildir - her halükarda bunlar bizim kontrolümüz dışındadır. Büyük O gösterimi, içinde çalıştığı "ortamı" değil, algoritmanın kendisinin karmaşıklığını ifade eder. Örneğimizle devam edelim. En sonunda toplam 800 terabaytlık dosyalar göndermemiz gerektiğini öğrendiğimizi varsayalım. Elbette bunları internet üzerinden göndererek görevimizi yerine getirebiliriz. Tek bir sorun var: standart ev veri iletim hızlarında (saniyede 100 megabit), yaklaşık 708 gün sürecek. Neredeyse 2 yıl! :O Algoritmamız açıkçası buraya pek uygun değil. Başka bir çözüme ihtiyacımız var! Beklenmedik bir şekilde imdadımıza bilişim devi Amazon yetişiyor! Amazon'un Snowmobile hizmeti, büyük miktarda veriyi mobil depolamaya yüklememizi ve ardından kamyonla istenen adrese teslim etmemizi sağlıyor! 
Demek yeni bir algoritmamız var! "Bilgileri 5000 millik bir mesafeye dosya biçiminde aktarmak istiyorsanız ve bunu yapmak İnternet üzerinden 14 günden fazla sürecekse, verileri bir Amazon kamyonuyla göndermelisiniz." Burada keyfi olarak 14 gün seçtik. Diyelim ki bekleyebileceğimiz en uzun süre bu. Algoritmamızı analiz edelim. Peki ya hızı? Kamyon saatte sadece 50 mil hızla gitse bile, 5000 mili sadece 100 saatte katedecektir. Bu dört günden biraz fazla! Bu, verileri İnternet üzerinden gönderme seçeneğinden çok daha iyidir. Peki ya bu algoritmanın karmaşıklığı? Aynı zamanda doğrusal mı, yani O(n)? Hayır öyle değil. Ne de olsa kamyon, onu ne kadar yüklediğinizi umursamaz — yine de aynı hızda gidecek ve zamanında varacaktır. İster 800 terabaytımız olsun ister bunun 10 katı olsun, kamyon yine de hedefine 5 gün içinde ulaşacaktır. Başka bir deyişle, kamyon tabanlı veri aktarım algoritması sürekli karmaşıklığa sahiptir.. Burada "sabit", girdi veri boyutuna bağlı olmadığı anlamına gelir. Kamyona 1GB flash sürücü koyun, 5 gün içinde gelir. 800 terabayt veri içeren disklere koyun, 5 gün içinde gelir. Büyük O gösterimi kullanılırken, sabit karmaşıklık O(1) ile gösterilir . O(n) ve O(1) 'e aşina olduk , şimdi programlama dünyasından daha fazla örneğe bakalım :) Diyelim ki size 100 sayılık bir dizi verildi ve görev her birini ekranda göstermek. konsol. 
Görüntünün üst satırında sıralanmış bir dizi görüyoruz. İçindeki 23 sayısını bulmamız gerekiyor. Sayılar üzerinde yineleme yapmak yerine, diziyi 2 parçaya böleriz ve dizideki ortadaki sayıyı kontrol ederiz. 4. hücrede bulunan sayıyı bulun ve kontrol edin (resmin ikinci satırı). Bu sayı 16 ve biz 23'ü arıyoruz. Mevcut sayı bizim aradığımızdan daha az. Bu ne anlama gelir? Bu demektirönceki tüm sayıların (16 sayısından önce bulunanlar) kontrol edilmesine gerek yoktur : dizimiz sıralandığından, aradığımızdan daha az olmaları garanti edilir! Kalan 5 element arasından aramaya devam ediyoruz. Not:sadece bir karşılaştırma yaptık, ancak olası seçeneklerin yarısını zaten eledik. Sadece 5 elementimiz kaldı. Kalan alt diziyi tekrar ikiye bölerek ve yine ortadaki elemanı (resimdeki 3. sıra) alarak bir önceki adımımızı tekrarlayacağız. Sayı 56 ve aradığımızdan daha büyük. Bu ne anlama gelir? Bu, 3 olasılığı daha elediğimiz anlamına gelir: 56 sayısının kendisi ve ondan sonraki iki sayı (çünkü dizi sıralandığı için 23'ten büyük olmaları garanti edilir). Kontrol edilecek sadece 2 numaramız kaldı (resimdeki son satır) — dizi indeksleri 5 ve 6 olan sayılar. İlkini kontrol edip aradığımızı buluyoruz — 23 sayısı! Endeksi 5! Algoritmamızın sonuçlarına bakalım ve sonra karmaşıklığını analiz edeceğiz. Bu arada, buna neden ikili arama dendiğini şimdi anladınız: verileri tekrar tekrar ikiye bölmeye dayanır. Sonuç etkileyici! Sayıyı aramak için doğrusal bir arama kullansaydık, 10 adede kadar karşılaştırmaya ihtiyacımız olurdu, ancak ikili arama ile görevi yalnızca 3 ile başardık! En kötü ihtimalle 4 karşılaştırma olurdu (son adımda istediğimiz sayı kalan olasılıklardan birincisi değil de ikincisi olsaydı. Peki ya karmaşıklığı? Bu çok ilginç bir nokta :) İkili arama algoritması, dizideki öğelerin sayısına doğrusal arama algoritmasına (yani basit yineleme) göre çok daha az bağımlıdır. Dizideki 10 öğeyle , doğrusal arama maksimum 10 karşılaştırmaya ihtiyaç duyacaktır, ancak ikili arama maksimum 4 karşılaştırmaya ihtiyaç duyacaktır. Bu 2,5 kat fark demek. Ancak 1000 öğelik bir dizi için , doğrusal bir arama 1000'e kadar karşılaştırma gerektirecektir, ancak ikili arama yalnızca 10 gerektirecektir ! Fark şimdi 100 kat! Not:dizideki öğelerin sayısı 100 kat arttı (10'dan 1000'e), ancak ikili arama için gereken karşılaştırma sayısı yalnızca 2,5 kat arttı (4'ten 10'a). 10.000 öğeye ulaşırsak , fark daha da etkileyici olacaktır: doğrusal arama için 10.000 karşılaştırma ve ikili arama için toplam 14 karşılaştırma . Ve yine, öğe sayısı 1000 kat artarsa (10'dan 10000'e), karşılaştırma sayısı yalnızca 3,5 kat artar (4'ten 14'e). İkili arama algoritmasının karmaşıklığı logaritmiktir veya büyük O gösterimi kullanırsak, O(log n). Neden buna denir? Logaritma, üstel almanın tersi gibidir. İkili logaritma, bir sayı elde etmek için 2 sayısının yükseltilmesi gereken kuvvettir. Örneğin, ikili arama algoritmasını kullanarak aramamız gereken 10.000 öğemiz var. 
Şu anda, bunu yapmanın en fazla 14 karşılaştırma gerektireceğini bilmek için değerler tablosuna bakabilirsiniz. Peki ya hiç kimse böyle bir tablo sağlamadıysa ve tam olarak maksimum karşılaştırma sayısını hesaplamanız gerekiyorsa? Basit bir soruyu yanıtlamanız yeterlidir: sonucun kontrol edilecek öğe sayısından büyük veya ona eşit olması için 2 sayısını hangi güce yükseltmeniz gerekir? 10.000 için, 14. kuvvettir. 2'nin 13'üncü kuvveti çok küçük (8192), ancak 2'nin 14'üncü kuvveti = 16384, ve bu sayı koşulumuzu karşılar (dizideki öğe sayısından büyük veya ona eşittir). Logaritmayı bulduk: 14. İşte bu kadar karşılaştırmaya ihtiyacımız olabilir! :) Algoritmalar ve algoritmik karmaşıklık, bir derse sığmayacak kadar geniş bir konu. Ancak bunu bilmek çok önemlidir: birçok iş görüşmesi, algoritmaları içeren sorular içerecektir. Teorik olarak size birkaç kitap önerebilirim. " Grokking Algoritmaları " ile başlayabilirsiniz . Bu kitaptaki örnekler Python ile yazılmış ancak kitap çok basit bir dil ve örnekler kullanıyor. Yeni başlayanlar için en iyi seçenek ve dahası, çok büyük değil. Daha ciddi okumalar arasında Robert Lafore ve Robert Sedgewick'in kitapları var.. Her ikisi de Java'da yazılmıştır, bu da öğrenmeyi sizin için biraz daha kolaylaştıracaktır. Sonuçta, bu dile oldukça aşinasınız! :) İyi matematik becerisine sahip öğrenciler için en iyi seçenek Thomas Cormen'in kitabıdır . Ama teori tek başına karnını doyurmaz! Bilgi != Yetenek . HackerRank ve LeetCode'da algoritma içeren problem çözme alıştırmaları yapabilirsiniz . Bu web sitelerindeki görevler genellikle Google ve Facebook'taki röportajlarda bile kullanılıyor, bu yüzden kesinlikle sıkılmayacaksınız :) Bu ders materyalini pekiştirmek için YouTube'da büyük O notasyonu ile ilgili bu mükemmel videoyu izlemenizi tavsiye ederim. Sonraki derslerde görüşmek üzere! :)
