分析函数最坏时间复杂度（基于n），确认循环是否为O(N)

首先还原图片中的函数代码（基于图片内容整理）：

void function(int n) {
    int i = 0;
    while (i < n) {
        int j = i;
        while (j < n && arr[j] != 0) {
            j++;
        }
        i = j + 1;
    }
}

你的结论是正确的，该函数在最坏情况下的时间复杂度为O(n)，详细分析步骤如下：

1. 明确最坏场景 #

当数组arr中所有元素都不为0时，内层循环无法提前终止，这是该函数的最坏执行场景。

2. 统计执行次数 #

• 外层循环：初始i=0，第一次内层循环结束后，j会递增到n（因为j <n时arr[j]始终非0，触发内层循环退出条件），随后i被赋值为j+1 = n+1，此时外层循环的i <n条件不成立，外层循环仅执行1次。
• 内层循环：从j=0开始，每次递增1，直到j=n，总共执行n次判断与递增操作。

3. 推导时间复杂度 #

总操作次数与输入规模n呈线性关系，根据大O表示法的规则（忽略常数项与低阶项），该函数最坏情况下的时间复杂度为O(n)。

拓展补充 #

• 最好情况：数组第一个元素即为0，此时内层循环仅执行1次，外层循环也仅执行1次，时间复杂度为O(1)。
• 平均情况：假设0元素在数组中均匀分布，每个元素最多被访问1次，总操作次数仍为线性规模，时间复杂度为O(n)。

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