Yineleme algoritmasında karmaşıklık

Şu anda üniversitedeki veri yapılarını inceliyorum ve özyinelemede karmaşıklık hakkında bir soruyla karşılaştım. Yineleme algoritmasında karmaşıklık

bu kodu Verilen:

Unsigned func (unsigned n) 
{ 
if (n ==0) return 1; 
if(n==1) return 2; 

\\do somthing(in O(1)) 

return func(n-1) + func(n-1); 
}

ben kod ne yaptığını biliyoruz. Şu an formda olduğunu biliyorum, zaman karmaşıklığı O (2^n).

Ancak sorum şu: kodun son dönüşü çağrısı yerine zaman karmaşıklığı değişecek mi? return 2*func(n-1)?

Bellek karmaşıklığı açısından, özyinelemenin uzaydaki önemli bir azalmasından bahsediyoruz, ancak zaman karmaşıklığı açısından herhangi bir değişiklik olacak mı?

Özyinelemeli bir işlev kullanarak matematik yaptım ve zaman karmaşıklığında hiçbir değişiklik olmayacağına dair anlayışa geldim, doğru muyum? Eğer 5 ile çalıştırırsanız, bu 4 ile özyineleme gittiği için

kaynak

2015-11-05 Tom

Bu yöntem 3 vs ile daha sonra, sadece O(n) yaşıyor

Unsigned func (unsigned n) 
{ 
if (n ==0) return 1; 
if(n==1) return 2; 

\\do somthing(in O(1)) 

return 2*func(n-1); 
}

Ancak peki ya bu:

Unsigned func (unsigned n) 
{ 
if (n ==0) return 1; 
if(n==1) return 2; 

\\do somthing(in O(1)) 

return func(n-1) + func(n-1); 
}

örnek fonksiyon (5) için en çok

5 -> 4 -> 3 -> 2 -> 1

daha sonra 2 döner aşağıdaki ilk olarak çalıştırır,

: Bu O(n) den O(2^n)

pratik örneğini bu kodu deneyelim için büyük ölçüde karmaşıklığı değiştirmek ETMEZ nedenle

5 -> 4 -> 3 -> 2-> 1; 2-> 1; 3->2->1; etc.

gibi bütün süreci görünmesi için ama orada o "ikinci" bölümünü çalıştırır

public class Complexity { 
    private static int counter; 
    public static void main(String[] args) { 
     for (int i = 0; i < 20; i++) { 
      counter = 0; 
      func(i); 
      System.out.println("For n="+i+" of 2*func the number of cycles is " + counter); 
      counter = 0; 
      func2(i); 
      System.out.println("For n="+i+" of func + func the number of cycles is " + counter); 
     } 
    } 

    public static int func(int n) { 
     counter++; 
     if (n == 0) { 
      return 1; 
     } 
     if (n == 1) { 
      return 2; 
     } 
     return 2 * func(n - 1); 
    } 

    public static int func2(int n) { 
     counter++; 
     if (n == 0) { 
      return 1; 
     } 
     if (n == 1) { 
      return 2; 
     } 
     return func2(n - 1) + func2(n - 1); 
    }  
}

olması bu çıkışı:

