一、为什么需要复杂度分析?

想象你正在开发一个手机通讯录应用,需要实现联系人搜索功能。你有两种算法可以选择:

// 算法A:线性搜索
public Contact linearSearch(List<Contact> contacts, String name) {for (Contact c : contacts) {if (c.getName().equals(name)) {return c;}}return null;
}// 算法B:二分搜索(需要排序)
public Contact binarySearch(List<Contact> contacts, String name) {// 先排序(假设已实现)Collections.sort(contacts, Comparator.comparing(Contact::getName));int left = 0, right = contacts.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;int cmp = contacts.get(mid).getName().compareTo(name);if (cmp == 0) return contacts.get(mid);if (cmp < 0) left = mid + 1;else right = mid - 1;}return null;
}

问题:当联系人数量很少时(如100人),两种算法都很快。但当联系人增长到10万人时:

  • 算法A可能需要10秒
  • 算法B可能只需0.01秒

复杂度分析就是帮助我们预测算法在数据量增长时的表现,避免上线后才发现性能问题

二、时间复杂度:算法执行时间的增长趋势

1. 基本概念

时间复杂度不是计算具体时间,而是描述算法执行时间随数据规模增长的变化趋势

2. 大O表示法

我们使用大O表示法描述时间复杂度,常见的有:

  • O(1):常数时间
  • O(log n):对数时间
  • O(n):线性时间
  • O(n log n):线性对数时间
  • O(n²):平方时间
  • O(2ⁿ):指数时间
// 示例1:数组随机访问
int getElement(int[] arr, int index) {return arr[index]; // 只需一次操作
}// 示例2:判断奇偶
boolean isEven(int num) {return num % 2 == 0; // 一次计算
}
 

3. 常见时间复杂度详解

(1) O(1):常数时间

特点:执行时间不随数据规模变化

// 示例1:数组随机访问
int getElement(int[] arr, int index) {return arr[index]; // 只需一次操作
}// 示例2:判断奇偶
boolean isEven(int num) {return num % 2 == 0; // 一次计算
}
(2) O(log n):对数时间

特点:数据量翻倍时,操作数只增加1

// 示例:二分查找
int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) return mid;if (arr[mid] < target) left = mid + 1;else right = mid - 1;}return -1;
}

操作次数:每次循环数据量减半,N个元素最多需要log₂N次操作

(3) O(n):线性时间

特点:执行时间与数据规模成正比

// 示例:遍历数组
int findMax(int[] arr) {int max = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i] > max) max = arr[i];}return max;
}
// 示例:遍历数组
int findMax(int[] arr) {int max = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i] > max) max = arr[i];}return max;
}

操作次数:N个元素需要N次比较

(4) O(n log n):线性对数时间

特点:常见于高效排序算法

// 示例:归并排序
void mergeSort(int[] arr, int left, int right) {if (left < right) {int mid = (left + right) / 2;mergeSort(arr, left, mid);     // T(n/2)mergeSort(arr, mid + 1, right); // T(n/2)merge(arr, left, mid, right);  // O(n)}
}
// 时间复杂度:T(n) = 2T(n/2) + O(n) = O(n log n)
(5) O(n²):平方时间

特点:数据量翻倍时,时间增加4倍

// 示例1:冒泡排序
void bubbleSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);}}}
}
// 操作次数:(n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ O(n²)// 示例2:矩阵乘法
int[][] multiply(int[][] A, int[][] B) {int n = A.length;int[][] C = new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {for (int k = 0; k < n; k++) {C[i][j] += A[i][k] * B[k][j];}}}return C;
}
// 三重循环 → O(n³)
(6) O(2ⁿ):指数时间

特点:数据量增加1,时间翻倍

// 示例:斐波那契递归
int fibonacci(int n) {if (n <= 1) return n;return fibonacci(n - 1) + fibonacci(n - 2);
}
// 时间复杂度:T(n) = T(n-1) + T(n-2) + O(1) ≈ O(2ⁿ)

4. 时间复杂度计算规则

  1. 忽略常数:O(2n) → O(n)
  2. 取最高阶:O(n³ + n² + n) → O(n³)
  3. 忽略系数:O(3n²) → O(n²)
  4. 对数底数忽略:O(log₂n) → O(log n)

三、空间复杂度:算法占用内存的增长趋势

1. 基本概念

