| Yazar |
|
ruveyda
Kayıt: 21.03.2009 |
|
int Sum (int N)
{
int i, PartialSum;
PartialSum=0;
for(i=1 ;i<=N ; i++)
PartialSum+=i*i*i;
return PartialSum;
}
Arkadaslar bu algoritmanın çalışma zamanı 6N+4=O(N) olarak verilmiş bu aşamalarına göre nasıl bulunmuş olabilir?
|
|
|
| Yazar |
|
mrflz
Luleburgaz
admin
Kayıt: 15.06.2006 |
|
ruveyda yazdi | | int Sum (int N)
{
int i, PartialSum;
PartialSum=0;
for(i=1 ;i<=N ; i++)
PartialSum+=i*i*i;
return PartialSum;
}
Arkadaslar bu algoritmanın çalışma zamanı 6N+4=O(N) olarak verilmiş bu aşamalarına göre nasıl bulunmuş olabilir? |
Kabulleri bilmeden anlatmak biraz zor olacak ama genel mantık olarak sunları soyleyebilirim.
Bir atama işlemi varsa ve birkez yapılıyorsa bunun için gecen süre 1 idr.
MEsela burada PartialSum=0 ataması var atama işlemleri için bu programda c1 paramateresini ve program sonlana kadar 1 kez bu atama olduğunndan c1*1 deriz..
for dongusu kendi basına 3 durum içerir.
once 1 kez i degeri atanır.sonra her dongude i nin N den kucuk olup olmadıgı kontrol edilir bu da N kez olur, bu kontrol için c2 dersek bu da c2*n olur, i++ durumu da hem toplama hem atama olur.. toplama için c3 dersek c1 zaten atama idi bu durmda n-1 kez olur bu durumda (c2+c3)*(n-1) olur gibi asagıda da mesela carpma ve atama var i in kubu alınamsı için burada da aynı yol iznirse kabullere gore mesela False olan durumlar goz ardı edlip edilmemesine gore değişkenlerele durumların capımlarının alt alta toplama bize denklemi veriri buradan da O(n) hesaplanır.
EKLEME :
Açıkcası burda daha temiz bir anlatım var .. belki daha çok yardımcı olur.
http://www.csanimated.com/animation.php?t=Big_O_notation
http://www.csanimated.com/animation.php?t=Master_theorem
I see the ghosts of navigators but they are lost
|
|
|
| Yazar |
|
ruveyda
Kayıt: 21.03.2009 |
|
Binary searchın T(n)=O(1)+T(n/2) burdan algoritmanın çalışma mantıgına göre neden O(n) olmamışta O(1) olmuş?
|
|
|
| Yazar |
|
ruveyda
Kayıt: 21.03.2009 |
|
Binary searchın T(n)=O(1)+T(n/2) burdan algoritmanın çalışma mantıgına göre neden O(n) olmamışta O(1) olmuş?
|
|
|
| Yazar |
|
kartane
istanbul
Kayıt: 22.02.2007 |
|
ruveyda yazdi | |
Binary searchın T(n)=O(1)+T(n/2) burdan algoritmanın çalışma mantıgına göre neden O(n) olmamışta O(1) olmuş? |
Binary search diziyi ikiye bölüp baktığından t(n/2) boldukten sonrada ortadakı elemanla karşılaştırmak 1 zaman alıyor o yuzden O(1) ama ornegin merge sorte O(n) oluyo cunku orda diziyi ikiye boluyu( t(n/2) ) yapılan işlemden sonra n tane elemanı bırleştırmesı gerektıgınden n kadar zaman harcanmış oluyo o yuzden O(n) oluyo benim anladığım kadarıyla boyle bır mantık var ıyı çalışmalar...
|
|
|
| Yazar |
|
ruveyda
Kayıt: 21.03.2009 |
|
Arkadaslar master teoremde ben bulurken önce t(1)=1 vs verilirse birbirine benzetip sadeleştirme sonucu buluyorum fakat bu yöntem haricinde sanırım bir tiyo var hemen 1 2 3 hangisini uydugunu buldugumuz yani daha acıkcası asagıdaki örnekte hemen master teorem case 3 nasıl bulmuş bunun tiyosu nedir?neye bakıyoruzda hemen case 3 e uyuyor vs.diyoruz yani su master teoremi iyi anlayan biri mantıgını anlatabilirmi azcıkkk
T (n) = 16T (n/4)+ n! =) T (n) = (n!) (Case 3)
|
|
|
| Yazar |
|
ysfyzl
Kayıt: 04.12.2006 |
|
Master theorem sorularında hangi case olduğunu bulma konusu benimde aklıma takıldı.
anlayan birileri anlatabilir mi???
|
|
|
| Yazar |
|
uslanmaz4
ANKARA
Kayıt: 15.01.2006 |
|
Eger master teoremde a yı b yi ve f(n) ni bilince gerisi formül.Örneğin
T(n)=T(n/2) +n^3
a=1 b=2 f(n)=n^3
-------İlk teoremde bakıyorsunuz f(n)=n^(log b(a) -e).
n^3 = n^(log2(1)-e)
//log2(1) bunu nasıl çözüyoruz derseniz log2( 1)=x derseniz => 1=2^x => x=0
//veya başka bir yolu log 1/log 2 dir.
n^3=n ^ (0-e) bu değeri saglayan herhangi bir pozitif e sayısı varsa 1. teoremdir.Yok.
-----ikinci teorem n^3 =n^(log2(1)) bunun eşit olmadığı zaten belli
-----ücüncü teoreme bakıyoruz f(n) = n^(log b(a) +e)
n^3 = n ^(0+e) bu değeri sağlayan herhangi bir e değeri var mı?Var. O zaman ikinci aşamasına bakıyoruz a f(n/b) = c f(n) ---c<1 için bir c sayısı olması lazım
1 f(n/2) <= c n^3 // f(n)= n^3 tü
(n/2)^3 <= c n^3
n^3/8 <= c n^3 bunu sağlaması için c=1/2 olabilir
O zaman üçüncü teoremi sağlıyor.ve T(n) elemanıdır Q=n^3 (işareti yapamadım :D)
kedicik kedicik
|
|
|
| Yazar |
|
ruveyda
Kayıt: 21.03.2009 |
|
uslanmaz4 yazdi | | Eger master teoremde a yı b yi ve f(n) ni bilince gerisi formül.Örneğin
T(n)=T(n/2) +n^3
a=1 b=2 f(n)=n^3
-------İlk teoremde bakıyorsunuz f(n)=n^(log b(a) -e).
n^3 = n^(log2(1)-e)
//log2(1) bunu nasıl çözüyoruz derseniz log2( 1)=x derseniz => 1=2^x => x=0
//veya başka bir yolu log 1/log 2 dir.
n^3=n ^ (0-e) bu değeri saglayan herhangi bir pozitif e sayısı varsa 1. teoremdir.Yok.
-----ikinci teorem n^3 =n^(log2(1)) bunun eşit olmadığı zaten belli
-----ücüncü teoreme bakıyoruz f(n) = n^(log b(a) +e)
n^3 = n ^(0+e) bu değeri sağlayan herhangi bir e değeri var mı?Var. O zaman ikinci aşamasına bakıyoruz a f(n/b) = c f(n) ---c<1 için bir c sayısı olması lazım
1 f(n/2) <= c n^3 // f(n)= n^3 tü
(n/2)^3 <= c n^3
n^3/8 <= c n^3 bunu sağlaması için c=1/2 olabilir
O zaman üçüncü teoremi sağlıyor.ve T(n) elemanıdır Q=n^3 (işareti yapamadım :D)
Teşekkürler...
|
|
|
|
| Yazar |
|
ysfyzl
Kayıt: 04.12.2006 |
|
uslanmaz4 yazdi | | Eger master teoremde a yı b yi ve f(n) ni bilince gerisi formül.Örneğin
T(n)=T(n/2) +n^3
a=1 b=2 f(n)=n^3
-------İlk teoremde bakıyorsunuz f(n)=n^(log b(a) -e).
n^3 = n^(log2(1)-e)
//log2(1) bunu nasıl çözüyoruz derseniz log2( 1)=x derseniz => 1=2^x => x=0
//veya başka bir yolu log 1/log 2 dir.
n^3=n ^ (0-e) bu değeri saglayan herhangi bir pozitif e sayısı varsa 1. teoremdir.Yok.
-----ikinci teorem n^3 =n^(log2(1)) bunun eşit olmadığı zaten belli
-----ücüncü teoreme bakıyoruz f(n) = n^(log b(a) +e)
n^3 = n ^(0+e) bu değeri sağlayan herhangi bir e değeri var mı?Var. O zaman ikinci aşamasına bakıyoruz a f(n/b) = c f(n) ---c<1 için bir c sayısı olması lazım
1 f(n/2) <= c n^3 // f(n)= n^3 tü
(n/2)^3 <= c n^3
n^3/8 <= c n^3 bunu sağlaması için c=1/2 olabilir
O zaman üçüncü teoremi sağlıyor.ve T(n) elemanıdır Q=n^3 (işareti yapamadım :D)
|
şükran
|
|
|
| Yazar |
|
serdar5
Kayıt: 12.02.2006 |
|
uslanmaz4 arkadaşım Allah razı olsun senden, ben bi saat baksam zor anlardım, iki dakkada hallettin olayı
Kanit gösterilmeden yapilmis bir iddiayi çürütmek için kanita ihtiyaç yoktur
|
|
|
| Yazar |
|
nightfall
Kahramanmaras
Kayıt: 18.11.2007 |
|
Algorithm taskSchedule(T)
m ← 0 {no. of rooms}
while T is not empty
remove conference i with smallest si
if there’s a room j for i then
schedule i on room j
else
m ← m + 1
schedule i on room m
This is a greedy algorithm with runtime O(nlogn).
Midtermin üçüncü sorusunda verilen bu algoritmanın karmaşıklığının O(nlogn) olduğu nasıl anlaşılıyor
Dunyanin tek madalyali sehri KAHRAMANMARAS...
FENERLI OLUNMAZ FENERLI DOGULUR!!!
|
|
|
| Yazar |
|
virgo
istanbul
Kayıt: 18.01.2006 |
|
ANALYSIS OF ALGORITHMS - FALL 2008 - Dr. Olcay Kursun
FINAL PRACTICE QUESTIONS (vize konularını da içermekte)
http://rapidshare.com/files/300989429/AA.FINAL.PRACTiCE.QUESTiONS.pdf
there is no place like 127.0.0.1
|
|
|
|
|
-
 Del.icio.us
-
 Digg
-
 Facebook
-
 Furl
-
 Google
-
 Blink
-
 Simpy
-
 Spurl
-
 Y! MyWeb
|
|
| | | | | | | | | | |
