arrays - 如果我们将数组划分为 log(n) 而不是 2，时间复杂度是多少？

Question

我正在尝试改进我的项目的算法。我计划将数组分为 log(n) 和其余部分(即 (logn-1)(n/logn) )，而不是将数组分成两部分。例如:对于 n=64日志(n)= 6我将传递数组并以这样的方式划分它，一部分将包含 logn=6，另一部分将剩余 (64-6)=58 个元素，我将递归地对 6 和 58 执行此操作，直到得到 2。即在下一轮中，我会将 58 划分为 logn=5 和 53 个元素，对于 6，我会将其划分为 log n=2，其他部分将有 4 个元素。

最后时间复杂度是多少？我得到 nlogn，但随之而来的常数因子是多少？谁能帮我找到 nlogn 的常数因子？

Answer 1

看看你的例子:

n=64 log(n)=6

您的意思好像是 log2(n)(不是 log10(n))。

由于 n 的个数是整数，对于这种使用 2^n 作为除数的计算，最好的是使用右位移位运算符(也就是说，在大多数语言中，它看起来像this: >>) 你可以考虑使用它来加速你的计算。

这样，您可以更快地将数组分成 2 个。使用您的公式。

现在回答你的问题。如果您完全使用数组元素的这种划分，时间复杂度可能会或可能不会减少，具体取决于所讨论的算法。

例如，如果算法是 x 个数字之间的简单加法。通过递归地将它分成更小的数组，它并没有降低复杂性。反之，会增加时间复杂度。

但是，如果您的算法是根据 n 个元素对某些内容进行排序，那么数组的递归划分可能是个好主意。在这种情况下，它可能会降低复杂性，因为算法中的数量或元素决定了操作的数量。

因此，了解这里的复杂性的底线是算法的样子，而不是如何递归地将算法的元素分成 2 或 log2(n)。