Временная сложность функции, вызывающей другую функцию?
Я знаю, как найти временную сложность практически для любой опции (простая функция, функция с циклами и т. Д.), Но я не могу понять, как определить временную сложность вызывающей функции другой функция, в частности, если вызывающая функция находится внутри цикла.
Я написал несколько функций, которые я использую в качестве примера.
int g(int k) {
int i=0;
while(k>0) {
i += k;
k= k/2;
}
return i;
}
int f(int n) {
int m = 0;
for (int i=0; i<n; ++i) {
for (int j=i; j<n; ++j) {
m += g(j);
}
}
return m;
}
Я не могу понять: я должен учитывать сложность времени функции g()и если мне нужно, как рассчитать его в функции f()? Или я просто игнорирую функцию g() и включать только вызовы функций в функции f()?
Решение
Поскольку сложность функции g зависит от параметра k (логарифмического), вы должны учитывать его при вызове из функции f. В случае, если наихудшая операция g имеет постоянную временную сложность, вам, возможно, нет необходимости рассматривать это явно.
В вашем случае сложность f равна O (n2) & Сложность g равна O (LG (N)), в результате чего общая сложность O (N)2LG (п))
Другие решения
Вы должны принять во внимание сложность g в f,
g имеет O(log(n)) сложность.
так сложность f это сумма этих сложностей log(j)s.
В худшем случае это O(n²log(n)),
Чтобы найти сложность f, просто вставьте код g внутри f и подумайте, как будто это была одна целая функция. Сам вызов является O (1) и, следовательно, не влияет на сложность, как если бы код внутри g был выполнен в том месте, где вызывается g.
В некоторых случаях это будет неверно, например, если вы передадите в качестве параметра массиву значение n в качестве параметра: в этом случае самой копией массива будет O (n), поэтому вызов будет иметь некоторый эффект сложность.
Это интуитивно понятно n²log (n), но, точнее, вы получите следующее доказательство:
