查找递归公式的时间复杂度
Finding time complexity of recursive formula
我正在尝试找出递归公式的时间复杂度（大 O）。
我试图找到一个解决方案，你可以在下面看到公式和我的解决方案：
您用问号指定的最后一个假设是错误的！不要做这样的假设。
您提供的其余操作似乎都是正确的。但他们实际上让你无处可去。
你应该在草稿中间完成这个练习：
T(n) = O(T(1)^(3^log2(n)))
就是这样。这就是解决方案！
你实际上可以声称
3^log2(n) == n^log2(3) ==~ n^1.585
然后你得到：
T(n) = O(T(1)^(n^1.585))
这有点类似于你在草稿的第二部分所做的操作。
所以你也可以这样放着。但是你不能弄乱指数。更改指数值会更改 big-O 分类。
正如 Brenner 所说，您最后的假设是错误的。原因如下：让我们从 Wikipedia page 中获取 O(n) 的定义（使用 n 而不是 x）：
f(n) = O(n) if and only if there exist constants c, n0 s.t. |f(n)| <= c |g(n)|, for alln >= n0.
我们要检查是否 O(2^n^2) = O(2^n)。显然，2^n^2 在 O(2^n^2) 中，所以让我们选择 f(n) = 2^n^2 并检查它是否在 O(2^n) 中。把这个代入上面的公式：
exists c, n0: 2^n^2 <= c * 2^n for all n >= n0
让我们看看是否可以找到合适的常量值 n0 和 c 使上述为真，或者我们是否可以推导出一个矛盾来证明它不正确：
两边取日志：
log(2^n^2) <= log(c * 2 ^ n)
简化：
2 ^n log(2) <= log(c) + n * log(2)
除以log(2):
n^2 <= log(c)/log(2) * n
很容易看出不存在 c, n0 上面对所有 n >= n0 都是正确的，因此 O(2^n^2) = O(n^2) 不是一个有效的假设.
我正在尝试找出递归公式的时间复杂度（大 O）。
我试图找到一个解决方案，你可以在下面看到公式和我的解决方案：
您用问号指定的最后一个假设是错误的！不要做这样的假设。
您提供的其余操作似乎都是正确的。但他们实际上让你无处可去。
你应该在草稿中间完成这个练习：
T(n) = O(T(1)^(3^log2(n)))
就是这样。这就是解决方案！
你实际上可以声称
3^log2(n) == n^log2(3) ==~ n^1.585
然后你得到：
T(n) = O(T(1)^(n^1.585))
这有点类似于你在草稿的第二部分所做的操作。 所以你也可以这样放着。但是你不能弄乱指数。更改指数值会更改 big-O 分类。
正如 Brenner 所说，您最后的假设是错误的。原因如下：让我们从 Wikipedia page 中获取 O(n) 的定义（使用 n 而不是 x）：
f(n) = O(n)if and only if there exist constantsc,n0s.t.|f(n)| <= c |g(n)|, for alln >= n0.
我们要检查是否 O(2^n^2) = O(2^n)。显然，2^n^2 在 O(2^n^2) 中，所以让我们选择 f(n) = 2^n^2 并检查它是否在 O(2^n) 中。把这个代入上面的公式：
exists c, n0: 2^n^2 <= c * 2^n for all n >= n0
让我们看看是否可以找到合适的常量值 n0 和 c 使上述为真，或者我们是否可以推导出一个矛盾来证明它不正确：
两边取日志：
log(2^n^2) <= log(c * 2 ^ n)
简化：
2 ^n log(2) <= log(c) + n * log(2)
除以log(2):
n^2 <= log(c)/log(2) * n
很容易看出不存在 c, n0 上面对所有 n >= n0 都是正确的，因此 O(2^n^2) = O(n^2) 不是一个有效的假设.