算法概论

简介: 打好牢固的基础,是成就高楼万丈的基石头。在学习算法之前,我们先了解算法是什么?如何设计算法?什么才是“好”算法?如何优化算法?

什么是算法?


算法是对特定问题求解步骤的一种描述,如果将问题看作函数,那么算法是把输入转化为输出


对特定问题求解步骤的一种描述,是为了解决一个或者一类问题给出的 一个确定的、有限长的操作序列。


算法的设计依赖于数据的存储结构,因此对确定的问题,应该需求最适宜的存储结构上设计出一种效率较高的算法


算法的特性:


有穷性:


对于任何一组合法的输入值,在执行有穷步骤之后一定能结束,即算法中的操作步骤为有限个,并且每个步骤都能在有限的时间内完成


确定性:


对于每种情况下所应该执行的路径的操作,在算法中都有确切的规定,使算法的执行者或阅读者都能明确其含义及如何执行;并且在确切的条件下只有唯一一条执行流程路径


可行性:


算法中的所有操作都必须足够基本,都可以通过已经实现的基本运算执行有限次实现


有输入:


作为算法加工对象的量值,通常体现为算法中的一组变量。有些输入量需要在算法的执行过程中输入,而有些算法表面上没有输入,但实际上已被嵌入算法之中


有输出:


它是一组与“输入”有确定关系的量值,是算法进行信息加工能够得到的结果。这种确定关系即为算法的功能


如何设计算法算法?


正确性:


算法应满足具体问题的需求,正确反映求解问题对输入、输出加工处理等方面的需求


  1. 程序中不含语法错误,计算的结果却不能满足规格说明要求。


  1. 程序对于特定的几组输入数据能够得出满足要求的结果,而对于其他的输入数据能够正确的计算结果;


  1. 程序对于精心选择的、经典、苛刻且带有刁难性的几组输入数据能够得到满足需求的结果;


(正确的算法)

  1. 程序对于一切合法的输入数据都能得出满足要求的结果


可读性:


算法处理用于编写程序在计算机上执行之外,另一个重要用处是阅读和交流。


算法中加入适当的注释,介绍算法的设计思路、各个模块的功能等一些必要性的说明文字来帮助读者理解算法。


要求:


算法中加入适当的注释,介绍算法的设计思路、各个模块的功能等一些必要性的说明文字来帮助读者理解算法


对算法中出现的各种自定义变量和类型能做到“见名知义”,即读者一看到某个变量(或类型名)就能知道其功能


健壮性:


当输入数据非法时,算法能够适当地做出反应或进行处理,输出表示错误性质的信息并终止执行,而不会产生莫名其妙的输出结果。


时间效率与存储占用量:


一般来说,求解同一个问题若有多种算法,则


执行时间短的算法效率高


占用存储空间少的算法较好


算法的执行时间开销和存储空间开销往往相互制约,对高时间效率和低存储占用的要求

只能根据问题的性质折中处理


什么才是“好”算法?


算法的时间复杂度:


算法的效率指的是算法的执行时间随问题“规模”(通常用整型量n表示)的增长而增长的趋势


“规模”在此指的是输入量的数目,比如在排序问题中,问题的规模可以是被排序的元素数目


假如随着问题规模n的增长,算法执行时间的增长率和问题规模的增长率相同则可记为:

T(n) = O(f(n))


f(n) 为问题规模n的某个函数;


T(n)被称为算法的(渐进)时间复杂度(Time Complexity)

O表示法不需要给出运行时间的精确值;


选择f(n),通常选择比较简单的函数形式,并忽略低次项和系数

常用的有O(1)、O(logn)、O(n)、O(nlogn)、O(n*n)等等


多项式时间复杂度的关系为:

O(1) < O(logn) < O(n) < O(N logn) < O(n²) < O(n³)


指数时间算法的关系为:

O(2(n方))< O(n!) <O(n(n方))


由于估算算法时间复杂度关心的只是算法执行时间的增长率而不是绝对时间,因此可以忽略一些因素。


方法:从算法中选取一种对于所研究的问题来说是“基本操作”的原操作,以该“基本操作”在算法中重复执行的次数作为算法时间复杂度的依据。


算法的空间复杂度:


算法在执行期间所需要的存储量包括:


  1. 程序代码所占用空间


  1. 输入数据所占用空间


  1. 辅助变量所占用的空间


如何评定一个程序算法的好坏?


简而言之:在符合算法设计标准的前提下,运行的更快、所用计算资源更少。即是更好的算法


为了降低复杂度,直观的思路是:梳理程序,看其流程中是否有无效的计算或者无效的存储。我们需要从时间复杂度和空间复杂度两个维度来考虑。


常用的降低时间复杂度的方法有递归、二分法、排序算法、动态规划,缓存算法等

降低空间复杂度的方法:就要围绕数据结构做文章了。


降低空间复杂度的核心思路就是,能用低复杂度的数据结构能解决问题,就千万不要用高复杂度的数据结构。


当然,时间与空间常常不可得兼,现实中一般更倾向时间。算法+数据结构 即可产生化学反应


探究算法优化


算法相对有优与劣?又该如何优化算法?


思路有:边界处理, 升维、时空转换


例如:我们要对n中最大的数,那么我们就需要把所有的数都判断一次。如果需要下次能够快速的找到,就需要排序。


边界处理:


在满足算法性质下,将无用的计算剔除。从而减少计算量,达到加速的效果


升维:


别人每次走一步,我们一次走两步或者三步。那么就可以更快


时空转换:


缓冲&缓存


例如:1 + 1 + 1 = 3为例子,为得到正确答案,方法是多种多样的。计算方面:三个1相加,2 + 1 或 1  + 2


简单的理解为:我记住”答案“,从而减少计算。


斐波那契数列求和为例:


一般有以下几种方式:(从暴力到优化)


  1. 一步一步计算


  1. 记住基础的答案


  1. 结论求解
目录
相关文章
|
存储 机器学习/深度学习 算法
数据结构与算法概论
数据结构与算法概论
106 0
|
11天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
13天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
100 1
|
12天前
|
传感器 机器学习/深度学习 算法
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
|
11天前
|
机器学习/深度学习 传感器 算法
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
102 14
|
14天前
|
传感器 算法 数据挖掘
基于协方差交叉(CI)的多传感器融合算法matlab仿真,对比单传感器和SCC融合
基于协方差交叉(CI)的多传感器融合算法,通过MATLAB仿真对比单传感器、SCC与CI融合在位置/速度估计误差(RMSE)及等概率椭圆上的性能。采用MATLAB2022A实现,结果表明CI融合在未知相关性下仍具鲁棒性,有效降低估计误差。
129 15
|
16天前
|
机器学习/深度学习 传感器 算法
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
|
16天前
|
算法 安全 BI
基于粒子群算法的多码头连续泊位分配优化研究(Matlab代码实现)
基于粒子群算法的多码头连续泊位分配优化研究(Matlab代码实现)
|
15天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于WOA鲸鱼优化的XGBoost序列预测算法matlab仿真
基于WOA优化XGBoost的序列预测算法,利用鲸鱼优化算法自动寻优超参数,提升预测精度。结合MATLAB实现,适用于金融、气象等领域,具有较强非线性拟合能力,实验结果表明该方法显著优于传统模型。(238字)
|
11天前
|
机器学习/深度学习 运维 算法
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)

热门文章

最新文章