c - 如何将插入排序转换为 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*log n 通过转向更快的数据结构，例如平衡二叉树。

这将意味着将线性的 while 循环搜索替换为二叉树中的搜索(logn)。