chapter_computational_complexity/performance_evaluation/

[giscus[bot]]

chapter_computational_complexity/performance_evaluation/

Your first book to learn Data Structure And Algorithm.

https://www.hello-algo.com/chapter_computational_complexity/performance_evaluation/

[hsamgle]

数据结构与算法追求 “运行地快、内存占用少” ，而如何去评价算法效率则是非常重要的问题

运行"地"快，是不是有错别字？

[krahets]

感谢指正！（可以点击页面右上角的“铅笔”图标，直接修改原文内容，谢谢！）

[nobt854]

感觉“运行速度快、占用内存少”更优

[1931668642]

二者不可兼得

[sakkyakei]

有个小建议：
因为作者希望初学者初步了解一下计算复杂度，这里是不是可以放一些您觉得比较适合小白的科普文呢？

[krahets]

哈喽，下一节“时间复杂度”和“空间复杂度”即计算复杂度，有做详细介绍～

[Wenwen555]

个人认为作者已经深入浅出的讲解了复杂度的概念啦，尽管没有一个很具体的例子～

[husenlinwei]

这一句“复杂度分析评估的是算法运行效率随着输入数据量增多时的增长趋势。” 貌似可以润色成 “复杂度分析旨在评估随着输入数据量增加，算法运行效率所呈现的增长趋势。” ？

[krahets]

已润色该定义～

[ljl312869]

应该去掉增长 有些算法运行效率和数据量是无关的 是一个常量

[yicijohncy]

“它描述了随着输入数据大小的增加，算法执行所需时间和空间的增长趋势”这个定义虽然抽象，但也挺好理解。

前面说过“随着输入数据量的变化，算法会表现出不同的效率”。

也就是说，数据量是「算法执行效率」的重要影响因素。

而时间和空间又是我们重要的消费资源。

把数据量看做 x 值，算法计算 x 值所需时间或空间当做 y 值。

计算出来的数据，就是一个横坐标的点（x，y）。

把不同的点，连接起来，就会是一条曲线。

不同的算法，就会有属于自己的不同“曲线”。

通过观察这条曲线的“陡峭”程度，也就是时间或空间增长的“快慢”，从而评价这个算法的性能。

[krahets]

栩栩如生！

[7CkShy]

那已知一系列的x，怎么得到对应的y值呢？通过实际计算机运行统计出来？

[xx10n31y]

如果你仍对复杂度的概念感到困惑，无须担心，我们会在后续章节中详细介绍。

哈哈, 确实感到些许困惑, 可能这就是理论知识让人略感抽象

[liangguitao]

Day 1 : LGT 总结 ：理论估算不同的算法 最后我们都可以用（x,y）抛物线的形式来表示，不同的算法，随着数据量的增加（x改变），那么时间或者空间也可能发生改变（y改变）

[zerlindali]

我连复杂度都看不懂，咋搞

[krahets]

可以理解个大概，先看后面几章，回头再看这里

[mix8889]

嗯，老板
真的写的很好很赞！

[yalishiduozhang]

太强啦！

[UNUKyfmt]

太赞了

[Rinato-C417]

Completed

[krahets]

Hi，建议只在每章的首节打卡，
欢迎在内容章节多分享见解和提问噢～

[yujingzhou]

‧ 时间效率:算法运行速度的快慢。
这个定义不太准确。更准确的定义应该是

‧ 时间效率:算法运行的计算次数。

[krahets]

“时间效率”整体上指的就是算法在“时间”上的快慢，而非运行计算次数。

即使算法 A 比算法 B 的计算次数更多，但算法 A 仍然可能比算法 B 更快（算法 B 的单元操作的平均计算时间长）。

[gofunbox]

我的智商都看得懂

[NgxuAnGMH]

抛去拗口的概念，采取两种方式实现同一个功能，但是不知道它们的优劣，直接为了这么小的功能进行测试（甚至是整个系统的测试），一是不切实际（资源有限），二是未必能屏蔽所有干扰（环境完全一致）。也因此考虑用复杂度来衡量，估算“时间”和“空间”各自的开销，是一种完全从代码层面（嵌套循环/所用内存多少）就可以估算的指标。

[DayDayYES]

下面有一个关于时间效率的讨论，作者认为：“时间效率”整体上指的就是算法在“时间”上的快慢，而非运行计算次数。还有人则说： 时间效率指算法运行的计算次数。

[krahets]

是的，原因很直接：我们提出时间效率这个概念，最终想要关心的是“时间”上的快慢，而不是“执行次数”。

执行次数更多和时间复杂度关联，它是反映时间效率的有效指标，但很有可能给出错误的结论。我们有时会遇到一种情况：算法 A 比算法 B 的时间复杂度更高（更差），但反而在给定数据下运行地更快（时间更短、效率更高）。一个典型的例子是插入排序 vs. 归并排序在数据量较小时的效率对比。

[xbsheng]

因为执行不同类型计算的时间成本不同，所以通过计算次数衡量时间效率不太科学，我们应该要关心的是“时间”上的快慢

[xiaozhuge123]

day02

[zengfantaoGit]

day1

[jidaojiuyou]

实际上 2C的项目基本上都是空间换时间。甚至上超大规模的分布式系统。

[jidaojiuyou]

2C = 面向消费者

[Xfront-end]

写跑在开发板上 树莓派这种卡片电脑时， 才能体会到 空间复杂度的重要。

[EdwinNull]

打卡

[Bronc-X]

大家用电脑登着看的还是一边电脑跑代码一边平板看教材

[jezyzg]

对复杂度一知半解，不会求

[pulo2000]

打卡

[CrescentZM]

打卡

[nimobnaz]

建议给出简单例子说明复杂度

[NuyoahCh]

看到作者对 “实际测试” 和 “理论估算” 的两种方式展开了讨论和分析，这里也有一些自己的感悟。

所谓的实际测试我们有的时候很难去在项目/工程刚刚开始的时候就实现落地，反而理论估算是更加符合在当下软件开发的场景。

举个例子，比如瀑布模型，虽然我们当前不推荐这样的开发模型进行落地，但是它会给我们一些指导建议——我们在开发完成一个工程之前是没有办法看到它的整体完整的一个模型的。

所以这样的话，理论估算是更加重要的，我们可以在工程初期或者是实施阶段，对我们做的东西进行整体上的预估和评价，这样会极大的提高我们对整体上的把握，和降低工程所带来的成本消耗。

所以，我们学习数据结构与算法的本质就是更好的分析和处理，在这个理论阶段进行估算。

当然，算法的本质并不是在实际测试没有任何作用的，而是一个相辅相成的作用，当我们在前期对工程的实现和落地有一个整体的把控之后，对于之后的实际测试也就是一个水到渠成的事情了。

分享链接
https://www.yuque.com/codereview1024/uboc4y/rf2rncqdrgetbu74?singleDoc# 《后端程序员对算法的思考》

[zhengads]

好的算法能够在时间和空间复杂度上做到好的平衡，既能够快速出结果，又不会占太大的空间，又快又小是算法设计的根本目的。

[zhengads]

当然复杂度分析不只是静态的，更表现了时间和空间随输入规模的增大的变化，有的算法在输入规模比较小时不会让人感觉时间和空间的消耗，但当输入规模一大时，时间和空间的消耗便极为明显。

[LiLi-0226]

2.1打卡

[ttrx2023]

复杂度分析衡量的就是dy/dx

[ttrx2023]

y：时间或空间； x：输入数据规模

[Daniel-Zun]

感觉渐进分析的名字来源于，对大的数据的分析从而取近似值的操作