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

Question

我已经编写了一个 java 程序来使用牛顿 method.This 程序求给定数字的平方根，该程序完全符合预期但我不擅长时间复杂度。

那么你能告诉我下面程序的时间复杂度是多少吗？欢迎提出改进建议。

sqrt 方法的大 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 是最大迭代次数。您不需要以递归方式编写此算法，您可以使用这样的循环：

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 的牛顿法的实现。

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

由于你的初始猜测总是“1”，这可能不满足二次收敛的条件，如果我没记错的话，这意味着对于大x，某些步骤会收敛一些慢，然后是快速二次收敛。计算实际时间复杂度的细节非常复杂，可能超出您的预期。

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

Time complexity for square root using Newton's method

java

algorithm

time-complexity

newtons-method