NPS*_*NPS 2 algorithm complexity-theory stack space-complexity
当算法并不比辅助存储器的恒定量使用更多,但的确有O(log(N))递归调用(每一个走在堆栈上一些额外的空间),是算法的空间复杂度O(1)还是O(log(N))？
O(log(N))
O(1)
Tim*_*lds 6
如果递归算法没有利用尾递归,那么,是的,直接实现将使用O(log(N))空间.这是因为运行时必须一次将O(log(N))堆栈帧(每个O(1)大小)保留在内存中.
归档时间：
11 年，2 月 前
查看次数：
540 次
最近记录：