什么是最坏的时间复杂度为2D模式匹配使用蛮力算法?
我觉得如果草堆大小=n针大小=m(都是正方形),就等于0(m^2*n^2)。
我得到的方法是在m=2和n=4时使用一个简单的案例场景如果我们在行中水平移动(匹配haystack中的m x m字符),我们将进行m^2字符串比较(n-1)次。我们垂直重复(n-1)次。所以,时间=m^2(n-1)x(n-1)=m^2*n^2-2*m^2*n+m*2=o(m^2*n^2)。
这个分析正确吗?是o(m^2*n^2)还是o(m^2*n^2-2*m^2*n+m*2)?
编辑:我只是比较字符串的两个矩阵或者类似于两位矩阵的东西。例子:
haystack = [["a", "b", "c", "d"],
["e", "f", "g", "h"],
["i", "j", "k", "l"],
["m", "n", "o", "p"]]
needle = [["j", "k"],
["n", "o"]]
最佳答案
要匹配2个2d数组,要查找所有子数组,我认为是m*n*o*p(如果第一个数组是m*n,第二个数组是o*p),以确定是否有任何单个字符匹配。然后我会说,你需要乘以较大数组的维数,因为这会给你可能的子数组的数量。但是,毫无疑问,有一种比暴力方法更聪明的方法,它从最小的匹配子数组开始,并智能地扩展它,可能使用动态编程。我将研究子串匹配算法,因为这是类似的,但在二维。
关于algorithm - 2D模式匹配的最差时间复杂度,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/22546325/