普林斯顿公开课 算法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)


相关推荐

  • ZigBee协议栈简介

    ZigBee协议栈简介文章目录Zigbee协议栈简介如何理解Zigbee协议栈如何使用Zigbee协议栈Zigbee协议栈简介  Zigbee协议分为2部分:IEEE802.15.4定义了PHY(物理层)和MAC(介质访问层)技术规范。Zigbee联盟定义了NWK(网络层)、APS(应用程序支持层)、APL(应用层)技术规范。  Zigbee协议栈就是将各个层定义的协议都集合在一起,以函数的形式实现,并给用户提供API,用户可以直接调用。如何理解Zigbee协议栈  TI推出的ZigBee2007协议栈也

  • odoo环境搭建_apache web服务器

    odoo环境搭建_apache web服务器1.新建用户1.1新建只能在控制台下登录的用户1)切换为root用户为了获取创建用户的权限peng@ubuntu:~$sudosu2)添加一个新用户(如用户名为csdn)root@ubuntu:/home/peng#useraddcsdn3)为该用户设定登录密码root@ubuntu:/home/peng#passwdcsdn4)为该用户指定命令解释程序(通常为/bin/b…

    2022年10月24日
  • idea导入springboot源码

    idea导入springboot源码两天啊,导入了两天没有成功啊,网上搜了超级多的教程,没有用啊。而后我让领导帮我试试,领导从github直接下载源码包,然后通过idea的open导入,然后idea就自动下载jar包,然后,然后就好了!!!我人傻了。下载的是2.2.X,因为我本地用的是maven,所以在2.2.9.release版本之后用的都是gradle构建项目的。后来发现,是我自作聪明了。原来,maven默认配置文件在C盘,我当时装的时候移到D盘,然后导入源码的时候怎么都识别不了,目前具体原因还没有找到,但是我把maven的配置

  • gateway网关详解_网关怎么设置才能上网

    gateway网关详解_网关怎么设置才能上网本文介绍了微服务中Gateway的使用,正在学习Gateway或者准备学习的大佬看过来哟

    2022年10月11日
  • [技术干货]高并发下如何保证接口的幂等性?

    [技术干货]高并发下如何保证接口的幂等性?

  • 【Java】爬虫,看完还爬不下来打我电话[通俗易懂]

    前言防砸声明:此文仅仅能保证入门,不保证商业生产。最终实现效果:爬虫简介:引用钱洋博士课程的部分内容(有删改):网络爬虫技术,有效的获取网络数据资源的重要方式。简单的理解,比如您对百度贴吧的一个帖子内容特别感兴趣,而帖子的回复却有1000多页,这时采用逐条复制的方法便不可行。而采用网络爬虫便可以很轻松地采集到该帖子下的所有内容。网络爬虫的作用,我总结为以下几点:舆情分析:企业或…

发表回复

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

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