For n=0 of 2*func the number of cycles is 1 
For n=0 of func + func the number of cycles is 1 
For n=1 of 2*func the number of cycles is 1 
For n=1 of func + func the number of cycles is 1 
For n=2 of 2*func the number of cycles is 2 
For n=2 of func + func the number of cycles is 3 
For n=3 of 2*func the number of cycles is 3 
For n=3 of func + func the number of cycles is 7 
For n=4 of 2*func the number of cycles is 4 
For n=4 of func + func the number of cycles is 15 
For n=5 of 2*func the number of cycles is 5 
For n=5 of func + func the number of cycles is 31 
For n=6 of 2*func the number of cycles is 6 
For n=6 of func + func the number of cycles is 63 
For n=7 of 2*func the number of cycles is 7 
For n=7 of func + func the number of cycles is 127 
For n=8 of 2*func the number of cycles is 8 
For n=8 of func + func the number of cycles is 255 
For n=9 of 2*func the number of cycles is 9 
For n=9 of func + func the number of cycles is 511 
For n=10 of 2*func the number of cycles is 10 
For n=10 of func + func the number of cycles is 1023 
For n=11 of 2*func the number of cycles is 11 
For n=11 of func + func the number of cycles is 2047 
For n=12 of 2*func the number of cycles is 12 
For n=12 of func + func the number of cycles is 4095 
For n=13 of 2*func the number of cycles is 13 
For n=13 of func + func the number of cycles is 8191 
For n=14 of 2*func the number of cycles is 14 
For n=14 of func + func the number of cycles is 16383 
For n=15 of 2*func the number of cycles is 15 
For n=15 of func + func the number of cycles is 32767 
For n=16 of 2*func the number of cycles is 16 
For n=16 of func + func the number of cycles is 65535 
For n=17 of 2*func the number of cycles is 17 
For n=17 of func + func the number of cycles is 131071 
For n=18 of 2*func the number of cycles is 18 
For n=18 of func + func the number of cycles is 262143 
For n=19 of 2*func the number of cycles is 19 
For n=19 of func + func the number of cycles is 524287

Ama zaten hesaplanan sonuçlar hatırlarsanız, karmaşıklık bile ikinci yaklaşım ile hala O(n) geçerli:

public class Complexity { 
    private static int counter; 
    private static int[] results; 

    public static void main(String[] args) { 
     for (int i = 0; i < 20; i++) { 
      counter = 0; 
      func(i); 
      System.out.println("For n="+i+" of 2*func the number of cycles is " + counter); 
      counter = 0; 
      func2(i); 
      System.out.println("For n="+i+" of func + func the number of cycles is " + counter); 
      counter = 0; 
      results = new int[i+1]; 
      func3(i); 
      System.out.println("For n="+i+" of func + func with remembering the number of cycles is " + counter); 
     } 
    } 

    public static int func(int n) { 
     counter++; 
     if (n == 0) { 
      return 1; 
     } 
     if (n == 1) { 
      return 2; 
     } 
     return 2 * func(n - 1); 
    } 

    public static int func2(int n) { 
     counter++; 
     if (n == 0) { 
      return 1; 
     } 
     if (n == 1) { 
      return 2; 
     }   
     return func2(n - 1) + func2(n - 1); 
    } 

    public static int func3(int n) { 
     counter++; 
     if (n == 0) { 
      return 1; 
     } 
     if (n == 1) { 
      return 2; 
     } 

     if (results[n] == 0){ 
      results[n] = func3(n - 1) + func3(n - 1); 
     } 

     return results[n]; 
    }   
}

bu çıktıyı Having:

