<分区>
自然数 n 的立方根定义为满足 m^3≤n 的最大自然数 m。计算n(n用二进制表示)的立方根的复杂度为
(A) O(n) 但不是 O(n^0.5)
(B) O(n^0.5) 但不是 O((log n)^k) 对于任何常数 k > 0
(C) O((log n)^k) 对于某个常数 k > 0，但对于任何常数 m > 0 则不是 O((log log n)^m)
(D) O((log log n)^k) 对于某个常数 k > 0.5，但不是 O((log log n)^0.5)
我迷失了解决前一年的问题。任何人都可以帮助我理解这个问题
最佳答案
要回答这个问题，您需要找到寻找 n 的整数立方根 m 的复杂性的上限和下限。至少有一个上限是微不足道的，并且排除了答案 A 和 B:可以使用二分查找在 O(log n) 时间内找到 m。
另请注意，输入大小为 O(log n)，因为用二进制表示法表示任意 n 所需的最少位数与 log n 成正比。因为数的所有位都必须被处理才能解决问题，θ(log n)是解决问题时间的下界，因此问题不能在时间内解决 O((log log n)^w) [w is some constant > 0] 因为那不是 O(log n)。因此，答案 C 适用。
关于algorithm - 求 n 的立方根的复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20767702/
相关文章：
algorithm - 手动计算递归斐波那契算法的时间复杂度
algorithm - 对于大小为 n 的输入，对于 n 的哪些值，插入排序优于合并排序？
perl - 是否可以以具有 `O(log(n))` 查找和插入的方式使用 Perl 哈希？
c# - 如何以最少的访问量(最有效)从位置FIFO中选择项目
algorithm - 我在哪里可以学习/找到使用 OpenCV 从 Kinect 流式传输的手势识别示例？
javascript - 带缓存的递归求解最长回文子序列的大O分析