下述循环算法的运行时间复杂度是多少？是否为O(n)？

时间复杂度结论 #

你给出的这段算法的时间复杂度确实是O(n)。

推导依据 #

• 整个算法执行过程中，索引变量i始终单调递增，不存在回退逻辑。末尾的i--会抵消外层for循环下一次迭代开头的i++，不会出现重复访问已经遍历过的元素的情况。
• 无论是外层for循环还是内层while循环，每执行一次循环体都会让i加1，而i的取值范围最大是0到n-1，所有循环的总执行次数最多为n次，整体操作次数和输入规模n成线性正比。

对应的代码片段：

for(int i=0;i<n;i++){
    if(a[i]%10==0){
        temp=a[i];
        i++;
        while(a[i]%10!=0){
            a[i]=temp;
            i++;
        }
        i--;
    }
}

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