алгоритмы - Найти Theta-асимптотику и вычислить функцию

Дана программа:

функция f(n)

   if n>1

печать("алгоритм")

печать("алгоритм")

печать("алгоритм")

f([n/2])

f([n/4])

endif

Пусть g(n) - число слов "алгоритм", которые напечатает программа.

1) Найти Theta-асимптотику g(n).

2) Считая n степенью двойки, вычислить g(n) точно.

***[n/4] - наибольшее целое, не превосходящее число n/4.

задан 16 Фев '16 20:19

animag
21●9

https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method

начните пока с этого

и напишите рекуррентное соотношение для алгоритма. Если сможете написать - подскажу дальше.

Также полезно сначала решить задание 2)

(16 Фев '16 20:56) Trumba

@Trumba f(n)=f(n/2)+f(n/4), если n>1 f(n)=c, если n<1

(17 Фев '16 23:42) animag

@animag: это неправильно. Вы забыли про то, что при n>1 программа три раза печатает слово ещё до вызова процедур. При n=1 она ничего не печатает, и f(1)=0.

(18 Фев '16 0:02) falcao

Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

регистрация »

отмечен:

алгоритмы ×299
теория-алгоритмов ×211
сложность-алгоритма ×83
асимптотика ×59

задан
16 Фев '16 20:19

показан
1300 раз

обновлен
18 Фев '16 0:02

Связанные вопросы

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии