悟的复杂度分析
复杂度分析:
时间复杂度(算法中的基本操作的执行次数);
空间复杂度。
时间复杂度:
实际上我们计算时间复杂度时,我们其实并不需要计算准确的执行次数,只需要大概的执行次数,因此我们在这里使用大O的渐进表示法。常见的时间复杂度O(1), O(N²), O(N), O(logN)。
大O符号:
是用于描述函数渐进行为的数学符号。
推导大O阶方法:
1.用常数1取代运行时间中的所有加法常数;
例:
计算下面代码的时间复杂度
void f(int N)
{int count = 0;for(int k = 0; k < 100; ++k){++count;}
}
答案:O(1)
注:确定的常数次,都是O(1)。
2.在修改后的运行次数函数中,只保留最高阶项;
例:
计算下面代码的时间复杂度
void f(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;}printf("%d", count);
}
答案:O(N²)
注:准确的执行次数:N² + 2 * N + 10
随着N的增大,这个表达式中N²对结果的影响最大
3.若最高阶项存在且不是1,则去除与这个项相乘的常数。得到的结果就是大O阶。
例:
计算下面代码的时间复杂度
void f(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){count++;}int M = 10;while (M--){++count;}printf("%d", count);
}
答案:O(N)
特殊情况:
例一:
计算下面代码的时间复杂度
void f(int N, int M)
{int count = 0;for (int k = 0; k < N; k++){++count;}for (int k = 0; k < M; k++){++count;}
}
答案:O(M + N)
注:假如给了条件:M远大于N,答案是O(M);M和N差不多大,O(M)或O(N)。
例二:
计算下面代码的时间复杂度
const char* s(const char* str, char cha)
{while (*str != '\0'){if (*str == cha){return str;}++str;}return NULL;
}
假设字符串长度是N。
答案:O(N)
注:有些算法的时间复杂度存在最好,平均,最坏情况:
最坏:O(N)
平均:O(N/2)
最好:O(1)
在实际中一般情况关注的是算法的最坏运行情况。
例三:
计算下面代码的时间复杂度
void B(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){break;}}
}
答案:O(N²)
注:第一趟冒泡:N
第二趟冒泡:N - 1
........
第N趟:1
以上是个等差数列,所以准确的次数是(N+1)*N/2
时间复杂度为O(N²)
例四:
计算下面代码的时间复杂度
int B(int* a, int n, int x)
{assert(a);int begin = 0;int end = n;while (begin < end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x){begin = mid + 1;}else if (a[mid] > x){end = mid;}else{return mid;}}return - 1;
}
答案:O(logN)
注:假设找了X次
2的X的平方 = N
X=logN
因为有很多地方不好写底数,所以一般省略简写成logN。
例五:
计算下面代码的时间复杂度
long long f(size_t N)
{return N < 2 ? N : f(N - 1) * N;
}
答案:O(N²)
注:递归调用了N次,每次递归运算--》O(1)
整体就是O(N)。
相关文章:
悟的复杂度分析
复杂度分析: 时间复杂度(算法中的基本操作的执行次数); 空间复杂度。 时间复杂度: 实际上我们计算时间复杂度时,我们其实并不需要计算准确的执行次数,只需要大概的执行次数,因此我们…...
《网络是怎样连接的》2.5节图表(自用)
图5.1:ip包结构 图5.2:ip网络包的传输方式 1.以太网的部分也可以替换成其他的东西,例如无线局域网、ADSL、FTTH等,它们都可以替代以太网的角色帮助IP协议来传输网络包 2.根据ARP协议,客户端可以根据ip地址得到下一个路…...
java 音乐会售票平台系统Myeclipse开发mysql数据库struts2结构java编程计算机网页项目
一、源码特点 java 音乐会售票平台系统 是一套完善的web设计系统,对理解JSP java编程开发语言有帮助struts2框架开发mvc模式,系统具有完整的源代码和数据库,系统主要采用B/S模式开发。开发 环境为TOCAT7.0,Myeclipse8.5开发,数据…...
鸿蒙开发解决agconnect sdk not initialized. please call initialize()
文章目录 项目场景:问题描述原因分析:解决方案:总结:项目场景: 鸿蒙开发报错: agconnect sdk not initialized. please call initialize() 问题描述 报错内容为: 10-25 11:41:01.152 6076-16676 E A0c0d0/JSApp: app Log: 数据查询失败: {“code”:1100001,“messag…...
秋招阿里巴巴java笔试试题-精
一、单项选择题 1、以下函数的时间复杂度是 ( ) 1 2 3 4 5 6 7 8 9 void func(int x,int y, int z){ if(x<0) printf("%d, %d\n", y, z); else { func(x-1,y1,z); func(x-1,y,z1); } } A.O(x*y*z) B.O(x^2*y^2) C.O(2^x) D.O(2^x*…...
018、通用集合类型
Rust标准库包含了一系列非常有用的被称为集合的数据结构。大部分的数据结构都代表着某个特定的值,但集合却可以包含多个值。 与内置的数组与元组类型不同,这些集合将自己持有的数据存储在了堆上。这意味着数据的大小不需要在编译时确定,并且可…...
【Leetcode】236.二叉树的最近公共祖先
一、题目 1、题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 示例1…...
C#,入门教程(11)——枚举(Enum)的基础知识和高级应用
上一篇: C#,入门教程(10)——常量、变量与命名规则的基础知识https://blog.csdn.net/beijinghorn/article/details/123913570 不会枚举,就不会编程! 枚举 一个有组织的常量系列 比如:一个星期每一天的名字…...
java SSM水质历史数据可视化设计myeclipse开发mysql数据库springMVC模式java编程计算机网页设计
一、源码特点 java SSM水质历史数据可视化设计是一套完善的web设计系统(系统采用SSM框架进行设计开发,springspringMVCmybatis),对理解JSP java编程开发语言有帮助,系统具有完整的源代码和数据库,系统主…...
C++推箱子游戏开发
游戏 自动地图生成背景音乐推箱子到目标位置 美工资源 美工资源: 链接:https://pan.baidu.com/s/1MZv8pDBXdNDbXxuAAPSM-A **提取码:**2syq 图形库: www.easyx.cn cpp文件 #include "box_man.h" #include <conio.h> #…...
Kotlin函数式接口
函数式接口 接口只有一个抽象方法的接口,称为 函数式接口 functional interface,也叫做 Single Abstract Method(SAM) interface。 注:函数式接口,只有一个抽象方法,但可以有多个非抽象方法。 一、Kotlin Kotlin支持…...
2024年1月9日学习总结
目录 学习目标学习内容联邦学习基础:why, what, howwhy?what?how? 联邦学习的例子——CIFAR-10数据集(分类问题)1、import libararies2、hyper-parameters3、加载并且划分数据4、创建神经网络模型5、helper…...
Nacos使用MySQL8时区问题导致启动失败
文章目录 配置下mysql的时区方式一 (永久)方式二(临时) 由于mysql8需要配置时区,如果不配置时区,nacos就连不上mysql,从而也就无法登录nacos自带的图形化界面 配置下mysql的时区 方式一 (永久) 直接修改配置文件&…...
在k8s集群中部署多nginx-ingress
关于ingress的介绍,前面已经详细讲过了,参考ingress-nginx详解和部署方案。本案例ingress的部署使用deploymentLB的方式。 参考链接: 多个ingress部署 文章目录 1. 下载ingress的文件2. 文件资源分析3. 部署ingress3.1 部署第一套ingress3.1…...
SLF4J Spring Boot日志框架
JAVA日志框架 JAVA有好多优秀的日志框架,比如log4j、log4j2、logback、JUL(java.util.logging)、JCL(JAVA Common Logging)等等,logback是后起之秀,是Spring Boot默认日志框架。 今天文章的目…...
mysql之导入导出远程备份
文章目录 一、navicat导入导出二、mysqldump命令导入导出2.1导出2.1.1 导出表数据和表结构2.1.2 只导出表结构() 2.2 导入(使用mysqldump导入 包含t _log表的整个数据库 共耗时 20s;)方法一:方法二: 三、LOAD DATA INFILE命令导入导出(只针对单表)设置导…...
Java虚拟机ART 读书笔记 第2章 深入理解Class文件格式
GitHub - Omooo/Android-Notes: ✨✨✨这有一包小鱼干,确定不要吃嘛?( 逃 深入理解Android:Java虚拟机ART 读书笔记 以下内容均来自书中内容 建议看原书哦 第2章 深入理解Class文件格式 2.1 class文件总览 Class文件格式全貌 u4ÿ…...
编程基础 - 初识Linux
编程基础 - 初识Linux 返回序言及专栏目录 文章目录 编程基础 - 初识Linux前言一、Linux发展简介二、现代Linux三、Linux系统各发行版小结 前言 为什么要学习Linux呢?我这Windows用得好好的,简单易用傻瓜式、用的人还超多!但是我要告诉你的…...
c yuv422转yuv420p
思路: yuv422 存储格式为 y u y v y u y v y u y v y u y v yuv420p 存储最简单,先存所以的y,再存u,最后v 所以先把422所有的y存在一起,再提奇数行的u ,偶数行舍弃。提…...
计算机网络 - 路由器查表过程模拟 C++(2024)
1.题目描述 参考计算机网络教材 140 页 4.3 节内容,编程模拟路由器查找路由表的过程,用(目的地址 掩码 下一跳) 的 IP 路由表以及目的地址作为输入,为目的地址查找路由表,找出正确的下一跳并输出结果。 1.…...
实现pytorch版的mobileNetV1
mobileNet具体细节,在前面已做了分析记录:轻量化网络-MobileNet系列-CSDN博客 这里是根据网络结构,搭建模型,用于图像分类任务。 1. 网络结构和基本组件 2. 搭建组件 (1)普通的卷积组件:CBL …...
vue多tab页面全部关闭后自动退出登录
业务场景:主项目是用vue写的单页面应用,但是有多开页面的需求,现在需要在用户关闭了所有的浏览器标签页面后,自动退出登录。 思路:因为是不同的tab页面,我只能用localStorage来通信,新打开一个…...
记一个集群环境部署不完整导致的BUG
一 背景 产品有三个环境:开发测试环境、验收环境、生产环境。 开发测试环境,保持最新的更新; 验收环境,阶段待发布内容; 生产环境,部署稳定内容。 产品为BS架构,后端采用微服务…...
Go zero copy,复制文件
这里使用零拷贝技术复制文件,从内核态操作源文件和目标文件。避免了在用户态开辟缓冲区,然后从内核态复制文件到用户态的问题。 由内核态完成文件复制操作。 调用的是syscall.Sendfile系统调用函数。 //go:build linuxpackage zero_copyimport ("f…...
http协议九种请求方法介绍及常见状态码
http1.0定义了三种: GET: 向服务器获取资源,比如常见的查询请求POST: 向服务器提交数据而发送的请求Head: 和get类似,返回的响应中没有具体的内容,用于获取报头 http1.1定义了六种 PUT:一般是用于更新请求,…...
详解flink exactly-once和两阶段提交
以下是我们常见的三种 flink 处理语义: 最多一次(At-most-Once):用户的数据只会被处理一次,不管成功还是失败,不会重试也不会重发。 至少一次(At-least-Once):系统会保…...
Qt/QML编程学习之心得:QDbus实现service接口调用(28)
D-Bus协议用于进程间通讯的。 QString value = retrieveValue();QDBusPendingCall pcall = interface->asyncCall(QLatin1String("Process"), value);QDBusPendingCallWatcher *watcher = new QDBusPendingCallWatcher(pcall, this);QObject::connect(watcher, SI…...
前端nginx配置指南
前端项目发布后,有些接口需要在服务器配置反向代理,资源配置gzip压缩,配置跨域允许访问等 配置文件模块概览 配置示例 反向代理 反向代理是Nginx的核心功能之一,是指客户端发送请求到代理服务器,代理服务器再将请求…...
接口测试到底怎么做,5分钟时间看完这篇文章彻底搞清楚
01、通用的项目架构 02、什么是接口 接口:服务端程序对外提供的一种统一的访问方式,通常采用HTTP协议,通过不同的url,不同的请求类型(GET、POST),不同的参数,来执行不同的业务逻辑。…...
显示管理磁盘分区 fdisk
显示管理磁盘分区 fdisk fdisk是用于检查一个磁盘上分区信息最通用的命令。 fdisk可以显示分区信息及一些细节信息,比如文件系统类型等。 设备的名称通常是/dev/sda、/dev/sdb 等。 对于以前的设备有可能还存在设备名为 /dev/hd* (IDE)的设备,这个设…...
做网站 商标分类/疫情防控数据
Java工程开发师这个岗位炙手可热,市场需求多,学习Java的人也不少,所以IT企业与求职者的选择都比较多。那么IT企业在与应聘者面试时都会问到哪些问题呢,下面小编就为求职者们奉上大型IT企业必问的六个Java面试问题。 Java技术题&a…...
广州思盾互动网站建设公司/网址查询入口
最近几年的电商行业整体的流量趋势都在提升,各个平台争相竞争流量,买家数量是固定的,可跨多个平台选择,对于流量的收割,也不在局限于一二线城市,在这种情况下,店铺提高流量的收割效果࿰…...
视频涉台互联网网站怎么做/爱站网关键词怎么挖掘
本文包括正文内容 和 与正文相关的其他内容列举,并给出它们在aaas系统中的性质和定位.。 本文正文 本文的正文描述 AI的三次模型法:第一次必然是理事两边的数据模型,再一次可能是理事无碍的算法模型,最后一次真实的是统计模型。…...
dedecms导入网站模板下载/软件培训班
时常有“2G冲浪”的亲戚朋友拿着一些网络热梗来问我,最近常问的是,什么是“行走的50w”。简单来说,指的就是潜伏在国内的间谍。极化的网络环境下,这些词汇频繁出现,到了普通人也无法忽略的程度。“人人皆可50w”&#…...
wordpress 网址导航/怎么在百度上做广告推广
一、USB请求 在USB规范里,对命令一词提供的单词为“Request”,但这里为了更好的理解主机与设备之间的主从关系,将它定义成“命令”。 所有的USB设备都要求对主机发给自己的控制命令作出响应,USB规范定义了11个标准命令,…...
南宁网站设计多少钱/有没有推广app的平台
Package gp in the OpenCASCADE eryar163.com China 一、简介 Introduction to Package gp gp是几何处理程序包(Geometric Processor package),简称gp。包gp提供以下功能: 代数计算;如坐标计算、矩阵计算;…...