如果我有一个算法需要n个log n个步骤（例如，heapsort），而这些步骤需要n个log时间（例如，比较/交换范围为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），则a在c方面是什么？
如果我有一个算法需要n个log n个步骤（例如，heapsort），而这些步骤需要n个log时间（例如，比较/交换范围为0到n-1的“大”整数），那么渐近界是什么对于...
这里有矛盾的证明：
通常，您不能像这样乘以复杂性：对于堆排序，N表示堆中的项目数，而对于大整数，N可能表示可能值的上限。通常，这些不必关联，因此它是N log N log M（其中M是项可能采用的范围）。
您不能将n (log n) (log n)降低到n (log n)仅仅是因为这不是一个恒定因子的降低。
好的，程序的一般复杂度度量如下：