时间复杂度、空间复杂度

结论先行：

时间复杂度：当一个问题量级增加的时间，时间增长的趋势；

空间复杂度：当一个问题量级增加的时间，内存空间增长的趋势的趋势；

一、时间复杂度

1、概念

时间复杂度：计算的是当一个问题量级增加的时间，时间增长的趋势；

O（大O表示法）：渐进的时间复杂度

 

2、举例

① 以下 for 循环的时间复杂度：O(1 + 3n) = O(n)  

去掉常数，保留最高次项、去掉系数为常数的数

② 以下 for 循环的时间复杂度：O( n + n²) = O(n²)  

保留最高次项 

② 以下代码的时间复杂度：O(1) 

常数的时间复杂度为 1 

③ 以下代码的时间复杂度：O(logN) 

转化为：2^i = n ，那么 logn = i， 所以当前的时间复杂度为 O(logN) 

④ 以下代码的时间复杂度：O(nlogN) 

⑤ 以下代码的时间复杂度：O(n²) 

⑥ 以下代码的时间复杂度：O(nm) 

⑦ 大题

 

3、常见的时间复杂度量级

排序：

4、其他复杂度指标

二、空间复杂度

1、概念

计算的是内存空间增长的趋势

2、举例

① 以下代码的空间复杂度：O(1) 

x 和 y 都是一个常数量，不会影响内存空间的分配； 

② 以下代码的空间复杂度：O(n) 

这个空间复杂度取决于 newArray 这个数组的长度； 

③ 以下代码的空间复杂度：O(n²) 

常见的是矩阵

3、常见的空间复杂度

 

三、总结

【时间空间复杂度】 = 【时间和空间增长的趋势】