当前位置: 首页 > news >正文

数据结构——时间复杂度

前言:

当谈到数据结构和算法时,时间复杂度是一个至关重要的概念。时间复杂度是衡量算法执行时间随输入规模增长而变化的度量,它指示了算法的效率和性能。在本篇博客中,我们将深入探讨时间复杂度的相关知识,并结合C语言给出一些代码示例来帮助读者更好地理解这一概念。

目录

1. 什么是时间复杂度?

2. 时间复杂度的分类

3. 时间复杂度的计算方法

O(1):常数时间复杂度

O(n):线性时间复杂度

O(n^2):平方时间复杂度

4. 总结


1. 什么是时间复杂度?

时间复杂度是一种描述算法执行时间随着输入规模增长而变化的度量。它用大O符号(O)来表示,表示算法执行时间的上界。时间复杂度描述的是算法执行时间与输入规模的增长趋势,而不是具体的执行时间。因此,时间复杂度是一种抽象的度量,用来评估算法的效率。

(大O符号代表的是大O表示法,这是一种粗略的统计方法,例如O(n*n+n)用大O表示法实际上表示为O(n*n),因为当n足够大的时候,n相对于n*n是可以忽略的。

2. 时间复杂度的分类

在数据结构和算法中,我们通常会遇到以下几种常见的时间复杂度:

  • O(1):常数时间复杂度,表示算法的执行时间不随输入规模的增长而变化,是最理想的情况。
  • O(log n):对数时间复杂度,通常出现在二分查找等分治算法中。
  • O(n):线性时间复杂度,表示算法的执行时间与输入规模成正比。
  • O(n log n):线性对数时间复杂度,通常出现在快速排序、归并排序等分治算法中。
  • O(n^2):平方时间复杂度,通常出现在嵌套循环的算法中。
  • O(2^n):指数时间复杂度,通常出现在递归算法中。

3. 时间复杂度的计算方法

在分析算法的时间复杂度时,我们通常关注算法中执行次数最多的那部分代码(代码的核心部分)。通过分析算法中基本操作的执行次数,并根据输入规模的增长情况确定时间复杂度。

下面通过C语言的代码示例来说明不同时间复杂度的计算方法:

O(1):常数时间复杂度
#include <stdio.h>int main() {int a = 10;int b = 20;int sum = a + b;printf("Sum: %d\n", sum);return 0;
}

在上面的代码中,无论a和b的值如何变化,计算sum的操作都只执行一次,因此时间复杂度为O(1)。

注:只要执行次数为常数次,即能数的过来,都表示成O(1).

O(n):线性时间复杂度
#include <stdio.h>int main() {int n = 10;for (int i = 0; i < n; i++) {printf("%d ", i);}return 0;
}

在上面的代码中,for循环的执行次数与n的大小成正比,因此时间复杂度为O(n)。

注:一般时间复杂度为O(n)的都是代码中有单层循环的。

O(n^2):平方时间复杂度
#include <stdio.h>int main() {int n = 5;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {printf("(%d, %d) ", i, j);}}return 0;
}

在上面的代码中,嵌套的两个for循环的执行次数与n的平方成正比,因此时间复杂度为O(n^2)。

注:一般时间复杂度为O(n^2)的都是代码中有循环嵌套的。

4. 总结

时间复杂度是评估算法效率的重要指标,通过分析算法中基本操作的执行次数来确定。在实际编程中,了解不同时间复杂度对算法性能的影响,能够帮助我们设计出更加高效的算法。通过本篇博客的介绍和代码示例,相信读者对时间复杂度有了更深入的理解。

希望本篇博客能够帮助读者更好地理解时间复杂度的相关知识,并在日常编程中更加灵活地运用这一概念。如果有任何疑问或者需要进一步的解释,请随时留言,我将尽力为您解答。感谢阅读!此外,鉴于本人水平有限,文中若有不足还请见谅并指出错误,给本人一个挽救的机会。

创作不易,还请一键三连。

相关文章:

数据结构——时间复杂度

前言&#xff1a; 当谈到数据结构和算法时&#xff0c;时间复杂度是一个至关重要的概念。时间复杂度是衡量算法执行时间随输入规模增长而变化的度量&#xff0c;它指示了算法的效率和性能。在本篇博客中&#xff0c;我们将深入探讨时间复杂度的相关知识&#xff0c;并结合C语言…...

《剑指Offer》笔记题解思路技巧优化 Java版本——新版leetcode_Part_5

