Сложность функции времени

Question

hi читает в книге, что вызовы подпрограмм считаются постоянной операцией времени, даже если сами подпрограммы не выполняются в постоянное время, но зависят от размера ввода. Тогда, если у меня есть следующий фрагмент кода:

void func(int m){ 
int n = 10; 
    subrout(m);//function which complexity depends on m 
    subrout2(n);//function which complexity depends on n 
} 

я полагаю, я могу считать FUNC(), чтобы быть постоянной функцией времени, например, O (1)?

и что, если у меня есть это:

void func(){ 
    int n = 10; 
    Type object; 
    object.member_method(n);/*member function which time complexity depends upon n*/ 
} 

может я до сих пор считают FUNC() постоянную функцию времени? есть ли какой-нибудь случай, когда это правило падает? спасибо!

Answer 1

Нет, вы не можете рассматривать func(int m), чтобы иметь постоянную временную сложность. Его временная сложность составляет O(T1(m) + T2(10)), где T1 и T2 - это функции, описывающие временную сложность subrout и subrout2 соответственно.

Во втором случае временная сложность, технически, постоянна.

В качестве общего замечания целью определения временной сложности с асимптотической нотацией является описание того, как количество операций увеличивается как функция размера ввода.

Answer 2

Что, вероятно, означает сказать, что временная сложность вызывающей функции T_func равна T_call + T_callee. Здесь T_call - это временная операция передачи параметров и настройка среды для вызываемого абонента, а T_callee - время, проведенное внутри подпрограммы. В книге говорится, что можно предположить, что T_call является постоянным, в то время как такие предположения не принимаются относительно T_callee.

Чтобы уточнить, предположим, что у нас есть функция func, которая вызывает одну подпрограмму callee.

func(s){ 
     callee(s); 
    } 

T_func(s) = T_call + T_callee(s). Если size(s) = n и T_callee = O(f(n)), то можно с уверенностью сказать, что T_func = O(f(n)).