Блог

Главная - Вопросы по программированию - Как найти Big O разделяющей рекурсивной функции

Как найти Big O разделяющей рекурсивной функции

#big-o

#big-o

Вопрос:

Я изучаю Big O и застрял на проблеме.

Проблема —

 int sample_function (int x) {
 if (x<1){
   return x;}
  
 int y = x/2; 
 return sample_function (y)   sample_function (x-y);
}

Каким будет big O, если мы вызовем 2 рекурсивных вызова (n / 2)?
Я знаю, что большой O разделяющей рекурсивной функции (n / 2) равен O (log (n)), но не уверен в этой проблеме.

Комментарии:

1. Обратите внимание, что это не вопрос о C или C . Речь идет о временной сложности этого алгоритма, которая не зависит от того, на каком языке вы его реализуете.

Ответ №1:

Решение рекуррентного соотношения

 T(n) = T(ceiling(n/2)) T(floor(n/2))   O(1)

является

 T(n) = O(n).

Это может быть доказано индукцией по n.
Индуктивный базис прост. Что касается шага индукции, пусть c будет положительной константой, такой, что T(ceiling(n / 2)) и T(floor(n / 2)) ограничены сверху c * ceiling(n / 2) и c * floor(n / 2) соответственно. Таким образом, T(n) ограничено сверху c * (потолок (n / 2) пол (n / 2) = c * n .

Ответ №2:

Деление целого числа x 2 на reach 0 занимает примерно log2(x) несколько шагов. Каждый шаг удваивает количество вызовов функций. Например:

   8
  4               4
  2       2       2       2
  1   1   1   1   1   1   1   1
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

В общем, это sum( 2^k ), k = 0 ...log2(x) = O(x) .

Для 0 и отрицательные значения, которые вы возвращаете при первом вызове, это O(1) .

PS: Можно утверждать, что функция на самом деле O(1) . Компилятор может заменить его на:

 int sample_function (int x) {
    if (x < 1) return x;
    else return 0;
}

Ответ №3:

T(n) = 2 * T(n / 2) O(1) = 4 * T(n / 4) 2 * O(1) = 8 * T(n / 8) 4 * O(1) = ... = n * O(1) (n / 2) * O(1)

Итак, это O (n) .