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

数据结构之算法的时间复杂度

1.时间复杂度的定义

在计算机科学中,算法的时间复杂度是一个函数,它定量描述了算法的运行时间。一个算法所花费的时间与其中语句的执行次数成正比列,算法中的基本操作的执行次数,为算法的时间复杂度

例1:

计算Func1中++count执行的次数

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

Func1的基本操作次数:F(N) = N^2 + 2 * N + 10来分析一下是为什么?

首先可以看到这段代码有三个循环

第一个是由两个for内外嵌套组成:每次循环N次,执行了N次,即N + N + N.....=N * N = N^2

第二个循环执行了 2*N

第三个循环执行了 10

如果每个时间复杂度都要这么表示的话那太复杂了,所以我们只取最大量级来表示这段代码的时间复杂度

当N  = 10时:F(N) = 130

当N = 20时:F(N) = 10210

当N = 30时:F(N) = 1002010

当我们的N取无穷大时 2 * N + 10这两个项对结果的影响已经不大了可以忽略不计,所以说只需要取N^2来表示它的时间复杂度就可以了

所以这段代码Func1的时间复杂度为: O(N ^ 2)

2.大O的渐进表示法

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

推导大O阶方法:

(1).用常数1来取代运行时间中的所有加法常数

(2).在修改后的运行次数的函数中,只保留最高阶项

(3).如果最高阶存在且不是1,则去除与这个项目相乘的常数,得到的结果就是大O阶

通过上面一个例子我们可以发现大O渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数

我们来计算几道代码的时间复杂度

例1:

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

F(N) = 2 * N +10

去掉与最高阶相乘的常熟和10使用大O渐进法表示法该段代码的时间复杂度为:O(N)

例2:

void Func3(int M, int N)
{int count = 0;for(int i = 0; i < M; i++){++count;}for(int j = 0; j < N; j++){++count;}printf("%d\n", count);
}

使用大O渐进法表示法该段代码的时间复杂度为:O(N + M)

因为M和N是未知的所以不能去掉它们两个任意一个

如果N大于M,则可以去掉M,反之可以去掉N,相等可任取M和N中任何一个

例3:

void Func4(int N)
{int count = 0;for(i = 0; i < 100: i++){++count;}printf("%d\n", count);
}

F(N) = 100

执行了100次,但是我们用1来表示

使用大O渐进法表示法该段代码的时间复杂度为:O(1)  

注:这里的1表示代表1次,而是常数次

3.时间复杂度的最好,最坏和平均情况

另外有些算法的时间复杂度存在最好,平均,最坏情况:

最坏情况:任意输入规模的最大运行次数(上界)

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

最好情况:任意输入规模最小运行次数(下界)

例4:

char* strchr(const char * str, int character)
{while(*Str){if(*str == character){return str;}str++;}return NULL;
}

例如:在一个长度为N的数组中找一个数据x

最好情况:1次找到

平均情况:N/2次找到

最坏情况:N次找到

在实际情况中一般关注的是算法的最坏运行情况,所以该段代码的时间复杂度为:O(N)

例5:

void BubbleSort(int *a, int n)
{assert(a);for(int end = n; end > 1; --end){for(int i = 1; i < end; i++){if(a[i - 1] > a[i]){int tmp = a[i];a[i] = a[i + 1];a[i + 1] = tmp;}}}
}

最好情况:O(N)

最坏情况将两个for循环跑满

外循环为n时,内循环循环n - 1次  然后按顺序n - 2, n-3, ....., 3, 2, 1通过判断可以知道这是一个等差数列,所以它的总和就为:n(n - 1 + 1)/2 = n^2*1/2 即最坏情况:O(N^2)

使用大O渐进法表示法去掉常数该段代码的时间复杂度为:O(N^2)  

例6:

在数组有序的情况下:可以使用二分法(折半查找)

int binarysearch(int *a,int n, int x)
{int begin = 0;int end = n - 1;while(begin <= end){int mid = begin + ((end - begin)>>1);if(a[mid] > x){end = a[mid] - 1;}else if(a[mid] < x){begin = a[mid] + 1;}else{return mid;}}return -1;
}

最好情况:O(1)

最坏情况:区间缩放到一个值,要么找到,要么找不到,假设N为数组个数,x是最坏查找次数N每次除2就等于查找一次,折半查找多少次就除多少个2

