MIT Açık Ders malzemeleri

http://ocw.mit.edu

6.046J Algoritmalara Giriş, Güz 2005

Bu materyallerden alıntı yapmak veya kullanım şartları hakkında bilgi almak için:

Erik Demaine ve Charles Leiserson, 6.046J IntroductiontoAlgorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare). http://ocw.mit.edu (Giriş Tarihi: 08, 01, 2010). Lisans: Creative CommonsAttribution-Noncommercial-ShareAlike.

Not: Lütfen atıf taparken bilgilere eriştiğiniz gerçek tarihi kullanınız.

Atıflar ve Kullanım Koşulları konusunda daha fazla bilgi için:

http://ocw.mit.edu/terms ve http://www.acikders.org.tr sitesini ziyaret ediniz.

AÇIK DERS MALZEMELERİ ( 6.046J)

ALGORİTMALARA GİRİŞ

Ders 1

Başlıyoruz. Ders notlarını hala almadıysanız kapının önünde duruyor. Benim adım Charles LEISERSON. Ben bu yarıyıl Algoritmalara Giriş dersini, Erik DEMAINE ile birlikte vereceğim. Ayrıca bu bir SMA kursu yani Singapur MIT Birliği kursu ve Singapur’da da David ŞU tarafından verilecek. Bu nedenle bütün dersler video teybe çekilecek ve WEB üzerinden Singapurlu öğrencilere ve MIT öğrencilerine aynı zamanda iletilecek.

Biraz da içerik konuşalım. Algoritmaların Çözümlemesi..

Dersin ilk yarısı analiz yani çözümleme üzerine odaklanıyor. İkinci yarısında da dizayn yani tasarım konusuna odaklanacağız. Tasarım yapmadan önce algoritma çözümlemesindeki bazı tekniklerde uzmanlaşmanız gerekiyor. Ancak bu düzeyden sonra verimliliğini irdeleyebileceğiniz algoritma tasarımları yapabilirsiniz. Algoritma çözümlemesi, bilgisayar program performansı yani başarımı ve kaynak kullanımı üzerine teorik bir çalışmadır. Özellikle başarım konusuna odaklanılır. Biz işleri nasıl daha hızlı yapabileceğimizi öğreneceğiz. Özellikle de bilgisayar programlarında.. Bunu yaparken iletişim, ana bellek, disk belleği gibi başka kaynaklarla da ilgili konuşacağız. Bunların dışında başka kaynaklar da olacak ama bu derste ana odağımız başarım olacak. Çünkü bu ders başarım ile ilgili bir ders. Perspektifinizi biraz geliştirmek için size bir soru sormak istiyorum. Programcılıkta başarımdan daha önemli neler vardır? --

Eğer bir mühendislik uygulamasına kod yazıyorsanız, bir yazılım üretiyorsanız, başarımdan daha önemli ne vardır.-- Doğruluk. Doğruluk güzel, başka. --Basitlik olabilir. Çok güzel. – Bakım kolaylığı. Bakım kolaylığı başarımdan bir çok konuda daha önemlidir. ----Fiyat. Hangi tip fiyattan bahsediyoruz. --Yani neyin fiyatı? --Burada yazılımdan bahsediyoruz unutmayın. -- Hangi konuda fiyat demek istediniz? --Programlama yaparken programcı zamanı diye bir gider vardır. Doğru. O halde programcı zamanı da başarımdan daha önemli olabilir. -- Sağlamlık. Doğru. Yazılımın sağlamlığı. Sürekli bozuluyor mu. --- Başka, haydi haydi burada birkaç tane mühendis var, daha bir sürü şey var. --Özelliklerden ne haber. Özellikler önemli olabilir. Rakiplerinizden daha fazla özelliği olan bir yazılım yapmak önemli olabilir. --İşlevsellik. Modüllere bölünebilme özelliği. Yani işlevselliği artırmak için programın küçük bölümünde bir kod değişikliği yaptığınız zaman bütün programı değiştirmek zorunda olmamak. -- Bir tane daha var özellikle 90 lı yıllarda bilgisayar alanında çok büyük bir kavramdı. En büyük kavram.. A, evet güvenlik, doğru. --Ben bunu listeme eklememişim. Güvenlik, mükemmel. Ama bu daha çok 2000 li yılların sorunları arasında sayılabilir. Ve başarımdan çok daha önemli bir kavram. Ölçeklenebilirlik. Önemlidir ama ölçeklenebilirlik bir bakıma başarım ile ilgili zaten. Ama doğru, listeye yazalım. Ölçeklenebilirlik güzel. --Ama hatırlayın hangi devrim Macintosh kullanıcılarını Windows kullanıcılarının önüne geçirmişti. Kullanıcı kolaylığı. Kullanıcı dostluğu. Evet bu kavram 90 lı yıllarda hemen hemen sıfırdan başlayıp büyüyerek bugünkü hale geldi ki, bugün bilgisayar alanında yazılımın kullanıcı dostu olması en önemli faktörlerden biri. Yani bütün bu faktörler başarımdan daha önemli. Bu ders başarım üzerine diyoruz. Siz de şunu sorabilirsiniz; başarımdan daha önemli bu kadar çok şey varken biz neden algoritmaları ve başarımı ele alıyoruz ve öğreniyoruz? Hemen hemen bütün kullanıcılar başarımdan çok yukarıda sayılan konulara önem veriyorlar. Gidin isterseniz herhangi birisine sorun başarım mı ister yoksa kullanıcı dostluğu mu ister. Kullanıcı dostu bir arayüz her zaman başarımdan daha önemli olmuştur. O zaman biz burada bununla niye uğraşıyoruz? ---- Bazen başarım, kullanıcı dostluğuyla kesinlikle çok yakından alakalıdır. Burada oturup programın çalışmasının uzun süre beklemenin sevimli bir tarafı yok herhalde. O halde bu iyi bir neden olabilir. Başka düşünebileceğimiz neler var? -- Bazen zaman sınırlamaları o kadar kısıtlıdır ki iyi bir başarım yoksa o program hiç çalıştırılmaz. -- Doğru söylüyorsunuz ama problem kullanıcı dostluğunu ölçemememizde.. Ama ne demek istediğinizi anladım. Arkadaşınız, kullanıcı dostluğu konusunda başarımda olduğu gibi üstel yani eksponansiyel gelişmeler olmadığını söylemek istiyor. Aslında üstel gelişmeleri başarımda da pek yakalayamıyoruz değil mi? Bazen yakalıyoruz, o zaman iyi oluyor. Bana başarımın önemli olduğunu düşündüren bazı sebepler var. Mesela başarım bir işin yapılabilir olmasıyla yapılamaz olması arasındaki çizgiyi tanımlıyor ve ölçüyor. Bunlarla ilgili örnekleri duymuşsunuzdur. Bazen zaman kısıtlamaları olduğunda eğer program yeterli ölçüde hızlı değilse işlevsel de değildir. Ya da gereğinden fazla bellek yiyorsa, program o zaman size uygun olmayabilir. Sonuçta bütün bunları değerlendirdiğinizde algoritmaların girişimciliğin sınırında yer aldığını görürsünüz. Eğer amacınız bundan 10 yıl önce başkalarının uyguladığı şeyleri tekrar yapmaksa başarım o zaman çok önemli olmayabilir. Ama eğer siz geçmişte çok zaman gerektirdiği ya da günün ölçütlerine uymadığı için kimsenin yapamadığı şeyleri bugün yapmayı amaçlıyorsanız o zaman başarımın önemi ortaya çıkar. Bu nedenle yapılabilir olmakla yapılamaz olmak arasındaki farkı açıklamada başarım iyi bir ölçüdür. Bu da başarımın önemini gösteren nedenlerden biridir.

