算法时间、空间复杂度(二)

目录

大O渐进表示法 

一、时间复杂度量级的判断

定义:

例一:执行2*N+1次

例二:执行M+N次

例三:执行已知次数

例四:存在最好情况和最坏情况

顺序查找

冒泡排序

二分查找

例五:阶乘递归

​编辑

例六:斐波那契递归

​编辑

总结:


算法时间、空间复杂度(一)-CSDN博客icon-default.png?t=O83Ahttps://blog.csdn.net/Xiaodao12345djs/article/details/142931619?spm=1001.2014.3001.5501

大O渐进表示法 

我们通常用大O渐进表示法来表示时间复杂度和空间复杂度的量级

例如:如果一个程序执行了2N+1次,那么这个程序的时间复杂度属于O(N)这个量级

一、时间复杂度量级的判断

定义:

算法中的基本操作的次数,与环境无关

例一:执行2*N+1次

时间复杂度的量级为O(N)

  • 保留执行次数的最高阶
  • 去掉最高阶的常系数
for(int k=0; k<2*N; k++)
{
    ++count;
}

while(w--)
{
    ++count;
}

例二:执行M+N次

时间复杂度为O(N)或者O(M)

  • 如果M>>N,时间复杂度量级为O(M)
  • 如果N>>M,时间复杂度量级为O(N)
  • 如果相差不多,相当于执行2*N次或者2*M次,所以时间复杂度量级为O(N)或者O(M)
for(k = 0; k < M; k++)
{
    count++;
}
for(k = 0; k < N ; k++)
{
    count++;
}

例三:执行已知次数

时间复杂度位O(1)

for(int k = 0; k < 10; k++)
{
    count++;
}

例四:存在最好情况和最坏情况

如果出现最好情况执行次数和最坏情况执行次数,看最坏情况(下限)

  • 顺序查找

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

最好情况:执行1次就能找到

最坏情况:执行N次才能找到

时间复杂度为O(N)

  • 冒泡排序

最好情况:N-1次

最坏情况:N(N-1)/2(等差数列)

时间复杂度为O(N^2)

  • 二分查找

最好情况:1次

最坏情况:logN(以2为底N的对数,在C语言中会简化为logN,有的书上会简化成lgN(不推荐))

时间复杂度为O(logN)

​​​​​​​例五:阶乘递归

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

时间复杂度为O(N)

例六:斐波那契递归

long long Fib(size_t N)
{
    if(N<3)
        return 1;
    return Fib(N-1)+Fib(N-2);
}

时间复杂度为O(2^N)

总结:

  • O(1)           常数阶
  • O(logN)       对数阶
  • O(N)           线性
  • O(N*logN)    nlog阶
  • O(N^2)        平方阶
  • O(N^3)        立方阶
  • O(2^N)        指数阶

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/892431.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

线下陪玩导游系统软件源码,家政预约服务源码(h5+小程序+app)

游戏陪玩系统源码陪玩小程序源码搭建基于PHP&#xff0b;MySQL陪玩系统app源码陪玩系统定制开发服务、成品陪玩系统源码 系统基于Nginx或者Apache PHP7.3 数据库mysql5.6 前端为uniapp-vue2.0 后端为thinkphp6 有域名授权加密&#xff0c;其他开源可二开 演示源码下载 开…

【实战项目】——Boost搜索引擎(五万字)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 前言 一、项目的相关背景 1.1、什么是Boost库&#xff1f; 1.2、什么是搜索引擎&#xff1f; 1.3、为什么要做Boost库搜索引擎&#xff1f; 二、搜索引擎的宏观原…

大数据开发电脑千元配置清单

大数据开发电脑配置清单 电脑型号HUANANZHI 台式电脑操作系统Windows 11 专业版 64位&#xff08;Version 23H2 / DirectX 12&#xff09;处理器英特尔 Xeon(至强) E5-2673 v3 2.40GHz主板HUANANZHI X99-P4T&#xff08;P55 芯片组&#xff09;显卡NVIDIA GeForce GT 610 ( 2…

负载均衡和反向代理区别和nginx负载均衡模块

目录 负载均衡和反向代理区别 相似之处&#xff1a; 区别&#xff1a; 负载均衡和反向代理使用什么服务 nginx的负载均衡模块 ​编辑 负载均衡和反向代理区别 相似之处&#xff1a; 请求分发&#xff1a;两者都可以将客户端的请求分发到多个后端服务器&#xff0c;以提…

【AI绘画】Midjourney进阶:留白构图详解

博客主页&#xff1a; [小ᶻZ࿆] 本文专栏: AI绘画 | Midjourney 文章目录 &#x1f4af;前言&#x1f4af;什么是构图为什么Midjourney要使用构图 &#x1f4af;留白构图特点使用场景提示词书写技巧测试 &#x1f4af;小结 &#x1f4af;前言 【AI绘画】Midjourney进阶&…

Java后端面试题:JVM篇

目录 1. 什么是JVM&#xff1f; 2. 请你介绍JVM的整体结构 3. 了解过字节码文件的组成吗&#xff1f; 4. 说一下运行时数据区&#xff08;介绍一下JVM内存模型&#xff09;。 5. 哪些区域会出现内存溢出&#xff0c;会有什么现象&#xff1f; 6. 请你说说类的生命周期。 …

AD9361 的 TX 输出中添加前置放大器,并在 RX 输入中添加 LNA。

AD9361 的 TX 输出中添加前置放大器&#xff0c;并在 RX 输入中添加 LNA。 https://www.analog.com/en/resources/evaluation-hardware-and-software/evaluation-boards-kits/AD-TRXBOOST1-EBZ.html https://wiki.analog.com/resources/eval/user-guides/ad-trxboost1-ebz/in…