空间复杂度描述算法运行过程中临时占用存储空间随数据规模增长的变化趋势

2. 常见空间复杂度

(1) O(1):常数空间

特点:占用固定内存,不随数据规模变化

// 示例:数组元素求和
int sum(int[] arr) {int total = 0;           // 1个变量for (int num : arr) {total += num;        // 无新空间}return total;
}
(2) O(n):线性空间

特点:占用空间与数据规模成正比

// 示例1:数组复制
int[] copyArray(int[] arr) {int[] newArr = new int[arr.length]; // 长度为n的数组for (int i = 0; i < arr.length; i++) {newArr[i] = arr[i];}return newArr;
}// 示例2:递归深度
int factorial(int n) {if (n <= 1) return 1;return n * factorial(n - 1); // 递归深度n → O(n)栈空间
}
(3) O(n²):平方空间

特点:常见于二维数据结构

// 示例:矩阵存储
int[][] generateMatrix(int n) {int[][] matrix = new int[n][n]; // n×n的矩阵for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {matrix[i][j] = i * j;}}return matrix;
}
// 占用空间:n² → O(n²)

四、复杂度分析实战

案例1:两数之和

// 方法1:暴力枚举
int[] twoSum(int[] nums, int target) {for (int i = 0; i < nums.length; i++) {for (int j = i + 1; j < nums.length; j++) {if (nums[i] + nums[j] == target) {return new int[]{i, j};}}}return new int[0];
}
// 时间复杂度:O(n²)  空间复杂度:O(1)// 方法2:哈希表
int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int complement = target - nums[i];if (map.containsKey(complement)) {return new int[]{map.get(complement), i};}map.put(nums[i], i);}return new int[0];
}
// 时间复杂度:O(n)  空间复杂度:O(n)

案例2:归并排序

void mergeSort(int[] arr) {if (arr.length <= 1) return;int mid = arr.length / 2;int[] left = Arrays.copyOfRange(arr, 0, mid); // O(n)int[] right = Arrays.copyOfRange(arr, mid, arr.length); // O(n)mergeSort(left);mergeSort(right);merge(arr, left, right);
}
// 时间复杂度:O(n log n)
// 空间复杂度:O(n)(递归栈O(log n) + 临时数组O(n))

五、复杂度优化策略

1. 时间优化技巧

  • 空间换时间:使用哈希表减少查找时间
  • 分治策略:归并排序、快速排序
  • 动态规划:避免重复计算
  • 双指针:减少不必要的遍历

2. 空间优化技巧

  • 原地操作:冒泡排序、堆排序
  • 迭代替代递归:减少栈空间
  • 数据压缩:位图代替布尔数组

六、常见算法复杂度总结

算法名称时间复杂度空间复杂度应用场景
二分查找O(log n)O(1)有序数据查找
快速排序O(n log n)O(log n)通用排序
归并排序O(n log n)O(n)大数据排序
冒泡排序O(n²)O(1)教学示例
深度优先搜索O(V+E)O(V)图遍历
动态规划O(n²)O(n)最优解问题

七、实际开发中的复杂度分析

1. 数据库查询优化

-- O(n) 全表扫描
SELECT * FROM users WHERE name LIKE '%john%';-- O(log n) 索引查询
SELECT * FROM users WHERE id = 10086;

2. 系统设计考虑

  • 用户量从1万到1000万时:
    • 时间复杂度O(n²)的算法会慢10000倍
    • 空间复杂度O(n)需要1000倍内存

3. 性能测试与复杂度验证

// 测试不同规模数据下的执行时间
void testPerformance() {for (int n = 1000; n <= 1000000; n *= 10) {int[] arr = generateArray(n); // 生成n个元素的数组long start = System.nanoTime();algorithm(arr); // 运行算法long duration = System.nanoTime() - start;System.out.printf("n=%d, time=%.2f ms%n", n, duration / 1e6);}
}

八、复杂度分析的局限性

  1. 忽略常数因子:O(100n)和O(n)视为相同
  2. 不考虑硬件差异:SSD vs HDD
  3. 不反映实际时间:只描述增长趋势
  4. 不适用于小数据量:小数据时简单算法可能更快

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/bicheng/87876.shtml
繁体地址,请注明出处:http://hk.pswp.cn/bicheng/87876.shtml
英文地址,请注明出处:http://en.pswp.cn/bicheng/87876.shtml

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

408第三季part2 - 计算机网络 - 交换机

理解 题目 如果你这么做 那你完了&#xff0c;因为这种叫存储转发 直通只转目的地址 b 再次理解 A发数据到交换机里想给B 然后交换表会记录A的MAC地址和端口 然后因为交换表找不到B&#xff0c;所以A会把BCD全部肘一遍&#xff08;广播&#xff09;&#xff0c;最终只有B会…

从零开始开发纯血鸿蒙应用之探析仓颉语言与ArkTS的差异

探析仓颉语言与ArkTS的差异 〇、前言一、IDE 的支持程度不同二、内置组件的使用方式不同三、页面路由实现方式的不同四、总结 〇、前言 截止到本文发布的日期为止&#xff0c;鸿蒙官方所推荐的开发原生鸿蒙应用的语言&#xff0c;有两种&#xff0c;分别是扩展自 Typescript 的…

Cursor/VScode ,点击运行按钮,就打开新的终端,如何设置为在当前终端运行文件而不是重新打开终端----一招搞定篇

我发现就是&#xff0c;我运行.py&#xff0c;点击完运行按钮&#xff0c;就给我重新打开一个终端&#xff0c;然后新的终端是在base环境中的&#xff0c;就跟麻烦 还得在当前终端输入python3 test.py 来运行文件。能不能修改。1、打开cursor或者vscode 。 同时按下 ctrlshiftp…

【STM32实践篇】:I2C驱动编写

文章目录I2C 物理层I2C 协议层1. 数据有效性2. 起始和停止信号3. 应答响应4. 总线的寻址方式5. 数据传输5.1 主机向从机发送数据5.2 主机由从机中读数据5.3 I2C通信复合格式I2C 驱动编写1. 配置 SCL 和 SDA2. I2C起始信号和停止信号3. 等待从设备应答4. 主机发送ACK和NACK信号5…

ragflow本地部署教程linux Ubuntu系统

以下是一份在 Ubuntu 系统上本地部署 RAGFlow 的详细教程。 一、基础环境准备 1.硬件要求 –CPU ≥ 4核 –RAM ≥ 16 GB –磁盘空间 ≥ 50 GB&#xff08;建议 SSD&#xff09; 2.系统配置 更新系统 sudo apt update && sudo apt upgrade -y 设置内核参数&#xff…

[netty5: WebSocketClientHandshaker WebSocketClientHandshakerFactory]-源码分析

在阅读这篇文章前&#xff0c;推荐先阅读以下内容&#xff1a; [netty5: WebSocketFrame]-源码分析[netty5: WebSocketFrameEncoder & WebSocketFrameDecoder]-源码解析 WebSocketClientHandshakerFactory WebSocketClientHandshakerFactory 是用于根据 URI 和协议版本创…

4.2 如何训练⼀个 LLM

⼀般⽽⾔&#xff0c;训练⼀个完整的 LLM 需要经过图1中的三个阶段——Pretrain、SFT 和 RLHF。 4.2.1 Pretrain 预训练任务与架构 任务类型&#xff1a;采用因果语言模型&#xff08;CLM&#xff09;&#xff0c;通过预测下一个 token 进行训练&#xff0c;与传统预训练模型…

Qt中的QObject::moveToThread方法详解

一、QObject::moveToThread方法QObject::moveToThread()是Qt框架中一个非常重要的功能&#xff0c;它允许改变QObject及其子对象的线程关联性。这个功能在多线程编程中特别有用&#xff0c;可以将耗时操作移到工作线程执行&#xff0c;避免阻塞主线程/GUI线程。基本用法void QO…

【9】用户接入与认证配置

本文旨在帮助网络管理员在 SD-WAN 环境中实现安全、稳定的用户接入与认证策略,涵盖本地/远程认证、权限管理、密码策略、SSH、会话控制等关键配置要素。 1.密码策略与账户安全 从 IOS XE SD-WAN 17.3.1 起,Cisco 引入密码强化功能,用于统一用户密码的复杂度与有效性要求。密…

第十六节:第三部分:多线程:线程安全问题、取钱问题的模拟

线程安全问题介绍&#xff1a;取钱的线程安全问题 取钱的线程安全问题 取钱案例需求分析 线程安全问题出现的原因 代码&#xff1a;模拟线程安全问题&#xff08;上述取钱案例&#xff09; Account类&#xff08;账户类&#xff09; package com.itheima.day3_thread_safe;pu…

APE:大语言模型具有人类水平的提示工程能力

摘要 通过以自然语言指令作为条件输入&#xff0c;大型语言模型&#xff08;LLMs&#xff09;展现出令人印象深刻的通用计算能力。然而&#xff0c;任务表现严重依赖于用于引导模型的提示&#xff08;prompt&#xff09;质量&#xff0c;而最有效的提示通常是由人类手工设计的…

X86 CPU 工作模式

1.概述 1.实模式 实模式又称实地址模式&#xff0c;实&#xff0c;即真实&#xff0c;这个真实分为两个方面&#xff0c;一个方面是运行真实的指令&#xff0c;对指令的动作不作区分&#xff0c;直接执行指令的真实功能&#xff0c;另一方面是发往内存的地址是真实的&#xff…

Java设计模式之行为型模式(策略模式)介绍与说明

一、策略模式简介 策略模式&#xff08;Strategy Pattern&#xff09;是一种行为型设计模式&#xff0c;它定义了一系列算法&#xff0c;并将每个算法封装起来&#xff0c;使它们可以相互替换&#xff0c;且算法的变化不会影响使用算法的客户。策略模式让算法独立于使用它的客…

【BIOS+MBR 微内核手写实现】

本文基于BIOS+MBR的架构,从四部分讲解微内核是如何实现的: 1)搭建微内核编译调试环境 2)梳理微内核的代码结构:伪指令讲解 3)手写实现微内核框架,输出简单的字符串 4)讲解微内核启动阶段的具体运行过程 先完成内核工程创建,如下图 我们这里使用nasm风格的汇编编写,…