Diğer bir neden, algoritmaların programların davranışları konusunda ortak bir lisan oluşturmasıdır. Ve bu lisan bilgisayar bilimi kapsamında giderek yaygınlaşmış olan ve uygulayıcılar tarafından bazı şeyleri açıkça anlamak için kullanılan bir lisan olarak kullanılmaktadır. Kavramlar arasında anlaşılabilir köprüler kurulabilir. Bu nedenle ben başarımı, listenin en alt sıralarında olmasına bakarak paraya yani bir değişim aracına benzetirim. Yani 100 dolarlık bir destenin size yararı nedir? Bunun yerine yiyecek, su veya barınak gibi şeylerin olması daha önemli değil mi? Bunlar için siz o 100 dolarları ödersiniz. Eğer 100 dolarlarınız varsa tabii. Su gibi yaşam için çok daha önemli olan şeyler için bu paraları harcarsınız. Benzer biçimde, başarım da, örneğin kullanıcı dostluğu için ödediğiniz bir bedeldir. Aynı şeyi güvenlik için de ödersiniz. İşlevselliğe gelince mesela insanlar JAVA ile program yazarlar ve bu C programcılığından çok daha yavaştır. Çünkü JAVA’da programlama yapmak diğerinden 3 kat daha pahalı olabilir. Ama öte yandan JAVA buna değer çünkü nesneye yönelik çözümleme olanakları ile bazı farklılık mekanizmaları vardır. Yani sonuç olarak insanlar 3 kat daha fazla performans harcayarak bu dilde programlama yaparlar. İşte başarıma burada ihtiyaç var. Yani istediğiniz diğer şeyler için bir bedel ödüyorsunuz ve bunu da başarımla ödüyorsunuz. Bir bakıma da, bu nedenle başarım listenin en altında çünkü diğer olanakları düzenlemek ve ölçeklemek için evrensel bir şey. Örneğin bir özellik için 2 faktör harcamak veya güvenlik için 3 faktör harcamak v.s gibi düşünebilirsiniz. Bu yaklaşımı derslerde iletişim gibi, bellek gibi diğer konulara da yaygınlaştıracağız.

Algoritma başarımını konu olarak almamızın son sebebi de çok eğlenceli bir konu olmasıdır. Hız her zaman eğlencelidir, öyle değil mi? İnsanlar niye hızlı araba kullanırlar? Yarış atlarına merak sararlar. Roketleri niye yaparız? Çünkü hız eğlencedir. Kayak kaymak. Kayak kaymayı seven var mı? Ben çok severim. O kayakların üzerinde hızla gitmeyi çok severim. Çünkü eğlencelidir. Hokey, hızlı sporlar. Öyle değil mi. Hepimiz hızlı sporları severiz. Belki hepimiz sevmeyebiliriz. Bazılarınız benim dilimde konuşmuyor diyebilir. Her neyse devam edelim. Sonuç olarak bizim algoritmayla ilgilenmemizin temelinde başka kullandığımız özelliklerin temelinde miktarlaştırabileceğimiz bir konu olması yatıyor. Böylece biz bilgi işlem yoluyla kendimize nasıl para kazandırırız onu anlamaya başlarız.

Çok basit bir problemle başlayalım. Bu en eski problemlerden biridir; algoritma kavramında incelenen bu problemin adı sorting yani sıralama. Bu konuyu aslında birkaç ders boyunca inceleyeceğiz. Çünkü sıralamanın birçok algoritmik tekniği var. Sıralama problemi şöyle ortaya konabilir. Bir dizimiz yani sequence’imiz var: , , olarak belirlenen sayılardan oluşan girişler. Ve bu rakamların bir permütasyonu yani devşirimi olan bir çıkış. Permütasyon, rakamların sıralamasının değiştirilmesidir. Bu yeniden düzenlemede rakamların hepsi birer defa görünür. Ve öyle ki ( ben bazen öyle ki anlamında Dolar işareti kullanırım) , (üssünden) daha küçüktür veya ona eşittir. Yani bunlar bir düzenle hep artarlar. Herhangi bir grup sayı seçin ve bunları sıraya koyun. Burada şimdi size bunu yapacak bir algoritmayı anlatacağım. Bu algoritmanın adı insertionsortyani araya yerleştirme sıralaması.-- Şimdi biz bu algoritmayı sözde kod yani pseudocode denen bir kodla yazacağız. Bu bir tür program dilidir, ama içinde İngilizce vardır. Yani anlaşılırlığı kolaylaştıran bir kısa formattır.

Bu kodla a’ yı 1 den n ye kadar sıralayacağız. Şu şekilde bir kodu var. --

Bu kodun adı sözde kod ve siz eğer sözde kodu bilmiyorsanız ya da anlamıyorsanız notasyonlarlayadasimgelemlerle ilgili soru sormanız gerekir. Derslerde ilerledikçe bu işe alışacaksınız. Sözde kodun özelliklerinden biri de burada indentation yani içerleklik kullanılmasıdır. Bir çok dilde de bu kullanılır; başlangıç ve sonu sınırlayan köşeli parantezler veya özel işaretler vardır. Mesela JAVA’da ve C’de olduğu gibi. Biz sadece içerleklik kullanacağız. Sözde kod yaklaşımının temelindeki amaç, algoritmaları mümkün olduğu kadar kısa hale getirmek ama bu sırada bağımsız adımların anlaşılır halde kalmasını sağlamaktır.

