1

考虑一个最初为空的 RB-tree，我们将 m 个元素插入其中。插入一个元素需要 O(log n) 时间，其中 n 是当前插入的元素数。所以我可以写出 m 次插入的总时间，如： sum log(i) for i=1..m == log(Pochhammer(1,m) ；由 WolframAlpha 提供。

事实上，m*logm 和 log(Pochhammer(1,m) 的比率收敛到 1，所以我想这就是为什么我以前没有见过 log--Pochhammer 的原因。

计算机科学中还使用了哪些其他“奇异”功能？我知道 inverse-ackerman 出现在 Union-Find 等...

4

1 回答 1

2

超几何函数（你可以称之为“奇异的”）在数学中出现了很多。原因是，根据定义，他们的泰勒级数有一个简单的形式。因此，它们会在您使用归纳法时立即出现。

许多“标准”函数实际上是超几何的（而且，大多数正交多项式也是）。较少使用的名字很花哨，但它们属于同一家族。

当然，也在这里 sum(log k) = log(prod k) = log k!，所以你甚至不需要花哨的东西。您得到 Pochhammer 符号的事实可能源于 Mathematica 的符号级数求和方法。看例如。对于 Zeilberger 的算法，它使用超几何函数对序列求和。

于 2012-03-17T12:00:33.867 回答