algorithm - 互递归分析

Question

我正在尝试分析这些功能，但我有点迷路了。所以对于函数 f 当 t(n) = c如果n < 1^-5

所以如果n >= 1^5我得到t(n) = c2 + t( n / 2 ) + t2( n / 2)其中 t2 是函数 h 的时间分析，但我对扩展它感到困惑，应该是类似

t(n) = ( t(n / 2) + t2( n / 2) ) * c2 + c

或者我应该在其中扩展 t2 吗？

这是我要分析的代码。

float f( float x) {
    if ( abs( x ) < 1e-5 ) {
        return x + ( ( x * x * x ) / 2 );
    }
    float y = f( x / 2 );
    float z = g( x / 2 );
    return 2 * y * z;
}

float g( float x ) {
    if ( abs( x ) < 1e-5 ) {
        return 1 + ( ( x * x ) / 2 );
    }
    float y = f( x / 2 );
    float z = g( x / 2 );
    return ( z * z ) + ( y * y );
}

Answer 1

T₁(n) = T₁(n/2) + T₂(n/2) + c1

T₂(n) = T₁(n/2)+T₂(n/2) + c2

所以我们有

• T₁(n) = O(T₂(n))
• T₁(n) = 2T₁(n/2) + c1

因为 c1 = O(n^log₂2) 主定理意味着

T(n) = O(n)