算法基本概念

1. 评估算法优劣的核心指标是什么

1.1 时间复杂度(流程决定)

常数时间的操作

如果一个操作的执行时间不以具体样本量为转移，每次执行时间都是固定的时间，这样的操作为常数时间操作。

常见的算术运算：+、-、*、/、%常见的位运算：>>、<<、>>>、<<<、|、&、^赋值、比较、自增、自减数组寻址 总之，执行时间固定的操作都是常数时间的操作。反之，执行时间不固定的操作，都不是常数时间的操作。

如何确定算法流程的总操作数量与样本数量

想象该算法流程所处理的数据状况，要按最差情况来把整个流程彻底拆分成一个个基本动作，保证每个动作都是常数时间的操作如果数据量为N，看看基本动作的数量和N是什么关系。

如何确定算法流程的时间复杂度？

当完成了表达式的建立，只要把最高阶项留下即可。低阶项都去掉，高阶项的系数也去掉。 记为 O(忽略掉系数的高阶项)

注意

算法的过程，和具体的语言是无关的相分析一个算法流程的时间复杂度的前提，是对这个算法的流程非常熟悉一定要确保拆分算法流程时，拆分出来的所有行为都是常数时间操作。这意味着你写算法时，对自己用过的每一个系统api，都非常的熟悉，否则会影响对时间复杂度的估算

1.2 额外空间复杂度(流程决定)

实现一个算法流程，在实现算法流程的过程中，必须要开辟一些空间来支持算法流程。 作为输入参数的空间，不算额外空间 作为输出结果的空间，也不算额外空间 因为这些都是必要的、和实现目的有关的。 但除此之外，算法流程如果还需要开辟空间才能让流程继续下去。这部分空间就是额外的空间。如果流程里只需要几个有限的变量，额外空间复杂度就是 O（1）

1.3 常数项时间(实现细节决定)

1.4 最优解

一般情况下，认为解决一个问题的算法流程，在时间复杂度的指标上，一定要尽可能的低，先满足了时间复杂度最低这个指标后，使用最少的空间的算法流程，叫这个问题的最优解。一般说起最优解都是忽略掉常数项这个因素的，因为这个因素之决定了实现层次的优化和考虑，和怎么解决整个问题的思想无关。

2. 对数器

测试方法a实现复杂度不好但是容易实现的方法b实现一个随机样本产生器把方法a和方法b跑相同的随机随机样本，看结果是否一致如果一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a和方法b当样本数量很多时比对测试依然正确，可以确定方法a已经正确 public static int[] generateRandomArray(int maxsize, int maxvalue) { int[] arr = new int[(int)((maxsize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxvalue +1) * Math.random()) - (int)(maxvalue * Math.random()); } return arr; }