检查数组是否是另一个数组类的子数组的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");
}
所以这个程序会检查一个给定的数组,是否包含某个子数组。我的问题是,这个项目的时间复杂度是多少?我试着通过检查所有的语句来计算它,因为变量我可以重置,所以我看不出它是多项式还是线性的。
1条答案
按热度按时间vxf3dgd41#
时间复杂性是
O(n * m)
:从每个n
数组中的元素A
我们横穿m
下一个元素。如果按以下方式重写代码,则可以更轻松地看到此时间复杂性:
还有一个“坏”数组的例子,我们将对其进行最大迭代次数: