这两天开始了数据结构和算法的学习，简单总结一下自己的心得。
为什么需要复杂度分析
- 和性能测试不一样，复杂度分析有着不依赖环境、成本低、效率高、易操作、方便操作、指导性强的优点。
- 掌握复杂度分析，将能编写出性能更优，效率更高的代码，有利于降低系统开发和维护的成本，提高用户的体验。
复杂度分析法则
单段代码取高频：例如循环
多段代码取最大：录入一段代码中有单循环和多重循环，取多重循环的复杂度
嵌套代码算乘积：例如多重嵌套 for 循环
多个规模算其和：例如方法中两段代码单独运算，最后结果根据这两段代码得出，那么取这两者复杂度的和
常见的时间复杂度（从低到高）
- O(1)
- O(logn)
- O(n)
- O(nlogn)
- O(n^2)
- O(2^n)
- O(n!)
注： 最后两个时间复杂度不常用，因为其效率过低。
四类时间复杂度
最好情况时间复杂度 在最理想的情况下，执行这段代码的时间复杂度。 比如：查找的元素就是数组的第一个元素，这时候这段代码只需要执行一次，时间复杂度最低。
最坏情况时间复杂度 在最糟糕的情况下，执行这段代码的时间复杂度。 比如：查找的元素不在数组中，或者是数组的最后一个（从第一个开始遍历），这时候这个数组需要全部遍历一遍，时间复杂度最高。
平均情况时间复杂度 所有会出现的情况除以次数 比如：查找的元素在数组的第一个，查找的元素在数组的最后一个，查找的元素在数组的中间，查找的元素不在数组里面，将以上所有情况统计起来，除以出现的次数，就是平均情况时间复杂度。
均摊时间复杂度 对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时许关系。通常，能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。
// 生成一个数组，长度为nint[] array = new int[n];int count = 0;void insert(int temp) { // 判断数组是否存满了 if(count == array.length) { int sum = 0; // 计算数组里面元素的和 for (int i = 0; i < array.length; ++i){ sum = sum + array[i]; } // 将和赋给数组的第一个 array[0] = sum; // 下次插入的时候只能插入到第二个元素 count = 1; } // 如果数组没存满，则插入元素 array[count] = temp; ++count;}复制代码