我读过的主题：

大O，你怎么计算/近似它？

和我不知道以下功能大O符号是：

And am not sure what the Big-O notation for the following function would be:

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

消毒是O（n），但对于回路将运行k次（k是逗号的字符串中的数字）。

Sanitize is O(n), but the for loop will run k times (k is the number of commas in the string).

所以，K *为O（n）仍然是O（N），会是为O（n ^ 2），O（KN），还是其他什么东西？

So, k * O(n) is still O(n), would it be O(n^2), O(k.n) or something else?

感谢。

推荐答案

看起来为O（n）对我来说，一目了然。

strtok_r（）通过原始字符串迭代= O（N）

strtok_r() iterates through the original string = O(n)

消毒（）你说的是O（n），但是这是presumably关于标记而不是原字符串的长度的，所以乘令牌长度的令牌数量= O（N）

sanitize() you say is O(n), but this is presumably with respect to the length of the token rather than the length of the original string, so multiply token length by number of tokens = O(n)

strncat函数（）最终复制所有原始字符串没有重叠= O（N）

strncat() ends up copying all of the original string with no overlap = O(n)

您添加字符输出字符串（固定数量的 ^ ，（，）， $ 和几个空值）= O（1）

you append a fixed number of characters to the output string (^, (, ), $ and a couple of NULLs) = O(1)

你追加一个 | 每个令牌字符串= O（N）

you append a | to the string per token = O(n)

别急！

因此​​，有你的答案。

So there's your answer.