Я наткнулся на это странное рекуррентное уравнение:
T(n,h) = T(n/2, h1) + T(n/2, h-h1) + nh
а также:
T(1,h) = O(h)
Мне нужно найти асимптотическую верхнюю границу. Я никогда не сталкивался с рекуррентным отношением с двумя аргументами.
После долгих поисков я нашел этот набор слайдов что указывает мне на то, что это связано с вычислительной геометрией.
Было бы неплохо, если бы кто-то мог указать мне в правильном направлении.
Предполагая, что n является степенью числа 2, 0 ‹= h1 ‹= h, T(0, h) = 0 и T(1, h) = h, согласно следующему индуктивному доказательству оценка сверху равна 2nh.
Базис: T(0, h) ‹= 0 ‹= 2(0)h и T(1, h) ‹= h ‹= 2(1)h.
Индуктивный шаг: T(n, h) = T(n/2, h1) + T(n/2, h - h1) + nh ‹= 2(n/2)h1 + 2(n/2)(h - h1) + nh ‹= 2nh независимо от h1.
Предполагая, что первый рекурсивный вызов включает h вместо h1 и заменив h1 на c (ради удобочитаемости), я решил действовать следующим образом:
h1? Этот рецидив выглядит так, будто он становится отрицательным довольно быстро. - person Sneftel schedule 15.05.2014h1я считаю, что это просто константа. - person Mohamed Ennahdi El Idrissi schedule 17.05.2014T(n,h) = T(n/2, h) + T(n/2, h-h1) + nh?hвместоh1в первом рекурсивном вызове, нет? - person Mohamed Ennahdi El Idrissi schedule 18.05.2014