如何知道这个 while 循环是 O(n) 还是 O(1)？

Question

我的任务是编写一个 return 自制链表长度的方法。该方法必须在常数时间 O(1) 内。我的想法是始终将计数器加 1，即链表中的节点不为空并且根本不会弄乱列表的大小以避免 O(n)。

我的代码：

public int getLength() {
    // TODO Code hier einfÃ¼gen
    
    if (headNode == null) {
        return 0;
    } 

    int count = 0;
    while (headNode != null)
    {
        count++;
        headNode = headNode.next;
    }
    return count;
}

我的代码是常数时间 O(1) 吗？如果不是，您将如何在 O(1) 中为链表创建长度方法？

Answer 1

你的代码是O(n)。如果已经装箱并且必须遍历它，则无法在 O(1) 中获得链表的长度。要获得 O(1) 中的长度，您可以做的是保留一个变量，该变量将在列表中插入节点时递增，而在从列表中删除节点时递减。

要了解任何代码的复杂性，您必须查看循环。假设列表的大小为 n。如果代码中有一个从 1 到 n 的循环，则复杂度为 O(n)，类似地，如果第一个循环中还有另一个嵌套循环也从 1 到 n，则复杂度为 O(n^2 ).如果代码中没有循环，这意味着它的复杂度是 O(1).

我希望这能回答你的问题。

Answer 2

你的代码是 O(n) 因为你至少要遍历链表的所有节点一次。要解决问题的第二部分，有两种方法可以完成：

定义一个静态变量length，每次从列表中添加或删除元素时，都必须更新此变量。
更改节点的结构以存储每个节点的索引或在头节点中保留一个额外的指针长度来跟踪链表的长度。

希望这对您有所帮助.. 编码愉快 :)

如何知道这个 while 循环是 O(n) 还是 O(1)？

How to know if this while loop is O(n) or O(1)?

java

time-complexity

complexity-theory