渐近表示法——n(logn)(logn)简化了吗?

一般来说,不能像这样增加复杂性:对于堆排序,N表示堆中的项数,而对于大整数,N可能表示可能值的上限。一般来说,这些不一定是相关的,因此它是N log N log M(其中M是项目可能采用的范围)。

在特定的应用程序中,大整数很可能遵循特定的分布。例如,可以知道它们都低于10^20。如果是这样,比较操作将花费恒定的时间(由10^20的上限确定)。然后,logm也是常数,整个复杂度是O(N logn)。

这里有一个矛盾的证明:

f(n) = n(log n)(log n) Θ(n log n) , theta(n log n) 换句话说,有一个 a f(n) <= a * n log n 大举 n .

现在考虑 f(2^(a+1)) :

f(2^(a+1)) = 2^(a+1) * log(2^(a+1)) * log(2^(a+1)) = 2^(a+1) * log(2^(a+1)) * (a+1) ,明显大于 a * 2^(a+1) * log(2^(a+1)) ,我们有一个矛盾。因此 f(n) n log n 作用

你将无法减少 n (log n) (log n) n (log n) 因为这不是一个常数因子的减少。

你怎么了 n(对数n) 2 ?

好的,程序的一般复杂性度量如下:

复杂性O(f(n))意味着存在 c ,使得相应的图灵机终止前的步数不超过c*f(n),其中n是输入的长度。

在这个定义中,考虑了所有因素,因为整数可能任意大,对它们进行算术运算也会增加O(n)下的函数。

但如果我们直接编程图灵机,你的问题就不会出现了。在现实世界中,我们更喜欢抽象。虽然我们仍然计算运行程序所需的“步骤”,但我们假设某些操作需要 一步 . 我们假设,由于不同的原因:

• 它可能类似于CPU的实际工作,其中每个32位整数加法实际上是一个步骤(并且存在实际滥用它的算法,例如“位verctor支配器”)。
• 我们比较同一领域中的不同算法(例如,通过测量比较次数来比较数组排序)。

在本例中(您的第一次编辑),如果您想要具体化您的复杂性度量,您应该将O下的函数相乘。如果您认为采取的一个步骤现在被视为采取O(logn)步骤,那么具体化步骤的数量将增加O(logn)倍。因此,总复杂度为O(N) 日志N

日志N)。但是你知道输入包括 M log K 日志K)(我们需要计算分隔符等)。然后将总体复杂度写为O(M*logk*(logm+logk)),这在数学上是正确的,所以这里没有问题。但通常我们会把不必要的细节提取出来,为不同的算法找到一个共同的基础进行比较。