从C/C++迁移到Go:内存管理思维转变

一、引言 在当今高速发展的软件开发世界中&#xff0c;语言迁移已成为技术进化的常态。作为一名曾经的C/C开发者&#xff0c;我经历了向Go语言转变的全过程&#xff0c;其中最大的认知挑战来自内存管理模式的根本性差异。 我记得第一次接触Go项目时的困惑&#xff1a;没有析构函…

正确设置 FreeRTOS 与 STM32 的中断优先级

在裸机开发&#xff08;非 RTOS&#xff09;时&#xff0c;大多数 STM32 外设的中断优先级通常不需要手动配置&#xff0c;原因如下&#xff1a; ✅ 裸机开发中默认中断优先级行为 特点说明默认中断优先级为 0如果你不设置&#xff0c;STM32 HAL 默认设置所有外设中断为 0&…

EasyExcel之SheetWriteHandler:解锁Excel写入的高阶玩法

引言在 EasyExcel 强大的功能体系中&#xff0c;SheetWriteHandler 接口是一个关键的组成部分。它允许开发者在写入 Excel 的 Sheet 时进行自定义处理&#xff0c;为实现各种复杂的业务需求提供了强大的支持。通过深入了解和运用 SheetWriteHandler 接口&#xff0c;我们能够更…

Python单例模式魔法方法or属性

1.单例模式概念定义:单例模式(Singleton Pattern)是一种创建型设计模式&#xff0c;它确保一个类只能有一个实例&#xff0c;并提供一个全局访问点来获取该实例。这种模式在需要控制资源访问、配置管理或协调系统操作时特别有用。核心特点:私有构造函数&#xff1a;防止外部通过…

【Kubernetes系列】Kubernetes 资源请求(Requests)

博客目录 引言一、资源请求的基本概念1.1 什么是资源请求1.2 请求与限制的区别 二、CPU 请求的深入解析2.1 CPU 请求的单位与含义2.2 CPU 请求的调度影响2.3 CPU 请求与限制的关系 三、内存请求的深入解析3.1 内存请求的单位与含义3.2 内存请求的调度影响3.3 内存请求的特殊性 …

大型语言模型中的自动化思维链提示

摘要 大型语言模型&#xff08;LLMs&#xff09;能够通过生成中间推理步骤来执行复杂的推理任务。为提示演示提供这些步骤的过程被称为思维链&#xff08;CoT&#xff09;提示。CoT提示有两种主要范式。一种使用简单的提示语&#xff0c;如“让我们一步一步思考”&#xff0c;…