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 Introduction to Algorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare). http://ocw.mit.edu (Giriş Tarihi: 08, 01, 2010). Lisans: Creative Commons Attribution-Noncommercial-Share Alike.

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.

DERS 4

Günaydın; bugün çok ilginç bir algoritma olan Quicksort yani Çabuk sıralamadan bahsedeceğiz. Bu algoritma Tony Hoare tarafından 1962 de bulunmuştu. Birçok açıdan bakıldığında gerçekten ilginç bir algoritma haline dönüştü; ismine yakışır bir şekilde. Bu yüzden bugünkü ders de hem zor, hem de hızlı olacak.

...Bu nedenle yanınızdakinin uyuduğunu görürseniz ona “haydi uyan, ders devam ediyor” demeniz gerekiyor.

--Bu bir “divide & conquer” yani “böl ve fethet” tipi bir algoritmadır.

Burada elemanlar “yerlerinde” sıralanıyor, yani dizilimin elemanları bulundukları dizi içerisinde, yani oldukları yerde. Aynı araya yerleştirme sırasında olduğu gibi oldukları yerde sıraya konuluyorlar. Birleştirerek sıralama, bunu yapmaz, birleştirme işlemini yürütmek için ek bir bellek alanına ihtiyaç duyulur. Bu birleştirmeyi doğrusal zamanda yapar ama aynı mekanda yapmaz. Bu işlemi sadece yeniden sıralayarak yapmaz. Bu algoritma ise yerleştirmeyi yerinde yaptığı için işlevseldir, çünkü depolama alanının verimli kullanımını sağlar; ve bununla biraz ince ayar yaparsanız daha da pratik bir uygulama haline gelebilir. İlk halinin uygulamasını kullanacak olursanız o kadar verimli bir algoritma değildir, ama yaptığınız şey standart türde uygulamalarsa ve bir şeyin koşma süresini biraz geliştirmek istiyorsanız, çabuk sıralama çok uygun bir araç haline gelebilir. Bunun nerelerde kullanılacağından az sonra bahsedeceğim; evet bu böl fethet paradigmasına uyan bir algoritmadır.

---Bunun birinci adımı bölmektir. Bu işi eldeki dizilimi partition’lara yani bölüntülere ayırarak yapıyor.Yani girdi dizilimini pivot dediğimiz bir elemanın etrafında 2 altdizilim halinde bölüntülere ayırıyorsunuz

Bu iki bölüntüden ilki, soldakindeki tüm elemanlar, pivot yani x’den küçük eşit, ve sağ alt dizilimdeki elemanlar ise x’den büyük veya eşit oluyor.

Bunu bir şekille girdi dizilimi üzerinde açıklayacak olursak, bu bölüntü alımına bir x elemanı alınıyor, pivot elemanıdır bu, ve bölüntünün bu bölgesindeki elemanlar, x’e eşit yada küçük, bu bölüntü adımından sonraki, buradaki elemamlar ise x’den daha büyük yada eşit oluyorlar.

---Bundan sonra fethetme adımı daha kolay hale geliyor öyle ki sadece bu iki altdizilim özyinelemeli olarak aynı yöntemle sıralanıyor. Yani x’ e eşit yada daha küçük olan elemanları özyinelemeli olarak sıralıyorum veya x’ e eşit veya daha büyük olan elemanları özyinelemeli olarak sıralıyorum.

---Sonunda sonra bunları birleştirmek önemsiz bir iş. Bu birleştirmeden önce x’e eşit veya küçük olan elemanları sıraladığım için ondan sonra da x’e eşit veya büyük olan elemanları sıraladığım için iki liste de sıralanmış durumda; böylece bunların birleşmesi için çok önemli bir iş gerekmiyor.

---Quicksort ya da çabuk sıralamadaki anahtar adım bölüntülere ayırmadır. Bütün işin çoğu burada yapılıyor; bu durumda siz çabuk sıralamayı bir özyinelemeli bölüntülere ayırma olarak düşünebilirsiniz. Yapılan tüm iş bu.

Birleştirerek sıralamadaki ana iş özyinelemeli birleştirme yaparken, çabuk sıralamada ise bunun tersine özyinelemeli bölüntüler elde ediliyor Buradaki anahtar olay, bölüntü alt yordamının doğrusal zamanda, yani Θ(n) olması. Şimdi bunun sözde kodunu yazacağım, buradaki, kod kitaptakinden biraz farklı. Kitapta da bir tane var, aslında kitapta da biraz daha farklı bir problem göreceksiniz ama temelde ikisi de aynı fikir etrafında oluşturuluyor.

