算法——A/算法通识

目录

一、复杂度分析

A/时间复杂度

B/空间复杂度

C/分析技巧

二、枚举分析

A/枚举算法介绍

B/解空间的类型

C/循环枚举解空间

三、模拟算法

四、递归

A/递归介绍

递归的两个关键要素:

B/递归如何实现

C/递归和循环的比较


一、复杂度分析

A/时间复杂度

1、时间复杂度是衡量算法执行时间随输入规模增长的增率;

2、通过分析算法中基本操作的执行次数来确定时间复杂度;

3、常见的时间复杂度包括:常数时间 O(1)、线性时间 O(n)、对数时间 O(log n)、平方时间O(n^2)等。

4、在计算的时候我们关注的是复杂度的数量级,并不要求严格的表达式。

        一般我们关注的是最坏时间复杂度,用O(f(n))表示,大多数时候我们仅需估算即可。评测机1秒大约可以跑2e8(2*10的8次方)次运算,我们要尽可能地让我们的程序运算规模的数量级控制在1e8以内。

B/空间复杂度

1、空间复杂度是衡量算法执行过程中所需的存储空间随输入规模增长的增长率。

2、通过分析算法中所使用的额外存储空间的大小来确定空间复杂度。

3、常见的空间复杂度包括:常数空间 O(1)、线性空间O (n)、对数空间 O(log n)、平方空间 (n^2)等。
        一般我们关注的是最坏空间复杂度,用O(f(n))表示,大多数时候程序占用的空间一般可以根据开出的数组大小精确算出,但也存在需要估算的情况。题目一般不会卡空间,一般是卡时间。

C/分析技巧

1、理解基本操作:基本操作可以是算术运算(加法、乘法、位运算等)、比较操作、赋值操作等。

2、关注循环结构:循环是算法中常见的结构,它的执行次数对子时间复杂度的分析至关重要。

3、递归算法:递归算法的时间和空间复杂度分析相对复杂。需要确定递归的深度以及每个递
归调用的时间和空间开销。

4、最坏情况分析:对于时间复杂度的分析通常考虑最坏情况下的执行时间。要考虑输入数据使得算法执行时间达到最大值的情况。

5、善用结论:某些常见算法的时间和空间复杂度已经被广泛研究和证明。可以利用这些已知结果来分析算法的复杂度。

二、枚举分析

A/枚举算法介绍

        枚举算法是一种基本的算法思想,它通过穷举所有可能的情况来解决问题。它的基本思想是并进行验证和比较,找到满足问题条件的最将问题的解空间中的每个可能的解都枚举出来,优解或者所有解
        枚举算法适用于问题规模较小、解空间可穷举的情况。它的优点是简单直观,不需要复杂的数学推导,易于实现。但是,由于需要穷举所有可能的情况,对于问题规模较大的情况,枚举算法的时间复杂度可能会非常高,效率较低。

B/解空间的类型

        解空间可以是一个范围内的所有数字(或二元组、字符串等数据),或者满足某个条件的所有数字。
        当然也可以是解空间树,一般可分为子集树和排列树,针对解空间树,需要使用回溯法进行枚举(搜索的时候会讲到)。
我们目前仅使用循环去暴力枚举解空间,具体的解空间类型需要根据题目来理解构造。

C/循环枚举解空间

1、首先确定解空间的维度,即问题中需要枚举的变量个数。

        例如当题目要求的是满足条件的数字时,我们可以循环枚举某个范围内的数字。如果要求的是满足条件的二元组,我们可以用双重循环分别枚举第一个和第二个变量,从而构造出一个二元组。

2、对于每个变量,确定其可能的取值范围。这些范围可以根据问题的性质和约束条件来确定。这一步往往是时间复杂度优化的关键

3、在循环体内,针对每个可能解进行处理可以进行问题的验证、计算、输出等操作。

三、模拟算法

        模拟算法通过模拟实际情况来解决问题,一般容易理解但是实现起来比较复杂,有很多需要注意的细节,或者是一些所谓很“ 麻烦 ”的东西。

        模拟题一般不涉及太难的算法,一般就是由较多简单且不好处理的部分组成的,考察选手的细心程度和整体的逻辑思维。

        一般为了使得模拟题写的逻辑清晰一些,经常会写比较多的小函数来帮助解题,例如 int 和 string 的相互转换、回文串的判断、日期的转换、各种特殊条件的判断等等。

四、递归

A/递归介绍

        概念:递归是指函数直接或间接调用自身的过程。

