为什么相乘比平方根快很多倍？

Question

我对以下算法有一些疑问，可以判断数字是否为质数，我也知道使用Eratosthenes筛子可以更快地响应。

1. 为什么计算速度更快i i * sqrt (n)。比sqrt (n)只有一次？
2. 为什么Math.sqrt()比我的sqrt()方法快？
3. 这些算法O（n），O（sqrt（n）），O（n log（n））的复杂度是多少？

        public class Main {

    public static void main(String[] args) {

    // Case 1 comparing Algorithms
    long startTime = System.currentTimeMillis(); // Start Time
    for (int i = 2; i <= 100000; ++i) {
        if (isPrime1(i))
            continue;
    }
    long stopTime = System.currentTimeMillis(); // End Time
    System.out.printf("Duracion: %4d ms. while (i*i <= N) Algorithm\n",
            stopTime - startTime);

    // Case 2 comparing Algorithms
    startTime = System.currentTimeMillis();
    for (int i = 2; i <= 100000; ++i) {
        if (isPrime2(i))
            continue;
    }
    stopTime = System.currentTimeMillis();
    System.out.printf("Duracion: %4d ms. while (i <= sqrt(N)) Algorithm\n",
            stopTime - startTime);

    // Case 3 comparing Algorithms
    startTime = System.currentTimeMillis();
    for (int i = 2; i <= 100000; ++i) {
        if (isPrime3(i))
            continue;
    }
    stopTime = System.currentTimeMillis();
    System.out.printf(
              "Duracion: %4d ms. s = sqrt(N) while (i <= s) Algorithm\n",
              stopTime - startTime);

    // Case 4 comparing Algorithms
    startTime = System.currentTimeMillis();
    for (int i = 2; i <= 100000; ++i) {
        if (isPrime4(i))
            continue;
    }
    stopTime = System.currentTimeMillis();
    System.out.printf(
              "Duracion: %4d ms. s = Math.sqrt(N) while (i <= s) Algorithm\n",
              stopTime - startTime);
    }

    public static boolean isPrime1(int n) {
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    public static boolean isPrime2(int n) {
        for (long i = 2; i <= sqrt(n); i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    public static boolean isPrime3(int n) {
        double s = sqrt(n);
        for (long i = 2; i <= s; i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    public static boolean isPrime4(int n) {
        // Proving wich if faster between my sqrt method or Java's sqrt
        double s = Math.sqrt(n);
        for (long i = 2; i <= s; i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    public static double abs(double n) {
        return n < 0 ? -n : n;
    }

    public static double sqrt(double n) {
        // Newton's method, from book Algorithms 4th edition by Robert Sedgwick
        // and Kevin Wayne
        if (n < 0)
            return Double.NaN;

        double err = 1e-15;
        double p = n;

        while (abs(p - n / p) > err * n)
            p = (p + n / p) / 2.0;

        return p;
    }
    }

这也是我的代码的链接：http :
//ideone.com/Fapj1P

Answer 1

1. Why is faster to compute i*i, sqrt (n) times. than sqrt (n) just one time ? 查看下面的复杂性。计算平方根的额外费用。

2. Why Math.sqrt() is faster than my sqrt() method ?
Math.sqrt（）委托对StrictMath.sqrt的调用以硬件或本机代码完成。

3. What is the complexity of these algorithms?
您描述的每个功能的复杂性

i=2 .. i*i<n O（平方（n））

i=2 .. sqrt(n) O（sqrt（n）* log（n））

i=2 .. sqrt (by Newton's method) O（sqrt（n））+ O（log（n））

i=2 .. sqrt (by Math.sqrt) O（平方（n））

牛顿方法的复杂性，来自
http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity