algorithm - 哪种方法在链表中存储项目更快？

我的算法课本上有一个练习题，我不太确定，希望有人能详细说明/解释一下：
当你设计一个分而治之的算法来存储大小为n的链表中的项目时，在最坏的情况下，将问题一分为二会比将列表分成大小为1的单个子问题和大小为n-1的另一个子问题的算法更快吗？

最佳答案

将流程视为树结构，如：

          [1,          n]
         /               \
 [1,     n/2]             [n/2,       n]
 /           \             /            \
[1, n/4] [n/4, n/2]  [n/2, n*3/4] [n*3/4, n]

时间成本取决于你在每一个层次上做了多少计算。
例如，在数组中找到最大数。

int f1(int a[], int n){
    if (n == 1) return a[0];
    return max(a[0], f1(a + 1, n - 1));
}


int f2(int a[], int n){
    if (n == 1) return a[0];
    return max(f2(a, n / 2), f2(a + n / 2, n - n / 2));
}

您在每个级别上的计算都是O(1)，因此f1和f2总共都是O(n)。
或者正如您所提到的，您在每个级别上执行的quicksort算法是O(n)，因此总成本取决于有多少级别。
如果将其分为[1, n/2]和[n/2, n]，则会有O(logn)级别，总时间成本为O(nlogn)。
如果我们把它分为[1, 1]和[2, n]，就会有O(n)级别，所以总的时间成本将O(n^2)

关于algorithm - 哪种方法在链表中存储项目更快？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20159393/