代码时间、空间复杂度分析

大家好，欢迎来到IT知识分享网。

1、通常跑一遍程序通过统计代码执行时长和占用的内存大小来判断代码执行效率会受测试环境机器配置和测试数据规模影响；所以需要一个不用真正执行代码就可以粗略地估计算程序的执行效率的方法，这种方法就是复杂度分析
2、时间复杂度
2.1、时间复杂度可以简单理解为代码重复执行的次数，如一个for循环的时间复杂度就是for循环的次数；通常用大O来表示时间复杂度；一个for循环n次，这个for循环的时间复杂度就是O(n)；但是一个for循环固定次数，那么它的时间复杂度又是O(1)；所以时间复杂度更是代表一种变化趋势（时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系）
2.2、分析时间复杂度只关注循环执行次数最多的那一段代码（多个for循环连续执行，整个代码时间复杂度是for循环次数最多的for循环次数）或是嵌套内外代码复杂度的乘积（多层for循环）
2.3、对于对数的时间复杂度，一般我们忽略对数的低，即使代码算出来是以3为低n的对数，时间复杂度也是logn；常见时间复杂度有常量阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶O(nlogn)、平方阶O(n^2)….K次方阶O(n^k)、指数阶O(2^n)和阶乘阶O(n!)
3、空间复杂度
3.1、类比时间复杂度，空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系；空间复杂度通常也是用大O来表示；比如int[] a = new int[n]，代码空间复杂度为O(n)；但是int[] a = new int[3]，代码空间复杂度为O(1)
3.2、常见的空间复杂度就是 O(1)、O(n)、O(n^2)，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到