Рецидив для индикаторной функции

Question

Предположим, что у вас есть рекурсивная функция, где:

Я знаю, рекуррентное соотношение для первого, если утверждение будет O (п) и рекуррентное соотношение состояния еще будет O (LOGN). Однако я смущен, чтобы рассчитать сложность всей функции. Будет ли общая сложность просто O (n), поскольку n доминирует в log (n)?

Answer 1

По определению, большая O является верхней границей, так что будет O (п) (с O (п) больше, чем O (Г (п)). Почитайте о большом O и большой тете Big-oh vs big-theta

EDIT:

Если предположить, что код будет выглядеть примерно так:

foo(x,y) 
{ 
if(y<0): 
    //call some other function, or throw an error, otherwise we're stuck in an infinite loop 
else if(y==0): 
    return 1 
else if(y%2!=0): 
    return x*foo(x,y-1) 
else: 
    return foo(x,y/2)*foo(x,y/2) 
} 

Здесь, Big O является O (N), но с технической точки зрения было бы также O (N^2) , O (n^3) и т. Д. Это связано с тем, что Big O является верхней границей.

Большая тета (плотная граница) - Theta (n).

Обратите внимание, что только потому, что вы можете уменьшить y, разделив y/2, вы не уменьшаете количество вызовов на foo, так как вы делаете вдвое больше: foo * foo. Поскольку вы удваиваете свои вызовы функций, вы не получаете производительность Theta (lg (n)).

Answer 2

Я считаю, что вы можете разбить его на O (n) в худшем случае, а O (logn) - лучший случай.

Просто давая некоторые идеи, это непременно не полный ответ.