Pratikte içerlekliği, bilgilerin iç içe yerleştirilmesinde kullanan diller var. Aslında bu çok iyi bir fikir değil. Çünkü bu tip işaretler bir sayfadan diğerine geçildiği zaman anlamlarını yitiriyorlar. Ama açıkça parantezler veya ayraçlarla neyin ne olduğunu anlatmak çok daha kolay. Onun için program yazımında ya da kod yazımında bunun neden kötü olduğunu yazılım mühendisliğinde anlayabilirsiniz. Fakat şu anda bizim için yararlı. Çünkü işleri kısaltıyor ve yazılacak şeyleri en aza indiriyor. Bunun adı daha önce belirtildiği gibi arayayerleştirme sıralaması. Bunun birazcık ne işe yaradığına bakalım.

Elimizde bir A dizilimi yani array’i var…. Ve bizim tanımladığımız herhangi bir noktanın dış döngüsünde, j’yi 2 olduğu noktadan n’ye kadar, iç döngüsünde de j’yi j- 1 den başlayıp sıfıra kadar götürüyoruz. Temelde algoritmanın herhangi bir noktasına baktığımız zaman biz burada j elemanına bakıyoruz. Yani A [ j ]sı.. J elemanı. Temelde yaptığımız şey buradan bir değer seçmek ve buna anahtar demek. Burada anlaşılması gereken önemli konu (ve bununla ilgili etütte de konuşacağız), bu döngünün her işlevinde bir değişmez yani invariant olduğudur. Ve bu değişmez dizilimin bu bölgesinde sıralanmış halidir.. – Hedef, bu döngünün işlemleri içindeki her adımda sıralanmış olana bir eleman daha ilave etmektir. Bunu yapmanın yolu da anahtarı yerinden çıkarmak ve değişmezin içinde yerini bulana kadar onu kaydırmaktır. Ve yerini bulduğu zaman biz bu anahtarı oraya yerleştiririz. Bu nedenle bunun adı araya yerleştirme sıralamasıdır. Yaptığımız şey elemanları hareket ettirmek ve o anahtar yerini bulana kadar onu defalarca kopyalamaktır. Böylece A dizilimi içerisinde değerler 1’den j’ye kadar sıralanmış hale gelirse, biz artık J+1 ile uğraşabiliriz. Bununla ilgili bir örnek verelim.

Şunu hayal edin. 8 2 4 9 3 6 sayılarını sıralayacağız. Biz j=2 den başlıyoruz. Ve diyoruz ki bunun yeri burası olmalıdır. / Şimdi elimizde 2 8 4 9 3 6 sıralaması var. Ondan sonra 4 e bakıyoruz. Ve diyoruz ki 4 ün gitmesi gereken yer burası. / Şimdi elimizde 2 4 8 9 3 6 var. İkinci tekrardan sonra yani dış döngünün 2. tekrarından sonra… / Sonra 9 a bakıyoruz ve hemen 9 un burada olması gerektiğine karar veriyoruz; yani bu adımda fazla bir iş yok. Bu tekrardan sonra elimizde olan sonuç bu şekilde. / Sonra 3 e bakıyoruz ve 3 ünde buraya girmesi gerektiğine karar veriyoruz. 2 3 4 8 9 6 ve son olarak da 6 ya bakıyoruz. O da buraya giriyor. / 2 3 4 6 8 9 ve bu noktada işimiz bitmiş oluyor.

Sorusu olan var mı? -- Evet dizilim 1 den başlıyor. a’nın 1’den n’ye kadar olan kısmı, tamam mı? Bu yaptığımız işe araya yerleştirme sıralaması algoritması diyoruz. Ve bu algoritma bizim ilk çözümleyeceğimiz algoritma. Bunu yapmak içinde matematik geçmişimizden bazı araçlara ihtiyacımız olacak. Öncelikle koşma süresi yani run time konusunu ele alalım.

Bu algoritmanın koşma süresi birçok faktöre bağlı. Bunlardan birisi girişin kendisi. --Örneğin eğer giriş zaten sıralanmışsa araya yerleştirme sıralamasının yapacağı iş çok azdır. Çünkü her seferinde olduğu yere varacaktır. Elemanların yerlerini değiştirmek zorunda kalmayacaktır. Çünkü elemanlar zaten yerlerindedir. Öyleyse araya yerleştirme sıralamasının en çok zorlandığı durum nedir? - Eğer tersten sıralama varsa bu algoritma çok iş yapmak zorundadır. Çünkü dış döngüdeki her elemanın yerini her adımda ayrı ayrı değiştirecektir. Ayrıca sürenin bağlı olduğu şeylerden biri de girişin boyutudur. -- Bu örnekte biz 6 elemanla çalıştık. Ama eğer 6 eleman yerine 6x10 nun 9 ncu kuvveti sayısında eleman olsaydı tabii ki çok daha uzun süre gerekecekti. Daha fazla elemanı sıralamaya kalkarsak doğal olarak bu çok daha fazla zaman alacak. -- Bu sorunu analiz etmenin yolu ise giriş boyutu ile ilgili parametreler oluşturmaktır. Sıralama algoritmasının davranışını anlamak için zamanı boyutun bir fonksiyonu olarak tanımlayacağız.

koşma süresi ile ilgili son söylemek istediğim şey, çoğunlukla bu konuda bazı üst sınırlarının belirlenmesine ihtiyaç duyulduğudur. İstediğimiz şey gereken zamanın belli bir miktarın ötesinde olmamasıdır. Bunun nedeni de böyle bir sınırlamanın kullanıcı için bir garanti sağlamasıdır. Örnek olarak burada bir program var ve bu en fazla 3 saniye içinde işlemini tamamlayacak dersem, o zaman size gerçek anlamda kullanacağınız bir güvence veririm. - Öte yandan ben size bu program en az 3 saniye çalışacak dersem programın bitiş süresinin 3 sene mi olacağını bilemezsiniz- ve kullanıcı olarak programınızın verimliliği konusunda herhangi bir fikriniz olmaz. Bu nedenle genelde biz üst sınırlarla ilgileniriz. Çünkü bu kullanıcıya bir garanti verir. --

İnsanların kullandığı birkaç analiz biçimi var. -- Bizim üzerinde duracağımız olanı en kötü durum analizi. Bu bizim genellikle yaptığımız şeydir. n boyutundaki herhangi bir girişin maksimum zamanını n’nin T fonksiyonu, T(n) olarak tanımlarız.—Bu fonksiyon, boyutu n olan bir girişin, bize zaman olarak maksimum maliyetini tanımlar. Böylece, girişlerin bazen iyi bazen de kötü yapılanmış olduğu düşünülürse, en kötü duruma bakıyoruz ki garantili olsun. Yani program sadece bazı durumlarda değil, her durumda çalışsın. Yani işin maksimum boyutuna bakıyoruz.

