【算法设计与分析】如何分析一个算法

2023-05-16

说明：参考书目为《Computer Algorithms --- Introduction to Design and Analysis》（第三版）Sara Baase, Allen Van Gelder

部分内容参考自大工林晓惠老师的课程【算法设计与分析】讲解。林老师讲算法非常细致，让人很容易理解，推荐一波~

（如部分内容涉及侵权，请联系我删除，谢谢）

该系列文章关于算法主要包含两部分：算法设计（分治、动态规划、贪心、图算法...） + 算法分析（算法的时间和空间分析、问题本身的计算复杂性、算法的正确性证明、NP-complete问题：对策论、数学归纳法等）

如何分析一个算法？

之后的文章请见：

【算法设计与分析】4.2 插入排序

【算法设计与分析】(习题4.2-4.5) 冒泡排序

本篇文章目录

算法评价的准则

1. 正确性

2. 时间

3. 空间

4. 简单性、清晰性

5. 优化

算法评价的准则：

1. 正确性

证明对于每一个合法的输入，该算法都会在有限的时间内得到满足要求的输出。

包括证明与该算法有关的引理、定理、公式。(一般使用数学归纳法证明)

2. 时间

1）主要影响算法时间效率的因素：①算法本身选用的策略；②问题的规模

在做时间效率分析时，我们从算法中选择出“基本操作”，以该“基本操作”的重复执行次数作为算法的时间量度f(n)。

比如：

问题	基本操作
在数组中查找x	x与数组元素进行比较
两个矩阵相乘	两个数值相乘

2）一般要进行平均A(n)和最坏W(n)情况下的时间复杂度分析：

$W(n)=max\left \{ f(I)\left | I\epsilon D_{n}\right \}$

$A(n)=\sum_{I}pr(I)f(I)$ pr(I)指的是相应情况的概率

3）时间复杂度 $\Theta$ 及其上界O、下界 $\Omega$ ：

①时间复杂度的上界O(g(n))=f(n) → 存在正数c和 $n_{0}$ ，使得对一切 $n\geq n_{0}$ ，有 $0\leq f(n)\leq cg(n)$

②时间复杂度的下界 $\Omega (g(n))=f(n)$ → 存在正数c和 $n_{0}$ ，使得对一切 $n\geq n_{0}$ ，有 $0\leq cg(n)\leq f(n)$

③时间复杂度 $\Theta (g(n))=f(n)$ → 存在正数 $c_{1}$ ， $c_{2}$ 和 $n_{0}$ ，使得对一切 $n\geq n_{0}$ ，有 $0\leq c_{1}g(n)\leq f(n)\leq c_{2}g(n)$

即， $f(n)=O(g(n)), f(n)=\Omega (g(n)),\Theta (g)=O(g)\bigcap \Omega(g)$

4）常见的时间复杂度函数

3. 空间

4. 简单性、清晰性

5. 优化

如果问题的计算时间下界是 $\Omega(f(n))$ ，则计算时间复杂度为 $O(f(n))$ 的算法是最优算法。例如，基于“比较”操作完成的排序问题的计算时间下界为 $\Omega(nlogn)$ ，则时间复杂度为 $O(nlogn)$ 的排序算法是最优算法。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

【算法设计与分析】如何分析一个算法的相关文章

【解决】client does not support authentication转载的两种解法

碰到这个问题一直难以解决 xff0c 直到我看到了以下两位博主的博客非常的有用第一位采用CMD cmd 窗口登陆mysql xff1a C Users Administrator gt sqlplus nolog mysql gt co
MATLAB实现传递函数模型、零极点模型和状态空间模型的建立与转换（1）

1 传递函数模型的建立 xff1a tf 1 1 格式 xff1a G 61 tf num den xff0c num和den分别代表分子分母的零极点输出为连续时间传递函数模型注 xff1a 工作区的模型G对应 1 1 tf 表示G为单
MATLAB中subs函数

subs函数 1 将变量x替换为数值1 xff1a subs S x 1 2 将变量x替换为变量z xff1a subs S x z 3 同时将变量x和y分别替换为1和z xff1a subs S x y 1 z 4 将单变量替换为数组 x
LQR线性二次型调节器3（Discrete-time system Linear-Quadratic Regulator design，离散系统分析及MATALB实例）

离散系统线性二次型调节器 xff0c dlqr函数 xff0c dare函数一离散时间系统二次型优化 xff1a dlqr 函数1 1 MATLAB函数形式1 2 举例 xff1a 二离散时间系统李卡提方程求解函数 xff1a dar
彻头彻尾理解JVM系列之八：Java代码是如何被CPU狂飙起来的？

大家好我是慕枫前阿里巴巴高级工程师 InfoQ签约作者阿里云专家博主一直致力于用大白话讲解技术知识在这里和大家分享一线互联网大厂面试经验技术人成长路线以及Java技术分布式高并发架构设计方面的经验总结感恩遇见希望我们都
最优控制理论（一）基本概念

1 概念在军事航空航天导航制导生产经济活动以及人类其他有目的的活动中 xff0c 常需要对被控系统被控过程施加某种控制作用 xff0c 使某个性能指标达到最优 xff0c 这种控制作用称为最优控制使控制系统的性能指标实现最优化
ROS学习笔记--cv_bridge

cv bridge是在ROS图像消息和OpenCV图像之间进行转换的一个功能包一 xff09 在ROS图像和OpenCV图像之间转换 xff08 C 43 43 xff09 xff11 xff0e Concepts xff08 概念 xf
stm32+esp8266+onenet （MQTT）

使用stm32采集温湿度 MQ2的数值用过 esp8266 43 mqtT协议把数据传输给onenet平台并且能通过onenet下发指令控制led灯的亮灭打开onenet平台 xff0c 使用旧版MQTT协议 xff0c 选择多协议接入
Hadoop The Definitive Guide：Hadoop权威指南-PART 1

简介 xff1a Hadoop起源于Nutch 当人们试图构建一个开源网络搜索引擎 xff0c 但在管理在少数计算机上运行的计算时遇到了麻烦后来Google发表了GFS和MapReduce相关介绍 xff0c 路线就变得清晰了他们设计了
【计算机图形学】绘制一个基于GDI的图形程序

这学期选修了计算机图形学这门课 xff0c 该合集用来记录课程所学知识概念类的内容来自于百度文库 xff1a https wenku baidu com view c3c5b36048d7c1c708a145a2 html 概念介绍 GD
Ubuntu 18.04 安装无人机开发环境 PX4+ROS+Gazebo

Ubuntu 18 04 安装无人机开发环境 PX4 43 ROS 43 Gazebo 本教程基于纯净的Ubuntu 18 04 配置上述环境由于国内网络环境问题 xff0c 无法正常从github下载文件的请用代理代理网站 xff1a
docker命令详解及参数作用

下载镜像 docker pull 镜像名标签查看本地镜像 docker images 删除镜像 xff1a docker rmi 镜像名标签启动容器 docker run d name 61 mynginx resrart 61 a
Mac sourcetree连接gitee码云仓库

一复制自己的ssh key 添加到gitee的ssh 共钥中二添加后 xff0c 在终端输入 ssh T git 64 gitee com gt gt 出现下面的successfully就代表关联成功了三 sourcetree中选择
路径规划与避障算法(一)---DWA算法概述

版权声明 xff1a 本文为博主原创文章 xff0c 转载请联系博主 https mp csdn net mdeditor 82764989 DWA 动态窗口算法算法概述算法原理可见 https blog csdn net heyiji
路径规划与避障算法(七)---DWA算法流程之三---碰撞检测评价函数

版权声明 xff1a 本文为博主原创文章 xff0c 原创不易转载请联系博主本篇博客主要介绍DWA算法所采用的评价函数中障碍物相关的评价函数评价函数轨迹主要依据以下三条准则进行评分综合评分后选取分数最小的路径作为下一时刻选择路径
彻头彻尾理解JVM系列之九：不会JVM调优怎么进互联网大厂

大家好我是慕枫前阿里巴巴高级工程师 InfoQ签约作者阿里云专家博主一直致力于用大白话讲解技术知识在这里和大家分享一线互联网大厂面试经验技术人成长路线以及Java技术分布式高并发架构设计方面的经验总结感恩遇见希望我们都
CVPR代码和论文链接目录大全

最新 xff01 CVPR 2021 语义分割论文大盘点 xff08 39篇论文 xff09 xff1a https blog csdn net amusi1994 article details 118426626 CVPR代码和论文链接
Ubuntu 桌面被删除，恢复

step1 在桌面上打开终端 xff0c cd 到自己的home文件夹 step2 ls la 出现隐藏的文件及文件夹 step3 找到 config文件夹中的user dirs dirs 如图图是找的图片将最后vim user dir
在Linux中编译带有自己编写的头文件的C程序

有三个文件callback c xff0c callback h xff0c demo c 其中callback h是自己编写的头文件在Linux中编译运行demo c的时候注意也要编译callback c文件 xff0c 否则会报错引
Anaconda和TensorFlow开发环境搭建

参考链接 xff08 MOOC大学深度学习应用开发 TensorFlow实践第二讲 xff09 xff1a https www icourse163 org course ZUCC 1206146808 一 Anaconda下载官网下

随机推荐

【wxPython导入失败】Failed building wheel for wxPython

导入包wxPython失败 xff1a Failed building wheel for wxPython 错误原因 xff1a 根据错误提示发现我的电脑上有两个版本的Python xff0c 一个是最开始学Pyhton的时候装的3 7版
【PEP 484】什么是.pyi文件？

在PyCharm中查看源代码的时候 xff0c 发现有些代码行有星号标识 xff0c 鼠标移上去会提示在某个 pyi文件中有其存根程序 xff0c 点击星号会跳转到对应的存根程序处那什么是存根程序呢 xff1f 我第一次看到这个概念是在
【timeout error】导入手写体识别数据(MNIST)超时

