algoritma karmaşıklığı ile ilgili.

[Fly]

4 derstir anlatıyor ancak yarısına alttan aldığım derslerin sınavı yüzünden giremedim, anlayamadığım iki soru var :

iki tane küme var, sequence bilmemne algoritması sanırım zaten ama ingilizcesini bilmediğim için bulamadım :

	f(p,q)

	{

	if (p==0 || q==0) matris[p][q]=0; return 0;

	else if (diz1[p-1]==diz2[q-1]) return f(p-1,q-1); 

	else a=f(p-1,q)

	     b=f(p,q-1)

	     return c=max(a,b)

	}

	

T(p,q)=max(O(1), T(p-1,q-1),T(p,q-1)+T(p-1,q)) gibi bir şey çıkıyor yanlış anlamadıysam, en kötü koşulda da p+q-1 defa döneceği için T(p,q-1) (veya diğeri) ve de T(p-1,q-1) ler min(p,q)-1 defadan fazla olamayacağı için O(p+q) oluyor diye anladım, yanlışım var mı ?


2. olarak ise fazladan bir matris var elimizde iki boyutlu, her hücre -1 değerini alıyor başta,

	

	f(p,q)

	{

	if (p>0 && q>0)

	then f(p-1,q); f(p,q-1); f(p-1,q-1)

	

	if (matris[p][q]!=-1) then return matris[p][q]

	else

	{

	if (p==0 || q==0) matris[p][q]=0; return 0;

	else if (diz1[p-1]==diz2[q-1]) return matris[p][q]=f(p-1,q-1); 

	else a=f(p-1,q)

	     b=f(p,q-1)

	     c=max(a,b) ; return matris[p][q]=c;

	}

	

recursive'leri hesaplama dersini toptan kaçırmıştım, google'dan anlamaya çalıştım ama en ekstrem olanı ismini şimdi hatırlamadığım en büyük sayı bulma algoritmasıydı logaritmik olan (ortasından başlıyor, N=2^k ise k defa işler falan diyip).

tıkandım bunda, yine p+q çıkıyor çünkü yanlış yaptığım hesaplara göre, sanki (pq)^2 miş gibi hissediyorum ama öte yandan önceki fonksiyonun aksine tek bir doğrultuda gitmeyip matrisin tamamını taradığı için.

yanlışlarımı düzeltebilecek olan varsa müteşekkir olurum.

[Ardeth]

algoritmaların tam olarak ne yaptığını anlayamadım ben.

birincisinde yazdığın bir fonksiyon değil mi p ve q değerlerini alan. onu ne için çağırıyorsun, bütün p ve q ikilileri için mi? biraz daha anlatırsan algoritmaları daha iyi olur. algoritma analizi dersi almadım ama az çok ne olduğunu görmüştüm bir yerde aklıma bir şey gelirse yazarım yoksa forumda vardı bir kaç csci onlar yazabilir heh

[Fly]

iki tane küme var p ve q boyutlarında,
algoritmanın yaptığı iş bu iki kümedeki en büyük sequence' ı çıkartmak

mesela (1,2,6,7,2,4) (p=6) ve (6,7,3,4) (q=4) için (6,7,4) çıkıyor, ha gerçi şu üsttekiler 6,7,4 ü döndürmüyor, uzunluğunu bulmak için sadece.

p ve q uzunluklarındaki iki küme için ortak en büyük sequence 'ın uzunluğuna Li,j dersek mesela (i ve j p ve q' dan başlıyor ikisinin de tamamına bakacağımız için), ilk fonksiyonun yaptığı :

kümelerin i ve j. pozisyonlarındaki (küme1[i] ve küme2[j] yani) sayılar aynı ise Li-1,j-1 + 1 döndürtüyor.
yok farklı ise Li-1,j ve Li,j-1 arasından max olanı döndürüyor.

ikincisinde ise i ve j' nin başlayabileceği tüm değerler için bir matris oluşturuluyor iki boyutlu. -1 değerini alıyor başta tüm hücreleri.

sırayla p-1,q , p,q-1 ve p-1,q-1 pozisyonlarındakini çağırıyor, ardından kendisinin değerini (p,q) hesaplıyor.

