渐近符号 - n(log n)(log n)是否简化？

Question

如果我有一个算法需要n个n步骤(例如heapsort),其中步骤需要log n时间(例如比较/交换0到n-1范围内的"大"整数),什么是渐近界限整个过程.

显然我们可以说"n(log n)(log n)",但是我很难说服自己我不能简化为"n log n".与此同时,我很难证明我坚持自己的本能.

我的直觉在这方面是否完全错误？

编辑

似乎我的简单例子 - 避免 - 复杂化问题使问题复杂化.那好吧.

这个问题的真正原因是我经常使用具有已知复杂性的标准算法,但使用不同的底层容器实现,因此各个步骤是O(log n)而不是O(1).例如,Hopcrofts自动机最小化算法是O(n log n) - 但是如果你开始使用二进制树容器来处理状态,转换和中间结果,那么步骤本身就变成O(log n) - O(n log n)是不再有效,因为O(1)访问的假设无效.

尽管如此,人们会声称存在n个状态和m个转换,但是n和m倾向于与自动机线性相关,假设转换注释的数量是恒定的并且自动机具有或多或少的确定性.

我过去对此并没有太多担心 - 与我合作的案例并不是很大.但是,好吧,我正在对我的自动机代码进行重大的重构,而且我认为我可以正确地为一些关键算法进行数学计算.

编辑

我也越来越相信"n(log n)(log n)"是错误的.

如果a是O(b log b),其中b是O(log c),那么就c而言是什么？

Answer 1

通常,您不能将这样的复杂性乘以:对于堆排序,N表示堆中的项数,而对于大整数,N可能表示可能值的上限.通常,这些不必相关,因此它相当于N log N log M(其中M是项目可能采用的范围).

在特定的应用程序中,大多数情况下,大整数遵循一些特定的分布.例如,可以知道它们都低于10 ^ 20.如果是,则比较操作采用恒定时间(由10 ^ 20的上限确定).然后,log M也是常数,整个复杂度在O(N log N).