V2EX › ipwx 的所有回复 › 第 176 页 / 共 205 页

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

1 ... 172 173 174 175 176 177 178 179 180 181 ... 205

❮

❯

2018 年 3 月 13 日

回复了 70599 创建的主题 › JavaScript › 请教用 JavaScript 计算这个东西的方法

@msg7086 @lightening 确实，我大 O 符号用得不合适，这种细节应该注意一下，哈哈。不过我的意思很明确，这个场景需要考虑常数。

2018 年 3 月 12 日

回复了 70599 创建的主题 › JavaScript › 请教用 JavaScript 计算这个东西的方法

@msg7086 @lightening 好吧根据维基百科（希尔排序），优化过的希尔排序其期望复杂度是 O(N (log N)^2)，也就比快速排序的期望复杂度 O(N log N) 慢那么一点。。。

2018 年 3 月 12 日

回复了 70599 创建的主题 › JavaScript › 请教用 JavaScript 计算这个东西的方法

@msg7086 @lightening 不过话说回来，不同阶不比常数也不是绝对的。写算法的时候，偶尔也会根据 N 的不同，使用不同阶的算法（因为常数有差别，高阶低常数算法在 N 小的时候反而更快）。比如 GCC C++ STL 中快速排序（ O(N log N)）的实现，在数据量小的时候（或者递归之后数据量小的时候）是 O(N^2) 的希尔排序。当然，你问我这两个算法的确切常数，我是不确定的，不过反正写 G++ 的人很厉害，我也就相信他们的判断了。

2018 年 3 月 12 日

回复了 70599 创建的主题 › JavaScript › 请教用 JavaScript 计算这个东西的方法

@msg7086 @lightening 而且所谓的复杂度分析时忽略常数，只是因为不同阶的复杂度，当 N 趋向于无穷时，比值渐进趋向于 0 （或无穷），没有比较常数的必要。比如 O(logN) 和 O(N) 有阶差，此时比较常数没有意义。然而当同阶时，你都忽略常数了，你还比啥？

复杂度分析理论是为了在没有运行算法的前提下比较算法优劣的理论方法。一切教科书上的定式、过程，都要为了这个目的让路。切记。

2018 年 3 月 12 日

回复了 70599 创建的主题 › JavaScript › 请教用 JavaScript 计算这个东西的方法

@msg7086 @lightening 这里可不适用忽略不计……更准确的复杂度是 O(kn) 和 O(2n)，其中 k 在本问题中取 10。再说，这么简单一个程序，为啥不用最佳写法？

2018 年 3 月 12 日

回复了 70599 创建的主题 › JavaScript › 请教用 JavaScript 计算这个东西的方法

@70599 好吧，我上面的代码可能理解错了题意。不过应该很好改才对，你也可以试试。

2018 年 3 月 12 日

回复了 70599 创建的主题 › JavaScript › 请教用 JavaScript 计算这个东西的方法

@70599 少年，如果你不会“优雅的写法”，为什么不一步一个脚印，用最基础的写法写呢？反正有 V8 的 JIT，用累加器和循环并不慢啊。比如 https://gist.github.com/korepwx/2c4c63741fed0effdd70f3bf80070530

再说这个写法其实比上面 @Building @rabbbit 高效才对。因为他们是 O(10N)，而这个写法是 O(2N)。

2018 年 3 月 12 日

回复了 70599 创建的主题 › JavaScript › 请教用 JavaScript 计算这个东西的方法

@rabbbit 抱歉，O(N) 应该到不了，O(2N) 应该行。

2018 年 3 月 12 日

回复了 70599 创建的主题 › JavaScript › 请教用 JavaScript 计算这个东西的方法

@rabbbit 我看你写了三遍，可是全都是 O(10N) 的。应该写 O(N) 的算法。

2018 年 3 月 12 日

回复了 cyspy 创建的主题 › 求职 › Java 实习不懂 SSH 是不是空间很小？

ssh 竟然是面试重点嘛？！

2018 年 3 月 11 日

回复了 gs139 创建的主题 › 问与答 › 培训班怎么不蹭人工智能这个热点？

微软 Azure ML 了解一下。