14天阅读挑战赛

话不多说，我们接着上篇文章 《趣学算法》阅读笔记（一），继续总结学习

1. 第一章 算法之美

1.3 哥德巴赫猜想的证明

哥德巴赫猜想：任一大于2的偶数，都可表示成两个素数之和。
验证：2000以内大于2的偶数都能够分解为两个素数之和。

class Main {
    public static void main(String[] args) {
        System.out.println(isPass(2000));
    }

    /**
     * 哥德巴赫猜想：任一大于2的偶数，都可表示成两个素数之和。
     * 
     * @Title: isPass
     * @Description:验证：2000以内大于2的偶数都能够分解为两个素数之和。
     * @author: itbird
     * @date 2022年10月19日 下午8:42:52
     * @param n
     * @return boolean 时间复杂度: O((n^2)logn) 空间复杂度: O(N)
     */
    public static boolean isPass(int n) {
        if (n <= 3) {
            return false;
        }
        // 4为第一个大于2的偶数
        for (int i = 4; i <= n; i = i + 2) {
            if (!isDecomposeForTwoPrime(i)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 是否可以分解为两个素数只和
     * 
     * @Title: isDecomposeForTwoPrime
     * @Description:
     * @author: itbird
     * @date 2022年10月20日 上午9:19:42
     * @param i
     * @return boolean 时间复杂度: O(nlogn) 空间复杂度: O(1)
     */
    private static boolean isDecomposeForTwoPrime(int i) {
        for (int j = 2; j < i; j++) {
            if (isPrime(j) && isPrime(i - j)) {
//                System.out.println(j + "  " + (i - j));
                return true;
            }
        }
        return false;
    }

    /**
     * 是否为一个素数 ,1和本身
     * 
     * @Title: isPrime
     * @Description:
     * @author: itbird
     * @date 2022年10月20日 上午9:23:01
     * @param j
     * @return boolean 时间复杂度: O(logn) 空间复杂度: O(1)
     */
    private static boolean isPrime(int j) {
        for (int i = 2; i <= Math.sqrt(j); i++) {
            if (j % i == 0) {
                return false;
            }
        }
        return true;
    }
}

1.4 时间复杂度如何求取？

求解算法的时间复杂度的具体步骤是：

• 找出算法中的基本语句：即算法中执行次数最多的那条语句，通常是最内层循环的循环体。
• 计算基本语句的执行次数的数量级；
• 用大Ο记号表示算法的时间性能。

例子1：O(1) 算法
此代码只需要执行一次，时间复杂度为O(1)。

int i = 1;
print("i = %d \n", i);

例子2：O(n) 算法
循环求和算法， 这个算法需要执行n次O(1)的打印操作，因此

for(int i=0; i<N; i++){
   printf("i = %d \n", i);
}

例子3： O(n^2)算法
嵌套循环求和算法，这个算法需要执行N*N此O(1)的打印操作，因此

for(int i=0; i<N; i++){
   for(int j=0; j<N; j++){
      printf("i = %d, j = %d \n", i, j);
   }
}

例子4： O(logN)算法
在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。假设循环x次之后，i 就大于 n 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2n，也就是说当循环 log2n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)。

int i = 1;
while(i<n)
{
    i = i * 2;
}