如何计算如下code大O符号

本文介绍了如何计算如下code大O符号的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我读过的主题：

大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)

别急！

• 您拨打的strlen（）在输出图形的为循环的每一次迭代的=为O（n ^ 2）

• you call strlen() over the output pattern for every iteration of the loop = O(n^2)

因此​​，有你的答案。

So there's your answer.