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

Musa B. · 25 Kasım 2021

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:

[CODE lang="cpp" title="Veri Yapıları"]for(int i =1; i<n;i=i*2)
{
for(int j=1; j<i; j = j*2)
{
cout << "hello";
}
} [/CODE]

The Anorak · 25 Kasım 2021

@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.

The Anorak · 25 Kasım 2021

~~log2( n )^2 gibi. Yani log( n )*log ( n ).~~

Az önce bir deneme yaptım ve cevabımı O( sqrt( n ) ) olarak güncelliyorum.

Musa B. · 25 Kasım 2021

@The Anorak 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 · 25 Kasım 2021

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.

Musa B. · 25 Kasım 2021

@The Anorak 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.
@The Anorak 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.

The Anorak · 25 Kasım 2021

@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.

bitwise · 25 Kasım 2021

O(log^2 n) bence.

The Anorak · 26 Kasım 2021

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.

0	1
1	2
3	4
6	8
10	16
15	32
21	64
28	128
36	256
45	512
55	1024
66	2048
78	4096
91	8192

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

RaSGooL · 26 Kasım 2021

n^2değilde (logn)^2 gibi gözüküyor.
Döngü bir bir artsaydı n^2 olurdu. Ama her loopta iki katına çıkıyor. Bu logn dir. İçiçe oldugu içinde (logn) ^2 oluyor.

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

Ayrıntılı düzenleme

Musa B.

Kilopat

The Anorak

The Anorak

Gigapat

Musa B.

Kilopat

The Anorak

Gigapat

Musa B.

Kilopat

The Anorak

Gigapat

bitwise

Megapat

The Anorak

Gigapat

RaSGooL

Kilopat

Benzer konular