网站公司销售/杭州网站制作排名
文章目录
- 为什么需要时间复杂度分析?
- 一、大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 前的代码中ÿ…...

AI与SEO关键词的完美结合如何提升网站流量与排名策略
内容概要 在当今数字营销环境中,内容的成功不仅依赖于高质量的创作,还包括高效的关键词策略。AI与SEO关键词的结合,正是这一趋势的重要体现。 AI技术在SEO中的重要性 在数字营销领域,AI技术的引入为SEO策略带来了前所未有的变革。…...

保姆级教程Docker部署Kafka官方镜像
目录 一、安装Docker及可视化工具 二、单节点部署 1、创建挂载目录 2、运行Kafka容器 3、Compose运行Kafka容器 4、查看Kafka运行状态 三、集群部署 在Kafka2.8版本之前,Kafka是强依赖于Zookeeper中间件的,这本身就很不合理,中间件依赖…...

解析PHP文件路径相关常量
PHP文件路径相关常量包括以下几个常量: __FILE__:表示当前文件的绝对路径,包括文件名。 __DIR__:表示当前文件所在的目录的绝对路径,不包括文件名。 dirname(__FILE__):等同于__DIR__,表示当前…...

WPS计算机二级•幻灯片的配色、美化与动画
听说这是目录哦 配色基础颜色语言❤️使用配色方案🩷更改PPT的颜色🧡PPT动画添加的原则💛PPT绘图工具💚自定义设置动画💙使用动画刷复制动画效果🩵制作文字打字机效果💜能量站😚 配色…...

C#,shell32 + 调用控制面板项(.Cpl)实现“新建快捷方式对话框”(全网首发)
Made By 于子轩,2025.2.2 不管是使用System.IO命名空间下的File类来创建快捷方式文件,或是使用Windows Script Host对象创建快捷方式,亦或是使用Shell32对象创建快捷方式,都对用户很不友好,今天小编为大家带来一种全新…...

单纯信息展示的站点是否可以用UML建模
凌钦亮 More options Aug 7 2010, 10:36 am 现在社会上大量的网站需求都还只是用于单纯的企业信息展示,那此种网站是否有必要用UML 建模呢?业务用例图的一个个用例是用来卖的,但是他只有信息展示这个需 求,我是否在划分业务用例…...

FinRobot:一个使用大型语言模型的金融应用开源AI代理平台
“FinRobot: An Open-Source AI Agent Platform for Financial Applications using Large Language Models” 论文地址:https://arxiv.org/pdf/2405.14767 Github地址:https://github.com/AI4Finance-Foundation/FinRobot 摘要 在金融领域与AI社区间&a…...

【Numpy核心编程攻略:Python数据处理、分析详解与科学计算】2.19 线性代数核武器:BLAS/LAPACK深度集成
2.19 线性代数核武器:BLAS/LAPACK深度集成 目录 #mermaid-svg-yVixkwXWUEZuu02L {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-yVixkwXWUEZuu02L .error-icon{fill:#552222;}#mermaid-svg-yVixkwXWUEZ…...

开发板目录 /usr/lib/fonts/ 中的字体文件 msyh.ttc 的介绍【微软雅黑(Microsoft YaHei)】
本文是博文 https://blog.csdn.net/wenhao_ir/article/details/145433648 的延伸扩展。 本文是博文 https://blog.csdn.net/wenhao_ir/article/details/145433648 的延伸扩展。 问:运行 ls /usr/lib/fonts/ 发现有一个名叫 msyh.ttc 的字体文件,能介绍…...

Love Tester:探索爱情的深度与维度
爱情是什么?是相互帮助、耐心、理解、鼓励、保护、可靠和牺牲。Love Tester 通过先进的算法,分析名字的兼容性和关系的潜力,帮助你计算爱情匹配的准确性。 相互帮助:在伴侣遇到困难时伸出援手,这是爱情的体现。耐心&a…...