Блог

  For I=1 to n
     For J=1 to n 
         k = b[I]
         F = Linear_search(a,k)
         Print F
      J=J*2
 

Какова будет временная сложность описанного выше алгоритма? Я думал, что это будет O(nlogn), но в алгоритме также есть линейный поиск, который имеет сложность O(n).Итак, какова будет сложность O(nlogn) или O(n), или это будет O(n^2 logn)?

Есть :

• n итераций для первого цикла
• протоколируйте(n) итераций для второго

Программа вызовет Linear_search nlog(n) раз.

Сложность линейного поиска составляет O(n), тогда сложность программы будет O(n^2log(n))