- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
复杂度分析本身是非常理论化的一个内容,在计算机科学中,有一个专门的学科叫做—— 计算复杂性理论 .
很多童鞋看过《算法导论》,这本书的内容很多很强调算法导论.
但是实际上,对于普通程序员来说, 不需要 过度强调理论化的内容 。因为工作中更多面对的是实际的 软件工程,工程化的工作不需要面对太多理论性的东东.
复杂度分析的作用:是为了表示算法的性能.
对于同样一个任务,可能有多个实现方式,即多个算法。这些不同的算法,它们的时间性能是否有差异呢?
我们虽然可以用一个测试用例,或者一组测试用例实际比较性能差异。 但是,这样的比较结果有局限性.
比如,需要保证运行不同算法的计算机硬件设备的性能一致,甚至深入的说,他们的OS当时的状态都需要是一致的。 这本身很难保证,而且测试结果也与我们的测试用例设计和用例输入相关.
而且,最重要的是这样比较是 事后的 .
如何突破局限性,如何事前比较呢? 种种这样的需求,都需要我们有一套工具,从数学的层面,用抽象的方式,判断一个算法的性能是怎样的?
为了回应这样的需求,就产生了复杂度分析这样一个概念.
复杂度分析,如何表示算法的性能呢?
需要注意的是,算法复杂度分析通常考虑最坏的情况.
这样的思想非常普遍,比如上班时,为了不迟到,考虑最长需要多少时间,甚至将堵车的时间都考虑进去.
即,复杂度分析,表示的是算法运行的上界.
对于我们的线性查找法代码,我们来进行一个复杂度分析吧,代码再一次贴出来:
public static <E> int search(E [] data,E target){
for (int i = 0; i < data.length; i++)
if (data[i].equals(target))
return i;
return -1;
}
具体的分析过程如下: n = data.length T 表示时间 T和n的关系到底是怎样的? T = n?n个元素全部扫描了一遍? 就是n? T = 2n?if里有比较、有返回结果这2步 就是2n? T = 3n? 其实if中的data[i],要在数组data中找到i这个元素,是一步寻址,也需要算作一个子步骤。 3n了? T = 4n?for循环中也包含每次要做的事情,i<data.length,也是一个判断操作,所以4n?
T = 5n?for循环中还有一个i++的操作,所以5n? T = 5n+2? int i =0;加1次,return -1;加1次,所T=5n+2? …… 。
其实,再继续分析下去还可以分析出很多可能,就不继续分析了,为什么不继续了呢?
因为真的分析的话,拿出for循环对应的汇编代码,看看这个循环执行了多少指令?
可是拿出汇编代码也不够,因为汇编代码对应着机器指令,而机器指令不仅仅是代码有多少行而已, 还要追溯到运行代码的CPU架构上,有些复杂指令在有些CPU上,就一个指令,但在另外一些CPU上,可能就是多个指令.
对于上层应用软件开发者来说,分析清楚每一行高级语言代码对应着多少机器指令,是一件非常困难,甚至说不可能的事情,其实也没有必要.
而且即便T=5n+2,那这个等式的时间单位是多少呢?是毫秒ms嘛?肯定不对应时间,对应的是指令数,但是一条指令在cpu中执行多久我们知道嘛?
我们不知道.
所以,这些其实我们都不需要考虑,我们需要进行一个化简。这也是计算机科学家们定义复杂度分析这个概念时做过的事儿,没错,他们做了化简.
我们不需要知道 执行这样一个循环,对这n个元素操作,每一次循环需要执行多少个指令; 我们只需要知道,整个算法和这个data数组的大小,和这个数据规模n成一个正比的关系即可.
这个就记作 O(n) ,表示的就是运行时间和数据规模n之间的一个正比关系。 进一步看,如果: T = c1*n + c2 这个算法我们就可以记作O(n),即常数c1、c2都被我们忽略掉了 ,即算法复杂度的世界中,常数不重要.
复杂度描述的是:随着数据规模的增大,算法性能的变化趋势.
假设有2个算法,分别是T1和T2,它们的详细情况如下:
T1 = 10000n T2 = 2n² 第一个算法 O(n)级别的算法,第二个算法O(n²)级别的算法。 从复杂度理论的角度来看,第一个算法优于第二个算法.
**因为总是会存在某一临界点n0,当n>n0,T1<T2。 可以计算出,这里的临界点n0为5000。 一旦数据规模大于5000,算法一的性能优势就体现出来了,而且n越大,体现的越明显.
所以O(n)描述的就是随着n的变化,算法的性能的变化趋势, 。
而不是说n取某个值时,算法的性能.
实际上,如果测试数据小于5000,比如为100时,第二个算法O(n²)反而优于第一个算法O(n); 。
但是评价算法性能,我们要看n逐渐上涨的情况, 甚至看n无穷大的情况 .
最后此篇关于扎实打牢数据结构算法根基,从此不怕算法面试系列之007week0102-07简单的复杂度分析的文章就讲到这里了,如果你想了解更多关于扎实打牢数据结构算法根基,从此不怕算法面试系列之007week0102-07简单的复杂度分析的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
初学者 android 问题。好的,我已经成功写入文件。例如。 //获取文件名 String filename = getResources().getString(R.string.filename
我已经将相同的图像保存到/data/data/mypackage/img/中,现在我想显示这个全屏,我曾尝试使用 ACTION_VIEW 来显示 android 标准程序,但它不是从/data/dat
我正在使用Xcode 9,Swift 4。 我正在尝试使用以下代码从URL在ImageView中显示图像: func getImageFromUrl(sourceUrl: String) -> UII
我的 Ubuntu 安装 genymotion 有问题。主要是我无法调试我的数据库,因为通过 eclipse 中的 DBMS 和 shell 中的 adb 我无法查看/data/文件夹的内容。没有显示
我正在尝试用 PHP 发布一些 JSON 数据。但是出了点问题。 这是我的 html -- {% for x in sets %}
我观察到两种方法的结果不同。为什么是这样?我知道 lm 上发生了什么,但无法弄清楚 tslm 上发生了什么。 > library(forecast) > set.seed(2) > tts lm(t
我不确定为什么会这样!我有一个由 spring data elasticsearch 和 spring data jpa 使用的类,但是当我尝试运行我的应用程序时出现错误。 Error creatin
在 this vega 图表,如果我下载并转换 flare-dependencies.json使用以下 jq 到 csv命令, jq -r '(map(keys) | add | unique) as
我正在提交一个项目,我必须在其中创建一个带有表的 mysql 数据库。一切都在我这边进行,所以我只想检查如何将我所有的压缩文件发送给使用不同计算机的人。基本上,我如何为另一台计算机创建我的数据库文件,
我有一个应用程序可以将文本文件写入内部存储。我想仔细看看我的电脑。 我运行了 Toast.makeText 来显示路径,它说:/数据/数据/我的包 但是当我转到 Android Studio 的 An
我喜欢使用 Genymotion 模拟器以如此出色的速度加载 Android。它有非常好的速度,但仍然有一些不稳定的性能。 如何从 Eclipse 中的文件资源管理器访问 Genymotion 模拟器
我需要更改 Silverlight 中文本框的格式。数据通过 MVVM 绑定(bind)。 例如,有一个 int 属性,我将 1 添加到 setter 中的值并调用 OnPropertyChanged
我想向 Youtube Data API 提出请求,但我不需要访问任何用户信息。我只想浏览公共(public)视频并根据搜索词显示视频。 我可以在未经授权的情况下这样做吗? 最佳答案 YouTube
我已经设置了一个 Twilio 应用程序,我想向人们发送更新,但我不想回复单个文本。我只是想让他们在有问题时打电话。我一切正常,但我想在发送文本时显示传入文本,以确保我不会错过任何问题。我正在使用 p
我有一个带有表单的网站(目前它是纯 HTML,但我们正在切换到 JQuery)。流程是这样的: 接受用户的输入 --- 5 个整数 通过 REST 调用网络服务 在服务器端运行一些计算...并生成一个
假设我们有一个名为 configuration.js 的文件,当我们查看内部时,我们会看到: 'use strict'; var profile = { "project": "%Projec
这部分是对 Previous Question 的扩展我的: 我现在可以从我的 CI Controller 成功返回 JSON 数据,它返回: {"results":[{"id":"1","Sourc
有什么有效的方法可以删除 ios 中 CBL 的所有文档存储?我对此有疑问,或者,如果有人知道如何从本质上使该应用程序像刚刚安装一样,那也会非常有帮助。我们正在努力确保我们的注销实际上将应用程序设置为
我有一个 Rails 应用程序,它与其他 Rails 应用程序通信以进行数据插入。我使用 jQuery $.post 方法进行数据插入。对于插入,我的其他 Rails 应用程序显示 200 OK。但在
我正在为服务于发布请求的 API 调用运行单元测试。我正在传递请求正文,并且必须将响应作为帐户数据返回。但我只收到断言错误 注意:数据是从 Azure 中获取的 spec.js const accou
我是一名优秀的程序员,十分优秀!