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