Dikkat edin maksimum tanımlaması olmasaydı T( n) bir ilişki olurdu, bir fonksiyon olmazdı. Çünkü n boyutlu girişteki zaman hangi n boyutlu giriş sorusunu akla getirirdi. -- Bu durumda bir sürü farklı zamanlar ortaya çıkardı. Ama buna bir maksimum verdiğim zaman o zaman bu ilişki bir fonksiyona dönüşüyor çünkü sadece bir tek maksimum olabilir.

Bazen ortalamalarla da ilgileneceğiz. Bunu da yapacağız. Bu durumda T (n),n boyutundaki tüm girişlerin için beklenen zaman olarak tanımlanacak. Beklenen zaman. Şimdi beklenen zamandan bahsederken başka ne söylemem lazım? Yani beklenen zaman ne anlama geliyor? - Pardon. Lütfen elinizi kaldırın. -- Beklenen girişler. Ne demek beklenen girişler? --Biraz daha matematik dilinde konuşalım. Beklenen zamanla matematik dilinde ne demek istiyorum? -- Her bir girişin gerektirdiği zamanı alıp onların ortalamasını almak, öyle mi? Bizim beklenen zamandan kastettiğimiz bu. Güzel. --Tam değil ama. Söylediğiniz şey tamamı ile doğru ama hala yetersiz. Evet- Bu her girişin gerektirdiği süre çarpı o girişin olasılığı.. Yani bu bir tür ağırlıklı ortalama. Tamamen doğru. Pekiyi ben her girişin olasılığının ne olduğunu nasıl bilirim? --Yani belli bir girişin o durumda ki olasılığını nasıl bilebilirim? –Belirli bir durumda..--- Bilemem. - O halde bir varsayım yapmam lazım. Bu varsayıma ne denir? --Nasıl bir varsayım benim amacıma hizmet edebilir.

Bir varsayıma ihtiyacım var.-- Girişlerin istatistiksel dağılımı üzerine. Aksi takdirde beklenen zamanın herhangi bir anlamı olmaz. Çünkü bir çok şeyin olasılığını bilmiyoruz. Olasılıklar hesabına girmek için bazı varsayımlar yapmamız lazım --ve bu varsayımları da çok açık bir şekilde ifade etmemiz lazım.

En çok kullanılan varsayımlardan biri bütün girişlerin eşit oranda olasılığının olduğunu kabul etmektir. Buna biz tekbiçimli dağılım deriz. n boyutunda her girişin olasılığı aynıdır gibi bir şey. Ama varsayım yapmanın başka yolları da vardır ve hepsi doğru olmayabilir. Gördüğünüz gibi işler giderek karmaşık hale geliyor. Ama eğer bir probability yani olasılık dersi geçmişiniz varsa o zaman şanslısınız. Bu durumda bu tip olasılık hesaplarını size anlatmakta ve beklentilerimizi karşılamakta çok büyük bir sorunlar olmaz. Eğer bir olasılık geçmişiniz yoksa, belki şu anda bu dersin ön koşulu olan olasılık dersini almayı düşünmelisiniz.

Son bahsedeceğim konu en iyi durum analizidir. --Ve bu tamamıyla yanıltıcı bir yaklaşımdır. Yanıltan bir yaklaşımdır. İyi değildir. Neden en iyi durum analizi bir kandırmacadır? -- Çünkü en iyi durum genelde gerçekleşmez. – Aslında, ilginç olan şu ki sıralama problemlerinde en fazla karşımıza gelen sorunlar zaten sıralanmış olan verilerin analizidir. Ya da nerdeyse tamamen sıralanmışa yakın. Örneğin en çok sıralanan şeylerden biri bankaların kullandığı çek numaralarıdır. Ama zaten onlarda yazılış tarihi itibari ile bir sıralanma yapılmıştır. Yani zaten kısmen sıralanmış olan şeyler bir daha sıralanır. Yani iyi. –

Üst sınır,. Alt sınır meselesi...-- Bir garanti vermek istiyorsanız bu neden bir garanti değildir? -- Evet buradaki görüşünüz fena değil ama daha detayda konuşmamız lazım. Örneğin ben nasıl aldatmaca yapabilirim? – Evet, evet aldatabilirsiniz. Kandırabilirsiniz. Herhangi bir yavaş algoritmayı alabilirsiniz ve belirli girişlerle deneyebilirsiniz ve o girişlerle çalıştırdıktan sonra evet benim cevabım bu dersiniz. Ve bu bir en iyi durum analizidir; ama çoğunlukla olan şeylerle ilgili bir şey söylemiş olmazsınız. Yani siz yavaş bir algoritma kullanarak belli girişlerle hızlı çalışan bir sonuç alabilirsiniz. Bu genelde fazla bir işinize yaramayacağı için biz bu konuyu biraz gündem dışı tutmayı tercih ediyoruz.

Bakalım araya yerleştirme sıralamasının en kötü zamanı nedir? Burada bazı komik şeylerle karşılaşırız. Birincisi bu, programı çalıştıracağınız bilgisayara bağlıdır.-- Kimin bilgisayarı. -- Bir süper bilgisayar mı yoksa bir kol saati mi? Çünkü bunların değişik hesaplayabilme yetenekleri var. Biz algoritmaları karşılaştırırken göreceli hız kavramı çerçevesinde karşılaştırırız. Yani iki algoritmayı aynı makinede çalıştırmak gibi.. Diyebilirsiniz ki bunun çok önemi yok. Hangi makinede çalıştıkları önemli değil çünkü ben onların göreceli hızına bakıyorum. Ama bazı durumlarda mutlak hız da önemlidir. Bir algoritma hangi makinede çalışırsa çalışsın acaba diğerlerinden üstün müdür? -- Burada işler giderek karışır. Çünkü bir yazılımın çalışmasına, algoritmanın en kötü zamanı açısından baktığımızda donanım nasıl hesaba katılmayabilir? Çünkü yazılımı daha hızlı bir makinede çalıştırırsam, algoritmam mutlaka daha hızlı çalışacaktır. İşte bu nokta algoritmalarda bir büyük fikrin doğduğu noktadır. Bu nedenle algoritmalar, Google, Akamai ve Amazon gibi firmaların sıklıkla kullandıkları çok büyük bir alan olmuşlardır. Bilgi işlem tarihi boyunca algoritmik çözümlemenin çok büyük bir başarıya erişmesinin sebebi, çok karmaşık ve karışık gibi görünen durumların algoritmalar vasıtasıyla matematik kullanılarak çözülebilir olmasıdır. Ve bu büyük fikrin ismi asymptoticanalysis yani asimptotikçözümlemedir. --

Asimptotik çözümlemenin ana fikri makineye bağlı sabiteleri görmezlikten gelmektir. - Yani gerçek koşma süresi yerine koşma süresinin büyümesine bakılır.-- Yani gerçek koşma süresine bakmıyoruz. Bunun büyümesine bakıyoruz. Bunun ne anlama geldiğini bir düşünelim.

Bu çok büyük bir fikir. Çok zor bir fikir değil. Aksi takdirde size ilk derste bunu açıklayamazdım. Ama çok büyük bir fikir. Bu fikrin anlamları konusuna birkaç ders ayıracağız. Ama yarıyıl boyunca da aslında bu sistemi kullanacağız. Ve siz eğer ilerde mühendislik alanında uzmanlaşmayı seçerseniz bu işlemi her zaman uygulayacaksınız. Bu işi yapabilmek için bize yardımı olacak bazı simgelemleri seçmemiz gerekiyor. Özellikle de asimptotik simgelemi seçeceğiz. -- Asimptotik simgelemibir çoğunuzun görmüş olduğunu düşünüyorum. Belki bazılarınız görmemiştir ama bir çoğunuz bunu mutlaka kısmen de olsa görmüştür. Bu sınıfta bizim kullanacağımız simgelemin adı TetaSimgelemiΘ..TetaSimgelemiuzmanlaşılması kolay bir simgelem. Çünkü bütün yapmanız gereken bir formülün içindeki düşük düzeyli terimleri ihmal etmek ve ön sabiteleri görmemezlikten gelmek.. Örneğin 3= 90- 5n + 6046 gibi bir formülümüz olduğunu düşünelim. Bu formülde hangi düşük düzeydeki terimleri görmemezlikten gelebiliriz? Aslında ’den daha büyük bir terimdir. Ben bütün buradaki terimleri ve elemanları görmezlikten geleceğim, sabiteyi de ihmal edeceğim ve buna Teta diyeceğim. Kolay değil mi. İşte tetasimgelemi bu.

Ama bu tetasimgeleminin mühendislik yaklaşımı ile işlenmesi.. Bu konuda bir de matematik tanımlama var ve gelecek sefer bundan bahsedeceğiz. Matematik tanımlamayı fonksiyon setleri ile yapacağız. Ve bu ders hem matematik, hem de bilgisayar bilimi mühendisliği dersi olacağı için, siz hepsinden sorumlu olacaksınız. Bu nedenle ders boyunca hem bir matematik dersi alıyormuş gibi matematiğin özel gücü ile, hem de bir mühendislik dersi alıyor gibi mühendisliğin mantığı ile ilgili çalışmalar yapacaksınız. Her ikisini birden yapacağız. Bu, yapılan işin ne olduğunu anlamanın mühendislik yoludur. Onun için bu uygulamaları ve işlemleri yapmak zorundasınız. Siz aynı zamanda tetasimgeleminin matematik tanımları olan O simgelemi ve Omegasimgelemini de anlamaktan sorumlu olacaksınız. Tetanın sonsuza yaklaştığını gözlemlediğimizde bir teta algoritması her zaman bir tetaalgoritmasına üstün gelir. n büyüdükçe formülde tanımlanan diğer terimlerin detayda davranışları anlamını yitirir. Eğer benim teta algoritmam varsa bu her zaman teta algoritmasından, yeterince büyük bir n için daha hızlıdır. Diğer terimlerin ne olduğu sabitelerin ne olduğu hiç önemli değildir. Aynı zamanda ön katsayının da ne olduğu hiç önemli değil. Bu her zaman diğerlerinden hızlı olacaktır. Teta algoritmasını yavaş bir bilgisayarda yürütseniz bile, hızlı bir bilgisayarda işleyen teta algoritmasına göre daha hızlı olacaktır. Asimptotik simgelemin en önemli yararı, hem göreceli hızı hem de gerçek hızı karşılaştırabilme kriterlerini sağlamasıdır. -- Çünkü bilgisayar platformuna bağımlı bir sonuç almayız. Değişik bilgisayarlarda değişik katsayılar elde ederiz. Gerçek zamanda makineye bağımlı olarak değişik sonuçlar elde ederiz. Fakat girişlerin boyutunun büyümesine bakarsak asimptotlar fazla değişmeyecektir. --Örnek olarak şuraya bir grafik çizeceğim. Bu eksende n’yi, diğer eksende de nnin T fonksiyonunu göstereceğim.. Örneğin-- bu bir teta algoritmasının eğrisi -- bu da teta algoritmasının eğrisi olabilir. -- Buna göre ismine diyebileceğimiz öyle bir nokta olacaktır ki-- bundan daha büyük n değerleri için Teta algoritması her zaman Teta algoritmasından daha hızlı olacaktır. İşletim için donanım hızını gösteren hangi katsayıyı koyarsanız koyun.

Şimdi mühendislik yaklaşımı ile bazı problemlerle uğraşmamız lazım. Çünkü bazen o kadar büyük olur ki evdeki bilgisayarlar programı çalıştırmak için uygun değillerdir. Bu nedenle böyle durumlarda bazen daha yavaş algoritmalarla ilgilenebiliriz. Çünkü bazı algoritmalar asimptotik açıdan daha yavaş olmakla birlikte sonuç verebilirler. Bazı büyüklüklerde bunlar daha hızlı uygulama sağlayabilirler. Bu nedenle programlama yaparken bazen mühendislik mantığımızı matematik anlayışımızla dengelememiz gerektiğinin farkında olmalıyız. Yani sadece algoritmaların çözümlemesini yapmak sizin iyi bir programcı olmanızı garanti etmez. Programlamayı da öğrenmeniz gerekir. Ve bu araçların pratikte ne zaman yararlı ne zaman da yararsız olduklarını bilerek değerlendirmemiz gerekir.

Şöyle bir söylem vardır. İyi bir programcı olmak istiyorsunuz; 2 yıl boyunca her gün kod yazarsanız bu süre sonunda mükemmel bir programcı olabilirsiniz. Eğer dünya çapında bir programcı olmak istiyorsanız 10 yıl boyunca her gün kod yazarak dünya çapında bir programcı olabilirsiniz. Ya da algoritma dersi alır ve 2 yıl boyunca her gün kod yazarak yine bu sonuca ulaşırsınız.

