复杂度分析
不依赖具体的执行环境
不用具体的测试数据
在算法实现前，我们在脑海就可以评估算法的性能
评估一个算法的性能：本质上就是评估这个算法代码执行的时间
N 为数据规模
大O复杂度表示法
表示算法的性能，通常看最差的情况，算法运行的上界
O(n) T=5n+2
常数不重要，复杂度描述的是随着数据规模n的增大，算法性能的变化趋势
T(n)就是表示算法程序段执行的时间
n表示的是算法输入数据规模的大小
f(n)表示程序段所有语句执行的次数总和
大O表示程序段执行时间T(n)与f(n)函数的关系
随着数据规模n的不断增大，以上T(n)中的系数
低阶、常量对执行时间的增长趋势影响非常的小
常量阶时间复杂度
只要你的程序段执行的时间和输入数据规模没有关系的话，即使需要执行成干上万行的代码，那么你的程序时间复杂度仍然是O(1)
对数阶时间复杂度
理论上我们知道对于所有底数 b>1，函数 在大O记号下的渐近增长率是相同的，但在实际图像上，我们可以观察到它们之间的差异仅在于比例系数
时间复杂度分析方法
加法法则
乘法法则
常用时间复杂度
阶乘（Factorial）是一个数学运算，通常表示为 n! ，指的是所有小于及等于 n 的正整数的乘积。例如，5 的阶乘（写作 5!）是 5 × 4 × 3 × 2 × 1 = 120。
最好最坏时间复杂度
平均时间复杂度（不关心）
public boolean contains(int[]arr,int target){
for (int i=0;i<arr.length -1j i++){
if (arr[i]=target){
return true;
}
return false;
}
}target在数组中和不在数组中的概率都是1/2
target在数组中每个位置的概率是1/2*1/n
不在数组中 需要比较
空间复杂度分析
常量空间复杂度：0(1)
public boolean contains(int[]arr,int target){
for (int i=0;i<arr.length -1j i++){
if (arr[i]=target){
return true;
}
return false;
}
}线性阶空间复杂度：O(n)
public int[]arrayCopy(int[]arr){
int[] newArray = new int[arr.length];
for (int i=0;i<arr.length -1;i++){
newArray[i]=arr[i];
}
return newArray;
}
}