입니까?

Question

입력은 1의 수 (또는 없음)와 2의 수 (또는 없음)의 목록 L입니다. 아래 알고리즘은 1의 수를 찾습니다. 평균의 경우에있어서, L은, 단순히리스트를 이등분하여 O를 해소 할 수있는 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

문제를 함유 동등한 확률 (LOG2 (N))를 갖는 가정한다.

여기 알고리즘은 O (2sqrt (n)) 정도입니다.

Answer 2

이 루프는 p가 n에 도달하기 전에 sqrt (n) 번만 실행될 수 있습니다.

while p<n and L[p]=1 
    p+=m 
p-=m+1 

동일 결과

while p<n and L[p]=1 
    p+=1 
return p 

SQRT (N)를 이하 사용자의 복잡성 평균 (SQRT (N)) O이고, P 및 N의 차이 사람이 루프 사실 최악의 경우.