普林斯顿公开课 算法1-5:算法理论

普林斯顿公开课 算法1-5:算法理论

本节主要解说的是算法的复杂度。

算法性能

算法的性能分为三种:

  • 最佳情况:计算时间最短的情况

  • 最差情况:计算时间最长的情况

  • 平均情况:随机输入的期望开销

以二分查找为例

最佳情况是1,由于第一次就有可能找到须要找的整数。

最差情况是logN

平均情况是logN

算法复杂度

算法复杂度用于定义问题的难度,另外也有助于开发最优化的算法,算法复杂度能够通过分析最坏情况来降低输入数据对算法性能的影响。

为了简化问题难度的表示方法,算法复杂度降低了算法分析的细节,忽略常数系数。

最优算法

所谓的最佳算法就是在不论什么情况下都能保证执行时间在理论范围内,并且没有更好的算法可以超越。

算法复杂度表示方法

常见的表示方法有比方O(N^2)表示算法最大可能的复杂度,Ω(N^2)表示最小可能的复杂度,Θ(N^2)表示算法复杂度的增长情况。

举例

问题描写叙述:推断一个数组中有多少个0。

以暴力方法为例。

这个问题中性能上限就是指某个特定的算法能实现的复杂度。

算法下限就是经过数学方法的证明,最优算法的复杂度是Ω(N)。由于数组中每一个元素都有可能是0,必需要循环整个数组才干得出结果。

最优算法:这个问题中暴力算法就是最优算法,所以最优算法的复杂度为Θ(N^2)。

算法的开发步骤

  1. 开发一个算法

  2. 证明最低下限

假设开发出的算法复杂度和证明得出的最低复杂度不相符的话,能够去寻找新的算法。也有可能是证明出错,当然证明出错的情况是比較少见的。

1970年代是算法设计的黄金年代。

误区

关于算法复杂度有下面误区:

  • 太在乎最坏情况。事实上实际应用中最坏情况基本上不会出现。

  • 试图通过提高复杂度的常数系数来提高性能。

  • 将大O当成近似复杂度,事实上真正的近似复杂度称之为波浪记法。



版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/119119.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 服务器CPU型号后缀的区别,CPU后缀英文简单科普知识,若能区别字母的含义,选购好CPU不求人…

    服务器CPU型号后缀的区别,CPU后缀英文简单科普知识,若能区别字母的含义,选购好CPU不求人…在组装电脑选购CPU时,很多人都会发现有不少的CPU名称后面,都会带有1个或2个英文字母。其实这些英文字母,都代表着每个CPU型号的不同特点。intel系列CPU最近又有网友咨询,CPU后面的英文字母有何意义,应该怎么样去区别字母的含义?小编今天就针对CPU后缀英文简单科普知识,若能区别字母的含义,选购好CPU不求人。011、intel系列CPU后缀英文的不同含义在intel系列CPU中,后缀带英…

  • android 磨皮原理,Android平台Camera实时滤镜实现方法探讨(九)–磨皮算法探讨(一)

    android 磨皮原理,Android平台Camera实时滤镜实现方法探讨(九)–磨皮算法探讨(一)上一篇开头提到了一些可用于磨皮的去噪算法,下面我们实现这些算法并且观察效果,咱不考虑实时性的问题该算法利用图像局部统计特性进行滤波处理,例如NXM像素的灰度图,首先计算点(i,j)所在窗口内(大小为(2n+1)(2m+1))的平均值m(i,j)以及均方差:得到加性去噪后的结果为:其中:1.根据原文提出的优化方法,首先是建立两个积分图,如图所示,点4的积分即为Sum(Ra)+Sum(Rb)+…

  • [LeetCode] Reverse Linked List II 倒置链表之二

    [LeetCode] Reverse Linked List II 倒置链表之二

  • 数据库概念结构设计_数据库概念结构设计怎么写

    数据库概念结构设计_数据库概念结构设计怎么写一、概念模型在需求分析阶段所得到的应用需求应该首先抽象为信息世界的结构,然后才能更改、更准确地用某一数据库管理系统实现这些需求。概念模型的主要特点:1.能真实、充分地反映现实世界,包括事物和事物之间的联系,能满足用户对数据的处理要求,是现实世界的一个真是模型。2.易于理解,可以用它和不熟悉计算机的用户交换意见。用户的积极参与是数据库设计成功的关键。3.易于更改,当应用环境和应用要求改变时容易对概念模型修改和扩充。4.易于向关系、网状、层次等各种数据模型转换…

    2022年10月12日
  • nginx前端跨域_nginx实现跨域

    nginx前端跨域_nginx实现跨域做前端开发的时候,使用nginx代理,如果我们当前的域名与请求接口的域名不在同一个域名下时,会有跨域问题打开nginx.conf文件打开Finder-前往-前往文件夹/usr/local/etc/nginx一般默认在这个目录下打开nginx.conf之后,增加一个location如下:location/test{prox…

  • shell中if elif_shell编程if语句格式

    shell中if elif_shell编程if语句格式测试shell脚本编程时,写了如下代码:在对if-elif-else分支进行数值判断时,发现一个奇怪的现象:如果使用testconditon(即[condition])进行判定,当第一条if条件为假时,无论代码中的elif语句条件是否为真,都输出elif分支下的语句;查看输出结果,发现输出结果显然与期望值不一样为了能够得到预期结果,发现如果采用双圆括号是进行判断,可得到预期结…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号