N/2/2/2..../2 = 1, 因为n为int所以最小二分到1,2^x = N 即:x = logN(log在时间复杂度中表示以2为底)所以最坏情况:O(logN)

例7:

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

使用大O渐进法表示法该段代码的时间复杂度为:O(N)

例8:

long long Fib(int n)
{if(n < 3){return 1;}else{return Fib(n - 1) + Fib(n - 2);}
}

最好情况:O(1)

可以观察到该递归的方式为等差数列我们用求和公式可以得出:2^(N-1)-1

最坏情况用大O渐进表示法:O(2^N)

总结以上时间复杂度:O(1)>O(logN)>O(N)>O(N^2)>O(N^3)>O(2*N)

相关文章:

数据结构之算法的时间复杂度

1.时间复杂度的定义 在计算机科学中&#xff0c;算法的时间复杂度是一个函数&#xff0c;它定量描述了算法的运行时间。一个算法所花费的时间与其中语句的执行次数成正比列&#xff0c;算法中的基本操作的执行次数&#xff0c;为算法的时间复杂度 例1&#xff1a; 计算Func1…...

unity中物体被激活自动执行挂载代码

在Unity中,如果希望当物体被激活时自动执行特定的函数,可以利用 MonoBehaviour 的生命周期函数 OnEnable()。这个方法会在对象被激活时调用,可以用来执行初始化或者处理其他逻辑。以下是如何在脚本中使用 OnEnable() 方法: using UnityEngine;public class ActivateFuncti…...

Pandas数据可视化详解:大案例解析(第27天)

系列文章目录 Pandas数据可视化解决不显示中文和负号问题matplotlib数据可视化seaborn数据可视化pyecharts数据可视化优衣库数据分析案例 文章目录 系列文章目录前言1. Pandas数据可视化1.1 案例解析&#xff1a;代码实现 2. 解决不显示中文和负号问题3. matplotlib数据可视化…...

Redis基础教程(七):redis列表(List)

&#x1f49d;&#x1f49d;&#x1f49d;首先&#xff0c;欢迎各位来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里不仅可以有所收获&#xff0c;同时也能感受到一份轻松欢乐的氛围&#xff0c;祝你生活愉快&#xff01; &#x1f49d;&#x1f49…...

鸿蒙开发:Universal Keystore Kit(密钥管理服务)【生成密钥(C/C++)】

生成密钥(C/C) 以生成ECC密钥为例&#xff0c;生成随机密钥。具体的场景介绍及支持的算法规格。 注意&#xff1a; 密钥别名中禁止包含个人数据等敏感信息。 开发前请熟悉鸿蒙开发指导文档&#xff1a;gitee.com/li-shizhen-skin/harmony-os/blob/master/README.md点击或者复…...

ssm“落雪”动漫网站-计算机毕业设计源码81664

目 录 摘要 1 绪论 1.1 研究背景 1.2 研究意义 1.3论文结构与章节安排 2系统分析 2.1 可行性分析 2.2 系统流程分析 2.2.1 数据新增流程 3.2.2 数据删除流程 2.3 系统功能分析 2.3.1 功能性分析 2.3.2 非功能性分析 2.4 系统用例分析 2.5本章小结 3 系统总体设…...

【面试题】Reactor模型

Reactor模型 定义 Reactor模型是一种事件驱动的设计模式&#xff0c;用于处理服务请求。它通过将事件处理逻辑与事件分发机制解耦&#xff0c;实现高性能、可扩展的并发处理。Reactor模型适用于高并发、事件驱动的程序设计&#xff0c;如网络服务器等。 特点 事件驱动&#…...

RedHat9 | kickstart无人值守批量安装

一、知识补充 kickstart Kickstart是一种用于Linux系统安装的自动化工具&#xff0c;它通过一个名为ks.cfg的配置文件来定义Linux安装过程中的各种参数和设置。 kickstart的工作原理 Kickstart的工作原理是通过记录典型的安装过程中所需人工干预填写的各种参数&#xff0c;…...

k8s-第五节-StatefulSet

StatefulSet StatefulSet 是用来管理有状态的应用&#xff0c;例如数据库。 前面我们部署的应用&#xff0c;都是不需要存储数据&#xff0c;不需要记住状态的&#xff0c;可以随意扩充副本&#xff0c;每个副本都是一样的&#xff0c;可替代的。 而像**数据库、Redis **这类…...

ai机器狗

ai机器狗的代码很早就开源了&#xff0c;相当于核心&#xff0c;最难东西美国人公开了&#xff0c;开源了&#xff0c;如果有钱&#xff0c;有足够资源的&#xff0c;造出东西有可能比公开这些核心代码的公司或者组织还好。没有技术含量&#xff0c;技术含量别人都解决了&#…...

数据库关键字执行顺序

在 SQL 中&#xff0c;关键字的执行顺序通常如下&#xff1a; FROM&#xff1a;确定要查询的表或数据源&#xff0c;并执行表之间的连接操作&#xff08;如 INNER JOIN、LEFT JOIN 等&#xff09;。FROM 子句执行顺序为从后往前、从右到左。ON&#xff1a;应用连接条件&#xf…...

Linux 永久挂载磁盘

文章目录 前言一、使用步骤1.命令 总结 前言 一、使用步骤 1.命令 第一步&#xff1a;创建挂载点 sudo mkdir /hhkj 第二步&#xff1a;磁盘挂载到挂载点&#xff08;lsblk、lvdisplay&#xff09; sudo mount /dev/sdb2 /hhkj 或者 sudo mount /dev/centos/home /hhkj 第三…...

windows启动Docker闪退Docker desktop stopped

Windows启动Docker闪退-Docker desktop stopped 电脑上很早就安装有Docker了&#xff0c;但是有一段时间都没有启动了&#xff0c;今天想启动启动不起来了&#xff0c;打开没几秒就闪退&#xff0c;记录一下解决方案。仅供参考 首先&#xff0c;参照其他解决方案&#xff0c;本…...

探索Redis GEOMETRY数据结构:地理空间索引与查询(基于Redis GEO和Java实现附近商户查找功能)

摘要 Redis是一个高性能的键值存储系统&#xff0c;广泛应用于缓存、消息队列、排行榜等场景。本文将介绍Redis中一个假设的GEOMETRY数据结构&#xff0c;用于高效地存储和查询地理空间数据。 1. Redis地理空间数据结构概述 地理空间数据结构允许用户存储地理位置信息&#…...

DP学习——策略模式

学而时习之&#xff0c;温故而知新。 敌人出招&#xff08;使用场景&#xff09; 业务中需要多个算法可替换&#xff0c;而不能重构代码时&#xff0c;怎么办&#xff1f;或者一个对象在运行中要根据业务切换不同的模式或者采用不同的算法&#xff0c;怎么办&#xff1f; 到…...

0701_ARM5

练习&#xff1a;使用usart4 main.c #include "uart4.h"int main() {// 初始化 UART4hal_uart4_init();while (1) {// 发送一个字符串//hal_put_char( hal_get_char());hal_put_string(hal_get_string());}return 0; } usart4.c #include "uart4.h"//**…...

Python用户宝典:了解并实现遗传算法

遗传算法是一种基于自然选择的技术&#xff0c;用于解决复杂问题。由于问题很复杂&#xff0c;遗传算法&#xff08;而不是其他方法&#xff09;被用来得出解决问题的合理方案。本文介绍遗传算法的基础知识以及如何用Python来实现。 遗传算法的要素 适应度函数 适应度函数衡…...

如何使用深度学习进行实时目标检测:速度与精度的双重挑战

如何使用深度学习进行实时目标检测&#xff1a;速度与精度的双重挑战 目标检测作为计算机视觉领域的核心任务之一&#xff0c;其目的是在图像或视频中识别和定位感兴趣的对象。随着深度学习技术的发展&#xff0c;基于深度学习的目标检测算法在实时性、准确性方面取得了显著进…...

创新引领,构筑产业新高地

在数字经济的浪潮中&#xff0c;成都树莓集团以创新驱动为核心&#xff0c;通过整合行业资源、优化服务、培养数字产业人才等措施&#xff0c;致力于打造产业高地&#xff0c;推动地方经济的高质量发展。 一、创新驱动&#xff0c;引领产业发展 1、引入新技术、新模式&#xf…...

npm,yarn清楚缓存

1.运行以下命令来清理npm缓存&#xff1a; npm cache clean --force或者运行以下命令清理Yarn缓存&#xff1a; yarn cache clean2.删除 node_modules 和锁文件&#xff1a; 删除 node_modules 目录和 package-lock.json 或 yarn.lock 文件&#xff0c;然后重新安装依赖 rm …...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...