如何将插入排序转换为 O(n logn) 算法？

Question

我编写了以下函数，它在创建排序的字符串序列时计算字符串的重复实例。然而它很慢，然后我意识到这是 O(n^2)。所以我想把它变成 O(n logn) 但我不知道如何进行。有没有已知的方法可以将这种 n^2 算法转换为 nlogn？应该怎么转换？

void insert (struct listNode **ptr, char *value) {
    struct listNode *newPtr;
    int cmp;

    // find a place to instert node to LL
    while(*ptr){
        // Comparision to detect & remove duplicates nodes

        cmp = strcmp(value, (*ptr)->data);
        // duplicate
        if(cmp == 0){
            (*ptr)->occurrence++;
            return; 
        }
        // the point where i need to add the node
        if(cmp < 0) 
            break;

        ptr = &(*ptr)->next;
    }

    // now here *ptr points to the pointer that i want to change
    // it can be NULL, if we are at the end of the LL

    newPtr = malloc(sizeof *newPtr);
    if(!newPtr)
        return;

    newPtr->data = strdup(value);
    newPtr->occurrence = 1;

    if(newPtr->data == NULL){
        free(newPtr);
        return;     
    }

    // here we are connecting our brand new node to the LL
    newPtr->next = *ptr;
    *ptr = newPtr;
}

struct listNode {
    char *data;
    struct listNode *next;
    int occurrence;
};

Answer 1

Are there any known methods for converting such n² algorithm to n*logn?

在你相乘的两个 n 之一来自访问线性数据结构的情况下，例如你的链表，你可以改进为 n*logn 通过转向更快的数据结构，例如平衡二叉树。

这将转化为用二叉树中的搜索替换线性的 while 循环搜索，即 logn。

Answer 2

插入排序是一种单独的排序技术。如果你convert(according complexity)这个，那将是另一种排序技术。我觉得这篇linkSorting Algorithm对你find different type complexity of sorting technique有帮助。

Answer 3

插入排序的最坏情况时间为 O(N2)。我建议使用另一种具有 Theta(n lg n) 时间复杂度的算法，例如合并排序，而不是尝试更改 stable 算法的时间复杂度。

让我们获取一些有用的信息，这些信息可能会帮助人们了解如何将此类问题的时间复杂度降低到 Theta(n lg n)。

通常，您可以使用分治法将排序问题的时间复杂度降低到 Theta(n lg n)。

让我们一起来了解这个算法设计范式

分而治之

这个想法是，如果你将一个敌人分成小块，那么每个小块，以及敌人，都可以被征服。当应用于计算机问题时，分而治之涉及三个步骤。

将问题分解成与原问题相似但规模更小的子问题
通过递归的方式解决子问题。如果足够小，直接解决就可以了。
结合解决方案创建原始问题的解决方案

使用分而治之进行排序

事实证明这很容易，以至于令人惊讶的是它是渐近最优的。关键观察是合并两个排序列表很快（时间与列表大小成线性关系）。步骤为

除法（带停止条件）：如果 S 有零个或一个元素，则简单 return S 因为它已经排序。否则 S 有 n≥2 个元素：将 S 的前 ⌈n/2⌉ 个元素移动到 S1 中，将剩余的 ⌊n/2⌋ 元素移动到 S2.
递归求解：对两个子序列分别进行递归排序。
合并：将两个（现在已排序的）子序列合并回 S

运行归并排序的时间T(n)

除法： 计算中间值 Theta(1)
征服：解决2个子问题需要2T(n/2)
合并： 合并 n 个元素需要 Theta(n) 总计：

T(n) = Theta(1) 如果 n = 1 T(n) = 2T(n/2) + Theta(n) 如果 n > 1

=> T(n) = Theta(n lg n)

有关更多信息和示例，请查看此 link。

Answer 4

通常，您不会通过修改现有算法来提高其复杂性，而是从一开始就将其设计为高效。无论如何，让我们玩这个游戏吧。

该算法的工作原理是保留一个N个元素的列表，按排序顺序排列，并将剩余的元素一个一个地合并。这种方法的缺点是插入成本高，涉及对排序列表进行线性搜索，O(N)，排序总共 O(N²)。

众所周知，通过二分查找可以更有效地及时 O(Log(N)) 完成对排序列表的搜索。不幸的是，这适用于数组（用于随机访问），但数组需要 O(N) 时间进行插入。很久以前就发现解决这个难题的方法是（平衡的）二叉树数据结构，它允许快速搜索和快速插入。

另一种不太明显的查看问题的方法是尝试减少插入遍数。实际上，如果您一次插入多个元素，并且将这些元素按排序顺序排列，则可以一次性完成插入：这称为合并操作。

如@ChakerMallek 所详述，如果将列表分成两半，分别对它们进行排序，全局排序相当于合并，及时完成 O(N)。两个子列表的排序可以递归完成，从而导致众所周知的 MergeSort，非常适合链表表示并且效率最高。它甚至可以调整为在接近排序的列表上更快。

Answer 5

如果我没看错的话，你使用的是插入排序，其复杂度为 O(n^2)。但是，如果您在查找阶段（while 循环）切换到二分查找，则可以在 O(nlogn) 中完成。

如何将插入排序转换为 O(n logn) 算法？

How to convert insertion sort to an O(n logn) algorithm?

c

sorting

algorithm

insertion-sort