时间和空间复杂度

时间复杂度为主，理解时间复杂度就能理解空间复杂度了。

学习目标

• 理解咋回事
• 清楚如何计算

因为它们和算法相关，先来说说算法。

什么是算法

1. 什么是算法

• 就是解决问题的方法步骤，不同的方法步骤就是不同的算法，

• 不同的算法消耗的两个东西是不同的：时间和资源(空间)

2. 衡量一个算法的好坏

• 时间复杂度

指的是一个算法那执行要消耗的时间，不是指的确切的时间，不是具体的几分钟，一个时间趋势。

• 空间复杂度

指的是一个算法执行要占用的内存空间

时间复杂度

• 衡量算法的好坏的其中一个标准。衡量一个算法的好坏要从多角度看。
• 表示一个算法运行需要的时间，准确来说是一个趋势，而不是具体的时间。

如何表示时间复杂度？

1. 大O表示法

• O(1)
• O(n):为什么是n，约定俗称。
• 只需要知道这个形式就行，用它来表示时间复杂度

2. 如何计算时间复杂度

• 时间复杂度没有具体的单位，像时分秒那种。

• 方法：把每行代码每执行一次需要消耗的时间作为一个时间单位记为1。看每行代码要执行多少次。

通过案例来看一下。

• 常数级的：O(1)

1
void m1(){
2
 int i =1;//一次
3
 int j = 2;//一次
4
 int sum = i + j;//一次
5
}

• O(n)

1
int sum = 0;//执行一次
2
for(int i = 0;i<n;i++){//执行n+1次,判断失败也是一次。
3
sum+=i;//执行n次
4
    }

整体就是2n+2,取高阶项就是n。用O(n)表示

O(n2)

3. 如何去计算时间复杂度

• 如果运行次数是常数，那复杂度就是O(1)
• 如果不是，只保留时间函数中的最高阶，并且省去最高阶前面的系数。

空间复杂度

• 就是算法执行要占用的内存空间。
• 一行行分析，每行代码的运行需要内存给予几个内存空间。

1
int[] arrayN = new int[n];//创建了数组，n个内存空间
2
int j = 0;//j，1个内存空间
3
j++;//常数，占用1个内存空间

一共是n+2的内存空间。