我的编程空间,编程开发者的网络收藏夹
学习永远不晚

Java数据结构与算法系列精讲之时间复杂度与空间复杂度

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

Java数据结构与算法系列精讲之时间复杂度与空间复杂度

概述

从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章.

算法的衡量标准

当我们需要衡量一个算法的的优越性, 通常会使用时间复杂度 (Time Complexity) 和空间复杂度 (Space Complexity) 来衡量.

时间复杂度

时间复杂度 (Time Complexity) 通常用 O(n) 表示, 用来描述一个算法运行的时间.

时间复杂度 & 空间复杂度计算规则:

  • 用常数 1 代替运行中的所有加减, lim n->∞cn = ∞
  • 只保留最高项, lim n->∞ n^2 + an + b = lim n->∞ n^2

最优时间复杂度

最优时间复杂度指的是在最优的情况下算法需要的运行时间.

平均时间复杂度

平均时间复杂度是指所有可能的输入实例以等概率出现的情况下, 算法需要的运行时间.

最坏时间复杂度

最坏时间复杂度指的是在最坏的情况下算法需要的运行时间. 一般使用最坏时间复杂度作为时间复杂度.

O(1)

没有循环结构, 只有普通加减的代码时间复杂度为 O(1).

例如:


int i = 1;
int j = 2;
int k = i + j;  // 1+2=3

O(n)

循环 n 次的代码的时间复杂度为 O(n).

例子:


int sum = 0;
for (int i = 1; i < n; i++) {
    sum += i;
}

O(n^2)

两层循环嵌套的时间复杂度为 O(n^2). 如下例子, 需要进行 2n^2 次计算

例子:


int sum = 0;

for (int i = 1; i < n; i++) {
    for (int j = 0; j < n; j++) {
        sum += i;
        sum += j;
    }
}

O(logN)

2^n = N, 所以会循环 logN 次.

例子:


int sum = 0;

for (int i = 0; i < n; i++) {
    sum += i;
    i *= 2;
}

空间复杂度

空间复杂度 (Space Complexity) 定义为该算法所耗费的存储空间.

O(1)

如果算法执行所需要的临时空间不会随着变量的大小而变化, 那么空间复杂度就为 O(1).

例子:


int i = 1;
int j = 2;
int k = i + j;  // 1+2=3

O(n)

长度为 n 的数组占用空间为 O(n).

例子:


int[] array = new int[n]

到此这篇关于Java 数据结构与算法系列精讲之时间复杂度与空间复杂度的文章就介绍到这了,更多相关Java 时间复杂度内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

Java数据结构与算法系列精讲之时间复杂度与空间复杂度

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

「算法与数据结构」时间与空间复杂度

可能有些人会吐槽,学算法有什么用,顶多就是去面试大厂的时候能用上,大厂面试算法也只是强中筛强的一个敲门砖而已,我又不去面大厂,不用学它,真的是这样吗?

如何解析Java 数据结构中时间复杂度与空间复杂度

这篇文章给大家介绍如何解析Java 数据结构中时间复杂度与空间复杂度,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。算法效率在使用当中,算法效率分为两种,一是时间效率(时间复杂度),二是空间效率(空间复杂度)。时间复杂度
2023-06-25

C语言数据结构的时间复杂度和空间复杂度

算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度,感兴趣的同学可以参考阅读
2023-05-15

算法必备知识:时间复杂度与空间复杂度的计算

我们今天要讲的内容:时间、空间复杂度分析。只要讲到数据结构与算法,就一定离不开时间、空间复杂度分析。复杂度分析是整个算法学习的精髓,只要掌握了它,数据结构和算法的内容基本上就掌握了一半。这就就像内功心法,上乘武功还需搭配心法。

C语言数据结构与算法时间空间复杂度实例分析

这篇文章主要介绍“C语言数据结构与算法时间空间复杂度实例分析”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“C语言数据结构与算法时间空间复杂度实例分析”文章能帮助大家解决问题。时间复杂度来看第一个:l
2023-06-29

学习算法必备:时间复杂度与空间复杂度,你了解多少

算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。算法是大厂、外企面试的必备项,也是每个高级程序员的必备技能。针对同一问题,可以有很多种算法来解决,但不同的算法在效率和占用存储空间上的区别可能会很大。

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录