Может ли кто-нибудь помочь с большой записью 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 (значение * 10, powerOfTen - 1); восемь раз и System.out.println (значение + "x 10 ^" + powerOfTen); один раз.

Таким образом, он называется рекурсивно показателем для e. Но как я могу представить это большой нотацией O?

Спасибо!

Answer 1

Это спорный вопрос? Этот код будет бесконечно возвращаться для некоторых его входов (например, value = -1.0, powerOfTen = 0), поэтому его время выполнения не O (f (n)) для любой конечной функции f (n).

Edit: Предположим, что value > 0.0 ...

Время работы (или глубина рекурсии, если вы предпочитаете смотреть на это таким образом) не зависит от величины powerOfTen, только на value. Для начального ввода value в диапазоне [1.0, 10.0) время работы постоянное, поэтому O (1), для value в [10.0, + бесконечность) вы делите value на 10 для каждого рекурсивного вызова до value < 10.0, поэтому время выполнения - O (log (value)). Аналогичный аргумент может быть сделан для value в диапазоне (0,0,1,0), но обратите внимание, что для этого случая отрицательный журнал value. Таким образом, ваш окончательный ответ может включать операцию абсолютного значения. Тогда вы можете подумать, нужно ли указывать базу логарифмов в контексте анализа асимптотической сложности. Надеюсь, вы можете взять это оттуда!