V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  also24  ›  全部回复第 127 页 / 共 286 页
回复总数  5704
1 ... 123  124  125  126  127  128  129  130  131  132 ... 286  
2020-07-27 13:38:05 +08:00
回复了 yxcoder 创建的主题 问与答 给定链表,找中点,两种方法时间复杂度对比
我们以 0->1->2->3->4 这个链表为例

朴素法的话:
变量 - 临时变量 n,临时指针 i
循环 - 共访问节点 8 次
i : 0 1 2 3 4 0 1 2
n: 1 2 3 4 5 2 1 0 ( n 先自增记录长度,再 n/2 后自减用于二次遍历)


快慢指针法的话:
变量 - 临时指针 fast, slow
循环 - 共访问节点 8 次
fast: 0 1 2 3 4
slow: 0 1 2

可见,朴素法多了个存长度的变量,快慢指针法多了个指针变量,但双方访问节点的数量是一致的。
不过也可以注意到,朴素法 和 快慢指针法都 做了 8 次指针赋值操作,朴素法多了 8 次长度变量的赋值操作。
2020-07-27 13:29:07 +08:00
回复了 yxcoder 创建的主题 问与答 给定链表,找中点,两种方法时间复杂度对比
其实快慢指针法,本质上就是朴素法变化而来的吧。

我们先来从朴素方法开始:
遍历一遍(n)->计算总数->计算中点所在位置->找到中点(n//2)

这里有个小问题, n/2 很容易计算,但是 n/2 对应的指针地址,该如何取出来呢?

先来最狠的方法,我们继续从 0 开始,遍历到第 n/2 的位置,就找到对应的指针了:
遍历一遍(n)->计算总数->计算中点所在位置->找到中点(n//2)->遍历半遍(n/2)->找到中点指针
时间上,多跑了半遍循环,复杂度层面都是 O(n),只是常数项从 1 变成了 1.5 而已。

然后我们用时间来换空间试试,把经过的每一个节点的指针都存进数组 arr,最后只需要取 arr[n/2] 就行了。
时间复杂度还是 O(n) ,但是空间复杂度从 O(1) 暴增到 O(n) 了。

然后我们想一下怎么优化,你看啊,我们其实最后只需要 arr[n/2] 这个指针,那我能不能优化成只存储 arr[n/2] 呢?
也就是在遍历的时候,只存储 n 和 n/2 这两个节点的指针,其它的不管。
诶?这不就是快慢指针法了么……

快指针走了 n 步,慢指针走了 n/2 步,算下来,其实还是访问了 1.5n 个节点。
从这个角度来说,大家的时间复杂度实际上都是 O(1.5n),空间上来说也都是 O(1) ,快慢指针法实际上还多出一个慢指针。

但是…… 很多时候,在计算时间复杂度的时候,习惯用循环的次数来算。
此时,由于快慢指针法的循环可以合并为 n 次甚至 n/2 次,就很容易得出快慢指针法的之间复杂度为 O(1n) 或者 O(0.5n) 的结论,再拿来和朴素法的 O(1.5n) 做对比的时候,就容易觉得朴素法更慢了。
2020-07-27 10:10:25 +08:00
回复了 Wayne716 创建的主题 Apple 刚买的 Trackpad2 用起来粘粘的
1 、喷点酒精擦一擦触摸板
2 、喷点酒精擦一擦手指头
2020-07-26 20:23:24 +08:00
回复了 revival83 创建的主题 问与答 孩子总抱着 iPad 玩没完,有远程锁定工具吗?
如果你恰好有一台 mac 的话,可以试试 Apple Configurator
https://support.apple.com/apple-configurator

通过它不止能指定哪些 APP 可以使用,系统内置功能也能一起干掉。

https://i.loli.net/2020/07/26/hEfyLwbBiKkGdQI.png
2020-07-26 17:36:24 +08:00
回复了 ptwop 创建的主题 问与答 大家眼睛度数都是在哪测的啊,眼镜店 or 医院?
宝岛 50 元验光
2020-07-25 12:53:47 +08:00
回复了 lxj770 创建的主题 Android 安卓隐藏系统应用图标(免 root)
@RiESA
我……… 我就是 NOVA 的付费用户……

去年换了华为以后我特别想死……
2020-07-25 01:12:38 +08:00
回复了 lxj770 创建的主题 Android 安卓隐藏系统应用图标(免 root)
第三方 launcher 要不要考虑一下?
2020-07-25 00:42:54 +08:00
回复了 nifengwobei 创建的主题 奇思妙想 写代码的时候为什么不手脚并用呢
当然,想要按键也可以,其实想一下油门刹车就晓得,臭打游戏的肯定藏的有这个
http://amazon.com/Lemo-1640835-Control-Keyboard-Action/dp/B00B3PV47O

https://i.loli.net/2020/07/25/WHYdjJgIwPfVlsD.png
2020-07-25 00:39:08 +08:00
回复了 nifengwobei 创建的主题 奇思妙想 写代码的时候为什么不手脚并用呢
2020-07-25 00:32:03 +08:00
回复了 AllenHua 创建的主题 分享发现 极客湾 整的 https://www.socpk.com/ 有点意思呀 很有参考价值
@AllenHua #4
你要是夸网页风格…… 我就不同意了,这特么明明就是直接挂了三张图,完全没有任何体验。
好看或许还能说的上,使用体验简直就是一塌糊涂。

体验角度来说,我随便找个天梯图都比它这个好啊,比如下面这个:
http://cdn.malu.me/cpu/

支持查找,支持对比,移动端可以无痛使用,比三张图不知道高到哪里去了……
// 注意,此处仅针对使用体验,无关数据真实性
2020-07-25 00:28:04 +08:00
回复了 AllenHua 创建的主题 分享发现 极客湾 整的 https://www.socpk.com/ 有点意思呀 很有参考价值
@inhd #1
@StanMarsh #3
@ostrichb #5
我个人是比较认可极客湾的这份表的,原因很简单,因为他们是真的买了这些机器来做测试。
https://www.bilibili.com/video/BV1hV411C7yL


常见的 CPU / GPU 天梯图等,大部分基于的其实还是网络上直接查到的跑分结果,而不是亲自测试。
自己做测试,虽然仍然无法完全控制变量,但是已经比直接上网查分数进步一大截了。

// 需要注意的是,受限于系统、APP,移动端 SOC 的测试是一定无法做到绝对客观的,只能说使用各种办法尽量接近客观,在我看来,至少目前我没看到更有可信度的移动端 SOC 的性能对比。
2020-07-24 15:53:29 +08:00
回复了 fangch 创建的主题 职场话题 周末面试的公司靠谱吗?
我遇到过两次周末面试,都是候选人主动要求周末面试的……

我本来是双休,被迫周末去公司……

然后其中一个候选人还鸽了我,周六下午我一个人坐在空荡荡的公司思考人生……
2020-07-23 15:07:08 +08:00
回复了 m4d3bug 创建的主题 路由器 有没有省事的软路由推荐
@hing #32
直接搜 “H310 四网口” 在马云家直接搜能搜到很多啊
2020-07-23 11:50:52 +08:00
回复了 saltbo 创建的主题 程序员 goget, 一个比 go get 更方便的装包工具
2020-07-22 22:52:02 +08:00
回复了 cs419 创建的主题 互联网 完美公司推出了 88 域名邮箱
6-20 位字符,可使用字母、数字、下划线,需要以字母开头
2020-07-22 17:01:26 +08:00
回复了 pabno 创建的主题 程序员 现在还有用 cookies 吗
@madNeal #58
对啊,这不就是我要表达的意思么?

放进 localStorage 的话,XSS 脚本就能获取到(然后发送出去);
放加了 HttpOnly 的 Cookie 里面,XSS 脚本获取不到了,于是就不会有(能发出去)这个问题。
2020-07-22 14:29:27 +08:00
回复了 pabno 创建的主题 程序员 现在还有用 cookies 吗
@ChanKc #41
恩,并不是防止攻击,只是控制损失,其实我觉得这也算是使用 Cookie 来存储凭据的一部分优势。

顺便说一下:
我并不是拥护 Cookie,Cookie 机制也有很多劣势(例如无脑带 Cookie 导致无关请求的体积增大);
只是说在 『限制 JS 读取凭据』这件事上,Cookie 有一定的优势。
1 ... 123  124  125  126  127  128  129  130  131  132 ... 286  
关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5750 人在线   最高记录 6679   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 55ms · UTC 06:36 · PVG 14:36 · LAX 22:36 · JFK 01:36
Developed with CodeLauncher
♥ Do have faith in what you're doing.