一个面试题，大家评评理

[gps949]

这两天去水了个面试，瞎写了一段代码，姑且不论这段代码能不能实现目标，面试现场 N 个面试官一位很牛逼哄哄地说：这个按理说 O(n)就可以了，你这两个遍历，都 O(n^2)了。
我简单解释两句说内层并不是完整遍历而是在计算连续 0 的长度后会把外层指针 i 移动过这一段，所以本质上还是近似算 O(n)的。
然后那个面试官又一脸不屑的说：你这两层遍历再怎么也不会是 O(n)，最多算 O(logn)，你回去再好好想想。
然后我无奈：好的。

下面是代码（只是近似，毕竟也没带出来材料）

a=[1,0,1,0,0,0,1,0,0,1,1,1,0,0,0,0,1,0,1,0]
for (i=0;i<a.length;i++) {
    if (a[i]==0) {
        j=i+1;
        for (;j<a.length && a[j]==0;j++) {}
    
        //此处省略一通利用 i 和 j 的判断运算（没有对 i 或 j 的值的改变，也没有任何循环）
    
        i=j+1
    }
}

[reter]

个人感觉也是 O(n). 说明 面试官 根本没有仔细看你的逻辑，认为有两个循环就是 O(n^2)

[theguagua]

确实是 O(n)，对于数组 a 中的每个元素，只需进行常数时间的操作，没有嵌套循环。

[ulala]

「你这两层遍历再怎么也不会是 O(n)，最多算 O(logn)」这面试官是不是对这两个复杂度的大小有误解，还是你说错了

[akaxiaok339]

问 AI 说是 O(n)

[pipasese]

面试官不行，不去也罢

[hefish]

在乎别人是好事，太在乎容易进入怪圈。。面试官也就是比你多吃几年萝卜干饭，过几年说不定面试官也要失业，到时候说不定就是你面试他了。

[hello2090]

看半天没看懂，觉得面试官说的没错啊。算法复杂度肯定不是说在某一个特定输入下，你这个两层循环为啥不是 n^2?

[ibinary]

外层 for 循环遍历数组 a 一次,时间复杂度 O(n)
内层 for 循环找到下一个不为 0 的元素,时间复杂度 O(m),其中 m 为 0 的元素个数
由于 m<n,所以内层 for 循环的时间复杂度可以看作 O(1)
结合外层 for 循环,总时间复杂度为 O(n)*O(1)=O(n)

[dem0ns]

这得根据 a 的值来看吧，a 全为 0 的时候也不是 O(n)啊，对于#4 的 AI ，我试了，刚开始给的答案也是 O(n)，后来纠正为 n^2 的


```
我对之前的回答有误解，请接受我的道歉。如果数组 a 的值全部为 0 ，那么内层循环无法找到下一个非零元素的意思是，由于数组中所有元素都是 0 ，内层循环的条件 a[j] == 0 永远为真，内层循环会一直执行直到 j 超出数组范围。

在这种情况下，代码的时间复杂度为 O(n^2)，其中 n 是数组 a 的长度。

外层的 for 循环会遍历整个数组 a ，这需要执行 n 次循环。

内层的 while 循环会在每次遇到 a[i] == 0 的情况下执行，并且会一直向后搜索直到找到下一个非零元素或者到达数组末尾。由于数组中所有元素都是 0 ，内层循环会执行 n - i 次，其中 i 是外层循环的迭代变量。

因此，总的时间复杂度是 O(n * (n - i))，即 O(n^2)。
```

[dem0ns]

https://www.baidu.com/s?wd=时间复杂度是按照是坏情况吗

[C47CH]

明显是 O(N)，O(logN)咋想的，怕不是有什么误解。

[xenme]

@dem0ns 你看最后还有一个 i=j+1

[ViriF]

O(logN)还有这种好事？也没排过序啊......

[dem0ns]

@xenme 我知道，但是复现后不符合 O(n)

if __name__ == '__main__':
count = 0
a = [0, 0, 0, 0, 0, 0, 0, 0]
print(len(a))
for i in range(len(a)):
if a[i] == 0:
j = i + 1
while j < len(a) and a[j] == 0:
count += 1 # 计数
j += 1 # j++
print(count, end=" ")
i = j + 1


把数组 a 依次添 0 ，得到的 count 为 3 ，6 ，10 ，15 ，21.....

O(n)应该是均匀递增才对？ （这里需要指教下）

[dem0ns]

对于#9 的补充，我不认同 O(n^2)，但也对 O(n)持怀疑

[grance]

O(nlogn)

[msg7086]

@dem0ns #14
for i in range(len(a))
与原题
for (i=0;i<a.length;i++)
不等价。

[GeruzoniAnsasu]

没去成是好事


还 logn ，与 n 比哪个更快都搞不清；就算他说的是 nlogn ，算法里的 log 都是以 2 为底的，logN 这个多项式代表「能在 N 次二分内找到目标」，其必定会对应某种分治思路。这算法里根本就没有分治，无论如何都凑不出 log

[dem0ns]

@msg7086 #17
确实忘记加了，但在 a 全为 0 的时候不影响结果

[qzeng2017]

虽然没看题目是什么，但是看你写的这个循环代码就不行，不仅容易出错，看的人也吃力，这种算法题基本都可以用很优雅的循环或者别的方式解决