время выполнения рекурсивного алгоритма
Для вышеприведенного алгоритма, я могу только выяснить, среда выполнения для
if n==0:
равен 1, и среда выполнения для
rec_opt(n-1)
будет T (n-1). Но я не могу понять, среду выполнения для
rec_opt(p[n])
и почему повторение имеет экспоненциальную замкнутую форму, O (2^п )
и, кроме того, почему это алгоритмом будет O (n).
rec_opt (р [п])
Для rec_opt рекурсии вызова (р [п]), то будет еще один рекурсию дерево, которое будет действовать как rec_opt (п-1). Поскольку p[n] может быть любым значением от 1 - n, то можно предположить, что он будет действовать как rec_opt(n).
И, кроме того, почему этот алгоритм будет O (n).
На второй части, как алгоритм, выполняющий memoization, он не будет вычислять одну и ту же суб-проблему снова и снова. Вот почему сложность резко сократилась до O(n).
Для более пожалуйста chech dynamic programming.
Теперь я понимаю rec_opt [n]. Но для времени выполнения первого алгоритма, который является T (n) = 2T (n-1) + c, не должно быть O (n)? Поскольку n - старший член в T (n). – yashirq
Если вы правильно поняли rec_opt (p [n]), тогда сложность будет понятна, если вы попробуете ее с помощью ручки и бумаги. Нарисуйте дерево и подсчитайте количество узлов. Для первого алгоритма вы увидите, что вы делаете одно и то же задание снова и снова. – ruhul