QT--文本框 QLineEdit、qtextedit

在Qt中&#xff0c;文本框&#xff08;QLineEdit 或 QTextEdit&#xff09;和标签&#xff08;QLabel&#xff09;是两种不同的部件&#xff08;widget&#xff09;&#xff0c;它们的主要区别在于用途和功能&#xff1a; QLabel&#xff08;标签&#xff09; 用途&#xff1…

PythonExcel批量pingIP地址

问题&#xff1a; 作为一个电气工程师&#xff08;PLC&#xff09;&#xff0c;当设备掉线的时候&#xff0c;需要用ping工具来检查网线物理层是否可靠连接&#xff0c;当项目体量过大时&#xff0c;就不能一个手动输入命令了。 解决方案一&#xff1a; 使用CMD命令 for /L %…

算法.图论-BFS及其拓展

文章目录 广度优先搜索简介经典bfs习题地图分析贴纸拼词 01bfs解析基本过程相关习题 广度优先搜索简介 bfs的特点是逐层扩散, 从源头到目标点扩散了几层, 最短路就是多少 bfs的使用特征是任意两个节点的距离(权值)是相同的(无向图, 矩阵天然满足这一特点) bfs开始的时候可以是…

树莓派应用--AI项目实战篇来啦-10.OpenCV进行车牌检测

1. 介绍 本项目使用 esseract、OpenCV和Python探索光学字符识别&#xff08;OCR&#xff09;的神奇世界&#xff0c;本项目将 带你了解最受欢迎的OCR引擎 Tesseract 背后的技术&#xff0c;以及如何用 Pytesseract 和 OpenCV实现字符识别。 从图像中检测字符的技术称为…

图(Java语言实现)

一、图的概念 顶点&#xff08;Vertex&#xff09;&#xff1a;图中的数据元素&#xff0c;我们称之为顶点&#xff0c;图至少有一个顶点&#xff08;非空有穷集合&#xff09;。 边&#xff08;Edge&#xff09;&#xff1a;顶点之间的关系用边表示。 1.图&#xff08;Graph…

Python Django 数据库优化与性能调优

Python Django 数据库优化与性能调优 Django 是一个非常流行的 Python Web 框架&#xff0c;它的 ORM&#xff08;对象关系映射&#xff09;允许开发者以简单且直观的方式操作数据库。然而&#xff0c;随着数据量的增长&#xff0c;数据库操作的效率可能会成为瓶颈&#xff0c…

如何在Ubuntu上更改MySQL数据存储路径

文章目录 0 背景1 备份现有数据库数据2 停止 MySQL 服务3 复制现有的 MySQL 数据到新目录4 修改 MySQL 配置文件5 更新 AppArmor 或 SELinux 配置&#xff08;如有启用&#xff09;6. 修改 MySQL 系统文件中的 datadir7. 启动 MySQL 服务8. 验证更改参考资料 0 背景 在原先划分…

股市入门常见术语介绍

鉴于最近行情讨论火热&#xff0c;我也想借此平台&#xff0c;结合我大学时期身边同学老师的投资经历&#xff0c;写一篇交易入门术语简介。内容不多但是足以达到科普之用。 ​ 希望大家能谨慎对待投资&#xff0c;始终保持谦虚学习的态度。不要迷失在瞬息万变的金融市场&…

webstorm 编辑器配置及配置迁移

1.下载地址 WebStorm&#xff1a;JetBrains 出品的 JavaScript 和 TypeScript IDE 其他版本下载地址 2.安装 点击下一步安装&#xff0c;可根据需要是否删除已有版本 注意&#xff1a; 完成安装后需要激活 3.设置快捷键 以下为个人常用可跳过或根据需要设置 如&#xff1a…

满级抗摔续航王者,荣耀X60系列发布,起步价仅1199元

10月16日&#xff0c;荣耀X60系列暨荣耀平板新品发布会正式举办&#xff0c;荣耀X60 Pro、荣耀X60以及荣耀平板GT Pro、荣耀亲选耳机LCHSE X7e、荣耀亲选WhizKid儿童手表2 Pro等新品悉数亮相。其中&#xff0c;荣耀X60 Pro首次搭载6600mAh最大青海湖电池、绿洲护眼屏、双向北斗…

pta-7-6 学生类设计

题目要求&#xff1a; 设计一个类Student&#xff0c;并在Main类中生成Student类对象进行测试 1.对于Student类&#xff0c;设计私有属性name和age&#xff0c;并为每一个成员变量name和age设计其setXXX&#xff08;&#xff09;和getXXX&#xff08;&#xff09;方法,并对于s…

GPT-SOVIT模型部署指南

一、模型介绍 强大的小样本语音转换和文本转语音 WebUI。 具有以下特征&#xff1a; 零样本 TTS&#xff1a; 输入 5 秒的声音样本并体验即时文本到语音的转换。少量样本 TTS&#xff1a; 仅使用 1 分钟的训练数据对模型进行微调&#xff0c;以提高语音相似度和真实感。跨语…

【Oracle数据库进阶】001.SQL基础查询_查询语句

课 程 推 荐我 的 个 人 主 页&#xff1a;&#x1f449;&#x1f449; 失心疯的个人主页 &#x1f448;&#x1f448;入 门 教 程 推 荐 &#xff1a;&#x1f449;&#x1f449; Python零基础入门教程合集 &#x1f448;&#x1f448;虚 拟 环 境 搭 建 &#xff1a;&#x1…