什么是时间复杂度和空间复杂度，原来我一直没搞懂。

痛定思痛。 2021-10-09 07:28 233阅读 0赞

之前在面试的时候，面试官问了我一句，你知道什么是时间复杂度和空间复杂度吗？

这直接给我问懵了，虽然这东西天天在嘴巴上跑，但是要我用一个很通俗易懂的语言来讲讲，我真的不知道。

那么我们就来说说吧：

**时间复杂度和空间复杂度一般都是在算法上出现的一个衡量值，是对一个算法是否高效的一个标准。其实之前一直有个误解，就是时间复杂度就是算法的运行周期的时间。其实这是错误的。并且对于算法来说，一个for就是一个算法，一个1-2-x-y=1，也是一个算法，对于我们了解的八大排序算法，都是算法，对于根本来说，八大排序算法都是循环本质实现的。**

### 时间复杂度 ###

对于时间复杂度是指的算法语句的执行次数。一个算法语句的执行次数最终都是可以通过函数f(n)来形容的。

就比如：

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

这里的i++就是算法语句，那么其f（n） = 100 - i -1；就可以知道他的时间复杂度了。

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

这输出语句就是算法语句，那么f(n)就是：f(n) = n \* n = n的平方。

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

这里的i++;为算法语句，那么f(n)就是 f(n) = n - i - 1;

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

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

（2）跟进第一条拿到系数最大项后，将系数化为1，剩下的就是时间复杂度。

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

根据以上3个规则，那么就可以对前三个例子分别得出对应的时间复杂度为：

（1）O(1)   （2）O(n的平方)    （3）O(n)

### 空间复杂度 ###

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

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

那么两者的区别很明显的了，前者的空间复杂度就是O(n)，因为temp变量再不断的被创建n次。那么后者就是在循环之前就声明好了一个变量，开辟了一个内存空间，那么在循环中，只是不断的将此变量的地址值指向i的内存地址。只是一个引用的操作，所以，如果算法语句中，有创建对象，那么这个算法的时间复杂度和空间复杂度一般来说就是一致的。

发表评论取消回复

表情：

评论列表（有 0 条评论，233人围观）

还没有评论，来说两句吧...

相关阅读

相关空间复杂度和时间复杂度

时间复杂度和空间复杂度是衡量算法性能的关键指标。时间复杂度评估算法执行时间，空间复杂度评估内存消耗。本文将深入探讨它们的概念、计算方式以及如何优化算法以提高效率。复杂度分...

朴灿烈づ我的快乐病毒、/ 2024年04月23日 15:58/ 0 赞/ 100 阅读

相关时间复杂度和空间复杂度

如何衡量一个算法的好坏呢？方法：分析算法效率。算法效率分析分为两种：第一种是时间效率，时间效率被称为时间复杂度第二种是空间效率。空间效率被称作空间复杂度。时间复杂度主要衡...

Myth丶恋晨/ 2024年04月20日 14:25/ 0 赞/ 109 阅读

相关搞懂时间复杂度、时间复杂度

文章目录写在前面 1、数学中的log什么意思？ 2、时间复杂度 2.1、用T(n)表示程序执行次数

末蓝、/ 2023年10月08日 12:48/ 0 赞/ 81 阅读

相关时间复杂度和空间复杂度

目录引入：算法的好与坏渐进时间复杂度空间复杂度什么是空间复杂度？空间复杂度的计算 -------------------- 引入：算法的好与坏衡

刺骨的言语ヽ痛彻心扉/ 2023年09月25日 22:46/ 0 赞/ 87 阅读

相关时间复杂度和空间复杂度

先说结论：常规的代码的算法时间复杂度是有规律的:看几重循环: 一重循环则为O(n)线性阶，二重循环为O(n^2) K方阶; 二分法则为O(logn)对数阶，二分例

Dear 丶/ 2023年01月18日 04:14/ 0 赞/ 197 阅读

相关时间复杂度和空间复杂度

一、时间复杂度 1、定义若存在函数，使得当趋向无穷大时，的极限值为不等于 0 的常数，则称是的同数量级函数，记作，称为算法的渐进时间复杂度，简称时间复

浅浅的花香味﹌/ 2022年11月12日 14:59/ 0 赞/ 297 阅读

相关时间复杂度和空间复杂度

算法的时间复杂度和空间复杂度合称为算法的复杂度。 1.时间复杂度（1）时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可

秒速五厘米/ 2022年08月21日 02:27/ 0 赞/ 301 阅读

相关时间复杂度和空间复杂度

一、为什么要研究时间和空间复杂度假设计算机是无限快的并且计算机存储器是免费的的，你还有什么理由来研究算法吗？即使只是因为你还想证明你的解法会终止并以正确的答案终

灰太狼/ 2022年04月13日 08:17/ 0 赞/ 444 阅读

相关什么是时间复杂度和空间复杂度，原来我一直没搞懂。

之前在面试的时候，面试官问了我一句，你知道什么是时间复杂度和空间复杂度吗？这直接给我问懵了，虽然这东西天天在嘴巴上跑，但是要我用一个很通俗易懂的语言来讲讲，我真的不知道。

痛定思痛。/ 2021年10月09日 07:28/ 0 赞/ 234 阅读

相关时间复杂度和空间复杂度

[https://blog.csdn.net/zxm490484080/article/details/72210501][https_blog.csdn.net_zxm490

待我称王封你为后i/ 2021年09月15日 09:46/ 0 赞/ 514 阅读