在O(n logstar(n))和O(n)之间是否存在真正的复杂性差异？ 我知道O(n sqrt(logstar(n)))和其他类似的函数介于这两者之间，但我的意思是指不由logstar(n)组成的原始函数。
在 O(nlog*n) 和 O(n) 之间？
3
- A. Mashreghi
1
1 < log (log* n) < log* n，渐进地。添加对数很有趣。 - G. Bach
1个回答
6
是的，有一个例子。最著名的例子是阿克曼反函数α(n)，它的增长比log* n慢得多。它出现在诸如不相交集合森林数据结构之类的上下文中，其中每个操作的平摊成本为O(α(n))。
您可以将log* n视为您需要应用log n的次数，以将值降至某个固定常数（例如2）。然后，您可以将其推广到log** n，这是您需要将log* 应用于n的次数，以将值下降到2。您可以以类似的方式定义log*** n、log**** n、log***** n等。通常将α(n)的值给出为您需要在log**...* n中放置星号的数量，以使该值下降到2，因此它的增长速度比迭代对数函数慢得多。
直观地说，您可以将log n视为指数（重复乘法）的倒数，将log* n视为tetration（重复指数），将log** n视为pentation（重复四次方），等等。Ackermann函数有效地将n阶幂的推广应用于数字n，因此它的反函数对应于需要应用多高级别的幂次才能到达它。这导致了一个难以置信缓慢增长的函数。
我曾经在严肃的上下文中使用过最搞笑的缓慢增长函数是α*（n），您需要将Ackermann反函数应用于数字n多少次才能将其降至某个固定常数。几乎无法想象要输入多大的输入才能获得接近10的任何东西。如果您感兴趣，介绍它的论文在此处提供。
您可以将log* n视为您需要应用log n的次数，以将值降至某个固定常数（例如2）。然后，您可以将其推广到log** n，这是您需要将log* 应用于n的次数，以将值下降到2。您可以以类似的方式定义log*** n、log**** n、log***** n等。通常将α(n)的值给出为您需要在log**...* n中放置星号的数量，以使该值下降到2，因此它的增长速度比迭代对数函数慢得多。
直观地说，您可以将log n视为指数（重复乘法）的倒数，将log* n视为tetration（重复指数），将log** n视为pentation（重复四次方），等等。Ackermann函数有效地将n阶幂的推广应用于数字n，因此它的反函数对应于需要应用多高级别的幂次才能到达它。这导致了一个难以置信缓慢增长的函数。
我曾经在严肃的上下文中使用过最搞笑的缓慢增长函数是α*（n），您需要将Ackermann反函数应用于数字n多少次才能将其降至某个固定常数。几乎无法想象要输入多大的输入才能获得接近10的任何东西。如果您感兴趣，介绍它的论文在此处提供。
- templatetypedef
1
谢谢，我一定会读这篇论文！伸展树真的很酷！ - A. Mashreghi
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接