递归函数的渐近复杂度是如何导出的
How is Asymptotic Complexity Derived for Recursive Functions
我还没有在网站上找到这个问题的一般答案
例如
如果我有一些算法；说二进制搜索我如何推导（数学显示）它的复杂性是 O(log(n)).
但更一般地说，如何推导任何递归算法的渐近复杂度？
很多递归算法的时间复杂度都可以用它本身来表示，就像算法一样。这称为 递归关系 ，通常采用
格式
T(N) = [sum of T(N_i) for recursive call i] + [sum of other work done in the function]
例如，二分搜索有一个非常简单的递归关系：对于每个递归调用 1) 搜索 space 减半，并且 2) 完成恒定量的工作。因此，该关系的形式为 T(N) = T(N / 2) + C。为了解决这个问题，反复替换它并找到一个模式：
T(N) = T(N / (2^1)) + C
= T(N / (2^2)) + 2C
= T(N / (2^3)) + 3C
= ...
= T(N / (2^m)) + mC
当搜索 space 只是一个元素时，即当 N / (2^m) = 1 时，二分搜索终止。这对应于 m = log2(N) 和 T(N / (2^m)) = 0.
因此时间复杂度为O(m) = O(log N)。 （对数的基数并不重要，C 也不重要，因为它们都是乘法常数）
对于大多数常见的递推关系，您的答案就是主定理。参见：https://en.wikipedia.org/wiki/Master_theorem
您还可以在 CRLS - 算法简介中找到相关说明。
我还没有在网站上找到这个问题的一般答案
例如
如果我有一些算法；说二进制搜索我如何推导（数学显示）它的复杂性是 O(log(n)).
但更一般地说，如何推导任何递归算法的渐近复杂度？
很多递归算法的时间复杂度都可以用它本身来表示，就像算法一样。这称为 递归关系 ，通常采用
格式T(N) = [sum of T(N_i) for recursive call i] + [sum of other work done in the function]
例如，二分搜索有一个非常简单的递归关系：对于每个递归调用 1) 搜索 space 减半，并且 2) 完成恒定量的工作。因此，该关系的形式为 T(N) = T(N / 2) + C。为了解决这个问题，反复替换它并找到一个模式：
T(N) = T(N / (2^1)) + C
= T(N / (2^2)) + 2C
= T(N / (2^3)) + 3C
= ...
= T(N / (2^m)) + mC
当搜索 space 只是一个元素时，即当 N / (2^m) = 1 时，二分搜索终止。这对应于 m = log2(N) 和 T(N / (2^m)) = 0.
因此时间复杂度为O(m) = O(log N)。 （对数的基数并不重要，C 也不重要，因为它们都是乘法常数）
对于大多数常见的递推关系，您的答案就是主定理。参见：https://en.wikipedia.org/wiki/Master_theorem
您还可以在 CRLS - 算法简介中找到相关说明。