简单理解时间复杂度和空间复杂度,通俗易懂

 

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

时间复杂度指算法语句的执行次数。一个算法语句的执行次数最终都是可以通过函数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 int temp = i;
}

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

此博客为让自己牢记时间复杂度和空间复杂度。只为知识学习与分享!如有侵权,请联系删除!

源链接:作者:滴哩哩哩滴哩哩哩哒哒

你可能感兴趣的