在 O(nlog*n) 和 O(n) 之间？
Between O(nlog*n) and O(n)?
O(n logstar(n) ) 和 O(n) 之间是否存在真正的复杂性？
我知道 O(n sqrt(logstar(n))) 和其他类似函数介于这两者之间，但我的意思是不是由 logstar(n) 组成的原创内容。
是的，有。最著名的例子是 Ackermann inverse function α(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 (repeated exponentiation), log** n as the inverse of pentation 的倒数（重复四次运算）等。阿克曼函数有效地应用了 n - 求幂到数字 n 的阶次泛化，因此它的倒数对应于您需要应用多高的求幂级别才能达到它。这导致了一个令人难以置信的缓慢增长的函数。
我见过在严肃的环境中使用的最滑稽的增长缓慢的函数是 α*(n)，您需要将阿克曼反函数应用于数字 n 以将其下降到的次数一些固定常数。几乎无法想象您必须向此函数输入多大的输入才能返回接近于 10 的值。如果您好奇，the paper that introduced it is available here.
O(n logstar(n) ) 和 O(n) 之间是否存在真正的复杂性？ 我知道 O(n sqrt(logstar(n))) 和其他类似函数介于这两者之间，但我的意思是不是由 logstar(n) 组成的原创内容。
是的，有。最著名的例子是 Ackermann inverse function α(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 (repeated exponentiation), log** n as the inverse of pentation 的倒数（重复四次运算）等。阿克曼函数有效地应用了 n - 求幂到数字 n 的阶次泛化，因此它的倒数对应于您需要应用多高的求幂级别才能达到它。这导致了一个令人难以置信的缓慢增长的函数。
我见过在严肃的环境中使用的最滑稽的增长缓慢的函数是 α*(n)，您需要将阿克曼反函数应用于数字 n 以将其下降到的次数一些固定常数。几乎无法想象您必须向此函数输入多大的输入才能返回接近于 10 的值。如果您好奇，the paper that introduced it is available here.