一、 初识算法
1. 算法用来做什么？解决同一个问题，不同的算法效率可能差距会很大吗？
- 算法是用来
解决特定问题的一系列的执行步骤
- 不同的算法效率，
差距是巨大的
// 计算 a 跟 b 的和
public static int plus(int a, int b) {
return a + b;
}
// 计算 1+2+3+4+...+n 的和
public static int sum(int n) {
int result = 0;
for (int i = 1; i < n; i++) {
result += i;
}
return result;
}
2. 斐波那契数列的计算，递归思路的代码如下，会有什么问题？
/*
* 0 1 1 2 3 5 8 13 ...
*/
public static int fib1(int n) {
if (n <= 1) {
return n;
}
return fib1(n - 1) + fib1(n - 2);
}
- 这应该是最容易想到的算法了，但是，我们看到当计算 64 的时候，程序已经住了，算不出来结果了。
3. 斐波那契数列的计算，我们换一种求和算法的代码如下，依然会有问题吗？
/*
* 0 1 1 2 3 5 8 13 ...
*/
public static int fib2(int n) {
if (n <= 1) return n;
int first = 0;
int second = 1;
int sum = 0;
for (int i = 1; i < n; i++) {
sum = first + second;
first = second;
second = sum;
}
return sum;
}
- 这个计算速度就非常快了，即使
n = 64 也能瞬间计算出来
4. 思考，如果是你，你会怎么量化的对比两个算法的效率？
package com.lsp;
public class Times {
public interface Block {
void runBlock();
}
public static void execute(String taskName,Block block) {
long startTime = System.currentTimeMillis();
block.runBlock();
long endTime = System.currentTimeMillis();
System.out.println("===========================");
System.out.println("【" + taskName + "】");
System.out.println("耗时：" + (endTime - startTime) / 1000.0 + "秒");
}
}
public static void main(String[] args) {
int n = 43;
Times.execute("fib1", new Block() {
@Override
public void runBlock() {
fib1(n);
}
});
Times.execute("fib2", new Block() {
@Override
public void runBlock() {
fib2(n);
}
});
}
===========================
【fib1】
耗时：1.703秒
===========================
【fib2】
耗时：0.0秒
二、 算法复杂度
1. 上一个方案评判算法复杂度有什么明显缺点？如何评判一个算法的好坏（从一个前提、两个维度来说）？
- 上述方案的明显缺点：
- ① 执行时间严重依赖硬件以及运行时各种不确定的因素
- ② 必须编写响应的测算代码
- ③ 测试数据的选择比较难保证公正性
- 评判算法的好坏：
- 一个前提：
正确性、可读性、健壮性
- 两个维度：
- ①
时间复杂度： 估算程序指令的执行次数（执行时间）
- ②
空间复杂度： 估算所需占用的存储空间
2. 用你的知识，计算一下下面代码的执行次数？我发现 log 这个函数，需要再去巩固下，忘记了~~
public static void test1(int n) {
if (n > 10) {
System.out.println("n > 10");
} else if (n > 5) { // 2
System.out.println("n > 5");
} else {
System.out.println("n <= 5");
}
for (int i = 0; i < 4; i++) {
System.out.println("test");
}
}
public static void test2(int n) {
for (int i = 0; i < n; i++) {
System.out.println("test");
}
}
public static void test3(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
public static void test4(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < 15; j++) {
System.out.println("test");
}
}
}
public static void test5(int n) {
while ((n = n / 2) > 0) {
System.out.println("test");
}
}
public static void test6(int n) {
while ((n = n / 5) > 0) {
System.out.println("test");
}
}
public static void test7(int n) {
for (int i = 1; i < n; i = i * 2) {
// 1 + 3n
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
public static void test10(int n) {
int a = 10;
int b = 20;
int c = a + b;
int[] array = new int[n];
for (int i = 0; i < array.length; i++) {
System.out.println(array[i] + c);
}
}
public static void test1(int n) {
// 汇编指令
// O(1)
if (n > 10) {
System.out.println("n > 10");
} else if (n > 5) { // 2
System.out.println("n > 5");
} else {
System.out.println("n <= 5");
}
// 1 + 4 + 4 + 4
for (int i = 0; i < 4; i++) {
System.out.println("test");
}
// 140000
// O(1)
}
public static void test2(int n) {
// O(n)
// 1 + 3n
for (int i = 0; i < n; i++) {
System.out.println("test");
}
}
public static void test3(int n) {
// 1 + 2n + n * (1 + 3n)
// 1 + 2n + n + 3n^2
// 3n^2 + 3n + 1
// O(n^2)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
public static void test4(int n) {
// 1 + 2n + n * (1 + 45)
// 1 + 2n + 46n
// 48n + 1
// O(n)
for (int i = 0; i < n; i++) {
for (int j = 0; j < 15; j++) {
System.out.println("test");
}
}
}
public static void test5(int n) {
// 8 = 2^3
// 16 = 2^4
// 3 = log2(8)
// 4 = log2(16)
// 执行次数 = log2(n)
// O(logn)
while ((n = n / 2) > 0) {
System.out.println("test");
}
}
public static void test6(int n) {
// log5(n)
// O(logn)
while ((n = n / 5) > 0) {
System.out.println("test");
}
}
public static void test7(int n) {
// 1 + 2*log2(n) + log2(n) * (1 + 3n)
// 1 + 3*log2(n) + 2 * nlog2(n)
// O(nlogn)
for (int i = 1; i < n; i = i * 2) {
// 1 + 3n
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
public static void test10(int n) {
// O(n)
int a = 10;
int b = 20;
int c = a + b;
int[] array = new int[n];
for (int i = 0; i < array.length; i++) {
System.out.println(array[i] + c);
}
}
3. 大 O 表示法是忽略了三个什么因素？对数要注意什么？
- 一般用大 O 表示法描述复杂度，它表示的是数据规模 n 对应的复杂度
- 忽略
常数、系数、低阶
- 注意：大 O 表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的好坏。
image.png
image.png
4. 常见的复杂度（至少列举三个）？
image.png
5. 实战：自行计算斐波那契数列两种算法的时间复杂度，你能算出来吗？
image.png
网友评论