如何计算这个程序的时间复杂度(在更大的阵列中检查子阵列)

qzlgjiam  于 2021-07-06  发布在  Java
关注(0)|答案(1)|浏览(322)

检查数组是否是另一个数组类的子数组的java程序

// Function to check if an array is 
// subarray of another array 
static boolean isSubArray(int A[], int B[],  
                               int n, int m) 
{ 
    // Two pointers to traverse the arrays 
    int i = 0, j = 0; 

    // Traverse both arrays simultaneously 
    while (i < n && j < m) 
    { 

        // If element matches 
        // increment both pointers 
        if (A[i] == B[j]) 
        { 

            i++; 
            j++; 

            // If array B is completely 
            // traversed 
            if (j == m) 
                return true; 
        } 

        // If not, 
        // increment i and reset j 
        else
        { 
            i = i - j + 1; 
            j = 0; 
        } 
    } 
    return false; 
} 

// Driver Code 
public static void main(String arr[]) 
{ 
    int A[] = { 2, 3, 0, 5, 1, 1, 2 }; 
    int n = A.length; 
    int B[] = { 3, 0, 5, 1 }; 
    int m = B.length; 

    if (isSubArray(A, B, n, m)) 
        System.out.println("YES"); 
    else
        System.out.println("NO"); 
}

所以这个程序会检查一个给定的数组,是否包含某个子数组。我的问题是,这个项目的时间复杂度是多少?我试着通过检查所有的语句来计算它,因为变量我可以重置,所以我看不出它是多项式还是线性的。

vxf3dgd4

vxf3dgd41#

时间复杂性是 O(n * m) :从每个 n 数组中的元素 A 我们横穿 m 下一个元素。
如果按以下方式重写代码,则可以更轻松地看到此时间复杂性:

for (i = 0..n - m)
  for (j = 0..m - 1)
    if (A[i + j] != B[j]) break
  if (j == m) return true  
return false

还有一个“坏”数组的例子,我们将对其进行最大迭代次数:

A = [a, a, a, a, a, a] 
B = [a, a, b]

相关问题