字符串匹配算法的大O表示法

Question

函数foo的大O符号是什么？

int foo(char *s1, char *s2)
{
   int c=0, s, p, found;
   for (s=0; s1[s] != '\0'; s++)
   {
      for (p=0, found=0; s2[p] != '\0'; p++)
      {
         if (s2[p] == s1[s])
         {
            found = 1;
            break;
         }
      }
      if (!found) c++;
   }
   return c;
}

函数foo的效率是多少？

a)O(n!)

b)O(n ^ 2)

c)O(n lg(base2)n)

d)O(n)

我会说O(MN)......？

Answer 1

它是O(n²)n = max(长度(s1),长度(s2))(可以在小于二次时间内确定 - 见下文).我们来看看教科书的定义:

f(n)∈O(g(n))如果存在正实数c和正整数N,则对于所有n> = N,f(n)<= cg(n)

通过这个定义,我们看到n表示一个数字 - 在这种情况下,该数字是传入的字符串的长度.但是,存在明显的差异,因为该定义仅提供单个变量函数,f(n)并且在这里我们明确地传入2具有独立长度的字符串 因此,我们搜索Big O的多变量定义.但是,正如Howell在"On Asyodotic Notation with Multiple Variables"中所证明的那样:

"不可能以暗示所有这些[通常假定的]属性的方式为多变量函数定义big-O表示法."

实际上有一个具有多个变量的Big O的正式定义,但是这需要超出单个变量Big O的额外约束,并且超出了大多数(如果不是全部)算法课程的范围.对于典型的算法分析,我们可以通过将所有变量绑定到限制变量来有效地将函数减少到单个变量n.在这种情况下,变量(具体地说,长度(s1)和长度(s2))显然是独立的,但可以绑定它们:

方法1

Let x1 = length(s1)
Let x2 = length(s2)

当没有匹配时,会出现此函数的最坏情况,因此我们执行x1*x2迭代.

因为乘法是可交换的,最坏的情况foo(s1,s2)== foo的最坏情况(s2,s1).因此,我们可以假设x1> = x2而不失一般性.(这是因为,如果x1 <x2,我们可以通过以相反的顺序传递参数来获得相同的结果).

方法2(如果你不喜欢第一种方法)

对于最坏的情况(其中s1和s2不包含公共字符),我们可以在迭代循环之前确定长度(s1)和长度(s2)(在.NET和Java中,确定字符串的长度是O (1) - 但在这种情况下它是O(n)),将较大的值分配给x1,将较小的值分配给x2.这里很清楚x1> = x2.

对于这种情况,我们将看到确定x1和x2的额外计算使得这个O(n + 2n)我们使用以下简化规则,这里可以简化为O(n²):

如果f(x)是几个项的和,则保留具有最大增长率的那个,并且省略所有其他项.

结论

对于n = x1(我们的限制变量),x1 >= x2最坏的情况是这样的x1 = x2.因此: f(x1) ? O(n²)

额外提示

对于发布到与Big O表示法相关的SO的所有作业问题,如果答案不是以下之一:

O(1)
O(log log n)
O(log n)
O(n^c), 0<c<1
O(n)
O(n log n) = O(log n!)
O(n^2)
O(n^c)
O(c^n)
O(n!)

然后问题可能最好发布到https://math.stackexchange.com/

Answer 2

在big-O表示法中,我们总是必须定义出现的变量意味着什么. O(n)除非我们定义什么,否则没有任何意义n.通常,我们可以省略这些信息,因为从上下文中可以清楚地看到它.例如,如果我们说某些排序算法是O(n log(n)),则n始终表示要排序的项目数,因此我们不必总是说明这一点.

关于big-O表示法的另一个重要的事情是它只给出一个上限 - 每个算法O(n)也在O(n^2).符号通常用作意思"算法具有由表达式给出的精确渐近复杂度(直到常数因子)",但它的实际定义是"算法的复杂性受给定表达式的限制(达到常数)因子)".

在你给出的例子中,你接受m并n成为两个字符串的相应长度.有了这个定义,算法确实如此O(m n).如果我们定义n为两个字符串中较长字符串的长度,我们也可以将其写为O(n^2)- 这也是算法复杂性的上限.并且使用相同的定义n,算法也是O(n!),但不是O(n)或O(n log(n)).