数据结构:时间复杂度
文章目录
- 为什么需要时间复杂度分析?
- 一、大O表示法:复杂度的语言
- 1.1 什么是大O?
- 1.2 常见复杂度速查表
- 二、实战分析:解剖C语言代码
- 2.1 循环结构的三重境界
- 单层循环:线性时间
- 双重循环:平方时间
- 动态边界循环:隐藏的平方
- 2.2 递归的时空折叠
- 线性递归:阶乘计算
- 指数递归:斐波那契噩梦
- 三、高级技巧:复杂度组合计算
- 3.1 顺序结构:取最大值
- 3.2 嵌套结构:乘积法则
- 四、常见误区与破解之道
- 误区1:误判循环边界
- 误区2:低估数学级数
- 破解工具:关键公式
- 五、复杂度优化实战
- 案例:寻找数组中的重复元素
- 暴力解法(O(n²))
- 优化方案(O(n))
- 六、自测练习
- 结语:复杂度即格局
为什么需要时间复杂度分析?
想象你正在处理一个包含百万条数据的数组:
- O(n²) 的算法可能需要几天才能完成
- O(n log n) 的算法可能只需几秒
- O(n) 的算法眨眼间就能得出结果
时间复杂度就像算法的「体检报告」,它揭示了代码执行效率如何随数据规模增长而变化。本文将用C语言示例,手把手教你掌握这项核心技能!
一、大O表示法:复杂度的语言
1.1 什么是大O?
- 本质:描述算法执行时间的增长趋势
- 特点:忽略常数项和低阶项,专注主要矛盾
- 公式:
T(n) = O(f(n))
表示存在常数C,使得当n足够大时,T(n) ≤ C·f(n)
1.2 常见复杂度速查表
复杂度 | 典型场景 | 可视化增长趋势 |
---|---|---|
O(1) | 数组下标访问 | 水平直线 |
O(log n) | 二分查找 | 缓慢爬坡 |
O(n) | 遍历数组 | 线性上升 |
O(n log n) | 快速排序 | 优雅曲线 |
O(n²) | 冒泡排序 | 陡峭抛物线 |
O(2ⁿ) | 暴力穷举 | 垂直火箭 |
二、实战分析:解剖C语言代码
2.1 循环结构的三重境界
单层循环:线性时间
// 示例:计算数组和
int sum = 0;
for (int i = 0; i < n; i++) { // 执行n次sum += array[i]; // O(1)操作
}
// 总复杂度:O(n)
双重循环:平方时间
// 示例:打印所有数对
for (int i = 0; i < n; i++) { // 外层n次for (int j = 0; j < n; j++) { // 内层n次printf("(%d,%d)", i, j); // O(1)操作}
}
// 总复杂度:O(n) × O(n) = O(n²)
动态边界循环:隐藏的平方
for (int i = 0; i < n; i++) { // 外层n次for (int j = 0; j < i; j++) { // 内层i次(0到n-1)count++; // 总次数 = 0+1+2+...+(n-1) = n(n-1)/2}
}
// 总复杂度:O(n²)
2.2 递归的时空折叠
线性递归:阶乘计算
int factorial(int n) {if (n <= 1) return 1; // 基准情形return n * factorial(n-1); // 递归调用n次
}
// 调用栈深度:O(n)
// 时间复杂度:O(n)
指数递归:斐波那契噩梦
int fib(int n) {if (n <= 1) return n;return fib(n-1) + fib(n-2); // 每次产生2个分支
}
// 时间复杂度:O(2ⁿ) (实际约为O(1.618ⁿ))
递归树呈指数级展开
三、高级技巧:复杂度组合计算
3.1 顺序结构:取最大值
void process_data(int n) {// 阶段1: O(n)for (int i=0; i<n; i++) { /* ... */ }// 阶段2: O(n²)for (int i=0; i<n; i++) {for (int j=0; j<n; j++) { /* ... */ }}
}
// 总复杂度 = O(n) + O(n²) = O(n²)
3.2 嵌套结构:乘积法则
void matrix_ops(int n) {for (int i=0; i<n; i++) { // O(n)for (int j=1; j<n; j*=2) { // O(log n)printf("%d", i*j); // O(1)}}
}
// 总复杂度 = O(n) × O(log n) = O(n log n)
四、常见误区与破解之道
误区1:误判循环边界
int k = 0;
while (k < 100) { // 固定循环100次process(data[k++]);
}
// 真实复杂度:O(1) 而非 O(n)
误区2:低估数学级数
for (int i=1; i<=n; i*=2) { // 执行次数:log₂nfor (int j=0; j<i; j++) { // 内层总次数:1+2+4+...+2^log₂n = 2n-1count++;}
}
// 总复杂度:O(n) 而非 O(n log n)
破解工具:关键公式
- 等差数列和:
1+2+3+...+n = n(n+1)/2 → O(n²)
- 等比数列和:
1+2+4+...+2^k = 2^(k+1)-1 → O(2^k)
- 对数计算:
循环变量i每次乘以2 → 循环次数log₂n
五、复杂度优化实战
案例:寻找数组中的重复元素
暴力解法(O(n²))
for (int i=0; i<n; i++) {for (int j=i+1; j<n; j++) {if (arr[i] == arr[j]) return true;}
}
优化方案(O(n))
// 使用哈希表记录出现次数
int hash_table[MAX_SIZE] = {0};
for (int i=0; i<n; i++) {if (hash_table[arr[i]]++) return true;
}
六、自测练习
- 分析以下代码复杂度:
for (int i=0; i<n; i+=5) {for (int j=0; j<1000; j++) {sum += i*j;}
}
答案:O(n)(外层循环n/5次,内层固定1000次 → 忽略常数后为线性)
- 递归函数复杂度分析:
void fun(int n) {if (n <= 0) return;printf("%d", n);fun(n/2);fun(n/2);
}
答案:O(n)(递归树总节点数=1+2+4+…+n → 约2n个节点)
结语:复杂度即格局
不同复杂度的时间增长对比
掌握时间复杂度分析,就像获得了一副「算法透视眼镜」:
- 在面试中快速评估解法优劣
- 在大数据场景下避免性能灾难
- 培养对代码的直觉敏感性
下次看到嵌套循环时,试着在心中画出它的增长曲线。当复杂度从O(n²)优化到O(n log n)时,那种思维的跃迁感,正是编程最迷人的魔法时刻!
相关文章:

数据结构:时间复杂度
文章目录 为什么需要时间复杂度分析?一、大O表示法:复杂度的语言1.1 什么是大O?1.2 常见复杂度速查表 二、实战分析:解剖C语言代码2.1 循环结构的三重境界单层循环:线性时间双重循环:平方时间动态边界循环&…...

SPI(Serial Peripheral Interface)串行外围设备接口
SPI概述: SPI协议最初由Motorola公司(现为NXP Semiconductors的一部分)在20世纪80年代中期开发。最初是为了在其68000系列微控制器中实现高速、高效的串行通信。该协议旨在简化微控制器与外围设备之间的数据传输。 1980年代:SPI协…...

Java 8 Stream API
通过 Stream.of 方法直接传入多个元素构成一个流 String[] arr {“a”, “b”, “c”}; Stream.of(arr).forEach(System.out::println); Stream.of(“a”, “b”, “c”).forEach(System.out::println); Stream.of(1, 2, “a”).map(item -> item.getClass().getName()…...

亚博microros小车-原生ubuntu支持系列:21 颜色追踪
背景知识 这个测试例子用到了很多opencv的函数,举个例子。 #cv2.findContours函数来找到二值图像中的轮廓。#参数:#参数1:输 入的二值图像。通常是经过阈值处理后的图像,例如在颜色过滤之后生成的掩码。#参数2(cv2.RETR_EXTERNA…...

GESP6级语法知识(六):(动态规划算法(六)多重背包)
多重背包(二维数组) #include <iostream> using namespace std; #define N 1005 int Asd[N][N]; //Asd[i][j]表示前 i 个物品,背包容量是 j 的情况下的最大价值。 int Value[N], Vol[N], S[N];int main() {int n, Volume;cin &g…...

MySQL 事务实现原理( 详解 )
MySQL 主要是通过: 锁、Redo Log、Undo Log、MVCC来实现事务 事务的隔离性利用锁机制实现 原子性、一致性和持久性由事务的 redo 日志和undo 日志来保证。 Redo Log(重做日志):记录事务对数据库的所有修改,在崩溃时恢复未提交的更改,保证事务…...
AI协助探索AI新构型自动化创新的技术实现
一、AI自进化架构的核心范式 1. 元代码生成与模块化重构 - 代码级自编程:基于神经架构搜索的强化学习框架,AI可通过生成元代码模板(框架的抽象层定义)自动组合功能模块。例如,使用注意力机制作为原子单元ÿ…...

九. Redis 持久化-RDB(详细讲解说明,一个配置一个说明分析,步步讲解到位)
九. Redis 持久化-RDB(详细讲解说明,一个配置一个说明分析,步步讲解到位) 文章目录 九. Redis 持久化-RDB(详细讲解说明,一个配置一个说明分析,步步讲解到位)1. RDB 概述2. RDB 持久化执行流程3. RDB 的详细配置4. RDB 备份&恢…...
mac连接linux服务器
1、mac连接linux服务器 # ssh -p 22 root192.168.1.152、mac指定密码连接linux服务器 (1) 先安装sshpass,下载后解压执行 ./configure && make && makeinstall https://sourceforge.net/projects/sshpass/ (2) 连接linux # sshpass -p \/\\\[\!\\wen12\$ s…...

oracle: 表分区>>范围分区,列表分区,散列分区/哈希分区,间隔分区,参考分区,组合分区,子分区/复合分区/组合分区
分区表 是将一个逻辑上的大表按照特定的规则划分为多个物理上的子表,这些子表称为分区。 分区可以基于不同的维度,如时间、数值范围、字符串值等,将数据分散存储在不同的分区 中,以提高数据管理的效率和查询性能,同时…...

使用Pygame制作“走迷宫”游戏
1. 前言 迷宫游戏是最经典的 2D 游戏类型之一:在一个由墙壁和通道构成的地图里,玩家需要绕过障碍、寻找通路,最终抵达出口。它不但简单易实现,又兼具可玩性,还能在此基础上添加怪物、道具、机关等元素。本篇文章将展示…...

AJAX案例——图片上传个人信息操作
黑马程序员视频地址: AJAX-Day02-11.图片上传https://www.bilibili.com/video/BV1MN411y7pw?vd_source0a2d366696f87e241adc64419bf12cab&spm_id_from333.788.videopod.episodes&p26 图片上传 <!-- 文件选择元素 --><input type"file"…...

Day35-【13003】短文,什么是双端队列?栈和队列的互相模拟,以及解决队列模拟栈时出栈时间开销大的方法
文章目录 第三节进一步讨论栈和队列双端队列栈和队列的相互模拟使用栈来模拟队列类型定义入队出队判空,判满 使用队列来模拟栈类型定义初始化清空操作判空,判满栈长度输出入栈出栈避免出栈时间开销大的方法 第三节进一步讨论栈和队列 双端队列 假设你芷…...
力扣 55. 跳跃游戏
🔗 https://leetcode.cn/problems/jump-game 题目 给一个数组 nums,最开始在 index 0,每次可以跳跃的区间是 0-nums[i]判断是否可以跳到数组末尾 思路 题解是用贪心,实际上模拟也可以过遍历可以到达的下标,判断其可…...
深入剖析 HTML5 新特性:语义化标签和表单控件完全指南
系列文章目录 01-从零开始学 HTML:构建网页的基本框架与技巧 02-HTML常见文本标签解析:从基础到进阶的全面指南 03-HTML从入门到精通:链接与图像标签全解析 04-HTML 列表标签全解析:无序与有序列表的深度应用 05-HTML表格标签全面…...

本地快速部署DeepSeek-R1模型——2025新年贺岁
一晃年初六了,春节长假余额马上归零了。今天下午在我的电脑上成功部署了DeepSeek-R1模型,抽个时间和大家简单分享一下过程: 概述 DeepSeek模型 是一家由中国知名量化私募巨头幻方量化创立的人工智能公司,致力于开发高效、高性能…...
MVC 文件夹:架构之美与实际应用
MVC 文件夹:架构之美与实际应用 引言 MVC(Model-View-Controller)是一种设计模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种架构模式不仅提高了代码的可维护性和可扩展性,而且使得开发流程更加清晰。本文将深入探讨MVC文…...

Redis --- 秒杀优化方案(阻塞队列+基于Stream流的消息队列)
下面是我们的秒杀流程: 对于正常的秒杀处理,我们需要多次查询数据库,会给数据库造成相当大的压力,这个时候我们需要加入缓存,进而缓解数据库压力。 在上面的图示中,我们可以将一条流水线的任务拆成两条流水…...

如何确认设备文件 /dev/fb0 对应的帧缓冲设备是开发板上的LCD屏?如何查看LCD屏的属性信息?
要判断 /dev/fb0 是否对应的是 LCD 屏幕,可以通过以下几种方法: 方法 1:使用 fbset 命令查看帧缓冲设备的属性信息 Linux 的 帧缓冲设备(Framebuffer) 通常在 /dev/fbX 下,/dev/fb0 一般是主屏幕ÿ…...

C++多线程编程——基于策略模式、单例模式和简单工厂模式的可扩展智能析构线程
1. thread对象的析构问题 在 C 多线程标准库中,创建 thread 对象后,必须在对象析构前决定是 detach 还是 join。若在 thread 对象销毁时仍未做出决策,程序将会终止。 然而,在创建 thread 对象后、调用 join 前的代码中ÿ…...

【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...

AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...