有人可以帮忙用大O表示法吗？
void printScientificNotation(double value, int powerOfTen)
{
if (value >= 1.0 && value < 10.0)
{
System.out.println(value + " x 10^" + powerOfTen);
}
else if (value < 1.0)
{
printScientificNotation(value * 10, powerOfTen - 1);
}
else // value >= 10.0
{
printScientificNotation(value / 10, powerOfTen + 1);
}
假设
输入不会导致无限循环，
我理解该方法是如何进行的，但我无法找出表示该方法的方法。 例如，如果 value 为 0.00000009 或 9e-8，则该方法将调用 printScientificNotation(value * 10, powerOfTen - 1);八次和 System.out.println(value + " x 10^" + powerOfTen);一次。
因此，它由 e 的指数递归调用。但我该如何用大 O 表示法来表示呢？
谢谢！
void printScientificNotation(double value, int powerOfTen)
{
if (value >= 1.0 && value < 10.0)
{
System.out.println(value + " x 10^" + powerOfTen);
}
else if (value < 1.0)
{
printScientificNotation(value * 10, powerOfTen - 1);
}
else // value >= 10.0
{
printScientificNotation(value / 10, powerOfTen + 1);
}
}
assuming that imputs will not lead to infinite loops
I understand how the method goes but I cannot figure out a way to represent the method.
For example, if value was 0.00000009 or 9e-8, the method will call on printScientificNotation(value * 10, powerOfTen - 1); eight times and System.out.println(value + " x 10^" + powerOfTen); once.
So the it is called recursively by the exponent for e. But how do I represent this by big O notation?
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是一个技巧问题吗？该代码将对其某些输入进行无限递归（例如，value=-1.0、powerOfTen=0），因此对于任何有限函数 f(n)，其运行时间都不是 O(f(n))。
编辑：假设
值> 0.0...运行时间（或递归深度，如果您喜欢这样看）不取决于
powerOfTen的值，仅取决于value.对于 [1.0, 10.0) 范围内的初始输入value，运行时间是恒定的，因此 O(1)，对于 [10.0, +无穷大) 中的value，对于每个递归调用，您将value除以 10，直到value10.0，因此运行时间为 O(log10(value))。对于 (0.0,1.0) 范围内的value也可以进行类似的论证，但请注意，在这种情况下 log10value为负数。所以你的最终答案可能涉及绝对值运算。然后您可能会考虑是否有必要在渐近复杂性分析的背景下指定对数底。希望你能从那里得到它！Is this a trick question? That code will recurse infinitely for some of its inputs (for example, value=-1.0, powerOfTen=0), therefore its runtime is not O(f(n)) for any finite function f(n).
Edit: Assuming
value > 0.0...The run time (or recursion depth, if you prefer to look at it that way) does not depend on the value of
powerOfTen, only onvalue. For an intial inputvaluein the range [1.0, 10.0), the run time is constant, so O(1), Forvaluein [10.0, +infinity), you dividevalueby 10 for each recursive call untilvalue < 10.0, so the runtime is O(log10(value)). A similar argument can be made forvaluein the range (0.0,1.0), but note that log10valueis negative for this case. So your final answer might involve an absolute value operation. Then you might consider whether it's necessary to specify the logarithm base in the context of an asymptotic complexity analysis. Hopefully you can take it from there!