O(n logstar(n))和O(n)之间是否存在真正的复杂度? 我知道O(n sqrt(logstar(n)))和其他类似的函数在这两个之间,但我的意思是不是由logstar(n)组成的东西。O(nlog * n)和O(n)之间?
回答
是的,有。最着名的例子是Ackermann inverse function α(n),其增长速度比log * n慢得多。它显示在不相交集森林数据结构的上下文中,其中每个操作的摊销成本为O(α(n))。
您可以将log * n看作您需要将日志应用到n以将该值降低到某个固定常量(例如2)的次数。然后,您可以将其推广到log ** n,这是您需要将log *应用于n以将值降至2的次数。然后可以定义log *** n,log **** n ,log ***** n等以类似的方式。通常将α(n)的值作为您需要将日志数** ... * n中的值减至2,因此其增长速度比迭代对数函数慢得多。
直观地说,你可以把日志的n为幂(重复乘法)的倒数,数* N为tetration(重复幂)的倒数,数** n的pentation(重复迭代幂次)的倒数,等等.Ackermann函数将n次幂的n阶泛化有效地应用于数n,所以它的逆矩阵对应于需要应用的指数级别有多高。这导致了令人难以置信的缓慢增长的功能。
我曾经见过的最滑稽的慢速增长函数在一个严肃的语境中使用是α *(n),您需要将阿克曼反函数应用到数字n以将其降到某些值固定不变。这是几乎不可思议的多大的输入,你必须把这个函数返回接近,例如10。如果你很好奇,the paper that introduced it is available here。
谢谢,我绝对会读这篇论文!播放树木非常酷! –
- 1. O(nlogn)+ O(n),O(nlogn)和O(nlogn + n)之间的关系是什么?
- 2. 代码O(nlog(n))的T(n)如何?
- 3. 你如何看出O(log n)和O(n log n)之间的差异?
- 4. O(log_2(n))= O(log_10(n))?
- 5. Big O - O(N^2)or O(N^2 + 1)?
- 6. 证明最大(O(f(n)),O(g(n)))= O(max(f(n),g(n))
- 7. 时间复杂度 - O(n^2)到O(n log n)搜索
- 8. 时间复杂度O(N日志(log n)的)+ N O(L)
- 9. 大O符号 - O(n日志(N))对O(的log(n^2))
- 10. 大O复杂度O(n日志n)与O(n日志m)
- 11. O(N + m)和O(NM)之间的复杂性计算差异
- 12. 证明O(max {f(n),g(n)} = O(f(n)+ g(n))
- 13. 时间复杂度:O(logN)或O(N)?
- 14. Python脚本:如何判断在O(N)或O(N^2)时间?
- 15. 下面的函数是O(n)时间和O(1)空间,其中n = | A |?
- 16. 在渐近分析中,证明:O表示大O. O(f(n)+ g(n))= O(max {f(n),g(n)})
- 17. 大O符号 - 为什么是O(n^2/4)= O(N^2)
- 18. 比较O((logn)!)和O(2^n)
- 19. 在O(n)
- 20. 在O(N)
- 21. 大O N^2(日志N)
- 22. 是log(n!)= O((log(n))^ 2)?
- 23. 证明5^n = o(n!)
- 24. 证明lg(n!)= O(n!)
- 25. 哪里可以找到O(n^2)和O(n)等的含义?
- 26. 查找具有O(n)的时间和O(1)空间
- 27. 找到O(1)的空间和O(n)的时间
- 28. 显示n^2不是O(n * log(n))?
- 29. f(n)= N的大O! + 2^N
- 30. BIG O复杂度n或n^2log(n)
1