归并排序分步时间复杂度应用于链表

Question

我一直在研究归并排序在链表中的应用。我看过的一些文章宣称归并排序是对链表进行排序的最佳算法。这对于分而治之策略中的征服部分是有意义的，在这种策略中，您合并两个排序的链表，因为您最终节省了所需的内存（与数组相比）。但是，我不明白的是算法中除法步骤的时间复杂度。

对于数组，此步骤是利用随机访问并将数组拆分为更小的块的恒定时间。但是，对于链表来说，这不是需要额外的 O(n) 吗？我见过弗洛伊德算法（龟兔赛跑）用于找到链表的中点并将问题分成更小的块。我对划分步骤做了一些分析。假设链表的大小为n，那么刚才划分问题涉及的操作#如下，

n/2 + n/4 * 2 + n/8 * 4 + ... = n/2 * log(n)

从上面看来，与数组情况相比，弗洛伊德算法中出现了一个额外的因子“n”。因此，最终的时间复杂度为 O(n^2 * log(n))。有人可以解释差异吗？

编辑：根据@Yves 的评论，我发现了错误，

当应该添加时，我在从下到上合并排序的块时增加了工作量。因此，净时间为：nlogn/2 + nlogn = O(nlogn),

这可能是对上述问题最有效的答案；其他答案有点间接/没有提供解释

Answer 1

你的问题是，对于每个递归级别扫描半个子列表的额外 O(n/2) 时间复杂度转化为 O((0.5 n log(n) + 1.0 (n log(n)) = O(1.5 n log(n))，不是 O(n^2 (log(n)))，而是 O(1.5 (n log(n)))转换为 O(n log(n))，因为时间复杂度忽略了低阶项或常量。但是在我对具有分散节点的大型列表的实际测试中，大多数节点访问导致缓存未命中，我的基准测试显示相对时间递归与迭代的复杂度为 O(1.4 n log(n))，使用基于计数的扫描来拆分列表，而不是龟兔赛跑方法。

对于递归版本，使用龟兔赛跑的方法相对较慢，可以通过使用节点计数来改进，如果链表容器不维护计数，则可能需要一次性扫描 n 个节点节点（例如 C++ std::list::size()）。这减少了在链表运行.

中途推进单个指针（子计数 / 2）的开销

示例 C/C++ 代码：

Time taken to sort numbers in Linked List

但是，在这种情况下（大列表，节点分散），将数据从列表复制到数组中，对数组进行排序，然后从排序后的数组创建一个新的排序列表会更快。这是因为数组中的元素是按顺序合并的（不是通过随机链表下一个指针），这是缓存友好的。

Answer 2

在自上而下的合并排序中，找到拆分列表的位置所花费的时间与要拆分的列表的长度成正比。在每个递归级别，这些的总时间与所有子列表的长度成正比，即：与原始列表的长度成正比。递归级别的数量是 log2(length(L)) 所以拆分列表所涉及的总时间复杂度是 O(length(L) * log2(length( L))) 与合并阶段相同的复杂性。

在自下而上的合并排序中，列表一次拆分一个元素，这个单例要么存储到子列表数组的第一个元素中，要么与其合并存储到第二个元素中，等等。因此拆分list 只增加了线性时间，这就解释了为什么自下而上的合并通常比自上而下的合并更快。影响实现效率的其他因素是缓存友好性，这通常在自下而上和平衡长度上更好，这在自下而上的归并排序中更难实现。

下面是列表的自下而上合并排序的简单示例：

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct list {
    struct list *next;
    int value;
} list;

list *list_merge(list *a, list *b) {
    list *head, **tailp = &head;
    while (a && b) {
        if (a->value <= b->value) {
            *tailp = a;
            a = a->next;
        } else {
            *tailp = b;
            b = b->next;
        }
        tailp = &(*tailp)->next;
    }
    *tailp = a ? a : b;
    return head;
}

list *list_mergesort(list *p) {
    list *a[sizeof(size_t) * CHAR_BIT];
    list *e;
    size_t i, top = 0;

    while (p) {
        e = p;
        p = p->next;
        e->next = NULL;
        for (i = 0;; i++) {
            if (i == top) {
                a[top++] = e;
                break;
            }
            if (a[i] == NULL) {
                a[i] = e;
                break;
            }
            e = list_merge(a[i], e);
            a[i] = NULL;
        }
    }
    e = NULL;
    for (i = 0; i < top; i++) {
        e = list_merge(a[i], e);
    }
    return e;
}

list *list_append(list **headp, int value) {
    list *e = malloc(sizeof *e);
    if (e) {
        e->next = NULL;
        e->value = value;
        while (*headp)
            headp = &(*headp)->next;
        *headp = e;
    }
    return e;
}

void list_print(list *e) {
    while (e) {
        printf("%d%c", e->value, " \n"[!e->next]);
        e = e->next;
    }
}

void list_free(list *head) {
    while (head) {
        list *e = head;
        head = head->next;
        free(e);
    }
}

int main() {
    list *head = NULL;
    for (int i = 0; i < 10; i++)
        list_append(&head, rand());
    head = list_mergesort(head);
    list_print(head);
    list_free(head);
    return 0;
}

归并排序分步时间复杂度应用于链表

Time complexity of divide step in merge sort applied to linked list

algorithm

mergesort

linked-list