如何计算大O符号以下代码

Big O, how do you calculate/approximate it?

而且我不知道以下功能的大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）还是别的吗？

谢谢。

来源

2010-11-10 LAC

如果您提供算法的简化伪代码版本，此问题将更容易回答。 – 2010-11-10 22:09:19

不要忘记考虑字符串操作 - 它们可能会或可能不会影响您的计算（例如strtok，strlen，strncat等）使用pascal字符串的 – MahlerFive 2010-11-10 22:12:07

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

strtok_r()遍历原始字符串= O（n）的
sanitize()你说是O（n），但这种推测是相对于令牌的长度，而不是原始字符串的长度为，所以令牌长度乘以令牌的数量= O（n）
strncat()最终复制所有原始的s没有重叠特林= O（n）的
你个字符的固定数目附加到输出的字符串（^，(，)，$和几个空值）= O（1）
你每个令牌= O追加|字符串（N）

别急！

你叫strlen()在输出模式为循环 =为O（n^2）

所以这是你的答案的每一次迭代。

来源

2010-11-10 22:23:25 SimonJ

可以修复该字符串操作。 – ruslik 2010-11-10 23:13:01

一种方式来处理它，我喜欢的是与运行时间更换代码，所以例如

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

成为

O(1) 
O(n) (* Assume the size of value is the size of the input *) 
O(1)

环路

for each k in value { 
    strlen(value) 
}

变得

O(n) { 
    O(n) 
}

或其他类似的符号，然后您可以将它们编入O(n) * O(n) = O(n^2)。然后，您可以总结所有列出的大哦时间来获得最终的时间复杂度。

一个类似的窍门是首先将所有的代码与计算完成的工作数联系起来，然后删除代码以完成仅留下计数的实际工作。然后用简单的数学来简化计数。即，

count = 0; 
for (i = 0; i < k; i++) { 
    count++ 
}

很容易被count = k替代。

来源

2010-11-10 22:43:17

为什么每个人都假设strlen = O（n）？我认为O（n）只适用于循环。

来源

2010-12-09 23:47:34 67vette427

Strlen可以被认为是： int strlen（char * s）{int _len = 0; while（* s ++）len ++; return len; } 因此，如果N是字符串的长度，strlen是O（N），因为它是一个循环。 – James 2010-12-10 06:32:04

和你如何确定strncat不是一次一个一个地复制1个字节的while循环？这是大O符号的假设部分吗？ – 67vette427 2010-12-10 23:19:19

如何计算大O符号以下代码

回答

相关问题