时间戳

首页 > 解决方案 > 如何计算这个程序的时间复杂度？（检查更大数组中的子数组）

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

问题描述

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

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

标签： javaarraystime-complexitysub-array

解决方案

时间复杂度是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]

推荐阅读