我在网站上没有找到对此问题的一般答案
例如
如果我有一些算法；说二分查找如何导出(以数学方式显示)它的复杂性是O(log(n))。
但更一般地说如何推导任何递归算法的渐近复杂度？
最佳答案
很多递归算法的时间复杂度都可以用自身来表示，就像算法一样。这称为递归关系，通常采用以下格式
T(N) = [递归调用 i 的 T(N_i) 之和] + [函数中完成的其他工作的总和]
例如，二分搜索有一个非常简单的递归关系:对于每个递归调用，1)搜索空间减半，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
当搜索空间只有一个元素时，即当N/(2^m) = 1时，二分搜索终止。这对应于 m = log2(N) 和 T(N/(2^m)) = 0。
因此时间复杂度为O(m) = O(log N)。 (日志的基数并不重要，C 也不重要，因为它们都是乘法常数)
关于big-o - 递归函数的渐近复杂度是如何推导的，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45618366/