For n=0 of 2*func the number of cycles is 1 
For n=0 of func + func the number of cycles is 1 
For n=0 of func + func with remembering the number of cycles is 1 
For n=1 of 2*func the number of cycles is 1 
For n=1 of func + func the number of cycles is 1 
For n=1 of func + func with remembering the number of cycles is 1 
For n=2 of 2*func the number of cycles is 2 
For n=2 of func + func the number of cycles is 3 
For n=2 of func + func with remembering the number of cycles is 3 
For n=3 of 2*func the number of cycles is 3 
For n=3 of func + func the number of cycles is 7 
For n=3 of func + func with remembering the number of cycles is 5 
For n=4 of 2*func the number of cycles is 4 
For n=4 of func + func the number of cycles is 15 
For n=4 of func + func with remembering the number of cycles is 7 
For n=5 of 2*func the number of cycles is 5 
For n=5 of func + func the number of cycles is 31 
For n=5 of func + func with remembering the number of cycles is 9 
For n=6 of 2*func the number of cycles is 6 
For n=6 of func + func the number of cycles is 63 
For n=6 of func + func with remembering the number of cycles is 11 
For n=7 of 2*func the number of cycles is 7 
For n=7 of func + func the number of cycles is 127 
For n=7 of func + func with remembering the number of cycles is 13 
For n=8 of 2*func the number of cycles is 8 
For n=8 of func + func the number of cycles is 255 
For n=8 of func + func with remembering the number of cycles is 15 
For n=9 of 2*func the number of cycles is 9 
For n=9 of func + func the number of cycles is 511 
For n=9 of func + func with remembering the number of cycles is 17 
For n=10 of 2*func the number of cycles is 10 
For n=10 of func + func the number of cycles is 1023 
For n=10 of func + func with remembering the number of cycles is 19 
For n=11 of 2*func the number of cycles is 11 
For n=11 of func + func the number of cycles is 2047 
For n=11 of func + func with remembering the number of cycles is 21 
For n=12 of 2*func the number of cycles is 12 
For n=12 of func + func the number of cycles is 4095 
For n=12 of func + func with remembering the number of cycles is 23 
For n=13 of 2*func the number of cycles is 13 
For n=13 of func + func the number of cycles is 8191 
For n=13 of func + func with remembering the number of cycles is 25 
For n=14 of 2*func the number of cycles is 14 
For n=14 of func + func the number of cycles is 16383 
For n=14 of func + func with remembering the number of cycles is 27 
For n=15 of 2*func the number of cycles is 15 
For n=15 of func + func the number of cycles is 32767 
For n=15 of func + func with remembering the number of cycles is 29 
For n=16 of 2*func the number of cycles is 16 
For n=16 of func + func the number of cycles is 65535 
For n=16 of func + func with remembering the number of cycles is 31 
For n=17 of 2*func the number of cycles is 17 
For n=17 of func + func the number of cycles is 131071 
For n=17 of func + func with remembering the number of cycles is 33 
For n=18 of 2*func the number of cycles is 18 
For n=18 of func + func the number of cycles is 262143 
For n=18 of func + func with remembering the number of cycles is 35 
For n=19 of 2*func the number of cycles is 19 
For n=19 of func + func the number of cycles is 524287 
For n=19 of func + func with remembering the number of cycles is 37

kaynak

2015-11-05 14:16:44 libik

Bu yüzden, func (n-1) + func (n-1) 'nin yinelemeli çağrısının O (2^n) karmaşıklığında çalıştığından haklıymışım? Ayrıca, özü formülümde, kağıda yazdığımda ve hesapladığımda, her ikisinin de aynı zaman karmaşıklığına sahip olduklarını nasıl anlarım? – Tom

@ Tom - evet, formülünüzle ilgili karmaşıklığı (O) (2^n) ... çalıştırıyorsunuz - yanlış kullanıyorsunuz veya yanlış formülünüz var. Sorunuza bu formülü gönderin ve belki neyin yanlış olduğunu söyleyebiliriz. – libik

Formülüm: T (n) = 2T (n-1) iken T (0) = 1, T (1) = 2. "Gönderme yöntemini" kullandım ve genel işleve girdim: T (n) = 2^i * T (ni). i = n-1 veya i = n-2 gibi durma durumlarımı post-up ettikten sonra, T (n) = 2^(n-1) * T (1) = (2^n)/2'nin karmaşıklığına eriştim. ------> O (2^n). diğer durma koşulu için aynı sonuç. Her iki tür kod için de aynı formülü aldığım için neyi yanlış yapıyorum. – Tom

Bu anlamsal bağlıdır programlama/algoritma diliniz.

f(n) tarafından "işlevini daha önce aynı bağımsız değişkenle çağrılmış olursa olsun çağırın" ifadesini kullanırsanız (çoğu programlama dillerinde olduğu gibi), bu durumda değişiklikiniz karmaşıklığı önemli ölçüde azaltır (O) (n) . Argümanın azaltılması başına bir O (1) işlev çağrısı var.

Aksi takdirde (eğer saf işlevlerden ve bilinen sonuçlardan bahsediyorsanız), her iki algoritmanın da karmaşıklığı O (n) zaten var.

kaynak

2015-11-05 14:17:37

Yineleme algoritmasında karmaşıklık

cevap

İlgili konular