如何计算这个程序的时间复杂度？ （检查更大数组中的子数组）

Question

Java 检查一个数组是否是另一个数组的子数组的程序 class

// 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"); 
} 

因此该程序将检查给定数组是否包含某个子数组。我的问题是，这个程序的时间复杂度是多少？我试图通过检查所有语句来计算它，因为 变量 i 可以重置我不能为世界看到它的多项式或线性。

Answer 1

时间复杂度为O(n * m)：从数组A中的每个n个元素开始，我们遍历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]