问如果我们把数组分成log(n)而不是2，时间复杂度是多少？

EN

看看你的例子：

n=64 log(n)=6

似乎您指的是log2(n) (而不是log10(n))。

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

这样，你就可以更快地将你的数组拆分为2。

现在来问你的问题。如果使用这样的数组元素划分，时间复杂度可能会减少，也可能不会减少，这取决于所讨论的算法。

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

但是，如果您的算法是基于n个元素进行排序，那么数组的递归划分可能是一个好主意。在这种情况下，它可以降低复杂性，因为算法中的数量或元素决定了动作的数量。

所以，的底线要知道这里的复杂性是算法看起来是什么样子，而不是如何将算法的元素递归地分成2或log2(n)。

具有这种划分的算法的复杂性由以下递归关系表示：

T(n) = T(n - log(n)) + T(log(n)) + D(n)

其中D(n)是“合并”步骤的复杂度。

要创建此复杂性的渐近下界，首先请注意，第二项T(log(n))非常小。我们可以在进一步的分析中忽略它，仍然可以得到相当准确的下限估计。

至于第一项T(n - log(n))，我们可以注意到和

log(n) + log(n -log(n)) + log(n-log(n)-log(n-log(n))) + ... (k terms in total)

比k log(n)小。要通过反复从n中减去log(n)来将其减少到零，必须采取k = n / log(n)步骤。因此，存在平均大小为D(n/2)的n / log(n)步长(因为输入大小因n和0而异；平均而言，输入大小是原始输入大小的一半)。

现在让我们考虑一个具体的例子。假设D(n) = O(n)和quicksort或merge sort中的一样，也是D(n/2) = O(n)，并且总的复杂度是O(n / log(n)) O(n) = O(n^2 / log n)。

简而言之，这种除法不是很好:它将O(n log n)复杂度的算法转换为几乎二次复杂度的算法。