求解给定算法的时间复杂度，对循环复杂度判断存疑

先把代码逻辑拆解清楚：

1. for循环部分：从i=1遍历到n，一共执行n次，这部分时间复杂度是O(n)，这个判断没问题。
2. while循环部分：关键看k的初始值——for循环结束后i的值是n+1，所以k的初始值就是n+1，循环条件是k < 10。

分两种情况看while循环：

• 如果n+1 >= 10（也就是n >=9），while循环条件直接不成立，一次都不执行，时间复杂度是O(1)。
• 如果n+1 <10（也就是n <=8），k初始是小于10的数，每次循环里k先加1再乘2，增长速度是指数级的，最多执行3次就会让k >=10（比如初始k=1：第一次循环后k=(1+1)*2=4；第二次(4+1)*2=10，循环结束；初始k=8：第一次(8+1)*2=18，直接结束）。不管n是1还是8，循环次数都是固定的常数，和n的大小无关，所以这部分还是O(1)。

所以while循环的时间复杂度是常数时间O(1)，根本不是O(log n)——O(log n)要求循环次数随n增大而对数级增加，但这里不管n怎么变，while循环要么不执行，要么执行固定几次，完全和输入规模n无关。

整个算法的总时间复杂度就是O(n) + O(1) = O(n)，你的最初判断是对的。

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