java - 用于在 Java 中反转 LinkedList 的 BIg-Oh

Question

请告知这两种情况下的 Big-O 是什么。我知道基本情况将是常量 O(1)，但我对如何计算其余部分和递归感到困惑。

案例#1

public ListNode reverse1(ListNode list) {
    if (list == null || list.next == null) {
        return list;
    }
    ListNode after = reverse(list.next);
    list.next.next = list;
    list.next = null;
    return after;
}

案例#2

public ListNode reverse2(ListNode list) {
    if (list == null || list.next == null) {
        return list;
    }
    ListNode after = reverse2(list.next);
    ListNode temp = after;
    while (temp.next != null) {
        temp = temp.next;
    }
    temp.next = list;
    list.next = null;
    return after;
}

Answer 1

在你的第一种情况下递归给出:

T(n) = T(n-1) + c 

其中 T(n) 是 n 个节点的总步骤，为了反转 n 个节点，你只需反转 n-1 T(n-1) 并通过执行花费 c 的常量操作添加第 n 个节点(常量值无关紧要)。

上面的递归关系很容易看出:

T(n) = T(n-1) + c = T(n-2) + 2c =...= nc = O(n)

在你的第二种情况递归给出:

T(n) = T(n-1) + n + c 

那是因为为了反转 n 个节点，您在 T(n-1) 中反转了 n-1 并遍历列表以便将节点放在花费 n 的结束和花费最多 c 的恒定操作(c 无关紧要)。

上面的递归关系很容易看出:

T(n) = T(n-1) + n +c = T(n-2) + n + (n-1) + 2c =...= n(n-1)/2 +nc = O(n^2)