问题起因 xff1a 想要用TensorFlow做手写体识别 xff0c 在导入数据的时候出现了超时的问题解决方法 xff1a C Users Desny Anaconda3 pkgs tensorflow 1 2 1 py35 0 Li
【深度学习】如何计算AP（平均精度）和mAP（平均精度均值）？

起因 xff1a 最近导师给买了本书 xff0c 叫做智能计算系统 xff08 陈云霁等人编著 xff09 xff0c 让我上b站看看教材对应的视频不得不说这书写的确实不错 xff0c b站上的视频讲的也还可以书和视频的内容可以相互补
【TensorBoard】进入TensorBoard方法

1 打开Anaconda Prompt xff0c 切换目录必须切换到 log 文件夹所在的盘 xff0c 也可以进一步切换到 log 文件夹的位置 xff08 注 xff1a 如果没有切换到 log所在的盘 xff0c 比如 log放在
C/C++ strtok()是线程不安全

最近发生一题 xff0c 通过使用hwasan发现了一个问题 xff0c 指示代码使用了非法内存通过代码和dump一直查不到原因 xff0c 问题指示的是使用的内存被释放了函数传入参数后 xff0c 马上使用按asprinf copy了
解决TensorFlow指定版本升级的一系列问题

起因 xff1a 跟着MOOC学习的时候 xff0c 为了和课件配套下载1 2 1版本的tensorflow xff0c 现在讲到tensorflow中的keras包 xff0c 需要将tensorflow升级到1 10版本最终解决方法
【UnicodeEncodeError】导入pb模型文件失败

起因 xff1a 昨天想要导入pb模型文件 xff0c 结果发生了两次这样的错误一开始看错误提示以为真的是编码有问题 xff0c 后来发现都是文件路径文件名有错误才会出现此类问题解决方法 xff1a 注意文件名或路径是否有误错误举例
【浏览器】解决火狐和Chrome上不了网，只有IE能上网的问题

问题描述 xff1a 一早上打开电脑登陆浏览器的时候发现Chrome提示我您被禁止访问互联网然后我下载了火狐发现也是无法访问在网上找了一些方法 xff0c 发现根本不是什么局域网设置的问题 xff0c 也不是防火墙的问题 xff0c
【OptionParser】处理命令行参数

OptionParser的意义用来接收用户在命令行敲入的参数 xff0c 并解析这些参数下面用一段简单的代码举个例子 xff1a from optparse import OptionParser import sys op 61 Op
【论文复现】ECO_Efficient Convolutional Network for Online Video Understandin

论文链接 xff1a https arxiv org abs 1804 09066 代码链接 xff1a https github com mzolfaghari ECO pytorch 该篇论文是百度paddlepaddle线上训练营推荐
使用PaddlePaddle复现论文的心得

参加了百度顶会论文训练营 xff0c 目前已经实际完成了ECO论文主要网络结构的搭建和运行我实现该论文的水平非常粗糙 xff0c 我认为是达不到复现这样一个比较高的级别的 xff0c 但是可以对想要用paddlepaddle做论文复现的人
【Visual Studio】运行Node.js报错：“在计算机上找不到Node.js运行时”

一开始安装Visual Studio时没有选择安装Web相关的组件 xff0c 选择用Visual Studio Installer添加Node相关组件 xff0c 然后运行相关的代码报错 xff08 如图 xff09 xff1a 解决方法
【go get】下载的包放在哪里了？

我们在go文件import一些来自github gitlab等的包时 xff0c 一般在cmd命令行中敲击如下命令即可 xff1a go get github com go sql driver mysql 引入mysql的包可是这些包下
【go get】如何用ssh key下载gitlab的私有代码？

我参考了以下这篇文章 xff1a https mshk top 2019 01 go get gitlab https go get本身就是用git实现的 xff0c 所以如果你已经用git配置好对应gitlab的ssh密钥 xff0c 那
Docker在win10系统环境的安装过程

xff08 大部分内容参考菜鸟教程 gt https www runoob com docker windows docker install html xff09 1 开启Hyper V 在系统图标上右键 xff0c 选择应用和功能
安装Ubuntu 14.10后要做的事(下)—— 开发工具篇

1 完善GCC环境安装g 43 43 编译器命令 xff1a sudo apt get install build essential build essential是一套完整的软件包 xff0c 它提供了编译程序必需的软件包列表信息
家庭版windows没有Hyper-V的解决办法

本文转载自http www win7999 com news 332510800 html 1 将如下代码添加到记事本中 xff0c 并另存为Hyper V cmd文件代码如下 xff1a pushd 34 dp0 34 dir b Sy
用U盘安装ubuntu系统

1 我用的是MSI的主机 xff0c 首先在开机后按Delete键进入BIOS系统界面将U盘优先级用鼠标拖拽到第一位 xff0c 这样主机上插着装了系统的U盘时再开机就会跳出如下界面 xff0c 选择Install Ubuntu xff1
【算法设计与分析】如何分析一个算法

说明 xff1a 参考书目为 Computer Algorithms Introduction to Design and Analysis xff08 第三版 xff09 Sara Baase Allen Van Gelder 部分内容参

热门标签