performance - 算法的最差和平均复杂度？

Question

输入是一个列表 L，其中包含多个 1(或无)，后跟多个 2(或无)。下面的算法找到 1 的个数。对于一般情况，假设 L 包含 1 的机会均等。

A(L):
     n=L.length
     m=sqrt(n)
     p=m-1
     while p<n and L[p]=1
         p+=m
     p-=m+1
     while p<n and L[p]=1
         p+=1
     return p

Answer 1

只需将列表平分即可解决 O(log2(n)) 问题。

至于你这里的算法，它的复杂度大约是 O(2sqrt(n))。