Ben

Question

Benim Bilgisayar Bilimleri II Final yarın bir kod segmentinin Big-Oh nasıl bulacağını anlamak için yardıma ihtiyacım var ve kod segmentleri için Big Oh nasıl bulacağını anlayarak yardıma ihtiyacım var. İnterneti araştırdım ve bunu nasıl anladığımı gösteren örnekleri bulamadım. Biz algoritmanın sırasını (Big-Oh) bulmak gerekiyordu

for(int pass = 1; i <= n; pass++) 
{ 
    for(int index = 0; index < n; index++) 
     for(int count = 1; count < n; count++) 
     { 
      //O(1) things here. 
     } 
    } 
} 

:

İşte son bizim örnekten bir problem.

Burada olurdu O (n^3) düşünüyorum ve ben doğru yapıyorum ben sadece emin değilim bu sonuca

for(int pass = 1; i <= n; pass++) // Evaluates n times 
{ 
    for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
     for(int count = 1; count < n; count++) // Evaluates n * n * (n) times 
     { 
      //O(1) things here. 
     } 
    } 
} 
// T(n) = (n) + (n^2 + n) + n^3 
// T(n) = n^3 + n^2 + 2n 
// T(n) <= c*f(x) 
// n^3 + n^2 + 2n <= c * (n^3) 
// O(n) = n^3 

nasıl geldi. Birisi böyle bir kodu nasıl değerlendireceğimi açıklayabilir mi ve/veya cevabımı nasıl doğrulayabilir?

Answer 1

Evet, O(n^3) olduğunu. Bununla birlikte: toplam Eğer n^3 - n^2 sabiti böylece döngü için iç içe üç katman olduğundan

for(int pass = 1; pass <= n; pass++) // Evaluates n times 
{     //^^i should be pass 

    for(int index = 0; index < n; index++) //Evaluates n times 
     for(int count = 1; count < n; count++) // Evaluates n-1 times 
     { 
      //O(1) things here. 
     } 
    } 
} 

, iç içe geçmiş bir öze için en iç içinde n *n * (n-1) kez, her biri işlem değerlendirilecek, O (1) zaman alır büyüme amacıyla O(n^3) olan işlemler.

Büyük O notasyonu büyüme sırasını nasıl ölçüleceğini iyi bir özeti burada bulabilirsiniz: Yukarıdaki dosyadan kısmını aktaran

Big O Notation MIT

:

İç içe

döngüler

for I in 1 .. N loop 
    for J in 1 .. M loop 
     sequence of statements 
    end loop; 
end loop; 

dış döngü N kez yürütür. Dış döngü her yürütüldüğünde, iç döngü M kere yürütür. Bunun bir sonucu olarak, iç döngü ifadeler K * M kez toplam yürütmek. Böylece, karmaşıklık O (N * M) 'dir. İç döngünün durma koşulunun yerine 10'un (yani iç döngü de N kere yürütür) olduğu ortak bir özel durumda, iki ilmek için toplam karmaşıklık O (N^2) 'dir.

Benzer mantığı sizin durumunuzda uygulanabilir.

Answer 2

Kesinlikle haklısınız. Örneğiniz için O (n^3).

kodun herhangi bir segmentin Big Oh çalışma süresini bulmak için, kod parçası yok kaç kere O (1) şeyler düşünmek gerekir.

beni bu daha iyi bir fikir vermek için örnek basitleştirmek edelim: Yukarıdaki durumda

for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
    for(int count = 1; count < n; count++) // Evaluates n * n * (n) times 
    { 
     //O(1) things here. 
    } 
} 

, iç döngü dış döngü her çalışması için n kez çalışır. Ve dış döngüsünüz de n kere çalışır. Bu, n şeyler yaptığınız, n sayıda kez yaptığınız anlamına gelir. Yapma O (n^2).

Dikkat çekmek için başka bir şey de Big Oh'un bir üst sınırdır. Bu, büyük bir girişe sahip olduğunuzda, kodun başına ne geleceğini düşünmeniz gerektiği anlamına gelir (sizin durumunuzda, n'un büyük bir değeri. Bu gerçeğin başka bir anlamı da, sabitlerle çarpmanın ya da eklemenin Büyük üzerinde hiçbir etkisinin olmamasıdır. . Ah Örneğin bağlanmış:

for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
    for(int count = 1; count < 2*n; count++) // Runs 2*n times 
    { 
     //O(1) things here. 
    } 
} 

bu kodun büyük Ah çalışma süresi aynı zamanda O (n^2) O (n * (2n)) = O (n^2) itibaren

. Ayrıca şunu da gözden geçirin: http://ellard.org/dan/www/Q-97/HTML/root/node7.html