Написание и решение повторения, которое считает количество умножений в этом коде?
Пусть M (n) будет числом умножений, которое выполняет функция fct.
//precondition: n>0
int fct (const int A[], int n) {
if (n==1)
return A[0]*A[0];
else return A[n-1] * fct(A,n-1) * A[n-1];
}
записать рекуррентное соотношение для M (n), где n — количество элементов в массиве
Решите рекуррентное соотношение, чтобы получить M (n) через n
Запишите полученное выражение части 2 в больших обозначениях O
Так что это был тест, и у меня есть ключ ответа, но я не очень уверен, как это было вычислено, M (n) = 2n-1 с O (n). Я не знаю, как это было определено, кто-то может объяснить? Спасибо
Решение
Давайте посмотрим, что делает каждый звонок. Каждый звонок, когда n> 1,
- Делает ровно два умножения, то
- Делает рекурсивный вызов для задачи размера n — 1
Поэтому мы можем записать повторение как
- М (1) = 1
- M (n) = 2 + M (n-1)
Если вы используете метод итерации, вы заметите этот шаблон:
- М (1) = 1
- М (2) = М (1) + 2 = 3
- М (3) = М (2) + 2 = 5
- М (4) = М (3) + 2 = 7
- …
- M (n) = 2n — 1
Теперь, когда у вас есть это, вы можете написать это асимптотически как M (n) = Θ (n).
Надеюсь это поможет!
Другие решения
Других решений пока нет …