复杂性，求n的立方根 [英] Complexity to find cube root of n

问题描述

的自然数n的立方根定义为最大的自然数m，使得立方公尺3≤n。在计算n的立方根（n被重新psented二进制符号$ P $）的复杂性是

The cube root of a natural number n is defined as the largest natural number m such that m^3≤n. The complexity of computing the cube root of n (n is represented in binary notation) is

（A）为O（n），而不是为O（n ^ 0.5）

(A) O(n) but not O(n^0.5)

（B）为O（n ^ 0.5），而不是O（（log n）的^ K）> 0

(B) O(n^0.5) but not O((log n)^k) for any constant k > 0

（C）O（（log n）的^ k）的一些常数k> 0，而不是O（（日志log n）的^ M）为任何常数m> 0

(C) O((log n)^k) for some constant k > 0, but not O((log log n)^m) for any constant m > 0

（D）O（（log日志N）^ k）的一些常数k> 0.5，而不是O（（日志log n）的^ 0.5）

(D) O((log log n)^k) for some constant k > 0.5, but not O((log log n)^0.5)

我迷失解决这个previous年的问题。可以任何一个能帮助我理解这个问题。

I am lost solving this previous year problem .Can any one help me to understand this question

推荐答案

要回答这个问题，你需要找到上或许下限上找到n的整数立方根米的复杂性。至少有一个上限是微不足道的，而且排除了答案A和B：M可以在O使用二进制搜索（log n）的时间内找到。

To answer that question, you need to find upper and perhaps lower bounds on the complexity of finding an integer cube root m of n. At least one upper bound is trivial, and rules out answers A and B: m can be found in O(log n) time using binary search.

还要注意的是，输入大小为O（log n）的，因为重新present的任意n个二进制符号所需要的比特的最小数目成正比日志N。因为数字的所有位必须进行处理，以解决这个问题，θ（log n）的是一个下界时间来解决问题，因此，问题不能在时间为O解决（（日志log n）的^ w）的[其中w是一些常数> 0]，因为这不是O（log n）的。因此，答案C适用。

Also note that the input size is O(log n) because the minimum number of bits needed to represent an arbitrary n in binary notation is proportional to log n. Because all bits of the number must be processed to solve the problem, θ(log n) is a lower bound on the time to solve the problem, and therefore the problem cannot be solved in time O((log log n)^w) [where w is some constant > 0] because that isn't O(log n). Thus, answer C applies.

这篇关于复杂性，求n的立方根的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！