如何计算这段统计链表节点数的C代码的时间复杂度（Big O）？

先看你提供的C代码：

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);
}

核心思路：Big O看的是「操作次数随输入规模的增长趋势」 #

这里的输入规模就是链表的节点总数，我们记为n。分析时只关注最影响趋势的部分，忽略常数、单次执行的操作。

逐部分拆解代码： #

• 初始化count、ptr，还有空链表的判断，这些都是常数时间操作（O(1)）——不管链表有1个还是1000个节点，这些步骤都只执行1次，对整体趋势没影响。
• 关键是while循环：
  • 每次循环会处理1个节点，然后把指针移到下一个节点，直到遍历完所有节点。
  • 如果链表有n个节点，这个循环就会执行n次——每多1个节点，循环就多跑1次。
  • 循环里的count++和ptr = ptr->link也都是O(1)的操作，每次循环的操作次数是固定的。

最终时间复杂度 #

总操作次数可以简化为「常数 + n×常数」，根据Big O的规则，我们忽略常数项，只保留和输入规模直接相关的部分，所以这段代码的时间复杂度是O(n)（线性时间复杂度）。

另外要说明：Big O的分析逻辑和编程语言无关，你在Java中学的规则完全可以直接用到C代码上，核心都是看输入规模和操作次数的增长关系。

内容的提问来源于stack exchange，提问作者ashahmi