时间递归函数的复杂性

想我用下面的代码，以扭转打印链表：时间递归函数的复杂性

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+" "); 
}

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

来源

2015-11-28 idude

假设您的列表有n个元素。对reverse(Node)的每次调用都会通过一个元素减少列表的长度。因此效率是O（n），这显然是最优的：如果不考虑所有元素，就不能反转列表。

来源

2015-11-28 14:52:43 NietzscheanAI

您可以使用递归树或只是展开T（n）。两者基本上都是相同的方法。你在做什么是扩大递归函数，记下它每次在堆栈中调用它时会做什么。

例如，每次调用函数时，它都会执行一些常量时间（打印数据），然后递归。因此，扩大它，你会得到： = d + d + T（n-2）T（n）= d + T（n-1）{因为一次递归完成，，直到它fizzes out.So你的功能将继续高达的list.Hence复杂的长度，它会继续下去了，O（n）的看看这个：Time complexity of a recursive algorithm

来源

2015-11-28 14:50:40 kneelb4darth

计算时间的递归算法复杂，一般是硬。但是，有很多可用的资源。我会从这个计算器问题Time complexity of a recursive algorithm开始。这个函数的时间复杂度是O（n），因为你调用n次（每个节点一次）。没有更有效的方法来扭转甚至打印清单。问题本身要求您至少查看列表中的每个元素，根据定义，这是O（n）操作。

来源

2015-11-28 14:51:02

时间递归函数的复杂性

回答

相关问题