《剑指Offer》笔记&题解&思路&技巧&优化_Part_5 &#x1f60d;&#x1f60d;&#x1f60d; 相知&#x1f64c;&#x1f64c;&#x1f64c; 相识&#x1f622;&#x1f622;&#x1f622; 开始刷题&#x1f7e2;1. LCR 158. 库存管理 II——数组中出现次数超过一…...

ubuntu上安装docker

在 Ubuntu 上安装 Docker&#xff0c;可以按照以下步骤进行操作&#xff1a; 更新软件包列表&#xff1a;运行以下命令来更新系统的软件包列表&#xff1a; sudo apt update安装必要的依赖项&#xff1a;运行以下命令来安装 Docker 所需的依赖项&#xff1a; sudo apt install …...

【Docker】Linux主机部署Docker

Docker部署 1.二进制文件部署 到如下地址&#xff0c;下载二进制包。 Docker官网&#xff1a;https://docs.docker.com/engine/install/binaries/ 网易镜像源&#xff1a;https://mirrors.163.com/docker-ce/linux/static/stable/x86_64/ 下载好的二进制包上传到主机&#xf…...

vue前端docx库生成word表格 并合并单元格的例子

Vue.js 是一个流行的前端JavaScript框架&#xff0c;用于构建用户界面和单页应用程序。在Vue中生成Word表格并合并单元格&#xff0c;通常需要使用额外的库&#xff0c;如docx&#xff0c;它是一个用于创建和修改Word文档&#xff08;.docx&#xff09;的JavaScript库。 …...

FastGPT配置文件及OneAPI程序:

FastGPT配置文件及OneAPI程序&#xff1a;百度网盘 请输入提取码 提取码&#xff1a;wuhe 创建fastgpt目录&#xff1a;mkdir fastgpt 切换到fastgpt目录&#xff1a;cd fastgpt 下载docker-compose文件&#xff1a;curl -O https://raw.githubusercontent.com/labring/Fast…...

Positive Semidefinite Matrices 什么是半正定矩阵?(undone)

参考视频&#xff1a;https://www.bilibili.com/video/BV1Vg41197ew/?vd_source7a1a0bc74158c6993c7355c5490fc600 参考资料(半正定矩阵的定义)&#xff1a;https://baike.baidu.com/item/%E5%8D%8A%E6%AD%A3%E5%AE%9A%E7%9F%A9%E9%98%B5/2152711?frge_ala 看看半正定矩阵的…...

shapely 笔记:STR TREE

数据结构笔记&#xff1a;R树-CSDN博客 1 基本介绍 使用Sort-Tile-Recursive (STR) 算法创建的仅查询的R-tree空间索引该树索引每个几何图形的边界框。树在初始化时直接构建&#xff0c;且一旦创建后不能添加或移除节点所有操作返回输入几何图形的索引边界框限于二维并且是轴…...

neo4j常用代码

1】查版本&#xff1a; CALL dbms.components() YIELD name, versions RETURN name, versions; 2】清数据&#xff1a; MATCH ()-[r]->() DELETE r; MATCH (n) DETACH DELETE n; 3】NEO4J 操作入门_neo4j查看历史执行命令-CSDN博客 :play --首页 :help match/keys/com…...

OpenAI划时代大模型——文本生成视频模型Sora作品欣赏(五)

Sora介绍 Sora是一个能以文本描述生成视频的人工智能模型,由美国人工智能研究机构OpenAI开发。 Sora这一名称源于日文“空”(そら sora),即天空之意,以示其无限的创造潜力。其背后的技术是在OpenAI的文本到图像生成模型DALL-E基础上开发而成的。模型的训练数据既包含公开…...

Less预处理器教程

学习源码可以看我的个人前端学习笔记 (github.com):qdxzw/frontlearningNotes 觉得有帮助的同学&#xff0c;可以点心心支持一下哈 一、Less介绍 less官方文档 lesscss.org/ less中文文档 less.bootcss.com/ less是一种css预处理器&#xff0c;它扩展了css语言&#xff0c…...

PCL 计算点云AABB包围盒的体积

目录 一、AABB包围盒二、代码实现三、结果展示四、相关链接本文由CSDN点云侠原创,原文链接。爬虫自重,把自己当个人。 一、AABB包围盒 AABB包围盒又称了 轴对齐包围盒,是点云包围盒里最简单的一种,其计算方法也极其简单。获取包围盒之后,根据包围盒的长宽高进行体积计算即…...

论软件测试工程师 重要性!

在生活中&#xff0c;我们常常会遇到以下几种窘迫时刻&#xff1a; 准备骑共享单车出行&#xff0c;却发现扫码开锁半天&#xff0c;车子都没有反应&#xff1b;手机导航打车&#xff0c;却发现地图定位偏差很大&#xff0c;司机总是跑错地方&#xff1b;买个水&#xff0c;却…...

防御第六次作业-防火墙综合实验(av、url过滤、dns过滤)

目录 拓扑图&#xff1a; 要求&#xff1a; 8 9 10 11 拓扑图 要求 前7个要求在上一篇博客&#xff1b; 8.分公司内部的客户端可以通过域名访问到内部的服务器 9.假设内网用户需要通过外网的web服务器和pop3邮件服务器下载文件和邮件&#xff0c;内网的FTP服务器也需要…...

打码半年,开源一款自定义大屏设计软件!

hi&#xff0c;大家好&#xff0c;我是Tduck马马。 最近我们开源了一款大屏软件-TReport&#xff0c;与大家分享。 TReport是一款基于Vue3技术栈的数据可视化系统&#xff0c;支持静态、动态api等数据源&#xff1b;可用于数据可视化分析、报表分析、海报设计使用。 提供自定…...

云计算基础-大页内存

大页内存功能概述 什么是大页内存 简单来说&#xff0c;就是通过增大操作系统页的大小来减小页表&#xff0c;从而避免快表缺失 主要应用场景 主要运用于内存密集型业务的虚拟机&#xff0c;比如对于运行数据库系统的虚拟机&#xff0c;采用HugePages(大页)后&#xff0c;可…...

数据结构-邻接链表

介绍 邻接矩阵是运用较多的一种储存图的方法&#xff0c;但如果一张网图边数较少&#xff0c;就会出现二维矩阵中大部分数据为0的情况&#xff0c;浪费储存空间 为了避免空间浪费&#xff0c;也可以采用数组与链表结合的方式来存储图 假设有这样一张图 我们可以先用一个数组…...

十三、集合进阶——单列集合 及 数据结构

单列集合 及 数据结构 13.1 集合体系结构13.1.2 单列集合1. Collection2.Collection 的遍历方式迭代器遍历增强for遍历Lambda表达式遍历 3.List集合List集合的特有方法List集合的遍历方式五种遍历方式对比 4.数据结构1).栈2).队列3&#xff09;数组4&#xff09;链表小结5&…...

Android | ArcGIS入门

一、概述 ArcGIS是由Esri开发的地理信息系统&#xff08;GIS&#xff09;软件。它用于制图、空间分析和数据可视化。ArcGIS允许用户以各种格式创建、管理、分析和共享地理信息。它通常用于城市规划、环境管理和应急响应等领域。该软件包括一系列工具&#xff0c;用于创建地图、…...

dockerfile文件书写

1.dockerfile构建nginx镜像 1.1书写dockerfile文件 mkdir nginx #创建nginx目录 cd nginx vim dockerfile # 修改文件FROM centos # 基础镜像&#xff0c;默认最新的centos8操作系统 MAINTAINER xianchao # 指定镜像的作者信息 RUN rm -rf /etc/yum.repos.d/* # centos8默认…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

P10909 [蓝桥杯 2024 国 B] 立定跳远

# P10909 [蓝桥杯 2024 国 B] 立定跳远 ## 题目描述 在运动会上&#xff0c;小明从数轴的原点开始向正方向立定跳远。项目设置了 $n$ 个检查点 $a_1, a_2, \cdots , a_n$ 且 $a_i \ge a_{i−1} > 0$。小明必须先后跳跃到每个检查点上且只能跳跃到检查点上。同时&#xff0…...

Android Framework预装traceroute执行文件到system/bin下

文章目录 Android SDK中寻找traceroute代码内置traceroute到SDK中traceroute参数说明-I 参数&#xff08;使用 ICMP Echo 请求&#xff09;-T 参数&#xff08;使用 TCP SYN 包&#xff09; 相关文章 Android SDK中寻找traceroute代码 设备使用的是Android 11&#xff0c;在/s…...

开疆智能Ethernet/IP转Modbus网关连接斯巴拓压力传感器配置案例

本案例是将ModbusRTU协议的压力传感器数据上传到欧姆龙PLC&#xff0c;由于PLC采用的是Ethernet/IP通讯协议&#xff0c;两者无法直接进行数据采集。故使用开疆智能研发的Ethernet转Modbus网关进行数据转换。 配置过程 首先我们开始配置Ethernet/IP主站&#xff08;如罗克韦尔…...