Çözüldü Big O Notasyonu hesaplama nasıl yapılır?

Bu konu çözüldü olarak işaretlenmiştir. Çözülmediğini düşünüyorsanız konuyu rapor edebilirsiniz.

Musa B.

Hectopat
Katılım
1 Ekim 2017
Mesajlar
1.503
Makaleler
3
Çözümler
11
Merhaba, yarın veri yapıları sınavımız var ve hocamızın 2 hafta önce vermiş olduğu kodun Big-O notasyonunu hala bulamadık. Açıkçası ben log(logn) olduğunu düşünmüştüm lakin yanlış olduğunu söyledi hocamız. İlgili kod:

Veri Yapıları:
for(int i =1; i<n;i=i*2)
{
   for(int j=1; j<i; j = j*2)
   {
     cout << "hello";
   }
}
 
Çözüm
@M.Sc Jelly Bean biz kodun notasyonunu O(log(n^2)) olarak veya O(n^2) olarak düşünüyoruz; sebebi ise n´ye verdiğimiz değerlerde iç kısımdaki for döngüsünün çalışmasına baktık ve (2 üzeri n) + 1 değerine geldiğinde çalışma miktarı bir artıyor.

Doğrudur. Sayıları grafik şeklinde çizdirdiğimde elde ettiğim eğri O( n^2 )'nin ta kendisi.

bigO.png
KS
KS
Musa B.

Musa B.

Hectopat
Katılım
1 Ekim 2017
Mesajlar
1.503
Makaleler
3
Çözümler
11
@M.Sc Jelly Bean Hocam anlatma şansınız var mı nasıl bir deneme yaptığınızı? Çünkü kafayı yemek üzereyiz, bize öğrettikleri şeyle ilgisi yok ve işin kötü kısmı yarınki sınavda bunu sorabilir soru olarak.
 

The Anorak

Gigapat
Katılım
2 Mart 2014
Mesajlar
6.106
Çözümler
104
Yer
Master Boot Record
JavaScript:
function bigO(n) {
  let count = 0;
  for (let i = 1; i < n; i *= 2)
    for (let j = 1; j < i; j *= 2)
      count++;
  return count;
}

for (let i = 2; i < 100_000; i++) {
  console.count(bigO(i));
}

Bu şekilde count sayısının yakınsama eğrisinin değerlerini oluşturdum ve grafiğinin sqrt( n ) ile olmasa bile ona yakın bir eğri çizdiğini fark ettim.
 
KS
KS
Musa B.

Musa B.

Hectopat
Katılım
1 Ekim 2017
Mesajlar
1.503
Makaleler
3
Çözümler
11
@M.Sc Jelly Bean karmaşıklık sıralamasında sqrt( n ) log( n )´den daha mı az karmaşık? Bize verilen sıralamada 1-log( n )- n- n log( n )-n kare-n küp- iki üzeri n ve son olarak n faktöriyel var.
@M.Sc Jelly Bean biz kodun notasyonunu O(log(n^2)) olarak veya O(n^2) olarak düşünüyoruz; sebebi ise n´ye verdiğimiz değerlerde iç kısımdaki for döngüsünün çalışmasına baktık ve (2 üzeri n) + 1 değerine geldiğinde çalışma miktarı bir artıyor.
 
Son düzenleme:

The Anorak

Gigapat
Katılım
2 Mart 2014
Mesajlar
6.106
Çözümler
104
Yer
Master Boot Record
@M.Sc Jelly Bean biz kodun notasyonunu O(log(n^2)) olarak veya O(n^2) olarak düşünüyoruz; sebebi ise n´ye verdiğimiz değerlerde iç kısımdaki for döngüsünün çalışmasına baktık ve (2 üzeri n) + 1 değerine geldiğinde çalışma miktarı bir artıyor.

Doğrudur. Sayıları grafik şeklinde çizdirdiğimde elde ettiğim eğri O( n^2 )'nin ta kendisi.

bigO.png
 
Çözüm

The Anorak

Gigapat
Katılım
2 Mart 2014
Mesajlar
6.106
Çözümler
104
Yer
Master Boot Record
Diğer eğrileri ekleyince 2^n'nin büyük bir denominator ile bölümü veya logaritması gibi göründü.
log(2^n) veya sqrt(2^n) de olabilir.

graph.png


01
12
34
68
1016
1532
2164
28128
36256
45512
551024
662048
784096
918192

Doğrudan 2^n değil ancak 2^n ile bir bağlantısı mevcut.
 

Yeni konular

Yukarı