Şimdi yaptığımız işe geri dönelim. Araya yerleştirme sıralamasının çözümlemesine. En kötü duruma bakacağız. Bu da daha önce belirtildiği gibi tersten sıralama durumu; en büyük eleman en başta ve en küçük eleman en sonda. Bu durumda araya yerleştirme sıralaması için bütün elemanların yerlerinin değişmesi gerekiyor. Döngülerin nasıl iç içe yerleştirildiğine bakarak koşma zamanını belirleyebiliriz. Yaptığımız şey toplamadır. Varsayımız ise bu durumda her birim operasyonun belli bir süre sabiti kadar süreceğidir. Ama bu sabit konusunda endişe etmemize gerek yok. Çünkü asimptotik çözümleme yapıyoruz. Bu metodun güzelliği şurada ki gerçekten farklı olan birçok şeyin sonunda yok olduğunu görüyorsunuz. Yani şuna benziyor: Bu probleme 3mm den bakmak yerine 10.000 metreden bakıyoruz. Bu işlemlerin her biri basit temel operasyonlar olacak. Sayı işlemleri türünde yürütülen bu işlemle ilgili düşünmenin bir başka yolu da bellek referanslarını saymaktır. Bir değişkene kaç defa erişiyoruz? Bu soru bu modelle ilgili başka bir düşünce tarzıdır. Bu şekilde yaklaşıldığı zaman işlem, j 2 den n ye giderken o döngünün içindeki işlemlerin toplanması haline dönüşür. Bunu da matematiksel olarak j= 2’den n’ye kadar olan toplamı olarak yazabiliriz. Tamam; bu sırada bu döngü içinde ki çalışma ne? Aslında bu döngünün içindeki işlemler değişiyor ama, biz en kötü duruma baktığımız için her j değeri için kaç operasyon kaç işlem oluyor ona bakıyoruz. j’nin verilen bir değeri için bu döngü içerisinde kaç kaç kez çalışma oluyor? Biri bana bunu söyleyebilir mi? Asimptotik olarak… Bu j çarpı bir sabittir. Yani Teta J dir. Burada tetaj işlemi yürüyor. Çünkü döngü i =j-1 den başlıyor ve bir sabit işlem yaptıktan sonra her adımda i’nin değeri j-1 den 0 a gidene kadar işlem sürüyor. Yani biz bu durumda Teta(j) işi sürüyor diyebiliriz. Bunu takip edebiliyor musunuz?Evet şimdi değerlendirebileceğimiz bir formülümüz var elimizde. Eğer bu formülü basitleştirmek istersem neye eşittir? Pardon duymadım… Evet. Teta(. Güzel. Çünkü “işlem birbirini takip eden sayıların toplamıdır” dediğimiz zaman ne demek isteriz? Yani bunun için bizim iletişimde kullandığımız matematik terim nedir.

İletişim kurabilmek için bu şeyleri bilmeniz gerekiyor. Hangi tip bir dizi bu? Evet bu gerçekte bir dizi. Bu tip dizilere ne denir? Aritmetik dizi. Güzel. Tamam. Şimdi iletişim kurabileceğimiz bazı zeki insanların olduğu görülüyor. Bu bir aritmetik dizidir. Aslında temel olarak 1+2+3+4 ü topluyorsunuz, arada bazı sabiteler var ama, temelde 1+2+3+4+5+6, n ye kadar gidiyor. Bu Teta’dır. Bu matematiği bilmiyorsanız o zaman kitapta bununla ilgili bir bölüm var. Veyahut bu dersin önkoşul dersini almanız gerekirdi… Aritmetik serileri. Ama kabaca bunun ne olduğunu hatırlayacağınızı umuyorum. Evet. Şimdi bu işlemleri yapmayı öğrenmelisiniz. Gelecek sefer bu konu üzerinde biraz duracağız ama teta işlemlerini ve teta’yla ne tip bir mantığın çalıştığını öğrenmeniz gerekiyor. Ve burada çok dikkatli olmanız gerekiyor. Çünkü Teta zayıf bir simgelemdir. Sağlam bir simgelem, calculus dersinde öğrendiğiniz Leibnitzsimgelemi tipi bir simgelemdir. Orada zincir kuralı iki şeyi karşılıklı olarak götürebilir. Zincir kuralında bir takım karşılıklı götürmeler iptaller yapabilmeniz müthiş bir şeydir. Ve Leibnitzsimgelemindeki zincir kuralı bunu o kadar direk anlatır ki siz bu işlemi yapabilirsiniz. Tetasimgelemi bunun gibi değildir. Eğer Leibnitz’e benzetirseniz başınız derde girer. Tetasimgeleminin altında nelerin olduğunu iyi düşünmeniz lazım. Bu simgelem işleme dönük olmanın ötesinde tanımlamaya da dönük bir simgelemdir. Bu simgelemin altında yapabileceğiniz işlemler vardır, ama bunları yaparken neden yaptığınızı iyi anlamazsanız başınız iyice derde girer. İleride Tetanotasyonu ile ilgili daha fazla bilgi aktaracağız. Pekiyi, araya yerleştirme sıralaması hızlı mıdır? Aslında n’nin küçük değerleri için oldukça hızlıdır. .. Ama n büyüdükçe kesinlikle hızlı değildir. Onun için ben bu konuda kullanabileceğiniz başka bir algoritmayı size göstermek istiyorum. Bunun adı mergesort yani birleştirerek sıralama... Araya yerleştirme sıralamasını yukarıda mı bırakayım bilmiyorum. Tamam kalsın… Bunu daha sonra buraya yazacağım… Onun için not alıyorsanız sol tarafta biraz boşluk bırakın… Burada 1 den n’ye kadar uzayan bir A dizilimin birleştirilerek sıralaması var. Bu işlem 3 adımdan oluşuyor. Eğer n 1’e eşitse işimiz bitti. Bir elemanı sıralıyoruz, zaten sıralıymış.. Tamam. Özyinelemeli algoritma. Aksi takdirde yapmamız gereken şey A yı 1 den n/2’nin sonuna kadar özyinelemeli olarak tekrarlamak. Ve sonra da A dizininin n/2 + 1 değerinden n’ye kadar olan işlemini yapmak. Yani biz girişin iki yarısını sıralıyoruz. Ve 3 ncü adımda da bu iki listeyi alıyoruz ve birleştiriyoruz. Bu işlemi yapmak için kullanacağımız bir birleştirme alt programını size göstereceğim.. Buradaki anahtar alt program birleştirme programıdır ve şu şekilde çalışır. Benim 2 tane listem var. Diyelim ki bir tanesi 20 ile başlıyor.. Bu işi tersten yapıyorum. Onun için sıralamayı şu şekilde yaptım. Ondan sonra ben başka bir tanesini sıralıyorum. Niye bu düzende sıraladığımı bilmiyorum ama diyelim ki böyle yaptım. Bu da benim diğer listem. Bu şekilde elimde sıralı 2 tane liste var. Böylece bu a=1 den a= n/2 ye uzanan liste ve bu 2 listeyi birleştirmek için yapmak istediğim şey her ikisini de içeren başka bir sıralı liste hazırlamak. İlk yaptığım şey her iki listede en küçük sayının hangisi olduğunu belirlemek.. Bu 2 yerden birinde olabilir;.. ya birinci listenin başında ya da ikinci listenin başında..ve şu 2 sayıya bakıyorum ve hangisinin daha küçük olduğunu belirliyorum. Bu daha küçük. Ondan sonra yaptığım şey çıkış dizilimine küçük olanı koymak ve onu kendi listesinden silmek… Bundan sonraki en küçük sayı hangisi? .. Ve bu, yine bu 2 listenin başındaki sayılardan birisi olmalı. Bunu da o listeden siliyorum ve sıraya koyuyorum. Şimdi bu 2 listeye bir kez daha bakıyorum. Bu ötekinden daha küçük onun için onun etrafına bir daire çizip onu da çıkış dizilimime ilave ediyorum. Şimdi kalanların arasına bakıyorum ve 9’u çıkışa veriyorum. Böylece buradaki her adım dizilimlerin boyutuna bağlı olmadan bağımsız işlemlerden oluşan adımlar olarak belirleniyor.

Her bağımsız adımda iki elemana yani öğeye bakıyorum ve bunların en küçüğünü seçiyorum. Ondan sonrada dizinin içinde dizilimin içindeki bazı işaretçileri o listenin başına doğru kaydırıyorum. Böylece zaman, n toplam eleman için n düzeyinde oluyor…Yani iki listeyi birleştirmek için gereken toplam zaman n düzeyinde. Biz buna bazen lineer yani doğrusal zaman diyoruz. Çünkü kuadratik yada başka bir şey değil. Zaman burada n’ye oranlı, yani giriş boyutuna oranlı doğrusal bir zaman.. Bu basit işlemi bu listelerde yavaş yavaş yukarıya doğru yapıyorum ve sonunda n işlem yapmış oluyorum. Ve her biri sabit zaman alan işlemlerin süresi n düzeyinde oluyor. Bu toplam n’ye oranlı bir zaman. ..Herkes beni takip edebiliyor mu? Tamam. O halde bu bir öz yinelemeli bir program. Bu evrede biz bu program için bir recurrence yani yineleme yazabiliriz. Bunu yaparken n sayıda elemanı sıralamak için geçen zamana TN(n) diyelim… Pekiyi bu durumda birinci adımdaki işlemi yapmak için gereken süre nedir?.. Sabit bir zamandır. Gidip n’nin 1 e eşit olmadığına bakarız, ve eğer eşitse geri döneriz. Bu yaptığımız her şeyden bağımsız bir işlemdir. Belirli makine komutları gerektirir ve hangi makineyi kullanıyorsak kullanalım sabit bir zamandır. Buna Teta (1) diyeceğiz. İyi düşünecek olursanız aslında bu biraz mantığı kötüye kullanmak oluyor. Çünkü bunu söyleyebilmeniz için temelde neyle büyüdüğünü de söylemeniz gerekir. Yine de biz bu simgelemin bu kötü kullanımdan yararlanacağız ve buna bir sabit diyeceğiz. Bu sabittir diyeceğiz. Unutmayın ama bu simgelemi kötüye kullanmaktır aklınızın bir köşesinde olsun. Buna karşılık Teta (1) yazabildiğimiz takdirde işler büyük ölçüde kolaylaşacaktır. Aslında temelde aynı anlama gelir. Şimdi bu 2 öğeyi öz yinelemeli olarak sıralayacağız. Peki bunu nasıl açıklayabilirim?. Bunu yapmak için gerekli zamanı öz yinelemeli olarak tanımlayacak olursam T (n/2) nin tepe değeri + T (n-n/2) nin tepe değeri olarak yazabilirim..., Bu epey karışık oldu, bu nedenle biraz itinasız olacağız. Ve 2T (n/2) yazacağız.. Tekrar ediyorum bu itinasız bir yazım. İlerdeki etütlerde göreceğimiz gibi itinasız olmak aslında kabul edilebilir. Algoritmalarla ilgili en önemli olgulardan biri de bu. Yani itinalı ve kesin olduğunuz sürece istediğiniz kadar itinasız olabilirsiniz… Bu gerçekten de itinasız ya da laçka bir davranış şekli. Çünkü ne olup bittiğiyle hiç ilgilenmedim ama sonuca da etki etmeyeceğini göreceksiniz. Bunun böyle olduğunu ilerde göreceğiz.. Ve sonuçta benim 2 sıralı listeyi, ki bunların total n elemanı var, birleştirmek zorunluluğum var. Bunu yaparken de Teta (n) zamanı alacak bir birleştirme alt programını çalıştıracağız ve bunu çözümleyeceğiz… Bu yaklaşım bize birleştirerek sıralamanın başarımıyla ilgili bir yineleme yazma imkanı verecek… Diyeceğiz n’nin 1 olma durumunda.. T(n) eşittir Teta (1). Ve n eğer 1 den büyükse.. T(n), 2T (n/2) + teta (n)’e eşittir.. Çünkü ya birinci adımı yapıyorum… veya diğer adımları yani 1. 2. ve 3. adımları yapıyorum. ..Ya 1. adımla uğraşıp işimi bitirince. geri dönüyorum, veya 1. adımı tamamlayınca geri dönmüyorum ve bundan sonra 2. ve 3. adımları da uyguluyorum. Sonra bunları birbiriyle topluyorum; burada aynı zamanda Teta (n) + Teta (1) de diyebilirdim. Fakat Teta(n)+Teta(1) zaten Teta (n)’ ye eşit çünkü Teta(1) aslında Teta(n)’ye göre daha düşük düzeyli bir terim ve onu atabilirim…Yani sonuçta T(n), ya Teta(1) dir, veya 2T(n/2) +Teta(n)’dir… Genelde biz ilk satırı yazmayız; burayı görmezden geliriz… Eğer yinelemenin çözümüne bir etki yapmıyorsa genelde sabit bazlı durumları ihmal ederiz. Bu olay matematikte kabul edilen bir şey değildir. Ama algoritma yaklaşımında eğer sabit boyutlu bir giriş üzerine çalışıyorsanız bu her zaman sabit bir zaman alır.. Bu nedenle bunun değeri üzerinde durmayız. Ve sonuçta da görülür ki bu tür sabitlerin, yinelemelerin asimptotik çözümlemesinin sonuçlarına etkileri olmaz.

Böyle bir yinelemeyi nasıl çözebiliriz? Şu anda elimizde T(n)’ nin, T’nin n/2 düzeyinde ifade edilmiş bir hali var.. Bu hem kitapta hem de ikinci derste göreceğiniz bir şey; 2.derste bunu çözmeye çalışacağız; fakat bu evrede ben size bunun boyutunu görsel olarak hayal etmeniz için açıklamalar yapacağım ve gelecek sefer hangi tekniklerde bunu çözeceğimizi göstereceğiz. Bu tekniğin adı recursion tree technique yani yineleme ağacı tekniğidir. Bu tekniği gerçek yinelememiz yerine, ona çok yakın olan 2T(n/2) durumunda kullanacağım. Ama bunu daha kesin yapacağım çünkü bu oluşumu anlamanızı istiyorum ve buraya bir sabit zaman da koyacağım; bu sabit c sıfırdan büyük bir sayı.. Şimdi bu yinelemeye 1. adımdaki baz çalışması olarak bakacağız.. Burada bir sabit kullanıyorum. ve bu sabitin üst sınırının dolaylı olmasının yerine kesin bir değer olmasını istiyorum… Böyle bir yineleme ağacını çözmenin yolu şudur. Bu yinelemenin sol tarafını yazmaya başlarsınız. Bunu gerçekleştirdikten ve kabul ettikten sonra bunu bir ağaç olarak yazalım dersiniz. Bu sırada cn oranında bir iş yaparım. Ve şimdi bu işi 2 child yani ardılın üzerinde yapmam gerekir. Yani T(n/2) ve T(n/2)’nin üzerinde… Buradakileri topladığım zaman şunu elde ederim. Çünkü bu yinelemede böyle belirtilmiş.. T(n) = 2T(n/2) + cn’ dir. Elimde 2 tane T(n/2) ve cn var…Sonra bunu bir daha yaparım… Burada cn var diyelim.. Burada cn/2’ yi elde ederim. ve burada da yine cn/2’ yi… Ve bunların her birinin de iki tane T(n/4)’ü olur.. Ve burada da iki tane T(n/4) olur… Ve bunu yapmaya devam ederim… Tehlikeli nokta.. nokta.. noktalardan sonra,Bu işlemi yapmaya devam edersem işin sonunda şöyle bir şekle ulaşırım…… bunu aşağıya doğru..bir yaprağa gelene kadar yapmaya devam ederim... Ve bu yaprak temelde T(1)’dir. Bu Teta (1)’dir… Bu evrede size soracağım ilk soru, pekiyi bu ağacın yüksekliği yani h nedir?..Evet bu lg ndir. Bu değer logaritma n’ye çok yakındır. Çünkü tepede n ile başlıyorum, sonra aşağıda önce n/2 ye sonra n/4 e gidiyorum ve en altta da 1 e ulaşıyorum. Yani n den başlayıp hep ikiye bölerek en altta 1 e ulaşmam logaritma n’dir. Bu nedenle de ağacın yüksekliği logaritma n dir.. Aslında, bu bir sabit çarpı logaritma n’dir ama pek de fark etmez. Öte yandan bu ağaçta kaç yaprak var?.. Bu ağaçta kaç yaprak var?... Evet ağacın yaprakları bir kez daha çok yakın çıktı; gerçekte eğer en alta kadar devam ederseniz n kadar yaprak var.. Burada basitleştirici bir varsayım yapalım. Diyelim ki n, 2’ye artıksız bölünebilir.. Yani bir tamsayı kuvvetidir. O zaman bunun n’den T(1)’ e gidene kadar kesin logaritma n olduğunu görürsünüz. Bu durumda tam n sayısında yaprak olur. Çünkü bu sayı her nod’da yani dalda 1, 2, 4, 8 diye büyür. Bu durumda h yüksekliği içinde aşağı inildiğinde 2 üzeri h yaprağı, yani 2 üzeri logaritma sonucunu elde ederiz ki bu zaten n dir. Burada matematik yapıyoruz değil mi?.. Şimdi ne kadar iş yaptığımızı hesaplayalım. Yani bu ağaçtaki her şeyi birbirine topladığım zaman T(n)’yi elde edeceğim; haydi bu toplamayı yapalım. Bu toplamayı seviye seviye ( düzey düzey) yürütelim. Birinci düzeyde ne kadar işler yaparız? Sadece cn kadar… İkinci düzeyde ne kadar yaparız?.. Gene cn kadar. Peki üçüncü düzeyi de buna ekleyecek olursam ne çıkar?.. Yine cn… Peki bütün yaprakları toplarsam ne çıkar?..Teta(n).. Bu aslında cn olmayabilir, çünkü sınır durumunda başka bir sabit devreye girebilir… Buraya kadar hep cn idi ama gerçekte Teta(n)’dir. Bunların tümünü toplayacak olursam …bucn çarpı logaritma n’ ye eşittir. Çünkü bu yüksekliktir. Çünkü elimde bu kadar cn’im var. + teta n dir… Ve bu bundan daha yüksek düzeyde bir terim olduğu için şunu görmemezlikten gelebiliriz. Sabitleri atabiliriz ve böylece eşitliğimiz Teta(n) çarpı logaritma n olur… Ve Teta(n) çarpı logaritma n, asimptotik olarak Teta(n) den daha hızlıdır.. Bu nedenle birleştirerek sıralama eğer girişlerin sayısı fazlaysa araya yerleştirme sıralamasından daha hızlı sonuç verecektir.

Birleştirerek sıralama daha hızlı bir algoritma olacaktır. Kusura bakmayın arkadaşlar sizin oradan tahtayı göremediğinizi fark edemedim. Ama eğer göremiyorsanız lütfen bunu dile getirin. Bu daha hızlı bir algoritmadır. Çünkü Teta(n lg n), teta(n)’ den daha yavaş büyür. Ve birleştirerek sıralama bu nedenle araya yerleştirme sıralamasından asimptotik olarak daha hızlıdır. Yani araya yerleştirme sıralamasını bir süper bilgisayarda çalıştırsanız bile, yeterince büyük n değerindeki girişler için, birleştirerek sıralamayı normal bir bilgisayarda çalıştıran biri daha çabuk sonuç alacaktır. Çünkü her zaman n lg n’den çok daha büyüktür. Pratikte birleştirerek sıralama 30 dan fazla giriş varsa her zaman kazanır. Eğer giriş sayısı 30’dan azsa araya yerleştirme sıralamasını kullanmak uygun olabilir. Öte yandan eğer giriş sayısı birkaç düzineden fazlaysa o zaman birleştirerek sıralamayı kullanmak gerekir.. Çünkü çok daha hızlı bir algoritmadır. Ders bu kadar..tamam. Etüt ödevlerinizi almayı unutmayın. Ve gelecek etüte katılmayı da unutmayın, çünkü burada size açıklamadığım bazı şeyleri etütde anlatacağım.

Gelecek sefere görüşmek üzere…