使用牛顿方法的平方根的时间复杂度

Question

我编写了一个java程序，使用newton的方法找到给定数字的平方根。这个程序完全按照预期工作但我不擅长时间复杂度。

那么请你告诉我以下程序的时间复杂程度。欢迎提出改进建议。

sqrt方法的Big O表示法是什么？

/**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

我会说复杂度是O（n），n是maxIterations。您不需要以递归方式编写此算法，您可以使用如下循环：

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

Answer 2

您的代码是用于求解x ^ 2-c = 0的Newton方法的实现。

众所周知，它具有二次收敛，这意味着如果你想要D位数的精度，它将需要大致的log（D）迭代，尽管这取决于你以复杂的方式对平方根的初始猜测。您可以阅读维基百科上的二次收敛证明：https://en.wikipedia.org/wiki/Newton%27s_method，其中包括二次收敛的前提条件。

由于你的初始猜测总是“1”，这可能不满足二次收敛的条件，如果我的记忆是正确的，这意味着对于大的x，某些步骤会有一些缓慢的收敛，其次是快速二次收敛。弄清楚实际时间复杂度的细节是非常复杂的，可能超出了你想要的范围。