java - 递归函数的时间复杂度

Question

假设我使用以下代码来反向打印链接列表:

public void reverse(){
    reverse(head);
}

private void reverse(Node h){
    if(h.next==null){
        System.out.print(h.data+" ");
        return;
    }

    reverse(h.next);
    System.out.print(h.data+" ");   
}

链表以相反的顺序打印出来，但我不知道它是否有效。我如何确定这个函数的时间复杂度？有没有更有效的方法来做到这一点？

Answer 1

计算一般递归算法的时间复杂度是很困难的。然而，有大量可用资源。我将从这个 stackoverflow 问题开始 Time complexity of a recursive algorithm .

就该函数的时间复杂度而言，它是 O(n)，因为您调用了反向 n 次(每个节点一次)。没有任何更有效的方法来反转，甚至打印列表。问题本身要求您至少查看列表中的每个元素，根据定义，这是一个 O(n) 操作。