худшая и средняя сложность алгоритма?

Question

Ввод - это список L числа 1 (или none), за которым следует число 2 (или none). В приведенном ниже алгоритме найдено число 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)).

Answer 2

Этот цикл может быть выполнен только sqrt (n) раз до того, как p достигнет n.

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

То же самое справедливо и для этого цикла, так как разница между р и п меньше, чем SQRT (п)

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

В результате ваша сложность O (SQRT (п)) в среднем и в худшем случае.