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

数据结构:时间复杂度

文章目录

  • 为什么需要时间复杂度分析?
  • 一、大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;
}

六、自测练习

  1. 分析以下代码复杂度
for (int i=0; i<n; i+=5) {for (int j=0; j<1000; j++) {sum += i*j;}
}

答案:O(n)(外层循环n/5次,内层固定1000次 → 忽略常数后为线性)

  1. 递归函数复杂度分析
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)时,那种思维的跃迁感,正是编程最迷人的魔法时刻!

相关文章:

数据结构:时间复杂度

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

SPI(Serial Peripheral Interface)串行外围设备接口

SPI概述&#xff1a; SPI协议最初由Motorola公司&#xff08;现为NXP Semiconductors的一部分&#xff09;在20世纪80年代中期开发。最初是为了在其68000系列微控制器中实现高速、高效的串行通信。该协议旨在简化微控制器与外围设备之间的数据传输。 1980年代&#xff1a;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的函数&#xff0c;举个例子。 #cv2.findContours函数来找到二值图像中的轮廓。#参数&#xff1a;#参数1&#xff1a;输 入的二值图像。通常是经过阈值处理后的图像&#xff0c;例如在颜色过滤之后生成的掩码。#参数2(cv2.RETR_EXTERNA…...

GESP6级语法知识(六):(动态规划算法(六)多重背包)

多重背包&#xff08;二维数组&#xff09; #include <iostream> using namespace std; #define N 1005 int Asd[N][N]; //Asd[i][j]表示前 i 个物品&#xff0c;背包容量是 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(重做日志)&#xff1a;记录事务对数据库的所有修改&#xff0c;在崩溃时恢复未提交的更改&#xff0c;保证事务…...

AI协助探索AI新构型自动化创新的技术实现

一、AI自进化架构的核心范式 1. 元代码生成与模块化重构 - 代码级自编程&#xff1a;基于神经架构搜索的强化学习框架&#xff0c;AI可通过生成元代码模板&#xff08;框架的抽象层定义&#xff09;自动组合功能模块。例如&#xff0c;使用注意力机制作为原子单元&#xff…...

九. Redis 持久化-RDB(详细讲解说明,一个配置一个说明分析,步步讲解到位)

九. Redis 持久化-RDB(详细讲解说明&#xff0c;一个配置一个说明分析&#xff0c;步步讲解到位) 文章目录 九. Redis 持久化-RDB(详细讲解说明&#xff0c;一个配置一个说明分析&#xff0c;步步讲解到位)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: 表分区>>范围分区,列表分区,散列分区/哈希分区,间隔分区,参考分区,组合分区,子分区/复合分区/组合分区

分区表 是将一个逻辑上的大表按照特定的规则划分为多个物理上的子表&#xff0c;这些子表称为分区。 分区可以基于不同的维度&#xff0c;如时间、数值范围、字符串值等&#xff0c;将数据分散存储在不同的分区 中&#xff0c;以提高数据管理的效率和查询性能&#xff0c;同时…...

使用Pygame制作“走迷宫”游戏

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

AJAX案例——图片上传个人信息操作

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

Day35-【13003】短文,什么是双端队列?栈和队列的互相模拟,以及解决队列模拟栈时出栈时间开销大的方法

文章目录 第三节进一步讨论栈和队列双端队列栈和队列的相互模拟使用栈来模拟队列类型定义入队出队判空&#xff0c;判满 使用队列来模拟栈类型定义初始化清空操作判空&#xff0c;判满栈长度输出入栈出栈避免出栈时间开销大的方法 第三节进一步讨论栈和队列 双端队列 假设你芷…...

力扣 55. 跳跃游戏

&#x1f517; https://leetcode.cn/problems/jump-game 题目 给一个数组 nums&#xff0c;最开始在 index 0&#xff0c;每次可以跳跃的区间是 0-nums[i]判断是否可以跳到数组末尾 思路 题解是用贪心&#xff0c;实际上模拟也可以过遍历可以到达的下标&#xff0c;判断其可…...

深入剖析 HTML5 新特性:语义化标签和表单控件完全指南

系列文章目录 01-从零开始学 HTML&#xff1a;构建网页的基本框架与技巧 02-HTML常见文本标签解析&#xff1a;从基础到进阶的全面指南 03-HTML从入门到精通&#xff1a;链接与图像标签全解析 04-HTML 列表标签全解析&#xff1a;无序与有序列表的深度应用 05-HTML表格标签全面…...

本地快速部署DeepSeek-R1模型——2025新年贺岁

一晃年初六了&#xff0c;春节长假余额马上归零了。今天下午在我的电脑上成功部署了DeepSeek-R1模型&#xff0c;抽个时间和大家简单分享一下过程&#xff1a; 概述 DeepSeek模型 是一家由中国知名量化私募巨头幻方量化创立的人工智能公司&#xff0c;致力于开发高效、高性能…...

MVC 文件夹:架构之美与实际应用

MVC 文件夹:架构之美与实际应用 引言 MVC(Model-View-Controller)是一种设计模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种架构模式不仅提高了代码的可维护性和可扩展性,而且使得开发流程更加清晰。本文将深入探讨MVC文…...

Redis --- 秒杀优化方案(阻塞队列+基于Stream流的消息队列)

下面是我们的秒杀流程&#xff1a; 对于正常的秒杀处理&#xff0c;我们需要多次查询数据库&#xff0c;会给数据库造成相当大的压力&#xff0c;这个时候我们需要加入缓存&#xff0c;进而缓解数据库压力。 在上面的图示中&#xff0c;我们可以将一条流水线的任务拆成两条流水…...

如何确认设备文件 /dev/fb0 对应的帧缓冲设备是开发板上的LCD屏?如何查看LCD屏的属性信息?

要判断 /dev/fb0 是否对应的是 LCD 屏幕&#xff0c;可以通过以下几种方法&#xff1a; 方法 1&#xff1a;使用 fbset 命令查看帧缓冲设备的属性信息 Linux 的 帧缓冲设备&#xff08;Framebuffer&#xff09; 通常在 /dev/fbX 下&#xff0c;/dev/fb0 一般是主屏幕&#xff…...

C++多线程编程——基于策略模式、单例模式和简单工厂模式的可扩展智能析构线程

1. thread对象的析构问题 在 C 多线程标准库中&#xff0c;创建 thread 对象后&#xff0c;必须在对象析构前决定是 detach 还是 join。若在 thread 对象销毁时仍未做出决策&#xff0c;程序将会终止。 然而&#xff0c;在创建 thread 对象后、调用 join 前的代码中&#xff…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...