有人可以帮助大O符号吗？

Question

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); 
} 

}

假设imputs不会导致无限循环

我理解的方法如何去，但我不能想出一个办法来表示方法。例如，如果值为0.00000009或9e-8，则该方法将调用printScientificNotation（value * 10，powerOfTen - 1）;否则，将调用printScientificNotation（value * 10，powerOfTen - 1）。八次和System.out.println（值+“x 10 ^”+ powerOfTen）;一旦。

所以它被e的指数递归调用。但是，我怎么用大O符号表示这个呢？

谢谢！

Answer 1

这是一个诡计问题吗？该代码将为其某些输入无限递归（例如，value = -1.0，powerOfTen = 0），因此对于任何有限函数f（n），其运行时不是O（f（n））。

编辑：假设value > 0.0 ...

运行时间（或递归深度，如果你喜欢看这样的说法）不依赖于powerOfTen的价值，只有在value。对于初始输入value范围[1.0,10.0），运行时间是恒定的，因此O（1），对于[10.0，+ infinity]中的value，您将value除以10，每次递归调用至value < 10.0，因此运行时间为O（日志（value））。 value可以在范围（0.0,1.0）中进行类似的说法，但请注意，对于此情况，日志为 value为负数。所以你的最终答案可能涉及绝对值操作。然后，您可以考虑是否有必要在渐近复杂性分析的上下文中指定对数基数。希望你可以从那里拿走它！