algorithm - 如何根据以下代码计算 Big-O Notation

Question

我已阅读主题:

Big O, how do you calculate/approximate it?

我不确定以下函数的 Big-O 表示法是什么:

static int build_nspaces_pattern(const char * const value, char *pattern,
        size_t sz_pattern) {
   static char    val_buffer[1025];
   char           *ptr, *saveptr;
   size_t         szptrn;
   ptrdiff_t      offset;

   val_buffer[0] = '\0';
   strncat(val_buffer, value, sizeof(val_buffer) - 1);
   val_buffer[sizeof(val_buffer) - 1] = '\0';

   pattern[0] = '^'; pattern[1] = '('; pattern[2] = '\0';

   for ( ptr=strtok_r(val_buffer, ",", &saveptr);
         ptr!=NULL;
         ptr=strtok_r(NULL, ",", &saveptr)
       ) {
      szptrn = sz_pattern - strlen(pattern) - 1;

      if ( sanitize(ptr) != 0 ) {
         return -1;
      }
      strncat(pattern, ptr, szptrn);
      szptrn -= strlen(ptr);
      strncat(pattern, "|", szptrn);
   }     

   offset = strlen(pattern);
   pattern[offset-1] = ')'; pattern[offset] = '$'; pattern[offset+1] = '\0';

   return 0;
}

Sanitize 是 O(n)，但是 for 循环将运行 k 次(k 是字符串中逗号的数量)。

所以，k * O(n) 仍然是 O(n)，它会是 O(n^2)、O(k.n) 还是其他？

谢谢。

Answer 1

对我来说，一目了然。

• strtok_r() 遍历原始字符串 = O(n)

• sanitize() 你说的是 O(n)，但这大概是关于 token 的长度而不是长度原始字符串的，因此将标记长度乘以标记数 = O(n)

• strncat() 最终复制了所有原始字符串，没有重叠 = O(n)

• 您将固定数量的字符附加到输出字符串 (^, (, ), $ 和几个 NULL) = O(1)

• 您将 | 附加到每个标记的字符串 = O(n)

但是等等!

• 您在输出模式上调用 strlen() 循环的每次迭代 = O(n^2)

这就是你的答案。