给定算法的最坏情况运行时间是多少

Question

我在学术论文中被问到过这个问题。请告诉我答案？

 arrayFind(x, A)
    i =0 ;
    while( i < n ) {
       if(x==A[i])
           return i;
       else 
           i = i+1; 
   }
 return –1;

假设我们有一个算法，find2D（ ），在二维n x n数组A中查找元素x。算法 find2D（ ） 循环访问 A 的行，并在每个行上调用算法 arrayFind（），直到找到 x 或搜索了 A 的所有行。

这个算法最坏的运行时间是多少

一个。如果每行中的元素都已排序？
（二）如果每行中的元素未排序？

Answer 1

在给定信息的情况下，排序/不排序对最坏情况没有影响。在这两种情况下，最坏的情况是，最新行中的最新元素是要查找的元素。在这种情况下，运行时将是O（n^2），其中n具有您用nxn指出的含义。这是nxn，因为您必须迭代n行，然后在每行中进行n比较。

如果使用二进制搜索，则排序后的示例的最坏运行时为O（n log n），最坏情况是，搜索的元素位于最后一行的中间。