Büyük-O gösterimi anlıyorum, ama birçok işlevi için bunu hesaplamak için nasıl bilmiyorum. Özellikle, Fibonacci dizisi naif versiyonu hesaplama karmaşıklığını anlamaya çalışıyorum:

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1)   Fibonacci(n - 2);
}

Fibonacci dizisi hesaplama karmaşıklığı nedir ve nasıl hesaplanır?

Zaman fonksiyonu Fib(n-1) artı bunları birbirine eklemek için zaman artı Fib(n-2) hesaplamak için zaman (O(1)) hesaplamak için zaman toplamı olarakFib(n) hesaplamak için modeli.

T(n<=1) = O(1)

T(n) = T(n-1) T(n-2) O(1)

Bunu tekrar ilişkisi çözmek (üreten fonksiyonlar, örneğin kullanarak) ve cevabı bulursun.

Alternatif olarak, derinliği n ve sezgisel olarak bu işlevi olduğunu anlamaya sınıfları O(2 olacak özyineleme ağacı çizebilirsinizn). Sonra indüksiyon ile varsayım ispat edebilirsiniz.

Temel: n = 1 açıktır

T(n-1) = O(2 varsayalımn-1), . ben^>bu nedenle

T(n) = T(n-1) T(n-2) O(1) . ben^>eşittir

T(n) = O(2n-1) O(2n-2) O(1) = O(2n)

Bir yorumda belirtildiği gibi ancak, bu sıkı bağlıdır. Bu fonksiyon hakkında ilginç bir bilgi vereyim T(n) asimptotik olmasıdıraynıhem olarak tanımlandığı için Fib(n) değeri olarak

f(n) = f(n-1) f(n-2).

Özyineleme ağacının yaprakları her zaman 1 döndürür. Fib(n) değerini yaprak sayısı eşit olan bütün değerleri özyineleme ağacındaki yaprakları tarafından döndürülen toplamıdır. Her yaprak O(1) hesaplamak için alır bu yana, 27* *Fib(n) x O(1) eşittir. Sonuç olarak, sıkı bu işlev için Fibonacci dizisi bağlı kendisi (~θ(1.6n)). Bu sıkı yukarıda bahsettiğim gibi üreten fonksiyonlar kullanarak bağlı dışarı bulabilirsiniz.