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

算法复杂度

news 来源：原创 2025/5/13 6:03:05

目录：

算法的效率
时间复杂度

1.算法的效率

1.1旋转数组习题分析

如何衡量一个算法的好坏呢？

案例：旋转数组（189. 轮转数组 - 力扣（LeetCode））

思路：循环k次将所有元素向后移动一位

首先我们先看一下题目：

这道题其实就是把数组后k个元素放到开头，进行轮换。

图示：

代码展示：

void rotate(int* nums, int numsSize, int k) 
{int i = 0,end = 0;while(k--){end = nums[numsSize - 1];for(i = numsSize - 1 ; i > 0 ; i--){nums[i] = nums[i - 1];}nums[0] = end;}
}

这个代码点击执行可以通过，然而点击提交却无法通过。

1.2复杂度的概念

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量⼀个算法的好坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们已经不需要再特别关注一个算法的空间复杂度。

2.时间复杂度

定义：在计算机科学中，算法的时间复杂度是一个函数式T(N)，它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运行时间呢？

因为程序运行时间和编译环境和运行机器配置都有关系，比如同一个算法程序,用一个老编译
器进行编译和新编译器编译,在同样机器下运行时间不同。
同一个算法程序,用一个老低配置机器和新高配置机器,运行时间也不同。
并且时间只能程序写好后测试,不能写程序前通过理论思想计算评估。

那么算法的时间复杂度是一个函数式T(N)到底是什么呢?这个T(N)函数式计算了程序的执行次数。通过c语言编译链接章节学习,我们知道算法程序被编译后生成二进制指令,程序运行,就是cpu执行这
些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执行次数的函数式T(N),假设每句指令执行时间基本一样(实际中有差别,但是微乎其微),那么执行次数和运行时间就是等比正相关,这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣。比如解决一个问题的算法a程序T(N)=N,算法b程序T(N)=N^2,那么算法a的效率一定优于算法b。

案例1：

void Func1(int N) 
{ int count = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { ++count;} }for (int k = 0; k < 2 * N; ++k) { ++count;}int M = 10;while (M--) { ++count; } 
}

T(N)=N^2+2*N+10

N=10 T(N)=130
N=100 T(N)=10210
N=1000 T(N)=1002010

能够判断出，对结果影响最大的N^2，时间复杂度为O(N^2)。

2.1大O的渐进表示法

大O符号(Big O notation):是用于描述函数渐进行为的数学符号

推导大O阶规则：

时间复杂度函数式T(N)中,只保留最高阶项,去掉那些低阶项,因为当N不断变大时,低阶项对结果影响越来越小,当N无穷大时,就可以忽略不计了。
如果最高阶项存在且不是1,则去除这个项目的常数系数,因为当N不断变大,这个系数对结果影响越来越小,当N无穷大时,就可以忽略不计了。
T(N)中如果没有N相关的项目,只有常数项,用常数1取代所有加法常数。

2.2时间复杂度计算示例

代码1：

void Func2(int N) 
{int count = 0;for (int k = 0; k < 2 * N; ++k) {++count;}int M = 10;while (M--) {++count;}printf("%d\n", count);
}

T(N)=2N+10，根据规则2可知，时间复杂度为O(N)。

代码2：

    // 计算Func3的时间复杂度？
void Func3(int N, int M) 
{int count = 0;for (int k = 0; k < M; ++k) {++count;}for (int k = 0; k < N; ++k) {++count;}printf("%d\n", count);
}

T(N)=M+N

时间复杂度：

M>>N O(M)
M<<N O(N)
M==N O(M+N)

代码3：

    // 计算Func4的时间复杂度？void Func4(int N) {int count = 0;for (int k = 0; k < 100; ++k) {++count;}printf("%d\n", count);}

T(N)=100,根据规则3可知，时间复杂度为O(1)。

代码4：

    const char* strchr(const char* str, int character) {const char* p_begin = s;while (*p_begin != character) {if (*p_begin == '\0')return NULL;p_begin++;}return p_begin;}

strchr执行的基本操作次数：

若要查找的字符在字符串的前面，则：T(N)=1
若要查找的字符在字符串的中间，则：T(N)=N/2
若要查找的字符在字符串的后面，则：T(N)=N

因此：strchr的时间复杂度分为：

最好情况：O(1)
最坏情况：O(N)
平均情况：O(N)

总结：

通过上面我们会发现，有些算法的时间复杂度存在最好、平均和最坏情况。

最坏情况：任意输入规模的最大运行次数（上界）

平均情况：任意输入规模的期望运行次数

最好情况：任意输入规模的最小运行次数（下界）

大O的渐进表示法在实际中一般情况关注的是算法的上界，也就是最坏运行情况。

代码5：

    void BubbleSort(int* a, int n) {assert(a);for (size_t end = n; end > 0; --end) {int exchange = 0;for (size_t i = 1; i < end; ++i) {if (a[i - 1] > a[i]) {Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}}

这个代码大家可能并不陌生，没错就是冒泡排序

计算时间复杂度，我们就要去计算最坏的情况（此时end也为n），那么就是完整的进行一次循环

则我们能够指导代码规律：

外：n、n-1、n-2、……1
内：n-1、n-2、n-3、……0 （相加）

所以我们能够知道一共循环了n*(n-1)/2次，经过大O规则后，最后的出来的时间复杂度是O(N^2)

代码6：

    void func5(int n) {int cnt = 1;while (cnt < n) {cnt *= 2;}}

当n=2时，执行次数为1

当n=4时，执行次数为2

当n=16时，执行次数为4

假设执行次数为x，则2^x=n

因此执行次数：x=log n（以2为底）

因此：时间复杂度取最差情况为：log n（以2为底）

代码7：

long long Fac(size_t N)
{if(0==N)return 1;return Fac(N-1)*N;
}

调用一次Fac函数的时间复杂度为O(1)

而在Fac函数中，存在n次递归调用

因此：阶乘递归的时间复杂度为：O(n)

代码8：

int func(int n)
{if(n==0) return 1;return func(n) + func(n-1)
}

上面的代码中，有两次递归调用，函数的执行时间就会和输入n成指数的关系。

因此，这里可以用O(2^n)表示

3.空间复杂度

空间复杂度也是一个数学表达式,是对一个算法在运行过程中因为算法的需要额外临时开辟的空间。

空间复杂度不是程序占用了多少bytes的空间,因为常规情况每个对象大小差异不会很大,所以空间复
杂度算的是变量的个数。

空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法。

注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好
了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

3.1空间复杂度计算示例

代码1：

    void BubbleSort(int* a, int n) {assert(a);for (size_t end = n; end > 0; --end) {int exchange = 0;for (size_t i = 1; i < end; ++i) {if (a[i - 1] > a[i]) {Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}}

此时函数的栈帧已经在编译时就确定好了，所以我们这里关注函数内部就好，很显然，这里我们就创立了exchange等一些局部变量，此时可以直到开辟的空间为一个常量，所以最后计算的大O应该是O(1)。

代码2：

    long long Fac(size_t N) {if (N == 0)return 1;return Fac(N - 1) * N;}

Fac递归调用了N次，额外开辟了N个函数栈帧，每个栈帧使用了常数个空间

因此空间复杂度为：O(N)

4.常见复杂度对比

按增长量级递增排列，常见的时间复杂度有：

O(1)：常数阶
O(logn)：对数阶
O(n)：线性阶
O(nlogn)：线性对数阶
O(n^2)：平方阶
O(n^3)：立方阶
O(2^n)：指数阶
O(n!)：阶乘阶

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)

5.复杂度算法题

189. 轮转数组 - 力扣（LeetCode）

思路1：

时间复杂度O(n^2)
循环k次将数组所有元素向后移动一位（代码不通过）

void rotate(int* nums, int numsSize, int k) 
{int i = 0,end = 0;while(k--){end = nums[numsSize - 1];for(i = numsSize - 1 ; i > 0 ; i--){nums[i] = nums[i - 1];}nums[0] = end; }
}

思路2：

空间复杂度O(n) ，时间复杂度O(n)
申请新数组空间，先将后k个数据防到新数组中，再将剩下的数据挪到新数组中

void rotate(int* nums, int numsSize, int k) 
{int arr[numsSize];for (int i = 0; i < numsSize; i++){arr[(i + k) % numsSize] = nums[i];}for (int i = 0; i < numsSize; i++){nums[i] = arr[i];}
}

思路3：

时间复杂度O(N)，空间复杂度O(1)
前n-k个逆置：4321567
后k个逆置：4321765
整体逆置：5671234

void jiaohuan(int * arr,int left,int right)
{while(left < right){int tmp;tmp = arr[left];arr[left] = arr[right];arr[right] = tmp;left++;right--;}}void rotate(int* nums, int numsSize, int k) 
{k = k % numsSize;jiaohuan(nums,0,numsSize - k - 1);jiaohuan(nums,numsSize - k,numsSize - 1);jiaohuan(nums,0,numsSize - 1);}

算法复杂度

目录： 算法的效率时间复杂度 1.算法的效率 1.1旋转数组习题分析如何衡量一个算法的好坏呢？ 案例：旋转数组（189. 轮转数组 - 力扣（LeetCode）） 思路：循环k次将所有元素向后移动一…...

编程日记 2025/5/13 6:03:05

时序约束进阶六：Set_Clock_Groups详解

目录一、前言二、时钟间关系 2.1 时钟关系分类 2.2 时钟关系查看三、set_clock_groups设置 3.1 使用格式 3.2 优先级 3.3 约束设置示例 3.4 约束效果查看四、Exclusive差异说明 4.1 Asynchronous 4.2 Logically_exclusive与Physically_exclusive 4.3 logical…...

编程日记 2025/5/8 12:21:32

《运放秘籍》第二部：仪表放大器专项知识点总结

一、差分放大器与仪表放大器的讨论 1.1. 仪放的前世今生——差分放大器原理？ 1.2. 差分放大的原理 1.3. 差分放大器检测电流 1.4. 差分放大器端一：输入阻抗 1.5. 差分放大器端二：共模抑制比 1.6. 为什么关注输入阻抗？共模抑…...

编程日记 2025/5/13 5:51:16

JavaSE——异常

一、异常的概念在Java中，将程序执行中发生的不正常行为称为"异常"，开发过程中的语法错误和逻辑错误不是异常。主要分为以下两大类： Error(错误)：Java虚拟机无法解决的严重问题，是严重错误，程序…...

编程日记 2025/5/13 5:33:11

HormonyOS: 图形变换之Rotate

官网地址：rotate 1. 概述 rotate是鸿蒙系统为组件提供的旋转属性，通过rotate属性，可实现组件的旋转效果 2. rotate属性 2.1. 语法参数 rotate(value: RotateOptions) 参数： 参数名类型必填说明 value RotateOptions…...

编程日记 2025/5/7 14:54:43

【Solidity】入门指南：智能合约开发基础

🌈个人主页: 鑫宝Code 🔥热门专栏: 闲话杂谈｜ 炫酷HTML | JavaScript基础 💫个人格言: "如无必要，勿增实体" 文章目录 Solidity入门指南：智能合约开发基础引言1. 开发环境搭建1.1 Remix I…...

编程日记 2025/5/13 5:38:47

HTMLHTML5革命：构建现代网页的终极指南 - 3. 开发工具选择

HTML&HTML5革命：构建现代网页的终极指南 3. 开发工具选择大家好，我是莫离老师。前两节课我们学习了 HTML 的基础概念和 HTML5 的主要特性，为接下来的实际开发奠定了理论基础。今天，我们将讨论开发工具的选择问题。选择合…...

编程日记 2025/5/13 5:23:42

智能设备安全隐患：五项关键解决措施

目前，我们的智能设备越来越多，而背后的物联网（IoT）安全像一面隐形的盾牌，默默地守护着我们周围那些复杂连网的设备。为了让大家更加明白这些安全协议和操作是如何高效运作的，我们有必要深入探讨物联网安全…...

编程日记 2025/5/13 5:37:34

Android NDK开发 JNI 基础

在android 系统开发中 ndk开发是很重要的内容。ndk开发中 jni 是基础。目录一．什么是JNI 二. 如何使用JNI 1.Java 代码如何调用 c/c 代码 2. c/c如何调用 java 函数一．什么是JNI JNI——Java Native Interface，它是Java平台的一个特…...

编程日记 2025/5/6 17:34:14

嵌入式linux之文件系统管理

嵌入式Linux文件系统的管理涉及多个方面，包括文件系统的创建、配置、维护以及优化。以下是一些关键点和实践技巧： 文件系统的创建与配置选择合适的文件系统：根据应用需求（如读写频率、存储介质类型等）选择最合适的文…...

编程日记 2025/5/13 4:46:35

Y20030029 微信+SPRINGBOOT+MYSQL+LW+传统文化展示小程序的设计与实现源代码配置文档

传统文化展示小程序 1.项目描述2. 课题开发的背景与意义3.项目功能4.界面展示5.源码获取 1.项目描述基于微信小程序的传统文化展示小程序是一个集合了多种传统文化元素与现代化技术的创新平台。它充分利用了微信小程序的便捷性和普及性，为广大用户提供了一个深入了…...

编程日记 2025/5/12 11:51:49

【LC】3232. 判断是否可以赢得数字游戏

题目描述： 给你一个正整数数组 nums。 Alice 和 Bob 正在玩游戏。在游戏中，Alice 可以从 nums 中选择所有个位数或所有两位数，剩余的数字归 Bob 所有。如果 Alice 所选数字之和严格大于 Bob 的数字之和，则 Alice 获胜。如果…...

编程日记 2025/5/13 5:07:34

【人工智能基础03】机器学习（练习题）

文章目录课本习题监督学习的例子过拟合和欠拟合常见损失函数，判断一个损失函数的好坏无监督分类：kmeans无监督分类，Kmeans 三分类问题变换距离函数选择不同的起始点重点回顾1. 监督学习、半监督学习和无监督学习的定义2. 判断学习场景3. 监…...

编程日记 2025/5/13 4:55:56

C/C++每日一练：合并K个有序链表

本篇博客将探讨如何 “合并K个有序链表” 这一经典问题。本文将从题目要求、解题思路、过程解析和相关知识点逐步展开，同时提供详细注释的代码示例。链表（Linked List） 链表是一种线性数据结构，由一系列节点（Node&…...

编程日记 2025/5/6 20:21:14

jmeter基础07_组件的层级

课程大纲 1. 优先级/执行顺序（一般情况） 同级组件：按组件先后顺序执行。如：同一层的线程组、同一层的http请求。上下级组件：先执行外层（上级），再执行内层（下级&#xff…...

编程日记 2025/5/13 5:55:00

【QNX+Android虚拟化方案】125 - 如何创建android-spare镜像

【QNX+Android虚拟化方案】125 - 如何创建android-spare镜像 1. Android侧创建 (ext4 / sparse) test_img.img 镜像方法一2. Android侧创建 (ext4 / sparse) test_img.img 镜像方法二3. qnx 侧分区透传Android 配置3.1 配置分区透传3.2 Android 侧分区 rename3.3 创建挂载目…...

编程日记 2025/5/10 10:23:56

大R玩家流失预测在休闲社交游戏中的应用

摘要预测玩家何时会离开游戏为延长玩家生命周期和增加收入贡献创造了独特的机会。玩家可以被激励留下来，战略性地与公司组合中的其他游戏交叉链接，或者作为最后的手段，通过游戏内广告传递给其他公司。本文重点预测休闲社交游戏中高价值玩家…...

编程日记 2025/5/13 4:54:44

使用Postman搞定各种接口token实战

现在许多项目都使用jwt来实现用户登录和数据权限，校验过用户的用户名和密码后，会向用户响应一段经过加密的token，在这段token中可能储存了数据权限等，在后期的访问中，需要携带这段token，后台解析这段token才…...

编程日记 2025/5/13 4:48:56

【C++】printf 函数详解与格式化输出控制

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 💯前言💯printf 基础用法1.1 printf 的常见占位符1.2 占位符与参数的对应关系1.3 换行控制示例： 💯格式化输出控制2.1 输出宽度控制2.1.1 指定最小宽度 2.2 …...

编程日记 2025/5/13 5:45:29

在21世纪的我用C语言探寻世界本质——字符函数和字符串函数(1)

人无完人，持之以恒，方能见真我！！！ 共同进步！！ 文章目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现四、strcpy的使用和模拟实现五、strcat的使用和模拟实现六、strcmp的使用和…...

编程日记 2025/5/12 15:36:12

【专题】存储器管理

1. 存储器的层次结构在计算机执行时，几乎每一条指令都涉及对存储器的访问，因此要求对存储器的访问速度能跟得上处理机的运行速度。存储器的速度必须非常快，能与处理机的速度相匹配，否则会明显地影响到处理机的运行。此外还要求…...

编程日记 2025/5/12 15:40:03

python股票数据分析（Pandas）练习

需求： 使用pandas读取一个CSV文件，文件内容包括股票名称、价格和交易量。完成以下任务： 找出价格最高的股票； 计算总交易量； 绘制价格折线图。代码实现： import pandas as pd import matplotlib.pyplot …...

编程日记 2025/5/9 18:28:00

Hadoop生态圈框架部署（八）- Hadoop高可用（HA）集群部署

文章目录前言一、部署规划二、Hadoop HA集群部署（手动部署）1. 下载hadoop2. 上传安装包2. 解压hadoop安装包3. 配置hadoop配置文件3.1 虚拟机hadoop1修改hadoop配置文件3.1.1 修改 hadoop-env.sh 配置文件3.3.2 修改 core-site.xml 配置文件3.3.3 修改 …...

编程日记 2025/5/13 4:59:19

抗干扰设计的检查细则

抗干扰设计是确保电子系统或设备在复杂电磁环境中稳定运行的重要环节，涉及多个方面的设计和实施。以下是对抗干扰设计的检查细则的详细归纳： 一、电源线与地线设计电源线设计：选择合适的电源，尽量加宽电源线，保证电源…...

编程日记 2025/5/13 5:39:53

[Redis#12] 常用类型接口学习 | string | list

目录 0.准备 1.string get | set set_with_timeout_test.cpp set_nx_xx_test.cpp mset_test.cpp mget_test.cpp getrange_setrange_test.cpp incr_decr_test.cpp 2.list lpush_lrange_test.cpp rpush_test.cpp lpop_rpop_test.cpp blpop_test.cpp llen_test.cpp…...

编程日记 2025/5/12 6:47:35

React的ts文件中通过createElement拼接一段内容出来

比如接口返回一个值 const values [23.00, 40.00/kg];想做到如下效果， 如果单纯的用render渲染会很简单， 但是在ts文件中处理，所以采用了createElement拼接代码如下： format: (values: string[]) > {if (!values || !val…...

编程日记 2025/5/12 17:45:02

【Git系列】Git 提交历史分析：深入理解`git log`命令

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。推荐:kwan 的首页,持续学…...

编程日记 2025/5/13 4:37:20

深度学习笔记——生成对抗网络GAN

本文详细介绍早期生成式AI的代表性模型：生成对抗网络GAN。文章目录一、基本结构生成器判别器二、损失函数判别器生成器交替优化目标函数三、GAN 的训练过程训练流程概述训练流程步骤1. 初始化参数和超参数2. 定义损失函数3. 训练过程的迭代判别器训练步骤生成器…...

编程日记 2025/5/5 17:32:01

《地球科学与环境学报》

《地球科学与环境学报》报道范围涵盖基础地质、矿产地质、水资源与环境、工程地质、地球物理、地球信息科学等领域，刊载国内外未公开发表的有创新性或意义重大的研究论文和综述文章。　　来稿必须包括以下项目：题名（尽可能不要超过20字&…...

编程日记 2025/5/6 10:26:33

k8s 1.28 聚合层部署信息记录

–requestheader-client-ca-file –requestheader-allowed-namesfront-proxy-client –requestheader-extra-headers-prefixX-Remote-Extra- –requestheader-group-headersX-Remote-Group –requestheader-username-headersX-Remote-User –proxy-client-cert-file –proxy-cl…...

编程日记 2025/5/13 4:55:56

1.算法的效率

1.1旋转数组习题分析

1.2复杂度的概念

2.时间复杂度

案例1：

2.1大O的渐进表示法

2.2时间复杂度计算示例

代码1：

代码2：

代码3：

代码4：

代码5：

代码6：

代码7：

代码8：

3.空间复杂度

3.1空间复杂度计算示例

代码1：

代码2：

4.常见复杂度对比

5.复杂度算法题

思路1：

思路2：

思路3：

相关文章：