Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
Другие темы раздела
Алгоритмы Бинарный поиск http://www.cyberforum.ru/algorithms/thread2185163.html
Всем доброго времени суток. Помогите разобраться с бинарным поиском. В теории все понятно: С каждым ходом он отсеивает половину элементов, таким образом O(log2 N) с округлением вверх, где N...
Алгоритмы Не работает перенос в другой массив алгоритм должен переводить данные по очереди в массивы по 10 элементов, но вместо этого он всё пишет в первый, в чём проблема? (естессно, кроме моей криворукости :)) var cha,zn:real; a: array ... http://www.cyberforum.ru/algorithms/thread2185088.html
Физическая формула в виде объекта (дерева) Алгоритмы
Всем добрый день, в программировании чайник, перелопатил все(Гугл). Нужен алгоритм преобразования например вот этой формулы(во вложении) в виде объекта(дерева). Задача такова: в бд хранится...
Алгоритм расчета рейтинга Алгоритмы
Здрасьте всем! Есть тренажер с вопросами - пользователю показывается вопрос, а он выбирает ответ. Нужно расчитать вес вопроса в зависимости от числа показов этого вопроса и % правильных ответов (в...
Алгоритмы Задача о рюкзаке: выбрать не более L деталей так, чтобы полезность была max при ограничении на суммарную массу http://www.cyberforum.ru/algorithms/thread2183646.html
Существует ли алгоритм, позволяющий решить следующую задачу? Имеется k_1 одинаковых деталей 1-го вида, k_2 одинаковых деталей 2-го вида, ..., k_n одинаковых деталей n-го вида, (n>40). Каждая деталь...
Алгоритмы Разработать алгоритм вычисления суммы произвольной последовательности чисел с общим членом Разработать алгоритм вычисления суммы произвольной последовательности чисел с общим членом an , где n пробегает значения от N1 до N2, и представить алгоритм в виде псевдокода и блок-схемы. ... подробнее
William Blake
10 / 10 / 2
Регистрация: 09.08.2010
Сообщений: 314
0

Составить формулу рекуррентного соотношения

06.02.2018, 04:30. Просмотров 388. Ответов 2
Метки (Все метки)

Дан рекуррентный алгоритм суммирования чисел массива mas. Начальный индекс массива равен 1, массив содержит n элементов.

Алгоритм описан следующим образом:

F#
1
2
3
4
5
6
7
8
9
10
s = doSum(mas, 1, n)
 
func doSum(mas, left, right):
if (left == right) then
   return mas[left]
else
   center = (left + right) div 2
   s1 = doSum(mas, left, right, center)
   s2 = doSum(mas, center + 1, right)
   return s1 + s2
Мастер-теорема выглядит так: T(n) = a*T(n/b) + f(n), где a >= 1, b > 1 - некоторые константы, f - некоторые нерекуррентные вычисления.

Мой вопрос относится к нахождению функции f(n). Думаю, что f(n) равна нечто вроде (2*n/c + n/c), где 2 и c - некоторые константы, которые можно опустить, и, таким образом, получить в итоге f(n) = n. Правильно ли это? Если нет, то почему и чему тогда равно f(n)?

Вернуться к обсуждению:
Составить формулу рекуррентного соотношения
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.02.2018, 04:30
Готовые ответы и решения:

Построение и решение рекуррентного соотношения
Добрый день. Я изучаю книгу А.Левитина "Алгоритмы: Введение в разработку и анализ" и пытаюсь...

Составить программу вычисления суммы ряда с использованием рекуррентного соотношения
Цикл с параметром.Составить программу вычисления суммы ряда с использованием рекуррентного...

Решение рекуррентного соотношения
Не знаю с какого бока подойти к решению, прошу помощи. Вот само соотношение - Q0 = a Q1 = b Qn =...

Составление рекуррентного соотношения
http://padaread.com/?book=15274&pg=121 последний абзац обьясните пожалуйста как можно подробнее...

Решение рекуррентного соотношения
Привет. Подскажите, пожалуйста, как решить реккуретное соотношение и оценить степень роста...

2
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru