专栏首页营旗的小记录如何计算算法的复杂度

如何计算算法的复杂度


时间复杂度

什么叫做时间复杂度呢??

我们来看一个简单的程序

 int n = 10 ;
System.out.println("输出" + n);

这段伪代码运行了多少次呢! 1次 ,时间时间复杂度为O(1):常数复杂度/常数阶。

        for (int i = 0 ;i <n; i++){
            System.out.println("第几次"+i);
        }

这个for循环了多少次呢! n次,时间复杂度为O(n):线性时间复杂度。

再看下一个

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

这个循环了多少次呢!n*n次,时间复杂度为O(

):平方复杂度。

百度百科对时间复杂度的定义是:在计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。

我们再把常见的复杂度列举出来看看。

        int j = 0;
        for (int i = 0 ; i < n ; i++) {
            i = i * 2;
            j++;
            System.out.println("第几次"+j);
        }

这个循环了多少次呢!假设我们把次数设为x,那

,解得次数

,时间复杂度为O(log(n)):对数。

        for (int i = 0 ; i < Math.pow(2,n); i++) {

            System.out.println("第几次"+i);
        }

这个循环了多少次呢!

次,时间复杂度为O(

):指数复杂度。

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。

简单的讲就是包括下面几部分。

1.存储算法本身所占用的存储空间。

2.算法的输入输出数据所占用的存储空间。

3.算法在运算过程中临时占用的存储空间这三个方面。

int a[] = new int[n];

这个例子的空间复杂度是多少呢?这个数组开辟的空间是多少呢? O(n)。

总结

时间复杂度和空间复杂度本就是一个相互博弈的过程,一个多另一个就少,根据适当的问题,找到适当的解,这才是好办法。

下面给一张常见数据结构时间和空间复杂度的图作为结尾把。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 谈谈 Spring IOC

    学习过 Spring 框架的人一定都会听过 Spring 的 IoC(控制反转) 、DI (依赖注入)这两个概念,对于初学Spring的人来说,总觉得IoC 、...

    一个优秀的废人
  • Springboot总结,核心功能,优缺点

    Spring boot 可以以jar包形式独立运行,运行一个Spring Boot项目只需要通过java -jar xx.jar来运行。

    一个优秀的废人
  • SpringBoot 实战 (二十)| 整合 Redis

    两个月没更新原创了,实在惭愧。没有借口,就是因为自己懒了。最近看了「刻意学习」,这本书谈的是学习与行动的关系,书中提到了「持续行动」 这个概念,意思就是:我们要...

    一个优秀的废人
  • 你清楚这几个 Spring 常用注解吗?

    传统的Spring做法是使用.xml文件来对bean进行注入或者是配置aop、事物,这么做有两个缺点:

    一个优秀的废人
  • Arrays.asList 存在的坑

    阿里巴巴 java 开发规范说到使用工具类 Arrays.asList() 方法把数组转换成集合时,不能使用其修改集合相关的方法,它的 add/remove/c...

    一个优秀的废人
  • Java 基础 | Collection 集合概览

    老读者都知道,我是自学转行到 java 的。那时迫于生存压力,学得比较快,很多知识点仅停留在会用的层面。最近,光会用不知道原理,没什么意思。每次使用时都是机械性...

    一个优秀的废人
  • Java 基础 | Object 源码解

    Java 是一门面向对象的语言,在 Java 里面一切都可以看作是一个对象,而 Java 里面所有的对象都默认继承于 Object 类,所以狗哥今天就从源码角度...

    一个优秀的废人
  • Java | 浅克隆与深克隆

    克隆,即复制一个对象,该对象的属性与被复制的对象一致,如果不使用Object类中的clone方法实现克隆,可以自己new出一个对象,并对相应的属性进行数据,这样...

    一个优秀的废人
  • Java 并发编程 71 道面试题及答案

    任何线程都可以设置为守护线程和用户线程,通过方法Thread.setDaemon(bool on);true则把该线程设置为守护线程,反之则为用户线程。Thre...

    一个优秀的废人
  • Golang 基础篇

    我们使用go run运行后,会在控制台终端看到Hello, 世界的输出。我们来看下这段代码:

    爱敲代码的猫

扫码关注云+社区

领取腾讯云代金券