如何确定包含循环的递归函数的时间复杂度？

Question

我正在尝试解决LeetCode问题143。重新排序列表：

您将获得一个单链表的头。该列表可以表示为：

L₀ → L₁ → … → L_{n − 1} → L_n

将列表重新排序为以下形式：

L₀ → L_n → L₁ → L_{n − 1} → L₂ → L_{n − 2} → …

您不能修改列表节点中的值。只能更改节点本身。

这是我的尝试：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return; 
        }

        ListNode n1 = head;
        ListNode temp = null;

        while (n1.next.next != null) {
            n1 = n1.next;
        }

        temp = n1.next;
        n1.next = null;
        temp.next = head.next;
        head.next = temp;

        reorderList(temp.next);
    }
}

我无法对代码的时间复杂度提出具体的推理。我的大脑说 O(n^2) 但我无法证明原因。时间复杂度如何得出？

Answer 1

我的大脑说 O(n^2) 但我无法证明原因。

是的，是O(𝑛²)。

reorderList

的一次执行（不包括递归调用）将访问

while

循环中列表中的所有节点。因此，如果此时列表中有 𝑘 节点，则这将是 O(𝑘)。递归调用是使用具有 𝑘−2 个元素的列表进行的（因为

head

和

temp

位于传递给递归调用的引用“后面”）。这意味着我们有多次访问，进展如下：

𝑛 + 𝑛−2 + 𝑛−4 + ... + (1 或 2)

这大约是 𝑛/2 三角数的两倍，即 O(𝑛/2(𝑛/2+1)) = O(𝑛²)。

提高时间复杂度

可以用 O(𝑛) 时间复杂度解决这个问题。以下是一些剧透提示，可帮助您了解如何处理它：

提示1：

您能否操纵列表，以便从当前最后一个节点向后遍历列表变得更容易？

提示2：

反转链表的时间复杂度是多少？

提示3：

将列表分成两个列表有帮助吗？

剧透 O(𝑛) 解决方案：

class Solution {
     public ListNode getMiddle(ListNode head) {
         ListNode fast = head.next;
         while (fast != null && fast.next != null) {
             head = head.next;
             fast = fast.next.next;
         }
         return head;
     }

     public ListNode splitAfter(ListNode newTail) {
         ListNode head = newTail.next;
         newTail.next = null;
         return head;
     }

     public ListNode reverse(ListNode head) {
         ListNode prev = null;
         while (head != null) {
             ListNode next = head.next;
             head.next = prev;
             prev = head;
             head = next;
         }
         return prev;
     }

     public void zip(ListNode head1, ListNode head2) {
         if (head1 == null) return;
         ListNode head = head1;
         ListNode tail = head1;
         while (head1 != null && head2 != null) {
             head1 = head1.next;
             tail = tail.next = head2;
             head2 = head2.next;
             tail = tail.next = head1;
         }
     }

     public void reorderList(ListNode head) {
         if (head != null) {
             zip(head, reverse(splitAfter(getMiddle(head))));
         }
     }
 }