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

Question

在我的

学术论文中有人问过我这个问题。 请告诉我答案？

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

假设我们有一个算法，find2D( ) ，在二维中查找x元素 n x n阵列A .该算法find2D( )遍历A行，并在每行arrayFind()调用算法，直到找到x或搜索了所有A行。

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

一个。如果对每行中的元素进行排序？
b.如果每行中的元素未排序？

Answer 1

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

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