个人中心
文章发布
退出
作者热门文章
- Java锁的逻辑（结合对象头和ObjectMonitor）
- 还在用饼状图？来瞧瞧这些炫酷的百分比可视化新图形（附代码实现）⛵
- 自动注册实体类到EntityFrameworkCore上下文，并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
28
4
复杂度分析本身是非常理论化的一个内容，在计算机科学中，有一个专门的学科叫做—— 计算复杂性理论 .
很多童鞋看过《算法导论》，这本书的内容很多很强调算法导论.
但是实际上，对于普通程序员来说， 不需要 过度强调理论化的内容 。因为工作中更多面对的是实际的 软件工程，工程化的工作不需要面对太多理论性的东东.
复杂度分析的作用：是为了表示算法的性能.
对于同样一个任务，可能有多个实现方式，即多个算法。这些不同的算法，它们的时间性能是否有差异呢?
我们虽然可以用一个测试用例，或者一组测试用例实际比较性能差异。 但是，这样的比较结果有局限性.
比如，需要保证运行不同算法的计算机硬件设备的性能一致，甚至深入的说，他们的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的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
28
4
0
我正在努力实现以下目标， 假设我有字符串: ( z ) ( A ( z ) ( A ( z ) ( A ( z ) ( A ( z ) ( A ) ) ) ) ) 我想编写一个正则
给定: 1 2 3 4 5 6
很难说出这里要问什么。这个问题模棱两可、含糊不清、不完整、过于宽泛或夸夸其谈，无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开，visit the help center . 关闭 1
大家好，我卡颂。 Svelte问世很久了，一直想写一篇好懂的原理分析文章，拖了这么久终于写了。 本文会围绕一张流程图和两个Demo讲解，正确的食用方式是用电脑打开本文，跟着流程图、Demo一
身份证为15位或者18位，15位的全为数字，18位的前17位为数字，最后一位为数字或者大写字母”X“。 与之匹配的正则表达式： ?
我们先来最简单的，网页的登录窗口； 不过开始之前，大家先下载jquery的插件 本人习惯用了vs2008来做网页了，先添加一个空白页 这是最简单的的做法。。。先在body里面插入 <
1、MySQL自带的压力测试工具 Mysqlslap mysqlslap是mysql自带的基准测试工具,该工具查询数据,语法简单,灵活容易使用.该工具可以模拟多个客户端同时并发的向服务器发出
前言 今天大姚给大家分享一款.NET开源（MIT License）、免费、简单、实用的数据库文档（字典）生成工具，该工具支持CHM、Word、Excel、PDF、Html、XML、Markdown等
Go语言语法类似于C语言，因此熟悉C语言及其派生语言（ C++、 C#、Objective-C 等）的人都会迅速熟悉这门语言。 C语言的有些语法会让代码可读性降低甚至发生歧义。Go语言在C语言的
我正在使用快速将 mkv 转换为 mp4 ffmpeg 命令 ffmpeg -i test.mkv -vcodec copy -acodec copy new.mp4 但不适用于任何 mkv 文件，当
我想计算我的工作簿中的工作表数量，然后从总数中减去特定的工作表。我错过了什么？这给了我一个对象错误: wsCount = ThisWorkbook.Sheets.Count - ThisWorkboo
我有一个 perl 文件，用于查看文件夹中是否存在 ini。如果是，它会从中读取，如果不是，它会根据我为它制作的模板创建一个。 我在 ini 部分使用 Config::Simple。 我的问题是，如果
尝试让一个 ViewController 通过标准 Cocoa 通知与另一个 ViewController 进行通信。 编写了一个简单的测试用例。在我最初的 VC 中，我将以下内容添加到 viewDi
我正在绘制高程剖面图，显示沿路径的高程增益/损失，类似于下面的: Sample Elevation Profile with hand-placed labels http://img38.image
嗨，所以我需要做的是最终让 regStart 和 regPage 根据点击事件交替可见性，我不太担心编写 JavaScript 函数，但我根本无法让我的 regPage 首先隐藏。这是我的代码。请简单
我有一个非常简单的程序来测量一个函数花费了多少时间。 #include #include #include struct Foo { void addSample(uint64_t s)
我需要为 JavaScript 制作简单的 C# BitConverter。我做了一个简单的BitConverter class BitConverter{ constructor(){} GetBy
已关闭。这个问题是 not reproducible or was caused by typos 。目前不接受答案。 这个问题是由拼写错误或无法再重现的问题引起的。虽然类似的问题可能是 on-top
我是 Simple.Data 的新手。但我很难找到如何进行“分组依据”。 我想要的是非常基本的。 表格看起来像: +________+ | cards | +________+ | id |
我现在正在开发一个 JS UDF，它看起来遵循编码。 通常情况下，由于循环计数为 2，Alert Msg 会出现两次。我想要的是即使循环计数为 3，Alert Msg 也只会出现一次。任何想法都
我是一名优秀的程序员,十分优秀！