算法数据结构 - JAVA

1. 算法的评估

1.1 事后统计法

比较不同的算法对于同一组输入的执行处理时间。

缺点

• 在于执行时间严重依赖于硬件的以及运行时各种不确定的环境因素
• 且必须编写对应的计算代码
• 测试数据的选择也有关系。

1.2 正确的评判标准

• 正确性
• 健壮性
• 可读性
• 时间复杂度（执行时间，执行次数）小
• 空间复杂度（占用存储的空间）少

1.3 Big O 表示法

仅仅是一种估算，粗略的分析模型，短时间了解一个算法的执行效率。 O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

Notes fib(斐波拉切)函数的时间复杂度在 O(2^n)

1.4 算法的优化方向

• 用尽量少的存储空间
• 用尽量少的执行步骤（执行时间）
• 根据特定情况，空间换时间
• 根据特定情况，时间换空间

1.5 多个数据规模

• O（n + k）

2. 动态数组

2.1 线性表

线性表是具有n个相同类型元素的有限序列。 常见的线性表有：

• 数组
• 链表
• 栈
• 队列
• 哈希表

2.1.1 数组

数组是一种顺序存储的线性表，所有元素的内存地址都是连续的。

// JAVA
// arr 是一个局部变量，存放在 堆 空间。
// new 获取的数据存放在 栈 空间。
int[] arr = new Array[]{1,2,3};

泛型：让动态数组更加通用，可以存放任意数据类型。

// JAVA

elements = (E[]) new Object[capaticy];//

Reference

1. Love IT site