我已阅读主题:
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) 还是其他?
谢谢。
最佳答案
对我来说,一目了然。
strtok_r()
遍历原始字符串 = O(n)sanitize()
你说的是 O(n),但这大概是关于 token 的长度而不是长度原始字符串的,因此将标记长度乘以标记数 = O(n)strncat()
最终复制了所有原始字符串,没有重叠 = O(n)您将固定数量的字符附加到输出字符串 (
^
,(
,)
,$
和几个 NULL) = O(1)您将
|
附加到每个标记的字符串 = O(n)
但是等等!
- 您在输出模式上调用
strlen()
循环的每次迭代 = O(n^2)
这就是你的答案。
关于algorithm - 如何根据以下代码计算 Big-O Notation,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4149560/