时间戳

首页 > 解决方案 > 使用 T(n) 方法计算时间复杂度？

c - 使用 T(n) 方法计算时间复杂度？

问题描述

如何计算f()使用T(n)方法的时间复杂度？

int f (int n)
{
    if (n==1)
        return 1;
    return f(f(n-1));
}

到现在为止我做了什么？

T(n)=T(T(n-1))=T(T(T(n-2)))=T(T(T(T(n-3))))...

另外，我知道对于每个 n>=1 函数总是返回 1

以及为什么要更改最后一行：

return f(f(n-1));

至：

return 1+f(f(n-1));

会改变时间复杂度（注意：它肯定会将复杂度从 n 更改为 2^n）？

标签： calgorithmtime-complexity

解决方案

时间复杂度会发生变化，因为函数并不return 1;总是因为+1.

对于return T(T(n-1));第二个T呼叫将始终使用 呼叫1，这将仅再呼叫 1 个。调用次数为2*n-1，因此复杂度为 O(n)。

因为return 1 + T(T(n-1));并非所有调用T都会导致1,会T(3)导致调用。所以第二次调用取决于 的值。递增将导致调用加倍。调用次数为，因此复杂度为 O(2^n)。在这里可以看到调用次数：https ://ideone.com/1KEAkU37nn2^n - 1

第一个版本（T 总是返回 1）：

              T(4)
    T(1)                   T(3)
                     T(1)         T(2)
                              T(1)    T(1)

您可以看到左侧调用（外部调用）将始终被调用，1并且树不会继续存在。

第二个版本（T 并不总是返回 1）：

                    T(4)
          T(3)                   T(3)
   T(2)        T(2)         T(2)        T(2)
T(1) T(1)   T(1) T(1)    T(1) T(1)   T(1)  T(1)

在这里您可以看到，由于返回值的更改T(n) == n，第二次T调用使调用次数增加了一倍。

空间复杂度没有增加，因为递归深度没有改变，两个T(4)图都有 4 行，对于第二棵树，左边部分只能在右边部分完全完成后执行。例如，对于运行T(4)的最大T功能数都是4.

推荐阅读