我如何找到这个的时间复杂度（大O）

Question

void count_of_nodes(struct node*head) {
    int count = 0;
    if(head==null)
            printf("Linked List is empty");
    struct node*ptr = NULL;
    ptr = head;
    while(ptr != NULL) {
        count++;
        ptr = ptr->link;
    }
    printf("%d", count);
}

我不熟悉计算 C 程序的 Big O 表示法。此外，我对 Big O 表示法很陌生，因为我目前正在 Java 中学习它。请帮助我了解如何确定所提供的 C 代码的 Big O 表示法，该表示法计算链表中的节点数。非常感谢您的指导！

Answer 1

您确定昂贵的操作是什么。 在这种情况下，它正在追逐指针

ptr = ptr->link

。 然后你算出你做了这个操作多少次。 在具有

n

元素的链表中，发生

n-1

次，即

O(n)

。