递归的两个关键要素:

        a.基本情况(递归终止条件):递归函数中的一个条件,当满足该条件时,递归终止避免无限递归。可以理解为直接解决极小规模问题的发法

        b.递归表达式(递归调用):递归函数中的语句,用于解决规模更小的子问题,再将子问题的答案合并成为当前问题的答案。

B/递归如何实现

        过程:1.将大问题分解为规模更小的子问题;2.使用递归调用解决每个子问题;3.通过递归终止条件来结束递归。

        设计时需注意的细节:1.确保递归一定能到递归出口,避免无限递归,这可能导致TLE(超时)、MLE(超内存)或RE(运行错误);2.考虑边界条件,有时候递归出口不止一个;3.避免不必要的重复计算,尽可能优化递归函数的性能。

C/递归和循环的比较

递归的特点:

        1.直观、简洁,易于理解和实现;

        2.适用于问题的规模可以通过递归调用不断减小的情况;

        3.可以处理复杂的数据结构和算法,如树和图的遍历;

        4.存在栈溢出风险(栈空间一般只有8MB,所以递归层数不宜过深一般不超过1e6层)。

循环的特点:

        1.直接控制流程,效率较高;

        2.适用于问题的规模没有明显的缩减,或者需要特定的迭代次数;

        3.适合处理大部分的动态规划问题;在部分情况下,递归和循环可以相互转化。

前缀和

前缀和原理和特点

prefix表示前缀和,前缀和由一个用户输入的数组生成。对于一个数组a[ ](下标从1开始),我们定义一个前缀和数组prefix[ ]满足:prefix[i] = \sum_{j=1}^{i}a[j],prefix有一个重要的特性,可以用于快速生成prefix:prefix[i] = \sum_{j=1}^{i=1}a[j]+a[i]=prefix[i-1]+a[i]

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

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

相关文章

腾讯mini项目总结-指标监控服务重构

