Каково время работы T (n) = T (n / 2) + T (n / 2) + n ^ 2?

Question

Я знаю, это кажется вам каким-то легким, но кое-что беспокоило мой разум в эти дни.Имеют ли эти два уравнения одинаковое время выполнения?

1) T (n) = T (n / 2) + T (n / 2) + n ^ 2?

2) T (n) = 2T (n / 2) + n ^ 2?

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

Я думаю, что нашел свою ошибку, я не уверен, F (n) = F (n / 2) + .... отличается от T (n) !!

если мы напишем код {return f (n) + f (n)}, он должен отличаться от return 2 * f (n) в зависимости от времени выполнения.без оптимизации компиляторов

Answer 1

Оба алгоритма находятся в классе O (log n), но вариант № 2 всегда будет быстрее на практике.

Вызов функции повсеместно медленнее, чем целочисленное умножение, и обычно он значительно медленнее;это будет верно даже в тех ситуациях, когда детерминизм T может использоваться для эффективного кэширования результатов каждого T (x).

EDIT: Похоже, я неправильно понял OP.

Я понял, что ОП задает вопрос о двух разных, но математически эквивалентных реализациях конкретной рекурсивной функции T (n), которая возвращает сумму n ^ 2 + 2 (n / 2) ^ 2 + 4(n / 4) ^ 2 + ... + n (n / n) ^ 2, предполагая, что T (1) = 1, а n - идеальная степень 2.

Реализация # 1 называется T ()дважды для каждого уровня рекурсии.Я неправильно указал, что таким алгоритмом будет O (log n), когда на самом деле это O (2n - 1), или, проще, O (n).

Реализация # 2 называется T () только один раздля каждого уровня рекурсии, что делает его O (log n).Поэтому, скорее всего, они будут быстрее.

Теперь я понимаю, что T () должен был быть функцией Time для какого-то другого алгоритма!Виноват.Очевидно, что в этом случае для решения O () будет доминировать член n ^ 2.