tabi p-1 vs olanlar önceden hesaplanacağı için -1 olmayan hücreye gelebilme ihtimali var, gelince daha fazla recursion yapmadan direk döndürüyor oradaki değeri.

yok eğer vardığı hücre -1 ise, değeri bulmak için 1. deki işlemin aynısını yapıyor, bir yandan da matrisi dolduruyor.

[Fly]

direk c kodunu koyuyorum,

	int plsc_v1(int tab1[], int taille1, int tab2[], int taille2)

	{

	

		if((taille1==0)||(taille2==0)) return 0;

		else if(tab1[taille1-1]==tab2[taille2-1])

			return plsc_v1(tab1,taille1-1,tab2,taille2-1)+1;

		else

		{

			int a=plsc_v1(tab1,taille1-1,tab2,taille2);

			int b=plsc_v1(tab1,taille1,tab2,taille2-1);

			if (a>=b) return a;

			else return b;

		}

	}

	

	int plsc_v2(int tab1[], int taille1, int tab2[], int taille2, int l[P+1][Q+1])

	

	{

		if((taille1>0)&&(taille2>0))

		{

		l[taille1-1][taille2]=plsc_v2(tab1,taille1-1,tab2,taille2,l);

		l[taille1][taille2-1]=plsc_v2(tab1,taille1,tab2,taille2-1,l);

		l[taille1-1][taille2-1]=plsc_v2(tab1,taille1-1,tab2,taille2-1,l);

		}

	

		if(l[taille1][taille2]!=-1) return l[taille1][taille2];

		else

		{

		if((taille1==0)||(taille2==0))

		{

			l[taille1][taille2]=0;

			return 0;

		}

		else if(tab1[taille1-1]==tab2[taille2-1])

		{

			l[taille1][taille2]=plsc_v2(tab1,taille1-1,tab2,taille2-1,l)+1;

			return l[taille1][taille2];

		}

		else

		{

			int a=plsc_v2(tab1,taille1-1,tab2,taille2,l);

			int b=plsc_v2(tab1,taille1,tab2,taille2-1,l);

			if (a>=b) {

				l[taille1][taille2]=a;

				return a;

				}

			else {

				l[taille1][taille2]=b;

				return b;

			}

		}

		}

	

	}

	

[Ardeth]

Fly said:

T(p,q)=max(O(1), T(p-1,q-1),T(p,q-1)+T(p-1,q)) gibi bir şey çıkıyor yanlış anlamadıysam, en kötü koşulda da p+q-1 defa döneceği için T(p,q-1) (veya diğeri) ve de T(p-1,q-1) ler min(p,q)-1 defadan fazla olamayacağı için O(p+q) oluyor diye anladım, yanlışım var mı ?

Sanırım en kötü koşulda O(pq) mertebesinden bir algoritma olacak.

Çünkü, diyelim ki (1,2,3,4) ve (5,6,7,8) dizisini al.

4 ve 8 aynı olmadığı için sırayla 8-3, 8-2, 8-1 karşılaştıralacak. Daha sonra stackte en üstteki işlem için (yani p=0 durumunda), sırayla tüm q lara bakılacak. Yani 1-7, 1-6, 1-5 karşılaştırmaları yapılacak en sonda sıfır dönecek. Daha sonra stackte bir alttaki elemana yani p=1 durumuna geçecek. Bu sefer 2-8, 2-7, 2-6 ve 2-5 karşılaştırmaları yapacak. Kısacası ilk dizideki her eleman için dizideki ikinci elemanın sayısı kadar karşılaştırma yapacak.

En kötü durumda bunu dizideki her eleman için yapacak ve bu durumda fonksiyonun kompleksitesi T(p,q)= T(p,q-1)+T(p-1,q) = O(pq) + O(pq) olmuyor mu? ( o da herhalde yine O(pq) ya eşit. dediğim gibi dersini almadım yanlış hatırlıyor olabilirim, benim alanım değil ama elimden geleni yaptım sdf )

[Ardeth]

öf recursive algoritmaları bir kağıda falan çizmeden anlamaya çalışınca başımı ağrıtıyor. benim beynim kesinlikle recursive çalışmak için tasarlanmamış sdf

[Fly]

recursive'ler için formüller mormüller varmış da, mantıken yapmaya çalışıyorum, yarım yamalak ders notlarımda sabit alırız logn yaparız sonra kuşlar böcekler demiş de, devamı yok işte elimde.

bir iki sınav sorusu buldum google'dan, farazi bir sayı veriyoruz ,
mesela T(n)=2T(n-2)' de (2^1/2)^n çıkıyor, mantıklı iyi hoş ama Tn=3Tn/3 için logaritmik çıkışıni göremiyoruz ?

iteratif olarak düşünürsek bir matrisin ortasından başlayıp yarısını ala ala giden algoritmada (ismini cidden hatırlamıyorum) N=2^p + k ise, p kadar dönecektir, p=log2N diyoruz mesela.

rekürsif olanında da n/3 , n/9.. diye gider, demek ki 3^p kadar dönecek en fazla, oradan log3n deriz ama formüle dökemiyorum ? (direk Tn=3Tn/3 => Tn=log3n diyor, big o falan karıştırmadan önce)

öte yandan Tn=Tn-1+Tn-2 için mantıklı oluyor, c^n=c^n-1 + c^n-2 => c^2=c+1 'den (1+kök(5)/2)^n çıkıyor.

ek olarak notlarda tek bir değişken varken T(n)=O(1)+T(n-1) gibi bakmışız hep ama burada iki tane var, ifade ederken nasıl etmem gerektiğini bilmiyorum. pq dedim yine de en kötü koşulu düşündüğümüz ve de biri sıfır olursa toptan bittiği için :

T(pq) = T(pq-q) + T(pq-p) çıkıyor,

c^pq = c^pq-q + c^pq-p oluyor örneklere göre, gerisini yapmadım şimdilik yanlışsa boşuna bakmayayım diye.

neleri doğru/yanlış yapmışım ?

[Fly]

:(

şunu sorayım madem,

T (n) = 3T (n/3). T (n) = log3 n. ANSWER: T (n) = O(log n).

diyor bir soru için.

bölü bilmemkaçlı olunca şöyle düşündüm :

T(1)' de (veya <1) duracak ; T(n)=3T(n/3)=3^2(n/9)=...=3^i T(n/3^i) olacak,
n/2^i = 1 olduğunda da bitecek

i=log3n çıkıyor, tamam anladım bu kadar defa dönecek sonra bitecek.
lakin yerine koyunca T(n)=3^log3n = n çıkıyor, O(n) ' in içinde O(logn) ' in olduğunu bilip i defa döneceğini bildiğimden hadi dedim buna şu kadar diye.

başka bir soru,
T(n)=2T(n-2)=2^2T(n-3)=...=2^n-2 T(1)
n-2 defa dönüyor bunda da, lakin T(n)=2^n-2 çıktı,

e ben diyemem ki T(n)=2^n-2 diye, mantıklı değil. zaten cevap olarak kök(2)^n demiş.

logaritmik artanlarla lineer/polinomial artanları ayrı metodlarla (birinde kaç kere döndüğü, diğerinde x^n = x^n-1 vs diye) yapınca cevaplarla uyuşuyor, ammavelakin ikisi bir arada olursa ne olacak ?

mesela bir başkasında :
T(n) = 2O(1) + 2T(n/2) + O(n) <= 2T(n/2) + cn diyorum sabit c sıfırdan büyük doğal sayı olmak üzere,

<= 2(2T(N/4) + cn/2) + cn
2^i + i*cn oluyor görüldüğü gibi en sonda.

n/2^i = 1' den i=log2n çıktı.

2^log2n + log2n * cn.

buna O(nlogn) demiş sanırım ikinci terim sayesinde, iyi güzel.

e bunun karmaşıklığı T(n)=2T(n/2) olsaydı üstte dediğim gibi sadece 2^log2n = n çıkıyor, tamam O(n) veya daha küçük olduğu manasına geliyor da mümkün olduğunca küçüğünü arıyoruz (O(logn) bu soru için), ne yapılabilir ki bunun gibi nir durumda ?