为什么要学习数据结构与算法
- 提到数据结构与算法大多数人的第一印象一定是复杂、难学、工作用不到、面试还老问
- 既然工作用不到为什么面试还总是问呢，难道是为了故意刁难人？当然不是，他是考察一个人是否具有长期发展潜力的重要指标(就如同武侠秘籍里边的内功心法一样)
- 在哪里有用到？操作系统内核，一些框架源码，人工智能....
- 是否应该学？ 如果想在计算机行业长久待下去 可以说是毕竟之路
如何评价一个算法的好坏
1. 事后统计法
- 即对于同一组输入比较其最终的执行时间
public static void main(String[] args) {
Executors.execute(() -> sum(1000));
}
private static int sum(int n) {
int result = 0;
for (int i = 1; i <= n; i++) {
result += i;
}
return result;
}
public static void execute(Executor execute) {
if (Objects.isNull(execute)) { return; }
long start = System.currentTimeMillis();
execute.execute();
long end = System.currentTimeMillis();
long seconds = (start - end) / 1000;
System.out.println("该算法行时长为：【 " + seconds + " 】秒");
}
public interface Executor {
/**
* execute
*/
void execute();
}
此方法最大的特点就是简单直观，但却存在以下弊端
- 代码的执行时间严重依赖于硬件设备
- 需要编写一定量的代码才能测算出其好坏
- 难以保障测算公平性
2. 大O表示法(渐近分析)
-
特点
1.他是在数据规模为n时的一种估算方法 如：O(n)等。
2.大o表示法是一种粗略的估算模型，能帮助我们快速了解一个算法的执行效率
2.忽略常数 系数 - 示例
- O(n)
public static void print1(int n) {
for (int i = 0; i < n; i++) {
System.out.println(i);
}
}
- int i = 0; 复杂度 +1
- i < n; 每执行一次 +1 共需要+n次
- i++; 每执行一次 +1 共需要+n次
- System.out.println(i); +n次
- 1 + 3n 去掉常数以及系数
- 复杂度： O(n)
- O(n^2)
public static void print2(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println(i);
}
}
}
- 外层执行次数 1 + 2n
- 内层执行次数 n * (1 + 3n)
- 总工 1 + 2n + n * (1 + 3n) = 1 + 2n + n + 3n^2 = 1 + 3n + 3n^2
- 复杂度: O(n^2)
- O(logn)
public static void print3(int n) {
while ((n = n / 2) > 0) {
System.out.println(n);
}
}
- 如果n 为 8 执行次数为 3 即 2^3 = 8
- 执行次数为：log2(n)
- 复杂度 logn
- O(2^n)
public static int fib(int n) {
if (n <= 1) { return n; }
return fib(n - 1) + fib(n -2);
}
- 如果n为4
- 需要调用 16次 函数
- 复杂度为 2^n
- O(nlogn)
public static void print4(int n) {
for (int i = 0; i < n; i *= 2) {
for (int j = 0; j < 0; j ++) {
System.out.println(j);
}
}
}
- 1 + logn + logn + logn * (1 + 3n)
- 1 + 3logn + 3n * logn
- 复杂度为：O(nlogn)
- O(1)
public static int add(int a, int b) {
return a + b;
}
- 斐波那契数 O(n)级别写法
public static int fib1(int n) {
if (n <= 1) { return n; }
int first = 0;
int second = 1;
for (int i = 0; i < n - 1; i ++) {
int sum = first + second;
first = second;
second = sum;
}
return second;
}
public static int fib2(int n) {
if (n <= 1) { return n; }
int first = 0;
int second = 1;
while (n-- > 1) {
second += first;
first = second - first;
}
return second;
}
