1.算法复杂度分析
为什么要进行复杂度分析？
- 指导你编写出性能更优的代码
- 评判别人写的代码的好坏
分类：
- 时间复杂度分析
- 空间复杂度分析
/**
* 求1~n的累加和 * @param n * @return
*/
public int sum(int n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
sum = sum + i;
}
return sum;
}时间复杂度分析
时间复杂度分析：来评估代码的执行耗时的
1.假如每行代码的执行耗时一样：1ms
2.分析这段代码总执行多少行？
3.代码耗时总时间： T(n) = (3n + 3) * 1ms
- 大O表示法：不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势
- T(n)与代码的执行次数成正比(代码行数越多，执行时间越长)
T(n) =O(3n + 3) ->T(n) = O(n)
- 当n很大时，公式中的低阶，常量，系数三部分并不左右其增长趋势，因此可以忽略，我们只需要记录一个最大的量级就可以了
常见复杂度表示形式
常见复杂度
总结：只要代码的执行时间不随着n的增大而增大，这样的代码复杂度都是O(1)
由以上分析可知，代码的时间复杂度表示为O(log n)
以下代码的时间复杂度是多少？
public void test04(int n) {
int i = 1;
while (i <= n) {
i = i * 10;
}
}复杂度表示为O(log n)
总结
空间复杂度
空间复杂度全称是渐进空间复杂度，表示算法占用的额外存储空间与数据规模之间的增长关系
我们常见的空间复杂度就是O(1),O(n),O(n ^2)，其他像对数阶的复杂度几乎用不到，因此空间复杂度比时间复杂度分析要简单的多。
总结
1.什么是算法时间复杂度
- 时间复杂度表示了算法的执行时间与数据规模之间的增长关系
2.常见的时间复杂度有哪些？
- O(1)、O(n)、O(n^2)、O(logn)、O(n*logn)
- 速记口诀：常对幂指阶
3.什么是算法的空间复杂度？
- 表示算法占用的额外存储空间与数据规模之间的增长关系
- 常见的空间复杂度：O(1)、O(n)、O(n ^2)
2.AarryList的数据结构
数组：数组（Array）是一种用连续的内存空间存储相同数据类型数据的线性数据结构。
数组如何获取其他元素的地址值？
为什么数组索引从0开始呢？假如从1开始不行吗？
- 在根据数组索引获取元素的时候，会用索引和寻址公式来计算内存所对应的元素数据，寻址公式是：数组的首地址+索引乘以存储数据的类型大小
- 如果数组的索引从1开始，寻址公式中，就需要增加一次减法操作，对于CPU来说就多了一次指令，性能不高。
操作数组的时间复杂度（查找）
1.随机查询(根据索引查询)
数组元素的访问是通过下标来访问的，计算机通过数组的首地址和寻址公式能够很快速的找到想要访问的元素，时间复杂度O(1)
public int test01(int[] a, int i) {
return a[i];
// a[i] = baseAddress + i * dataSize
}2. 未知索引查询
情况一：查找数组内的元素，查找55号数据，在不排序的情况下，平均时间复杂度是O(n)
情况二：查找排序后数组内的元素，查找55号数据，在排序的情况下，通过二分查找，时间复杂度是O(logn)
操作数组的时间复杂度（插入、删除）
数组是一段连续的内存空间，因此为了保证数组的连续性会使得数组的插入和删除的效率变的很低。时间复杂度是O(n)