---Özyinelemenin bir aşamasını ele alalım ve, buradaki A diziliminin p ve q arasındaki parçası için (A [p,q] bölüntüsünü bakalım. Burada baktığımız şey, A altdiziliminde [p,q] arasındaki değerler; burada biz pivot olarak bu aralıktaki ilk eleman olan A[p]’yi seçiyoruz. Bilginiz için kitapta p yerine q olarak seçilmiş, ben burada p’yi kullanacağım; aslında bir şey fark etmez. Bundan sonra p için bir indeks oluşturacağız ve onun etrafında bir döngü kuracağız. Kodu işte bu; temelde bu bir for (için) döngüsü ve ortasında if (eğer) eğer komutu var.

Bu bölüntü adımında algoritmanın yapısı şöyle görünecek:

Biz pivot olarak ilk elemanı tanımlıyoruz; ---burası p ve şurası da q. ---Bu bizim döngümüzün değişmezi olacak. Bu döngü çalışırken herhangi bir anda elimde indeks değeri en fazla i olan bölgede x’den küçük eşit elemanlar olacak. Aynı biçimde indeks değeri en fazla (j-1) olan bölgede de x’e eşit ya da büyük elemanlar da olacak; bunun dışındakiler hakkında bir bilgim yok. Bu nedenle i=p olarak başlıyorum ve j=(p+1) olarak başlıyorum. Bu şekilde işlem (p+1) den başlıyor ve x’in buradaki değeri dışında hiçbir şey bilinmiyor. Bu işlemin anafikri, değişmezin sonuna kadar korunacağına göre, ve bunu yapmasının yolu da bu döngü içerisinde ilerlerken bir A(j) değerini alıyor ve bunun x’den büyük olup olmadığına ya da eşit olup olmadığına bakıyoruz. Af edersiniz bunun x’den küçük ya da x’e eşit olup olmadığına bakıyor; eğer bu değer x’e eşit ya da ondan büyükse hiçbir şey yapmıyor. Çünkü o durumda, eğer bu x’e eşit ya da ondan büyükse, o zaman tekrar döngüsüne giriyor, bu sınır değişiyor ve döngü değişmezi geçerliliğini koruyor. Eğer değişmezimi muhafaza etmek istiyorsam ve bu sonraki eleman x’e eşit veya ondan küçük ise bir problemim var demektir. Bu durumda yaptığı şey “pekiyi öyleyse, bu sınırı biraz kaydırayım ve x’e eşit veya ondan büyük bu elemanla x’ e eşit veya ondan küçük şu elemanın yerlerini değiştireyim.” Bu yöntemle şu altdizilimin boyutunu değiştiriyor ve değişmezin geçerliği sağlanııyor. Aslında oldukça basit bir algoritma..

Evet, aslında hem çok sıkı hem de kolay bir algoritma; bu nedenle bu kod çok önemli bir kod, çünkü çok verimli çalışıyor. Şimdi prensipte n elemanı üzerindeki koşma süresi, Teta(n) düzeyinde, çünkü ben temelde n sayısında eleman üzerinde çalışıyorum ve her birisiyle sabit miktarda iş yapıyorum; sonra dışarıda da sabit miktarda iş yapıyorum. Onun için bu çok akıllı bir kod parçası, aslında bölüntülere ayırmanın prensibi de kolay degil mi? Eğer işlemi olduğu “yerde” yapma kaygısı olmasaydı, o zaman bunu yapmak çok kolay olurdu; bir elemanı ele alırdım ve o elemanı diğerlerinin hepsi ile karşılaştırırdım. Bir tanesini bir kutuya, diğerini de öteki kutuya atardım. Bu kesinlikle doğrusal zamanda olurdu ama genellikle bunu teorik olarak bu yolla yapmanız demek, sonunda elinizde iyi bir kod var anlamına gelmez. Ama bu kod aslında işlemi kendi yerinde yapmaya izin veriyor. Bunun özellikle iyi bir algoritma olmasının sebeplerinden biri de sabitlerin iyi seçilmiş olması; biz asimptotik çözümleme yaparken sabitlerle ilgilenmiyoruz ama aslında kod yazmaya başladığınız zaman sabitlerle ilgilenmek zorundasınız. Ama başlangıçta sabitlere çok zaman ayırmak yerine algoritmanızın bütününün hızlı olup olmadığını anlamanız gerekir.

Size bu yöntemin bir özetini vermek için şurada bir örnek yapacağım, ---burada öylesine uydurduğum bir örnek dizilim var, ve burada biz x’i yani pivotu ilk eleman olan 6 olarak belirliyoruz. Şimdi bu algoritmanın nasıl çalıştığına bakalım:

Başlangıç koşullarında i burada başlıyor ve j de şurada başlıyor; ve yaptığımız şey sağa doğru taramaya başlamak. Aslında kod, j indeksini birer birer artırarak önüne pivot’a eşit ya da ondan daha küçük bir değer çıkana kadar dizilimi sağa doğru tarıyor. Bu şartı sağlayan değer 5’dir. Ondan sonra kod bu iki değerin yerlerini değiştiriyor; bu şekilde.

---Böylece elimizde oluşan dizlim değerleri 6,5,13,10,8,3,2,11 olur. Bu arada i değeri bir artar ve j bıraktığı yerden işe devam eder ve elimizde pivottan daha küçük veya ona eşit bir değer olana kadar sağa doğru taramaya devam ederiz. Bu durumda bu değer 3; biz 3 ile 5’in yerini değiştiririz ve ---6,3,13,10,8,5,2,11 elde ederiz. Bu aşamada bu sefer i’ yi artırmaya devam ederiz ve j ile de buradan başlarız ve bu durumda karşımızda x’den daha küçük olan veya ona eşit olan bir şey olur. Sonra bu ikisinin değiş tokuşunu yapacağız; bir dakika burada hata yaptım değil mi? Ne yaptım ben, yanlış şeyleri değiş tokuş yaptım değil mi? Hah ne yazık ki bir bilgisayar değilim; iyi, değiştirmemiz gereken şey şuydu değil mi? Değiş tokuşa girmesi gereken (i+1) olmalıydı, değil mi? Önceden ben i’ yi değiştirmiştim oysaki (i+1)’i değiştirmem gerekiyor. Onun için şu ana kadar olan her şey yanlış, şimdi doğru şeylerin yerlerini değiştirelim: Elimizde 6,5,3,10,8,13,2,11 var; hayret edilecek şey benim notlarımda da yanlış yazılmış olması.. Bu i, bu da j ve şimdi baktığımızda pivottan küçük eşit olan bir şey görebiliyorum. Bu nedenle bunun ve (i+1)’in değiş tokuşunu yapacağız ve böylece elimizde 6,5,3,2,8,13,10 ve 11 olacak ve bu noktada da i’yi ---şuraya artıracağız. Bu sırada j buraya gidiyor ve j sona kadar gidiyor ve döngü duruyor. Döngü durduğu zaman yapmamız gereken bir değiş tokuş daha olacak; bu durumda pivot elemanımızı iki alt dizilimin arasına yerleştiriyoruz. Burada bununla şunu değiştiriyoruz ve bu da bize 2,5,3,6,8,13,10 ve 11 i veriyor. Buradaki pivot da şu ve burada gördüğünüz her şey pivottan küçük eşit ve burada gördüğünüz her şey de pivottan büyük eşit. .

Evet, Quicksort yani çabuk sıralama yordamı bu. Bu bölüntü yordamını bir kez elde ettikten sonra çabuk sıralama kodunun yazılması kolaydır. ---Burada return i yazmam gerekiyordu değil mi? Çünkü pivotun indeksi olan i değerinin döndürülmesi gerekiyor; burada ben pivotun son bulunduğu yerin indeksi olan i değerini döndürmeliyim ki bir sonraki bölüntüyü tanımlayabileyim. Özür dilerim; Sonuçta bu değer Partiton (A, p, q) çağrısı ile r’ye atanıyor ve ondan sonra bölüntülerden (A, p, r-1) in; ve ardından (A, r+1, q)’ya kadar olan kısımların çabuk sıralamasını yine özyinelemeli olarak yapıyoruz. Hepsi bu işte, kod bu.

İlk hal, ilk çağrı, (A, 1, n) nin çabuk sıralamasını bulmak; ama bölüntü yapmış olmamız nedeni ile iki bölümü yani soldaki ve sağdaki bölümleri ayrı ayrı çabuk sıralamanız gerekiyor. Bu arada sınır durumunuzdan da bahsetmemizde yarar var; eğer burada 0 veya1 eleman varsa, ki olabilir, bu durumda yapılacak hiçbir şey olmaz, çünkü dizilim ya boştur ya da sadece bir elemanı olduğundan zaten sıralıdır.

Çabuk sıralamayı hızlandırmak için yapılabilecek numaralardan ya da ince ayarlardan biri dizilim bölüntüsünü içerisinde az sayıda eleman olması durumunda özel amaçlı bir sıralama yordamı geliştirmektir. Örneğin, elinizde sadece beş elemanınız varsa, bu kadar yinelemeyi yapmak yerine bu beşini çözümlemek için başka bir kod yazabilirsiniz. Kodlamaların başka türleri de var; bu koda kuyruk özyinelemeli kod deriz ve bunlarla siz tail recursion optimization yani kuyruk özyineleme iyileştirmesi yapabilirsiniz. Bu kodu hızlandırmak için bunun dışında da başka optimizasyon ya da en iyileme yöntemleri vardır; evet daha da iyileştirmek için orasında burasında biraz ince ayar yapabilirsiniz ama özünde burada açıklananlar bu verimli bölüntü yordamının çekirdeğidir, yada ana damarıdır. Algoritması budur. Bunun ne kadar hızlı çalıştığını ölçümlemek aslında biraz zor bir iştir, bu çözümlemeyi yaparken bütün elemanların birbirinden farklı olduğunu var sayacağız. Aslında elimizdeki kodun tekrarlanan elemanlar varsa o kadar başarılı olmadığını görürüz. Böyle bir durumda Hoare’nin orijinal bölüntü yordamı bundan çok daha verimli; yani sıralamanızda tekrarlar, ya da duplikasyonlar varsa..

Size Hoare’un orijinal yordamına bakmanızı öneririm; bölüntü yordamı için çok daha karmaşık bir değişmez yapısı var ama aynı şeyi yapıyor, yalnız biraz daha karmaşık. Eğer sayıların bazıları aynıysa, o zaman bunları farklı hale getirmek için yapılacak işler var ama Hoare’un kodunu kullansanız da olur; Çünkü Hoare’un orijinal kodu tekrarlayan sayılar durumunda oldukça iyi çalışır.

Ama bu örneğin anlaşılması daha kolay.

--Diyelim ki n elemanı üzerindeki en kötü koşma süresi T( n) olsun; bu durumda en kötü durum nedir? Yani çabuk sıralama için en kötü durum ne olacaktır?

---Doğru, eğer pivotu seçerken buradaki her şey bundan küçük veya her şey bundan büyük olursa, o zaman dizilimi bölüntülere ayırmada pek başarılı olamazsınız. Bu ne zaman olur? Bunu ortaya çıkaracak orijinal girdiler nelerdir?

--Eğer girdi sıralanmış veya tersten sıralanmışsa..

Bunu anlamak önemli çünkü en çok yapılan işlem zaten sıralanmış olan veya kısmen sıralanmış olan listelerin sıralanmasıdır. Ama bazen bu sıralanmış olabilir ve birileri bunu kontrol etmek ister yani bunun sıralı olup olmadığına bakmak yerine yeniden yapalım diyebilirlerler.

--Bu durumda bölüntünün bir tarafında hiç eleman olmaz; bu durum için biz özyinelemenin nasıl yazılacağına bakalım.

Elinizde T(n) var; eğer bir tarafta hiç eleman yoksa buraya T(0) diyebiliriz; bu durumda öteki tarafta da T(n-1) olur. Şimdi özyinelemeyi buna göre yazıyoruz: bir tarafta hiç eleman yok, diğer tarafta (n-1) eleman var. Bu ana kadar bütün bölüntüler ve kayıtlar Teta(n) düzeyinde;

---öyleyse T(0) nedir? Asimptotik olarak T(0) nedir? Evet, Bu bir sabittir yani 1 düzeyindedir.

Yani Θ(1) + T(n-1) + Θ(n) düzeyinde; aslında Θ(1), Θ(n) düzeyi içinde yok edilebilir ve biz T(n)= T(n-1) + Θ(n) diyebiliriz. Pekiyi, bu neye eşittir? Evet, bu Θ ()’dir. Neden Θ()’dir? Evet, çünkü bu bir aritmetik seridir. Aslında biz araya yerleştirme sıralamasında bu yaklaşımı görmüştük, aynı araya yerleştirme sırasında olduğu gibi bu bir aritmetik seri.

Bütün bu işleri yaptık, elimizde çabuk sıralama diye bir algoritma var ve görüyoruz ki bu araya yerleştirme sıralamasından daha hızlı değil. Ancak ben buna iyi bir algoritma demiştim. Buna iyi bir algoritma dememin sebebi bunun ortalama durum zamanının yani average case time‘ın çok iyi olmasıdır; şimdi bunu göreceğiz.

Ama şimdi durumu daha iyi anlamaya çalışalım ki, ortalama durumda ne olacağı ile en kötü durumda ne olacağı arasındaki farkı kavrayabilelim.

--Bunun için bir özyineleme ağacı çizelim ve bu T(n)=T(0)+T(n-1)+cn sabiti ile yazalım; bu şekilde neler olacağını sezmeye çalışalım. Yani bir sabit çarpı n..

Buraya T(n)’i ve sabiti cn olarak yazalım; ondan sonra buraya T(0)’ı koyalım ve buraya da T(n-1)’i yerleştirelim.

Şimdi ben biliyorum, hepiniz çok hızlısınız ve hemen tam ağacı görmek isteyeceksiniz ama size bir tavsiyem var; birkaç dakikayı bu ağacı yazmaya ayırın. Bu ağaç üstel olarak büyüdüğünden küçük durumları yazmak size belli bir yazma ek zamanı çıkaracak ama, geliştirmeye çalıştığınız şekli kavradığınızdan tam emin olmalısınız.

Onun için buraya bir ara adım daha yazacağım. Burada T(0) var, bu şimdi c(n-1) oluyor ; bundan sonra bir T(0)’ımız daha var ve yanına T(n-2) geliyor. Buna nokta nokta noktalarla devam ediyoruz. Bunların hepsi en üstte cn’e eşit ve bir düzey altında T(0) ve c(n-1) var; burada T(0) ve c(n-2) var; yine T(0) ve aşağıya doğru noktalar devam ediyor; sonunda Θ(1) elde edilene kadar.

Bu ağacın yüksekliği ne acaba? Buradaki bu ağacın yüksekliği nedir? ---Evet,n, güzel. Çünkü her adımda buradaki bağımsız değişkeni 1 azaltıyoruz. Bu nedenle yükseklik n’dir. Bunu çözümlemek için öncelikle buradaki her şeyi toplayalım. Buradakilerin nereden geldiğini anlamaya çalışırsak, bu Teta içinde, k 1’den n’e kadar ck’ların toplamıdır; Burada olan değerler budur. Ve bu da Teta(n²) ‘dir.

Bizim aritmatik serimiz işte buradan geliyor; evet, bu Teta(n²). Ve burada olan diğer şeylerin hepsi Θ(1). Bunlardan kaç tane var? Burada n sayısı kadar Θ(1) var.

---Böylece toplam miktar, yer kalmadı, yukarıdaki kısmı kullanayım tahtada, T(n) = Θ(n) + Θ(n²), yani sonuçta T(n), Θ(n²)’e eşit. Bu yineleme ağacının yapısına bakacak olursak çok dengesiz bir özyineleme ağacı olduğunu görürüz.

Şimdi size hiçbir zaman yapmamanız gerektiğini söylediğim bir şey yapacağım. Yapacağım şey de en iyi durum analizi. Bunu sadece önsezi için yapacağız. Biliyorsunuz genelde biz en iyi durum analizleri yapmayız. Aslında bu yapacağımız işlemin önseziyi geliştirmekten başka hiçbir anlamı yok.

--Ayrıca temelde matematiksel olarak hiçbir anlamı da yok, çünkü bize hiçbir garanti sağlamıyor. Onun için en iyi durum analizi sadece önseziyi geliştirmek için..

---Eğer gerçekten şanslıysak, nasıl bir bölüntü elde ederiz? Yani şanslı durum hangisi? Evet, tam ortadan ikiye bölünebilmesi. Yani aslında bölüntülerde n/2 ve n/2 durumunu elde etmek. Aslında gerçek değerler (n)/2 ve (n-1)/2 ama bu işi sadece önsezi için yaptığımızdan bu tip detaylar konusunda fazla kafa yormuyoruz.

Çünkü bunu. en iyi durumun önsezisi için yapıyoruz ve en iyi durum analizi bizim istediğimiz bir şey değil. Eğer bu gerçekleşirse nasıl bir özyineleme elde ederiz? Her seferinde tam ortadan 2 ye bölünebildiğini hayal edin, o zaman ne olur?

Evet o zaman T(n) = 2 tane T(n/2) + Θ(n) düzeyinde bir şey olur; Θ(n) bölüntüler ve ek işleri ifade eder. Pekiyi, bu özyinelemenin çözümü nedir? Evet, Bu özyinelemenin çözümü nlogn’dir; yani birleştirerek sıralama özyinelemesinin aynısıdır.

Bu master teoremin yani ana teoremin hangi durumudur? Doğru, ikinci durumu. Çünkü n’in 2’nin 2 bazında logaritmasını alırsak bu n’in birinci kuvveti demektir. Ve bununla aynı şeydir, böylece biz ekstra logn’i buna eklemiş oluruz. Ana teoremin 2. durumu. Bu iyi bir şey. Yani bu demek ki en iyi durumda çabuk birleştirme iyi sonuç verecek gibi görünüyor.

--Bu bölüntü işleminin, her zaman 1/10 . 9/10 biçiminde bölüntülendiğini varsaysak.. yani 1/10 kere n ile 9/10 kere n. Bu durumda biz şanslı mı yoksa şanssız mıyız? Yani söylemek istediğim şey bölme işlemi bu kadar oransızsa aslında şanssız olacağız, değil mi?

Çünkü o zaman diyelim ki durum 1 den n ye kadar olacak ve tam ortadan bölünebiliyorsa bu nlog’dir. Peki 1/10 e 9/10 durumunda ne elde edebileceğimizi düşünüyorsunuz? Şanslı mıyız, şanssız mı? Burada biraz demokrasiye başvuracağım. Kimler bunun şanslı bir durum olduğunu söylüyor? Yani koşma süresinin hızlı olacağını düşünüyor. Pekiyi, kimler bunun şanssız bir durum olacağını söylüyor? Tamam biraz cesaret gerekiyor. Kaç kişi oy kullanmadı? Haydi, oy kullanın. Tamam kararınızı verin. Burada evet veya hayır demek, doğru ya da yanlış olmak her zaman iyidir, çünkü o zaman cevaba bir duygusal bağlılığınız olur ve ileride bunu daha iyi hatırlarsınız. Onun için orada oturup sessiz kalmayın. Siz duygularınızı her şeyi daha iyi hatırlamak için kontrol edemezsiniz. Onun için bu konuda fikrini belirten ya da oylamaya katılanlar katılmayanlara göre doğru da olsalar yanlış da olsalar her zaman daha kazanırlar

... Haydi şimdi duruma bakalım; yineleme burada.. T(n)= T(1/10 n) + T( 9/10 n) + Θ (n) ve sonra da bunu çözümlemek üzere Θ (n) bölümünün bir cn ‘e küçük eşit olduğunu varsayacağız. Bunun için bir özyineleme ağacı yapacağız ve bakacağız.

--Özyineleme ağacı burada. Elimizde T(n) = cn var; sonra T(1/10 n) ve T(9/10n). Tepede yine cn’yi görüyoruz; karmaşıklaşıyor değil mi?

Bu cn’in 1/10’u olur. Şimdi şu tarafta 1/10’numuz var; bunu özyinelememizin içine uyguladığımızda burada T(1/100n) elde ediyoruz. Burada da T(9/100n) elde ediyoruz. Burada elimizde 9/10 cn var. Bu bize T(9/100 n)’i tekrar veriyor. Ve burada da T(81/100 n) elde ediyoruz, ve bu şekilde devam ediyoruz.

Şuraya sıkıştırmaya çalışayım. Önce cn var; altta 1/10 cn var. Bu yolla bir aşağıya indiğimizde 1/100 cn elde ediyoruz ve bu işlem aslında en altta Teta(1) elde edene kadar devam ediyor. Sağda 9/10 cn var. Bir altında 9/100 cn olacak ve bu da şimdi 9/100 cn olacak. Ve bu da 81/100 cn olacak ve bu bütün bu işlemler aşağıda Teta(1) elde edilene kadar sürdürülecek.

Ama buradaki yaprakların yapısı tekdüzey değil, değil mi? Bu taraftaki işlemler diğerinden çok daha uzun sürüyor. Çünkü burada her seferinde 9/10 aşağıya iniyoruz; o zaman buradaki yolun uzunluğu ne olur? Bu yolun uzunluğu..

Yani soldaki yolu ele alacak olursam aşağıya kadar yolun uzunluğu ne olur? Orada birisi el kaldırdı, evet? Doğru, 10 tabanına gore log(n). Çünkü her seferinde 10 faktörüyle bunu kesiyorum ve bunu en aşağıda 1’e kadar indirgemek ne kadar sürer diye sorduğumda, bu aslında 10 tabanlı logaritmanın tanımı oluyor. Pekiyi bu nedir? Bu yol ne kadar sürecek? n’in logaritması; daha doğrusu n; çünkü her seferinde 9/10 oranında aşağıya doğru gidiyoruz.

Aslında bu n’nin tanımı. Yani bu arada her şey, 10 tabanında log(n) ki haliyle 10/9 tabanı log(n) arasında. Yani bu aradaki her şey bu değerlerde. Şimdi burada birleştirerek sıralamada yaptığımız numarayı yapacağız, ve bunun değerlendirmesini düzeylerin yukarıdan başlayarak maliyetlerini topladıktan sonra ele alacağız.

--Bu sadece cn dir. Peki bundan sonraki düzeyin maliyeti nedir? O da cn dir. Bundan sonrakinin maliyeti nedir?. cn dir. Yani her seviyede aslında biz aynı miktarda iş yapıyoruz ve bu şekilde bütün hat boyunca aşağıya doğru iniyoruz. Sona doğru, artık bu değer cn ye eşit olmuyor; cn’e küçük eşit olmaya başlıyor. Çünkü bu düzeylerden itibaren bazı yapraklar hesaptan düşmüş oluyor.

Temelde bu yolda belli bir düzeye kadar 10 tabanlı log(n) oluyor; ondan sonra da cn’den daha küçük ya da ona eşit değerler elde ediyoruz. Ve sonunda bütün bu değerleri topluyoruz.

Yani T(n), cn’nin bir şeyle çarpımına eşit ya da küçük. Pekiyi, bu şey nedir? Buradaki en uzun yol ne olacaktır? Bu n nin 10/9 tabanında log(n)’i. Artı bunlara ilaveten eklememiz gereken yapraklar var. Ama bütün bu yaprakların toplamı da aslında n düzeyinde; böylece n düzeyinde olan tüm yapraklar + Θ(n)’ i elde ediyoruz. Bu durumda bu ne eder?

--Yani bütün bunları birbiri ile toplayacak olursam bu asimptotik olarak nedir? Bu n log n dir. Yani T(n) aslında n log n ile sınırlıdır. Şanslıyız. Şanslı olduğumuzu tahmin edenler haklı çıktı. Yani 1/10 a 9/10 bölmesi aslında asimptotik olarak %50 ye %50 bölmesi kadar iyi bir sonuç veriyor. Bunu bir alt sınır olarak bile tanımlayabiliriz; buradaki şeylere sadece bakarak T(n)’nin aslında cn çarpı n’in 10 tabanında log(n) gibi bir değerle sınırlandığını görüyoruz. Yani bu durumda T(n) asimptotik olarak n log(n) tarafından da alttan sınırlanıyor. Böylece T(n) aslında Θ(n log n)’e dönüşüyor.

Şimdi bu gerçek bir kanıtlama değil. Ben gerçek bir kanıtlama için bu tip şeyleri yapmamanızı öneririm. Bu, yineleme ağaçlarının yapılarının önsezisinde yararlı olabilir. Pekiyi, bunu nasıl kanıtlayacağız? Yerine koyma metoduyla. Doğru. Yani yapmanız gereken şey bu yöntemi tahmininiz için kullanmak ondan sonra da tahmininizin doğru olduğunu kanıtlamak için de yerine koyma metodunu kullanmak. Çünkü bu ilk metodla hata yapma ihtimaliniz oldukça yüksek. Hata yapma olasılığı çok yüksek. Yerine koyma metodunda ise hata yapmanız daha zordur; çünkü orada uğraştığınız şey cebirin kendisidir. Cebirle kanıtlama, bu yöntemde yapabileceğiniz nokta nokta hatalarından, yanlış çizilen ağaçlardan ve yanlış girilen değerlerinizin daha kolaydır. Tamam mı? O halde bu n log n’ dir ve bu çok iyi bir şey. Düzeyin n log n olması güzel ve biz şanslıyız.

Şimdi başka bir şey deneyelim. Bunu yine önsezi için yapacağız. Size şimdiden söyleyeyim, bu dersin sonunda hepiniz kapıya doğru koşacaksınız. Çünkü bugün iyi matematik uygulamaları da yapacağız. Bu aslında bana göre eğlenceli bir matematik, ama sizi aynı zamanda sizi zorlayacak. Şu anda uyanık değilseniz uyumaya devam edebilirsiniz ama size ne zaman uyanmanız gerektiğini ben söyleyeceğim. Bir önsezi uygulaması daha yapalım; diyelim ki adımların sırasını değiştirdik.

Öncelikle bölüntü işlemini yaptığımızı varsayalım. Bu işlemde şöyle bir durum olduğunu düşünelim: Şanslı bir seçimle başladık. Sonra bir bölüntü adımı olsun ve bunda şanssız olalım. Ondan sonraki adımda yine şanslı olalım. Sonra yine şanssız olalım ve ağaç boyunca aşağıya kadar şanslı şanssız, bu şekilde sürsün.

--Yani alternatif olarak bir şanslı bir şanssız gittiğimizi düşünelim. Bunun sonucunda şanslı mıyız, şanssız mıyız? Bu sefer herkesin oy vermesini istiyorum; vereceğiniz yanıtın doğruluğu veya yanlışlığı önemli değil. Bu oyunda herkes rol alacak. Bunu bir at yarışı gibi düşünün. Hiç at yarışı seyrettiniz mi? Yarış sıkıcıdır ama buna birazcık para yatırırsanız yani ganyan gibi bir şey oynarsanız, at yarışı ilginç hale gelir. Burada da aynı şey olacak. Bu oyunda herkesin bir şeyler katmasını istiyorum. Kaçınız bu işte şanslı olacağınızı düşünüyorsunuz? Kaçınız bu işte şanssız olacağınızı düşünüyorsunuz?. Tamam, oy vermeyenler kimler? Sizler, oyuna katılmadınız ha. Şimdi bunu çözümlemeye başlayalım ve bir özyineleme yapalım.

Şanslı adımımızda n boyutunda bir işlemin koşma süresi L(n) olsun. Ve bu 2 defa olacak. Ondan sonraki adımın şanssız olduğunu düşünelim. Yani bu 2U(n/2) +Teta(n). Bu bizim şanslı adımımız. Şanssız adım yani U(n) = L(n-1) zira ondan sonraki adım şanslı adım olacak artı Θ(n). Bu şanssız adım. Bu sistemin davranışını özyinelemelerle nasıl anlattığımı görüyor musunuz? Burada sınır koşullarına bağlılık kesin belirlenmiş değil, ama sabit girdilerde özyinelemenin sabit bir çözümü var. Şimdi yerine koymayı yöntemini kullanarak biraz cebir yapacağız.

L(n) neye eşit bir bakalım. Buraya ben U(n/2) yerine buradaki değerini yerleştirebilirim. Bu bana L(n) = 2 ( L(n/2 -1) + Θ(n))+ Θ(n) yi verecektir. Burada ne yaptığımı görüyor musunuz? U(n/2) ler için şu yinelemeyi yerine koydum. Aslında teknik olarak söylemem gereken Θ(n/2) ydi. Bunu daha açık anlatabilmek için Θ(n/2) kullanmam gerekirdi. Aslında bu aynı şeydir ama adım atlamamak için böyle yapıyorum. Şimdi bunu işlem sürecince yürütebiliriz. Ve böylece 2L(n/2-1) ve şimdi burada 2 tane Θ(n/2) ve şurada da bir tane daha var; bunların hepsinin toplamı Θ(n) . Pekiyi, bu özyinelemenin çözümü nedir? nlogn, yani Θ(n log n). Herkes bunu görebiliyor mu? Tamam. Θ(nlogn). Bu aslında temelde master teorem yani ana teorem ama birazcık şurasında oynadık; oradaki eksi 1, master teoremin çözümünde bize yardımcı olur. Ne demiştik? Bu n log n düzeyinde; yani ---şanslıyız. Eğer şanslı olmakla şanssız olmak arasında dönüşümlü olarak bir değişiklik yapıyorsak, biz sonuçta yine şanslıyız.

Peki genelde şanslı olmayı nasıl garanti edebiliriz? Eğer girdi sıralıysa bu şansız olacağım demektir. Af edersiniz. Evet elemanları rastgele düzenleyebilirsiniz. Yollardan birisi budur. Bundan başka yol nasıl bir yol seçebiliriz? Aslında söylediğiniz oldukça iyi bir yol ve genelde yapılması gereken şey. Pivotu rastgele seçmek. Doğru. Aslında işin sonunda iki yöntemin de aynı verimlilikte oldukları görülür ama burada biz pivotu rastgele seçmeyi ele alacağız çünkü bu yolla çözümlememiz daha kolay olacak. Ama algoritmanın etkinliği açısından birbirine eşittirler. Bu bize rastgele çabuk sıralama algoritması olarak adlandırılan Randomized Quicksort’u verir. Ve rastgele seçilmiş çabuk sıralama algoritması ile ilgili güzel olan şey, bunun koşma süresinin girdi sırasına bağlı olmayışıdır. Aslında girdiyi karıştırarak da girdi sıralamasından bağımsız hale getirebilirim; eğer girdiyi istediğim gibi karıştırırsam girdinin sırasının ne olduğunun önemi kalmaz. Öte yandan orijinal çabuk sıralamanın bazı yavaş durumları vardı; anımsarsanız girdinin sıralanmış olması veya girdinin tersten sıralanmış olması işi yavaşlatıyordu. Ama bazı hızlı durumları da vardı. Sonuçta görülür ki eğer girdi rastgele sıralanmışsa, o zaman çabuk sıralama hızlı bir performans gösterir.

Eğer girdiyi rastgele karıştırırsam veya rastgele bir elemanı pivot olarak seçersem, girdinin ne olduğunun bir önemi kalmaz. Bunu hayal etmenin yollarından biri, bir rakibiniz olduğunu düşünmektir. Şöyle bir durum düşünün. Bir rakibiniz var. Siz diyorsunuz ki “benim sıralama algoritmam iyidir” ve o da “benim de iyi bir sıralama algoritmam var” diyor ve aynı müşteriye siz bunu satmaya çalışıyorsunuz. Bunun üzerine müşteri de diyor ki “tamam arkadaşlar o zaman ikiniz de diğerinin algoritması konusunda benchmark’ lar oluşturun. Bu şekilde onun algoritmasını görüyorsunuz. Rakibinizin algoritmasına baktığınız zaman, çabuk sıralama kullandığını anlıyorsunuz ve “ben onu nasıl yenebilirim?” diyorsunuz. “Bu durumda zaten sıralanmış olan bir girdi veririm” diyorsunuz; ona yapabileceğiniz şey budur. Eğer sizinki de çabuk sıralamaysa, onun da size uygulayacağı benchmark testi budur. Bu durumda onu nasıl yenebilirsiniz Randomization yani rastgelelikle. Buradaki anafikir, eğer sıralamada rastgele permütasyon yaparsam veya rastgele yerlerde pivot seçersem, bu durumda girdi sırasının öneminin kalmaması önemlidir. Bu durumda benim kodumu yavaşlatmak için rakibimin yapabileceği herhangi bir kötü sıralama yoktur.

Bu durumda şanssız olabilirim ama şanssızlığım benim rastgele sayı yaratıcısından kaynaklanır; bu da girdi ile ilgili bir şanssızlık değildir. Girdinin ne olduğunun hiç önemi olmaz. Bunu herkes takip edebiliyor mu? Yani rastgele çabuk sıralamanın güzel yanı girdi dağılımı ile ilgili herhangi bir varsayıma dayanmamasıdır. Bu durumda siz bütün girdilerin aynı olasılıkta olduğunu varsaymak zorunda değilsiniz; çünkü dilerseniz bunu böyle yaparsınız veya öyle bir pivot seçersiniz ki, bütün içerisinde etkin sonucu alırsınız. Böylece hiçbir seçilmiş girdi en kötü davranış durumunu yaratmaz. En kötü durum sadece rastgele sayı yaratıcısı aracılığı ile belirlenir. Ve en kötü durum sadece rastgele sayı yaratıcısı ile belirlendiği için aslında biz bu şanssızlığı matematik olarak sınırlayabiliriz. Şunu sorabiliriz; ihtimaller nedir? Şimdi biz bunu çözümleyeceğiz ve bu noktada bu derse ait olup olmadığınızı anlayacaksınız.

Eğer daha önce Bilgisayar için Matematik (6.042) dersini herhangi bir nedenle almadıysanız bu uygulama karşılaştırmayı yapmak için uygun bir ortam olacak. Şimdi bu işlem biraz zamanımızı alacak. Onun için hepiniz neden bir süre ayağa kalkıp şöyle bir gerinme molası vermiyorsunuz? Biz aslında güzel bir matematik uygulaması yapacağız. Ve buna başlamadan önce sizin kendinizi iyi ve zinde hissetmeniz gerekiyor.

Gerinme molası bitti.

Çözümleme. Sanıyorum bunu başaracağız; aslında kendimi yarışıyor gibi hissediyorum. Bugün kapsamamız gereken epey konu var. Şimdi, T(n) nin, koşma süresinin rastgele bir değişkeni olduğunu varsayalım.

Aa, iyi de ne yaptığımı buraya yazmamışım bile. Şimdi rastgele bir elemanı pivot olarak seçeceğiz. Yapacağımız ana işlem bu. Bunu yapma yolu da, bölüntüde çalışırken, 1. bölüntüyü oluşturmadan önce, dizilim içindeki ilk elemanı başka bir elemanla, belki de kendisiyle, değiştirmek olacak; bu durumda her ikisi de pivot olmak için eşit şansa sahip olacaklar. Ondan sonra da normal bölüntüyü işleteceğim.

T(n) değişkeninin zaman ekseninde çalıştığını, ancak olasılık çalışmalarından kaynaklanan varsayımın da Rastgele sayıların bağımsız olduğu durumunu kabul edeceğiz. Bu şekilde bu algoritma çalışırken herhangi bir noktada pivot seçimi başka bir noktadaki seçimden bağımsız olmasını sağlar hale gelir. Ondan sonra bunu çözümlemek için nerede pivot seçtiğimi bilmek isterim.

k= 0,1 den ,… (n-1) e kadarken, belli bir bölüntüde değişken 1’e eşit olsun, Eğer k : n-k-1 bölüntüsü oluşturuyorsa; o zaman da bu değer 0’a eşit olsun. Yani, bölüntü yordamında pivot olması için rastgele bir eleman seçiyorum. Burada benim rastgele değişkenim oluyor. Sol tarafta k sayıda eleman sağ tarafta da (n-k-1) eleman oluşturuyorsa bu 1 sonucunu veriyor. Bunların toplamı doğal olarak n-1; çünkü elimde pivotum da var. Diğer bütün durumlarda 0 değerini alıyor. Şimdi elimde bir bölüntüde n sayıda rastgele değişkenim var; bunların hepsi 0 olacak, sadece biri, hangisi bilmiyorum, 1 değerini alacak.

Bu rastgele değişkenin adı ne acaba?

Bernoulli. Bernoulli’in başka varsayımları var; bu göstergesel rastgele değişken’ dir. Bunun adına Bernoulli denebilir ama bu bir göstergesel rasgele değişkendir ve değer olarak 0 ve 1 değerlerinden birini alır ve Bernoulli rasgele değişkenleri de belli bir tür göstergesel rasgele değişkendir. Burada biz bunlara göstergesel rasgele değişken diyeceğiz. Bir şeylerin toplamının ne olduğunu anlamaya çalıştığınızda göstergesel rasgele değişkenler iyi bir yöntemdir. Bu büyük boyuttaki rasgele değişkenleri küçük parçalara ayırarak bunların çözümlenmesini sağlar.

Buradaki göstergesel rasgele değişkene bir bakalım:

-- beklenen değeri yani E[]’nın neye eşit olacağını umuyorsunuz acaba? Başka bir şekilde sorarsam bir (k : n-k-1) bölüntüyü üretmemin olasılığı nedir? Belleklerinizi tazelemek için nın ne olduğunu ve bunun ne anlama geldiğini yazalım; ---bu nın 0 a eşit olma ihtimalinin 0 ile çarpımı artı nın 1 e eşit olma ihtimalinin 1 ile çarpımına eşittir; buradakiler zaten 0 eder. Bu durumda elimizde eşitlik olarak nın 1 e eşit olma ihtimali kalır. Ve göstergesel rasgele değişkenlerin genel özelliği bunların beklenen olasılığının 1 olmasıdır. Yani burada güzel olan şey aslında beklenen olasılığın başka terimlerin varlığına bağlı olmadan göstergesel rasgele değişkenler ile ilintisidir; öyleyse nın 1’e eşit olma olasılığı nedir? -1/n; bu durumda bütün bölünmelerin ihtimali aynıdır, yani elimde n elemanı varsa bunların her birinin pivot olarak seçilme olasılığı 1/n dir. Ve bir kez pivot seçtiğinizde de bunun solunda ve sağında kalanlar da belirlenmiş olur. Bu olasılık 1/n’dir; şu ana kadar herkes benimle birlikte mi? Aşağı yukarı,.. tamam. Yani daha önce söylediğim gibi şu andaki kavrayışınız benimle birlikte sınıfta olup olmadığınızın bir göstergesi olacak. Eve gittikten sonra bu söylediklerimi çalışırsanız ve matematik geçmişinizden dolayı konuyu anlayamazsanız, bu size dersin boyunuzu aştığını gösterebilir.

Bunun, T(n)’ nin neye eşit olduğunu buraya yazalım: T(n) = T(0) + T(n-1)+ Θ(n); eğer bölüntü 0’dan n-1’e kadarsa., aksi takdirde T(1) +T(n-2) + Θ(n)’dir; eğer bölüntünüz 1 : n-2 kadarsa. Ve aşağıda bir yerde T(n-1) +T(0) +Θ(n) haline gelecektir, eğer n-1 : 0 bölüntünüz varsa. Burada T(n)’le ilgili özyinelemelerimiz bu olacak, maalesef bu özyinelemenin zor tarafı elimizde n kadar durum olmasıdır. İşte bu noktada göstergesel rasgele değişkenlerin kullanımıyla ilgili parlak fikir ortaya çıkar. Çünkü bu durum analizini ele alıp bunu matematiksel olarak indirgeyebiliriz; göstergesel rasgele değişkenleri kullanan durumların olmadığını görürüz.

---Bunu yapmanın yolu da değişik durumları bir toplam haline getirecek bir teknik kullanmaktır. Şu iki toplam değerlerin neden aynı olduğuna bir bakalım: Göstergesel rasgele değişkeni, belirlenen bölüntünün olmaması durumunda 0 olur; bu nedenle, k’nın daha önce belirtiğimiz değer olması durumu haricindeki durumlarda bunun toplamı 0 olacaktır. Şimdi 0 ile 1’in çarpımlarının nasıl bir sonuç çıkaracağını görebiliyor musunuz? Bence bu çok akıllıca, evet, çok akıllıca; ve bu göstergesel rasgele değişkenler ile yapılan klasik bir uygulamadır. Sonuçta çok güçlü bir metot oluşturur, çünkü her ne kadar zor görünse de şimdi özyinelememiz için bir matematiksel modelimiz var.

Şimdi T(n)’in beklenen değerini çözümlemeye çalışalım; yapmak istediğimiz şey bu. T(n)’in beklenen değeri nedir?

---Bunu yapmak içinde ben T(n)’in beklenen değerinin bu büyük toplamın beklenen değerine eşit olduğunu yazıyorum. Bu noktadan sonra artık biz şu toplamanın beklenen değerini hesaplamaya başlayabiliriz; herkes benimle mi? Bu aşamada sorular var mı?

Başparmakları yukarıya doğru görüyorum; bunu görmek hoş ama bana göre aslında görmek istediğim başparmakların aşağıya dönük olmaması.. Baş parmakların yukarıya doğru olmasını görmek güzel, fakat bu birinizin anladığını veya anladığını sandığını gösterir.

Yani benim söylediğim, bunun şu aşağıdakine eşit olduğu; burada biraz daha fazla yere ihtiyacım olacak, şu eşit işaretini bu nedenle biraz kaydıracağım. Ben bu toplamanın şuna eşit olduğunu savunuyorum; bu beklenen değer bu beklenen değerlerin toplamına eşittir. Acaba neden? Bu adımı haklı çıkaracak sihirli sözcükler nedir? Linearity of Expectation, yani beklenenın doğrusallığı.. Bir toplamanın beklenen değeri beklenenlerın toplamına eşittir ve buna beklenenin doğrusallığı denir. Bunun için bağımsızlığa ihtiyacım yok; bu herhangi bir rasgele değişkenin beklenenı için her zaman doğrudur, beklenen değerlerin toplamı toplam beklenen değere eşittir, veya bunun tam tersi de geçerlidir. Burada biz tam tersini uyguladık. Bu durumda bu değer k 0’dan n-1’e kadar olan beklenen değerlerinin toplamı ile [(T(k) + T(n-k-1) + Θ(n)]’nin beklenen değerinin çarpımına eşittir. Bu neden doğru? Çünkü yaptığım şey çarpımın beklenen, çarpanların beklenenlerın çarpımına eşittir demek. Bu bağımsızlıktan kaynaklanır. Neden bağımsız? Buradaki , ki rasgele değişkendir, diğer bölüntülerin içinde bağımsızdır; yani her özyinelemeli çağrı için vardır. Yani burada olan biten her şey şurada olan bitenden bağımsızdır. Aslında biz saklanıyoruz. Elimizde bir özyineleme olduğundan aynı iş zamanını bölüntülere ayırmıyoruz; farklı bir değerle çalışıyoruz.

Aslında görünen matematiğin altında bir şeyler yapıyoruz ve buna dikkat etmeniz gerekiyor; burada T(k) aslında rasgele seçimlerin bir seti halinde ve bu nedenle buradaki değerlerin şuradakilerden farklı olduğunu anlamanız gerekiyor. Bu durumda da biz beklenen değerlerin olasılıklarını çarpabiliyoruz. Herkes benimle birlikte mi?

Bu önemli bir kavram, nın diğer rasgele seçimlerden bağımsız olması. Her şeyden önce bu güzel bir olgu, () nın beklenen değeri nedir? 1/n. Aslında bunun toplamayla da hiçbir ilişkisi yok, bunu toplamın dışına çıkarabiliriz. Çıkan sonuç, 1/n çarpı k 0’dan n-1’e, T(k)nın beklenen değerlerinin toplamı, artı 1/n çarpı k 0’dan n-1’e, T(n-k-1) beklenen değerlerinin toplamı, artı 1/n çarpı k 0’dan n-1’e, Θ(n)’lerin toplamları.. Bunu yaparken beklenen değerlerin doğrusallığından yararlandık ve burada bunu parçalara bölmek ve k’nın beklenen değerinin 1/n olduğunu çıkarmak için kullandık. Hala herkes benimle birlikte mi? Bunların hepsi kolay; zorluk burada çok fazla adım olmasından kaynaklanıyor. Bunların bazılarını eskiden görmüş olduğunuzu umuyorum,

Şimdi ikinci gözlemimiz aslında bu iki toplamanın gerçekte birbirine eşdeğer olduğu; bunlar aslında aynı toplamlar ama sıraları farklı.. Bu T(0), T(1), T(2), T(3),T(n-1)’e kadar çıkıyor; bu ise T(n-1), T(n-2), T(n-3)’den T(0)’ a kadar iniyor.

Aslında bunlar birbirine eşit; dolayısıyla elimde bunlardan iki tane var, bu durumda bu terim neye eşit olur? ---Bu neye eşit olur? Evet, neye eşit olacak? Θ(n)’e. Şimdi bunun neden böyle olduğuna bir bakalım: Θ(n)’in 0’dan n’e kadar toplamı Θ() ye eşittir ve n’e bölünür; veya burada ben Θ(n)’i dışarı çıkardığımda, Θ(n)’in n 1’den (n-1)’e toplamı 1’e eşittir. Yani hangi yöntemle giderseniz gidin sonunda n’ye ulaşıyorsunuz. Bunun böyle olmasının temel sebebi toplamların aynı elemanları içermesi ve bu da sadece cebir; başka bir şey değil.

Şimdi yapacağımız şey teknik kolaylık açısından bir uygulama; çünkü k 0 ve 1’i

teknik kolaylık sağlamak için Θ(n)’in içine alacağız. Burada elimizde n düzeyinde bir özyineleme var; ve ben k=0 ve k=1 durumlarına baktığımda beklenen değerin ne olduğunu biliyorum. 0 ve 1 değerleri için beklenen en kötü durum maliyeti sabit çünkü ben bu problemi bir sabit boyut için çözüyorum.

Ve bir varsayımız daha var: Yinelemelerin çözümündeki sınır durumlarında sürenin sabit olduğunu biliyoruz. Bu nedenle temelde bu iki terimi bunun içinden çıkarabilirim ve sonuçta olacak şey Θ(n)’in içinde birkaç sabitin daha birikmesidir. Ama bu, özyinelemenin çözümünü daha kolaylaştırır ve ben bunu yaptığımda T(n)’in beklenen değeri yani ---E[T(n)] = 2/n çarpı k 2’den n-1’ e kadar T(k)’nın beklenen değeri + Θ(n) olur.

Bütün bu çalışma özyinelemeyi çıkarmak içindi; şimdi biz bunu çözmek zorundayız.

Şu ana kadar yaptıklarımızı tekrar edecek olursak, işe bir özyineleme ile başladık ve bu bir durum komutu olan rasgele değişken içindi; sonra matematik kullanarak bunu bir durum komutu olmayan hale dönüştürdük, bir çarpım haline dönüştürdük ve bundan da beklenen değer için bir özyineleme elde ettik. Şimdi bu özyinelemeyi çözme işlemini deneyeceğiz. Yani bu özyinelemeyi anlamak için bazı basitleştirmeler yaptık ve şimdi bunu burada çözeceğiz. Bu arada ben quizlerde ve sınavlarda böyle şeyler sormuyorum; Öte yandan sizin bunu anlamanızı bekliyorum. Herhangi bir test ya da quiz’de buradaki elemanları bulabilirsiniz; bunun hesaplanması yoğun bir iş yükü ve akıllı insanların emeğini gerektirir. Bunun basit olduğunu söylemiştim ama basit bile olsa böyle bir şeyi hesaplamak konuda bilgi sahibi olan insanların çokça emeğini gerektirir.

Şimdi şuradaki özyinelemeyi çözeceğiz ve ---T(n)’in beklenen değerinin, 0’dan büyük bir a sabiti için, a çarpı (nlogn)’den küçük eşit olduğunu kanıtlayacağız. Şimdi bunu kanıtlamak için hangi tekniğin kullanılmasının uygun olduğunu düşüyorsunuz? Master metodu ya da ana metod gibi mi görünüyor? Master metoda benzemiyor. Böyle durumlarda şüpheniz varsa, sunstitution yani yerine koyma metodunu kullanın. Bu bütün diğer metotların büyük babasıdır.

Yapacağımız şey, taban durumunda yeterince büyük bir a değeri ve yeterince küçük bir n değeri seçerek, a(n lg n)’nin T(n)’nin beklenen değerinden daha büyük olmasını sağlamaktır. Daha önce özyinelemeden 0 ve 1’i çıkarmak istememin temelinde de bu yatıyordu. Çünkü mesela n sıfır olduğunda log 0, 0’a bölmek gibidir ve bu nedenle bu işlemi yapamazsınız. log1 = 0 dır; onun için burada bunu 1 ile sınırlasaydım 0 elde edecektim ve o zaman a’yı bu durumların üzerinde hakim olacak yeterince büyük bir değer olarak seçemeyecektim. Bu nedenle diyorum ki bunlar beni çok ilgilendirmiyor, teknik kolaylık açısından bu maliyetleri Θ(n) nin içine yedirebilirim ve bu sayede ben a(n log n) i yeterince büyük kabul edip taban durumu çözmede kullanabilirim; bu nedenle bir teknik varsayımda bulunduk.

--Burada klogk’ nın k 2’den n-1’e kadar olan değişimlerinin toplamı, bu da 1/2logn - 1/8 ‘den küçük eşit olması. Bunu size bir egzersiz olarak bırakıyorum. Bu egzersizin kitapta da olduğunu sanıyorum. Sizin bunu değerlendirmenizi istiyorum. Bunu hesaplamanın iki yolu vardır. Bunlardan birisi sadece toplama işlemi kullanmak ve bunu yaparken toplamı iki parçaya bölmek, toplamaların özelliklerinden yararlanmak ve yeniden yapılandırarak bu sınırlamayı kanıtlamak., İkinci yol ise toplamaların çözümünde entegral metodunu kullanmaktır. Bunu her iki yolla da kanıtlayabilirsiniz; aslında entegral metodunu kullandığınızda burada elde edeceğimizden daha sıkı bir sınır elde edersiniz. Bu temel bir bilgidir ve bunu yapmayı bilmeniz lazım.

Haydi şimdi yerine koyma metodunu uygulayalım.

---T(n)’nin beklenen değeri küçük eşit, 2/n çarpı k 2’den n-1 ‘e giderken , ak log k’ nın toplamından küçük ya da eşittir; bu noktada ak log k’ nın yerine koyma işleminin daha küçük değerler için yapacağız ve buna Θ(n)’i ekleyeceğiz. Burada zor olan şeyi anlatmam gerek; bu terimin sınırı olan (1/2 logn) i kolay elde edebiliriz. İkinci derecedeki terimi elde etmek daha zor. Ama sonuç olarak yapacağımız şeyi gerçekleştirebilmek için ikinci derecedeki terime de ihtiyaç var. Bu kanıtlamayı gerçekleştirmek için (log n)’den denklemin karesel kısmını çıkaracak durumda olmamız lazım. Ve bu toplamayı değerlendirmenin şaşırtıcı yönü de bu. Elde edilen bu ara sonucun aslında şu formülü kullanarak başka bir anlatımını biliyorum; bunu uygulayıp bu terimi 2a/n çarpı (1/2 log n - 1/8 + Θ n)’ den küçük eşit olarak elde edebilirim. Bir hata mı yaptım? log n Evet, şimdi oldu. Bu neye eşit? Birinci kısımda çarpma yaparsam, şurası (an log n) oluyor. Bunu istediğim gibi sonuçlandırmak için şimdi dikkatli olup hata yapmamalıyım. İstediğimi şu parça olarak yazıyorum; bir de eksi kalanımın olması lazım. Kalanımı buraya yazacağım parantez içerisinde, ve bu eksi olacak. Kalan buradaki terimle aynı olacağından sonuçta da an/4 olacak ve eksi Θ(n).

Bu da eğer bu bölüm pozitif ise küçük eşit a çarpı n çarpı logn olacak; .. Buranın artı olmasını sağlamak için yeterince büyük bir a değeri seçmeliyim ve an/4, Θ(n) terimini domine etsin. Buradaki değer ne olursa olsun öyle bir a değeri seçebilirim ki bu buradaki terimi pozitif yapar. Yani an/4 ün Θ(n) den daha büyük olması için a’ nın yeterince büyük olması gerekli.

Böylece rasgele çabuk sıralamanın koşma zamanı n logn düzeyinde olur. Evet şu anda kanıtladığımız şey beklenen koşma zamanının nlogn düzeyinde olduğudur. Pratikte çabuk sıralama çok iyi bir algoritmadır. Aslında birleştirerek sıralamadan üç veya daha fazla kat daha hızlıdır. Size sonuç olarak birleştirerek sıralamadaki kadar kuvvetli bir garanti vermez ama en kötü durumu nlogn dir. Öte yandan rasgele sıralamayı seçerseniz uygulamada size üç kere daha hızlı bir koşma zamanı verir. Ama bu kadar hızlı olması için kodunda biraz ince ayar yapmanız gerekebilir. Yani taban durumlarını biraz daha kabalaştırıp başka düzenlemeler de yapmanız gerekir, ama iyi sıralama algoritmalarının çoğu çabuk sıralama temeli üzerine kurulmuştur. Buna iyi çalışır denilmesinin diğer bir sebebi de sanal bellekteki cache yani önbelleklerde iyi çalışmasıdır. Burada ön bellek modelleri gibi şeyler üzerine çok fazla konuşmuyoruz ve bugünün algoritmalarında bu çok moda ama, bilmeniz gereken sanal hafızanın ön belleklerinde çabuk sıralamanın iyi sonuç verdiğidir. Bu nedenle buralarda kullanmak için iyi bir algoritmadır. Size iyi bir problem çözme saati diliyorum. Orada başka bir nlog n algoritması göreceksiniz.

Dersimiz bitmiştir.