在单链表时间复杂度中查找节点
Finding a node in singly linked list time complexity
我在 DSA 课程期中考试中遇到了这个问题：
考虑一个单链表包含 N 个节点（N > 8），方法 f1() 旨在
从头开始找到第 8 个节点，方法 f2() 旨在找到从头开始的第 8 个节点。
f1()和f2()的时间复杂度是多少？
Select一个：
一个。 O(N) 和 O(N)
b。 O(1) 和 O(1)
c。 O(1) 和 O(N)
d. O(N) 和 O(1)
给出的正确答案是c。 O(1) 和 O(N)。但是我认为正确答案是a。我知道如果 N = 8 从头开始找到第 8 个节点（只是 return 尾节点）需要 O(1) 时间，但在这种情况下 N > 8。有人可以为我解释一下吗？
提前感谢您提供的任何帮助。
O(1) 表示常数 运行 时间。换句话说，它不依赖于输入大小。
当您在此处应用该定义时，您会发现无论输入大小如何，获取第 8 个元素始终是一个常量操作。这是因为，无论输入的大小如何（例如：10,100,100..），操作 get(8) 将始终花费相同的时间。此外，由于我们确定 n > 8，因此尝试获取第 8 个元素不可能导致超出输入的大小。
我在 DSA 课程期中考试中遇到了这个问题：
考虑一个单链表包含 N 个节点（N > 8），方法 f1() 旨在 从头开始找到第 8 个节点，方法 f2() 旨在找到从头开始的第 8 个节点。 f1()和f2()的时间复杂度是多少？
Select一个：
一个。 O(N) 和 O(N)
b。 O(1) 和 O(1)
c。 O(1) 和 O(N)
d. O(N) 和 O(1)
给出的正确答案是c。 O(1) 和 O(N)。但是我认为正确答案是a。我知道如果 N = 8 从头开始找到第 8 个节点（只是 return 尾节点）需要 O(1) 时间，但在这种情况下 N > 8。有人可以为我解释一下吗？
提前感谢您提供的任何帮助。
O(1) 表示常数 运行 时间。换句话说，它不依赖于输入大小。
当您在此处应用该定义时，您会发现无论输入大小如何，获取第 8 个元素始终是一个常量操作。这是因为，无论输入的大小如何（例如：10,100,100..），操作 get(8) 将始终花费相同的时间。此外，由于我们确定 n > 8，因此尝试获取第 8 个元素不可能导致超出输入的大小。