Временная сложность для квадратного корня по методу Ньютона

Question

Я написал Java-программу для нахождения квадратного корня от заданного числа, используя метод Ньютона. Эта программа работает точно так, как задумано, но я не справляюсь со сложностью времени.

Так скажите, пожалуйста, какова сложность следующей программы. Приветствуются предложения по его улучшению.

Что такое система обозначений Big O для sqrt?

/**Find square root of a number using Newton's method**/
/**Specify number of correct precision required in a square root**/
/**Also specify maxIterations limit so that program won't go into into infinity loop**/
import java.util.*;
public class SqrtNewton{
        public static void main(String[] args){
            try{
                long startTime = System.nanoTime();
                Scanner scanner = new Scanner(System.in);
                //Number for which square root has to be found
                System.out.println("Enter number - ");
                long number = scanner.nextLong();
                //Maximum no of iterations if program does not found Square root untill then
                int maxIterations = 40; 
                //precision value to untill correct square root is required
                int precision = 3;
                //Value of x to start with for newton's method
                double x = 1;
                //Negative numbers do not have square roots
                if (number < 0) throw new IllegalArgumentException("Provided value is invalid");
                //iteration start
                int itr = 0;
                //epsilon value to check equality of double value untill given precision
                double epsilon = Math.pow(10,-precision);
                double squareRoot = sqrt(number,maxIterations,x,itr,epsilon);
                System.out.println("Square Root Of "+number+" With correct precision "+precision+" is :- "+squareRoot);
                System.out.printf("Square Root Of %d With correct precision %d is :- %."+precision+"f",number,precision,squareRoot);
                System.out.println();
                long endTime = System.nanoTime();
                System.out.println("Total Running Time - "+(endTime - startTime));
            }catch(Exception e){
                //e.printStackTrace();
                System.err.println("Exception - "+e.getMessage());
            }
        }
        private static double sqrt(long number,int maxIterations,double x,int itr,double epsilon) throws MaxIterationsReachedException{
            if(itr >= maxIterations){
                throw new MaxIterationsReachedException(maxIterations);
            }else{
                double x1 = (x + (number/x))/2;
                /**To check equality of double number untill given precision**/
                /**This will check 1.1333334 - 1.1333334 < 0.000001(if precision is 6)**/
                if(Math.abs(x1 - x) <=  epsilon){
                    System.out.println("Total Iterations - "+itr);
                    return x1;
                }
                else
                    return sqrt(number,maxIterations,x1,++itr,epsilon);
            }
        }
}


class MaxIterationsReachedException extends Exception{  
 MaxIterationsReachedException(int maxIterations){
     super("Maximum iterations limit "+maxIterations+" reached Increase maxIterations limit if required");
 }
} 

Answer 1

Ваш код является реализацией метода Ньютона для решения x ^ 2-c = 0.

Это, как известно, имеет квадратичную сходимость, что означает, что если вы хотите D цифр точности, это займет примерно логарифмические (D) итерации, хотя это сложным образом зависит от вашего первоначального предположения о квадратном корне. Вы можете прочитать доказательство квадратичной сходимости в википедии: https://en.wikipedia.org/wiki/Newton%27s_method, которая включает в себя предварительные условия для квадратичной сходимости.

Поскольку ваше первоначальное предположение всегда равно «1», это, вероятно, не будет удовлетворять условиям квадратичной сходимости, и если моя память верна, это означает, что для больших x будет некоторая медленная сходимость для некоторых шагов, после чего быстрой квадратичной сходимостью. Выработка деталей фактической сложности времени довольно сложна и, вероятно, выходит за рамки того, что вы хотите.

Answer 2

Я бы сказал, что сложность составляет O (n) с n это максимизации. Вам не нужно писать этот алгоритм рекурсивно, вы можете использовать цикл вроде этого:

private static double sqrt2(long number, int maxIterations, double x, int itr, double epsilon)
        throws MaxIterationsReachedException {
    double x1 = (x + (number / x)) / 2;
    while (Math.abs(x1 - x) > epsilon) {
        if (itr >= maxIterations) {
            throw new MaxIterationsReachedException(maxIterations);
        }
        x = x1;
        x1 = (x + (number / x)) / 2;
        itr++;
    }
    System.out.println("Total Iterations - " + itr);
    return x1;
}