永远不背时间复杂度和空间复杂度_空间复杂度要会背吗

时间复杂度和空间复杂度一般是针对算法而言，是衡量一个算法是否高效的重要标准。先纠正一个误区，时间复杂度并不是算法执行的时间，再纠正一个误区，算法不单单指冒泡排序之类的，一个循环甚至是一个判断都可以称之为算法。其实理解起来并不冲突，八大排序甚至更多的算法本质上也是通过各种循环判断来实现的。

时间复杂度指算法语句的执行次数。一个算法语句的执行次数最终都是可以通过函数f(n)来表示的，例如：

int x = 1;
while(x < 10){
    x ++;
}

这里的x++就是算法语句，其f(n)=10-x

for(int i = 0;i < n;i++){
    for(int j = 0;j < n;j++){
        System.out.println("-");
    }
}

这里的System.out.println就是算法语句，其f(n)如下图

int i = 0;
while(i < n){
    i ++;
}

 i++即算法语句，被执行次数为f(n)=n-i

理解了如何将算法语句执行次数通过函数表示出来，时间复杂度一眼就看出来了，有以下几条规则

1.选取f(n)系数最大的项，如果系数都是负数，就选常数，那么时间复杂度是常数阶O(1)

2.根据第一条拿到系数最大项后，将系数化为1，剩下的就是时间复杂度

3.一个算法可能有多条算法语句，即可能有多个循环判断，时间复杂度的计算考虑最坏情况，即取最大的。

根据以上3个规则，前面三个例子的时间复杂度分别为

空间复杂度就是一个算法在运行过程中临时占用的存储空间大小，换句话说就是被创建次数最多的变量，它被创建了多少次，那么这个算法的空间复杂度就是多少。举个例子：

for(int i=0;i<n;++){
int temp = i;
}
和
int temp=0;
for(int i=0;i<n;i++){
temp = i;
}

前者空间复杂度就是O(n)，而后者空间复杂度就是O(1)常数阶。很好理解，前者每循环一次都会重新创建一个temp对象，而后者只在循环外面创建了一个temp对象，每次循环只是给他不同的引用而已。所以有个规律，如果算法语句中就有创建对象，那么这个算法的时间复杂度和空间复杂度一般一致，很好理解，算法语句被执行了多少次就创建了多少对象。