while循环的Big-O？

Question

如何解决这个包含 while 循环的 Big-O 问题，该循环遍历节点并递增长度，只要它不等于 null 即可？这只是 O(N) 因为它经过 N 个节点吗？另外，while 循环中的语句只是 O(1)，对吗？

/**
*@param head the first node of the linked list 
*@return the length of the linked list
*/
public static <E> int getLength(Node<E> head) {
    int length = 0; 
    Node<E> node = head;
    while (node!=null) {
        length++;
        node = node.next; 
    }
    return length;
}

Answer 1

正如你所说，链表的遍历需要 O(N)，因为你需要遍历每个节点一次。

赋值运算符的复杂度为 O(1)，因为每次只需执行一次。

while循环的Big-O？

Big-O for while loop?

big-o

linked-list