Bu algoritmanın karmaşıklığı?

-1

Eğer func2 = O (n) ve func3 = O (n^2) ise func1 karmaşıklığı nedir?Bu algoritmanın karmaşıklığı?

void func1 (int n) { 
    int i, j, k; 
    for (k=0;k<n;k++)   // O(n) 
     printf("%d",k); 
    i=0; 
    while (i<2*n) {   // O(n) 
     for (j=i;j>1;j--) // Not executed 
      for (k=15;k>0;k--) 
       func2(n); 
     for (j=n;j>1;j--) // O(n) 
      func3(n);  // O(n^2) 
     i++; 
    } 
}

Böylece (n^2) O (n) O (n) + O (n) = maks (nO (n^4), O()) = O (n^4) O var ?

Teşekkürler!

kaynak

2016-04-11 Trapezera Buscando

Ne düşünüyorsun ve neden? –

Func2'nin yürütüldüğü ve func3'ün iki döngü altında olduğu için O (n^4) aldım: en çok 2'den n'ye ve diğeri 0'dan 2n-1'e kadar. –

'printf ("% d ", k)' O (log (k)) değil, O (1) değil, ilk döngüyü O (log (n!)) = O (n log n) yapar. Bu kez func1'in genel karmaşıklığı için herhangi bir fark yaratmaz, çünkü bu ilk döngü ikinci baskındır. –

void func1 (int n) { 
    int i, j, k; 
    for (k=0;k<n;k++)  
     printf("%d",k); 
    i=0; 
    while (i<2*n) {    // O(2*n) = O(n) 
    for (j=i;j>1;j--)   // O(n) 
     for (k=15;k>0;k--)  // O(15) = O(1) 
      func2(n);    // O(n) 
    for (j=n;j>1;j--)   // O(n) 
     func3(n);     // O(n^2) 
    i++; 
    } 
}

Diziler için, en fazla adımları bulun.

Genel kural olarak, iç içe geçmiş döngüler çoğalır, ancak bağımsız olmadıkça aralıkları dikkatli bir şekilde incelemeniz gerekebilir. Bunun böyle olduğundan emin olun (bir örnek için Paul'un yorumuna bakın).

kaynak

2016-04-11 00:54:42

O (n^2) O (n) O (n) = 0 (n^4)? Kitap awnser O (n^3) –

Gerçekten? Hangi kitap? @TrapezeraBuscand ve bu kitap onun sonuçlarını nasıl açıklıyor? –

Yuvalanmış ilmeklerin karmaşıklığı genel olarak çoğalmaz, ancak sözde-yöntem burada doğru sonucu verir. Örneğin, 'i = 0' yerine' i = 1' ve 'i ++' i 'i * = 2' ile değiştirdiyseniz, dış döngü çalışsa bile, func2 toplam maliyetinin hesaplamaları O (n^2) olur. O (log n) 'kere. –

cevap

İlgili konular