《具体数学》中有关“封闭形式”的具体解释

_maze · 2021-02-09 22:20:09 · 个人记录

当我们说到“封闭形式”时，通常把下面这些东西排除在外：

抑或是：

他们在求值时，都要用到与"..."或"T_{n-1}"类似的东西。换句话说，他们所用的量需要的调用次数与自身，也就是n有关。相应的，所谓的“封闭形式”就是调用次数与n无关的

封闭形式也有例子：

也许有人已经发现其中奇怪的东西了：

"n!"?我们需要这种东西干嘛？这个运算不是要调用n次吗？

事实上，简单封闭形式只包含加减乘除幂指这几种运算。但有人想着乘方这东西反正这么常见，于是就嘿嘿嘿嘿了。

我们还可以得出，简单封闭形式肯定是不包含递归式。但这并不能阻止一些常见递归式被添加到封闭形式的范畴。

尽管某老师反对，我还是认为我的下面这种解释能应对《具体数学》中所遇到的状况：

只有复杂度为O(1)的求解形式才叫封闭形式

但这句话已经在越来越多的常见递归式与奇奇怪怪的循环下冲击得不适用了。我们也许可以加一条条件：

我们认为常见的递归式与循环的复杂度是O(1)的（虽然显然错误）