Как рассчитать нотацию Big-O по следующему коду - PullRequest
Новая
       17

Как рассчитать нотацию Big-O по следующему коду

0 голосов
/ 11 ноября 2010

Я прочитал тему:

Большой О, как вы рассчитываете / приближаете его?

И я не уверен, что обозначение 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) или что-то еще?

Спасибо.

Ответы [ 3 ]

4 голосов
/ 11 ноября 2010

Взгляд O (n) мне, с первого взгляда.

  • strtok_r() перебирает исходную строку = O (n)

  • sanitize() вы говорите, что O (n), но это, вероятно, относится к длине токена , а не длине исходной строки , поэтому умножьте длину токена на количество токенов = O (n)

  • strncat() в конечном итоге вы скопируете всю исходную строку без наложения = O (n)

  • вы добавляете фиксированное количество символов к выходной строке (^, (, ), $ и пару NULL) = O (1)

  • вы добавляете | к строке для каждого токена = O (n)

Но подождите!

  • вы вызываете strlen() через выходной шаблон для каждой итерации цикла = O (n ^ 2)

Итак, ваш ответ.

2 голосов
/ 11 ноября 2010

Один из подходов, который мне нравится, это заменить код временем выполнения, например, 

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.

0 голосов
/ 10 декабря 2010

Почему все считают, что strlen = O (n)?Я думал, что O (n) был только для петель.

...