1
Если у вас есть квадратная область, которая содержит различные числа, то в результате каждого рекуррентного отношения:Может ли кто-нибудь объяснить рекуррентные отношения для четырех и двоичных разделов для поиска в отсортированной таблице?
T (n) = 3T (n/2) + c и T (n) = 2T (n/2) + cn
Я знаю, что первый должен привести к разделению квадов, а второй - к двоичному разделу, но я не могу интуитивно обернуть мою голову вокруг , почему это тот случай. Почему мы делаем 3 рекурсивных вызова в первом случае и 2 во втором? Почему эффект + c или + cn влияет на то, что мы делаем с проблемой?
Немного больше информации по вашему вопросу? что такое квадратная область? и как вы рекурсируете? Поскольку первый из них просто дает вам три рекурсивных вызова, если вы рисуете стоимость дерева рекурсии при каждом вызове, будет константа c. – sukunrt
Таблица сортируется вдоль ее строк и столбцов, и алгоритм пытается найти какое-то определенное значение в регионе. Первым повторением является подход с «четырьмя разделами», а второй - «двоичный раздел». –
Любая связь между вашим текстовым упоминанием о «четырехъядерных» и «двоичных» разделах и ваших повторных формулах совершенно неясна; если вы хотите, чтобы кто-то понял и объяснил это соединение, вы не предоставили контекста достаточно близко. У вас есть ссылка? – comingstorm