big-o - 这个函数的计算复杂度是多少？

Question

我想知道这个函数的计算复杂度是多少？

2^(log(n)-1)

日志以 2 为底。

Answer 1

这取决于使用什么算法来计算所有对数和幂。如果您足够聪明地注意到这个函数本质上是除以 2，那么您可以O(1)通过右移来在常数时间内（即 ）为整数实现它。