链表实现的时间复杂度差异(迭代VS递归)?

在这两种获取 Linkedlist 中节点数的实现中,时间复杂度是否会发生变化?


 private int getCountIterative() {


    Node start = head;

    int count = 0;

    while (start != null)

    {

        count++;

        start = start.next;

    }

    return count;

}



private int getCountRecursive(Node node) {

    if (node == null)

        return 0;

    return 1 + getCountRecursive(node.next);

}


阿晨1998
浏览 166回答 2
2回答

温温酱

不,时间复杂度不会改变。然而,递归解决方案的性能和整体运行时间通常会更差,因为 Java 不执行Tail Call Optimization。

慕姐4208626

TL;DR:同样的复杂性要计算操作的复杂性(例如搜索或排序算法 - 或者您的示例,计数),您需要确定主导操作。对于搜索和排序,通常是比较。你的主导业务是什么?假设它是node.next,查找下一个节点。然后,这两种方法都有O(n)操作 - 所以它的复杂性相同。请注意,这个时间复杂度是一种简化。有一些因素被忽略了,比如函数调用的开销。因此,它具有相同的复杂性,但这并不一定会告诉您哪个版本更快。
打开App,查看更多内容
随时随地看视频慕课网APP

相关分类

Java