Где сложение из рекуррентного отношения в суммировании?

Question

На этом курсе курса преподаватель показывает, как преобразовать рекуррентное отношение в фактическое суммирование проделанной работы.Чего я не понимаю, так это где постоянный объем работы на каждом уровне O(n^d) представлен в суммировании.Разве это не должно быть a(n/b)+O(n^d) вместо aO(n/b)^d?

Answer 1

В основной теореме вашей картины на каждом уровне работа - не что иное, как деление проблемы текущего уровня O(n) на a-th следующего уровня O(n/b) задач, а затем их объединение.

В level 0, у нас есть только один узел в дереве, эта devide and combine процедура имеет O(n^d) временную полноту (данные, согласно вашей картине, разные алгоритмы имеют различную devide and combine временную полноту).

В level 1 у нас есть узел a-th, и у каждого узла есть процедура devide and combine, из которых временная полнота равна O((n/b)^d), поэтому общая работа devide and combine на этом уровне составляет aO((n/b)^d).

Общая временная сложность всей работы, является суммой devide and combine временной сложности каждого уровня.Имейте в виду, что вся работа - не что иное, как выполнение devide and combine все время.

Answer 2

На основании определения big-O, поскольку a, b и d являются постоянными и превышают 1, оба значения aO((n/b)^d)) и O(n^d) эквивалентны.