loops - 循环中线性搜索的时间复杂度？

Question

 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登录）？

标签： loopstime-complexitynested-loopslinear-search

Answer 1

有 ：

• 第一个循环的 n 次迭代
• 第二次的 log(n) 次迭代

该程序将调用 Linear_search nlog(n) 次。

线性搜索的复杂度为 O(n)，程序的复杂度为 O(n^2log(n))