链表实现的时间复杂度差异（迭代VS递归）？

Question

在这两种获取 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);}

Answer 1

不，时间复杂度不会改变。

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

Answer 2

TL;DR：同样的复杂性

要计算操作的复杂性（例如搜索或排序算法 - 或者您的示例，计数），您需要确定主导操作。

对于搜索和排序，通常是比较。你的主导业务是什么？假设它是node.next，查找下一个节点。

然后，这两种方法都有O(n)操作 - 所以它的复杂性相同。

请注意，这个时间复杂度是一种简化。有一些因素被忽略了，比如函数调用的开销。因此，它具有相同的复杂性，但这并不一定会告诉您哪个版本更快。