findShortestSublist函数时间复杂度分析：O(n²)还是O(n)？

先看你提供的函数代码：

static void ListInsert(List l, int value);

List findShortestSublist(List l, int start, int end) {
    Node curr = l -> first;
    Node startNode = NULL;

    List shortest = ListNew();

    while (curr != NULL) {
        if (curr -> value == start) {
            startNode = curr;
        }

        if (curr -> value == end) {
            if (startNode != NULL) {
                Node curr2 = startNode;
                while (curr2 != curr) {
                    ListInsert(shortest, curr2 -> value);
                    curr2 = curr2 -> next;
                }
                ListInsert(shortest, curr -> value);
                return shortest;
            }
        }
        curr = curr -> next;
    }

    return shortest;
}

static void ListInsert(List l, int value) {
    // Inserting List function that was used.
    Node n = newNode(value);
    if (l -> first == NULL) {
        l -> first = n;
        l -> last = n;
    } else {
        l -> last -> next = n;
        l -> last = n;
    }
}

时间复杂度分析 #

这个函数的时间复杂度是O(n)，原因如下：

• 外层while循环遍历链表节点，虽然存在嵌套的内层while循环，但内层循环只会被执行一次：一旦找到第一个匹配end且之前存在匹配的start节点时，内层循环会遍历从startNode到当前curr的节点，完成插入后直接return，外层循环不会继续执行。
• 整个过程中，所有循环的总执行次数是线性的：外层循环最多走n步（n是链表总节点数），内层循环最多走n步，但两者的总步数不会超过2n，属于O(n)量级。
• 辅助的ListInsert函数每次插入操作都是O(1)，因为维护了链表的last指针，不需要遍历链表找尾节点，插入操作的时间开销不会影响整体的线性复杂度。

你之前担心的O(n²)是嵌套循环重复执行的场景，但这个函数里嵌套循环只会触发一次，所以不会出现平方级的时间开销。

内容的提问来源于stack exchange，提问作者Dunkle Nacht