项目概述 本项目的背景是,当前企业内部使用的指标监控服务的方案的成本很高,无法符合用户的需求,于是需要调研并对比测试市面上比较热门的几款开源的监控方案(选择了通用的OpenTelemetry协议:Signoz,otel-…

grafana安装DevOpsProdigy KubeGraf 1.5.2

安装DevOpsProdigy KubeGraf需要安装kube-state-metrics 官方地址:https://github.com/kubernetes/kube-state-metrics/tree/release-2.10/examples/standard 查看k8s版本和kube-state-metrics对应版本: [rootmaster1 kube-state-metrics]# ll 总用量 …

Elasticsearch:Geoshape query

Geoshape 查询可以用于过滤使用 geo_shape 或 geo_point 类型索引的文档。 geo_shape 查询使用与 geo_shape 或 geo_point 映射相同的索引来查找具有与查询形状相关的形状的文档,并使用指定的空间关系:相交(intersect)、包含(con…

Linux 命令 —— top

Linux 命令 —— top 相对于 ps 是选取一个时间点的进程状态,top 则可以持续检测进程运行的状态。使用方式如下: 用法: top [-d secs] | [-p pid] 选项与参数: -d secs:整个进程界面更新 secs 秒。默认是 5 5 5 秒。…

Tomcat 部署项目时 war 和 war exploded区别

在 Tomcat 调试部署的时候,我们通常会看到有下面 2 个选项。 是选择war还是war exploded 这里首先看一下他们两个的区别: war 模式:将WEB工程以包的形式上传到服务器 ;war exploded 模式:将WEB工程以当前文件夹的位置…

安泰前置微小信号放大器工作原理是什么

前置微小信号放大器是电子电路中的一种重要组件,主要用于放大输入信号中的微小电压。这种放大器的工作原理涉及到电子器件的特性和基本电路理论。以下是前置微小信号放大器的工作原理的详细解释: 前置微小信号放大器通常用于增强输入信号,以便…

YOLOv8-Segment C++

YOLOv8-Segment C https://github.com/triple-Mu/YOLOv8-TensorRT 这张图像是运行yolov8-seg程序得到的结果图,首先是检测到了person、bus及skateboard(这个是检测错误,将鞋及其影子检测成了滑板,偶尔存在错误也属正常),然后用方…

2024/2/1学习记录

echarts 为柱条添加背景色: 若想设置折线图的点的样式,设置 series.itemStyle 指定填充颜色就好了,设置线的样式设置 lineStyle 就好了。 在折线图中倘若要设置空数据,用 - 表示即可,这对于其他系列的数据也是 适用的…

Git安装,Git镜像,Git已安装但无法使用解决经验

git下载地址&#xff1a; Git - 下载 (git-scm.com) <-git官方资源 Git for Windows (github.com) <-github资源 CNPM Binaries Mirror (npmmirror.com) <-阿里镜像&#xff08;推荐&#xff0c;镜…

vue使用antv-x6 绘制流程图DAG图(二)

代码&#xff1a; <template><div class"graph-wrap" click.stop"hideFn"><Toobar :graph"graph"></Toobar><!-- 小地图 --><div id"minimap" class"mini-map-container"></div>…

0202-1-处理机调度与死锁

第三章:处理机调度与死锁 处理机调度算法的目标 处理机调度算法的共同目标 资源利用率:CPU的利用率CPU有效工作时间/(CPU有效工作时间CPU空闲等待时间)公平性平衡性策略强制执行 批处理系统的目标 平均周转时间短系统吞吐量高处理机利用率高 分时系统的目标 响应时间快均…

帅气的性能监控平台Grafana(Windows下使用Grafana监控系统指标与GPU指标)

帅气的性能监控平台Grafana&#xff08;Windows下使用Grafana监控系统指标与GPU指标&#xff09; 前情提要 系统环境准备 windows_exporter下载 nvidia_gpu_exporter下载 prometheus下载 Grafana下载 安装指导 windows_exporter安装与nvidia_gpu_exporter安装 promethe…

Mac brew教程

一、安装brew /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"二、查看brew版本 brew -vbrew -v 三、搜索软件 命令格式&#xff1a;brew search 软件名 eg&#xff1a; brew search nginx四、安装软件 命令格…

布局技巧及CSS初始化

一&#xff0c;margin负值巧妙应用 二&#xff0c;文字围绕浮动元素 三&#xff0c;行内块 四&#xff0c;CSS三角强化 五&#xff0c;CSS初始化 一&#xff0c;margin负值巧妙应用 制作盒子的细线边框&#xff1a; 鼠标经过li后变色&#xff1a; 二&#xff0c;文字围绕…

遇到ubuntu设置交叉编译环境的问题

今天交叉编译器一直没安装成功&#xff0c;环境变量也配置了还是不对&#xff0c;最后发现Ubuntu是64位的要装 然后就好了 另外在进行嵌入式Linux开发的时候&#xff0c;要把主机、虚拟机、以及开发板设置在同一网段下&#xff0c;虚拟机一般设成临时的就可以&#xff0c;但是…

POI操作word表格,添加单元格,单元格对齐方法(不必合并单元格)

添加单元格&#xff0c;直接对row进行create新的cell&#xff0c;则会导致新创建的单元格与前面的单元格不对齐的现象。 //表格信息XWPFTable table doc.createTable();table.setWidth("100%");//第一行XWPFTableRow row0table.getRow(0);XWPFTableCell cell00row0.…

机器学习:多项式回归(Python)

多元线性回归闭式解&#xff1a; closed_form_sol.py import numpy as np import matplotlib.pyplot as pltclass LRClosedFormSol:def __init__(self, fit_interceptTrue, normalizeTrue):""":param fit_intercept: 是否训练bias:param normalize: 是否标准化…

无法在 word 中登录 Grammarly

目录 1. 情况描述 2. 解决方法 3. 原因分析 1. 情况描述 在浏览器中可以登录 Grammarly&#xff0c;但是在 word 中登录失败&#xff0c;大致如下图所示&#xff1a; 我自己没有截图&#xff0c;这是网上别人的图&#xff0c;但差不多都长这个样子。 2. 解决方法 我点击了…

AJAX-入门

定义 概念&#xff1a;AJAX是浏览器与服务器进行数据通信的技术 使用 1.先使用axios库&#xff0c;与服务器进行数据通信 1&#xff09;基于XMLHttpRequest封装、代码简单、月下载量在14亿次 2&#xff09;Vue、React项目中都会用到axios 2.再学习XMLHttpRequest对象的使用…

基于微服务的高考志愿智能辅助决策系统(附源码)

目录 一.引言 1、编写目的 2、系统功能概述 二.功能分析 三.微服务模块 1、微服务用户相关模块 &#xff08;1&#xff09;用户注册 &#xff08;2&#xff09;用户登录 &#xff08;3&#xff09;用户信息管理 &#xff08;4&#xff09;用户操作 2、微服务文件云存…