int function(int n){
if (n<=1)
return 1;
else
return (2*function(n/2));
}
Что такое рекуррентное соотношение T(n) для времени работы и почему?
рекуррентное соотношение алгоритма сложности
Ответы (2)
Функция сложности этого алгоритма будет
T(n) = T(n / 2) + 1
T(1) = 1
Применяя основную теорему, мы получим
a = 1
b = 2
c = 0 (1 = n^0)
log b(A) = log2(1) = 0 = 0 c, thus case 2
apply values and the result is O(log n).
Как уже правильно сказал @guillaume, это можно решить намного проще, используя линейную функцию.
person
Paul
schedule
22.01.2016
@cstac это решение, которое возникает при использовании основной теоремы (если я не ошибся в расчетах - я еще раз проверю это). Вероятно, он ожидал точного решения? Должно быть какое-то примечание о том, что не так. Или просто спросите его
- person Paul; 23.01.2016
@cstac точное решение путем точного решения рекуррентного отношения. Основная теорема применима только в том случае, если вы хотите найти порядок сложности повторения.
- person Paul; 23.01.2016
@cstac Я бы просто спросил учителя. Я не использовал мастер-теорему в течение 2 лет. Есть большая вероятность, что я ошибся. Я просто ищу это.
- person Paul; 23.01.2016
Я решил это отношение и правильно, проблема в том, что если я должен иметь номер 2 в начале..
- person cstac; 23.01.2016
@cstac извините, я не скопировал эти 2 в начале. Вот где была ошибка. Мое решение неверно, так как
a должно быть 2, а не 1. Я исправил это. Однако теперь результат линейный, а не логарифмический. И я не совсем понимаю ваш вопрос
- person Paul; 23.01.2016
@cstac простите, я совсем устал, вообще-то час назад я собирался лечь спать... . Я посмотрю завтра. Я только что заметил, что приведенный выше код не
T, но нам нужно вычислить T для кода.
- person Paul; 23.01.2016
@cstac Я все перепроверил. Если я что-то не пропустил,
O(log n) верно.
- person Paul; 23.01.2016
Вы можете вычислить напрямую: это ближайшее 2 ^ n, самое большое или равное.
Вы вычисляете L=log2(n) и берете 2^L или 2^(L+1)
Сложность O(log2 N): log2 N операций.
person
guillaume girod-vitouchkina
schedule
22.01.2016
