Я хочу вычислить нотацию Big O для площади круга. Интересно, какова временная сложность Pi * r ^ 2? это O (n) или O (n ^ 2)? Также проверьте правильность моих действий.
Algorithm
Step 1: Start // f(n)=O(1) ( Executes 1 time)
Step 2: Get an integer input from user for AREA and RADIUS//. f(n)=O(n)=O(1) ( Executes 1 time)
Step 3: Print the statement "Enter the Radius of Circle: //f(n)=O(n)=O(1) ( Executes 1 time)
Step 4: Calculate the area of the circle using the formula of
//f(n)=O(n)=?
(r - Radius) //f(n)=O(n)=O(1) ( Executes 1 time)
Step 5: Print the statement "Area of Circle:" //f(n)=O(n)=O(1) ( Executes 1 time)
Step 6: Print Area//f(n)=O(n)=O(1) ( Executes 1 time)
Step 7: Stop //f(n)=O(n)=O(1) ( Executes 1 time)
f(n)=O(n)=?
я отредактировал вопрос. Извините за опечатку. Это должно быть большое обозначение O. Я не понимаю, должна ли большая нотация O для формулы быть pi * r ^ 2, это O (n) или O (n ^ 2)?
это ни то, ни другое: это O (1): сложность постоянна независимо от размера r
«Пожалуйста, также [...]» - существует ограничение на один вопрос на вопрос (и открытые вопросы «это правильно» здесь не по теме).
Спасибо, что сообщили мне, я удалил свой предыдущий комментарий.
Это зависит от вашей модели вычислений.
Для большинства практических целей это O(1)
, потому что время выполнения не зависит от вашего ввода r
. Это неявно предполагает, что ваш ввод ограничен, например, вписывается в 32-битное целое число.
Более теоретически вы можете думать о произвольном большом r
. Тогда N
в большой нотации O обычно представляет собой длину (количество битов) r
, а не размер числа. Здесь вы не можете предположить, что вы можете умножить любые два числа в O(1)
, но это будет зависеть от длины чисел.
В этом случае вы получите O(N^2)
с наивным алгоритмом умножения, который можно улучшить до O(N log N)
с помощью более продвинутых методов. См. https://en.wikipedia.org/wiki/Multiplication_algorithm#Computational_complexity_of_multiplication.
Большой О? ты имеешь в виду площадь? так как это то, что ваш расчет должен дать в результате. Или вы имеете в виду Big O = окружность?