当前位置: 首页 > 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…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...

PH热榜 | 2025-06-08

1. Thiings 标语&#xff1a;一套超过1900个免费AI生成的3D图标集合 介绍&#xff1a;Thiings是一个不断扩展的免费AI生成3D图标库&#xff0c;目前已有超过1900个图标。你可以按照主题浏览&#xff0c;生成自己的图标&#xff0c;或者下载整个图标集。所有图标都可以在个人或…...

Python 高级应用10:在python 大型项目中 FastAPI 和 Django 的相互配合

无论是python&#xff0c;或者java 的大型项目中&#xff0c;都会涉及到 自身平台微服务之间的相互调用&#xff0c;以及和第三发平台的 接口对接&#xff0c;那在python 中是怎么实现的呢&#xff1f; 在 Python Web 开发中&#xff0c;FastAPI 和 Django 是两个重要但定位不…...