我在一个单链表中编写了一个队列方法的代码，我想知道是否有人可以告诉我这个代码的大O。我一开始假设它是O(n)因为有循环。然而，循环将始终迭代特定次数，这取决于列表中有多少项。这让我相信它实际上是O(1)我错了吗?
public Node<T> enqueue(T data){
Node<T> toQueue = new Node<>(data);
if (this.head == null) {
this.head = toQueue;
return toQueue;
}
Node<T> lastNode = this.head;
while(lastNode.next != null){
lastNode = lastNode.next;
}
lastNode.next = toQueue;
return toQueue;
}
让我们从下面这个问题的节选开始:
然而，循环将始终迭代特定次数，这取决于列表中有多少项。
这是一个正确的语句。
请注意对输入大小的依赖:
迭代特定次数取决于列表中有多少项
因此，该算法具有线性时间复杂度-O(n)。
线性时间复杂度
时间复杂度:Linear_time - Wikipedia:算法的线性时间为如果时间复杂度为
O(n)，则为O(n)时间。非正式地说，这意味着运行时间最多与输入的大小呈线性增长。更准确地说，这意味着存在一个常数c，使得对于每个大小为n的输入，运行时间最多为cn。例如，如果添加时间是常数，或者至少有一个常数，那么将列表中所有元素相加的过程所需的时间与列表的长度成正比。
从文章中稍微重新格式化的摘录:大O符号:公共函数的顺序-维基百科:让我们参考相应的行:
符号:
O(n)线性名称:
示例:在未排序的列表或未排序的数组中查找项;用纹波进位
加两个n位整数
然而，循环将始终迭代特定次数，这取决于列表中有多少项。这让我相信它实际上是0(1)。
我错了吗?
你的推理是错误的。
算法的复杂度分析需要考虑所有可能的输入。
虽然在循环时可以假定单个给定列表中的元素数为常量，但任何列表中的元素数都不是常量。如果考虑所有可能作为算法输入的列表，列表的长度是一个变量，其值可以任意大1。
如果我们称这个变量为N，那么很明显你的算法的复杂度类是O(N)。(我就不细说了，因为我想你已经了解了。)
你的推理可能是半正确的唯一方法是，如果你可以明确地声明输入列表长度小于某个常数L。然后复杂度类将分解为O(1)。然而，即使这个推理是可疑的2，因为所写的算法没有检查该约束。它无法控制列表的长度!
另一方面，如果您将算法重写为:
public static final int L = 42;
public Node<T> enqueue(T data){
Node<T> toQueue = new Node<>(data);
if (this.head == null) {
this.head = toQueue;
return toQueue;
}
Node<T> lastNode = this.head;
int count = 0;
while(lastNode.next != null){
lastNode = lastNode.next;
if (count++ > L) {
throw InvalidArgumentException("list too long");
}
}
lastNode.next = toQueue;
return toQueue;
}
，那么我们可以合理地说该方法是O(1)。它要么给出一个结果，要么在常量时间内抛出一个异常。
1 -我忽略了这样一个事实:在Java程序中，像这样的简单链表的长度是有实际限制的。如果列表太大，它将无法放入堆中。堆的大小是有限制的。
2 -一个更数学合理的方式来描述这种情况是，你的算法是O(N)，但你使用的算法是O(1)，因为调用代码(未显示)强制列表长度的界限。