我被要求从递归函数形成一个递归方程,并用T(n(求解它。此函数将 n 个元素的数组分成两半;找到每半的最大值,然后返回两者中的最大值。但是,我在理解如何从这个函数形成递归方程时遇到了一些麻烦。
我在这里和互联网上的其他地方看过一些类似的问题,据我所知,这个函数执行两次递归调用,每次将数据拆分为 2,大小应为 = n,但我不确定函数中的其他元素以及如何正确编写它们。
𝑠𝑒𝑎𝑟𝑐ℎ𝑀𝑎𝑥(𝐴[], 𝑠𝑡𝑎𝑟𝑡𝐼𝑑𝑥, 𝑠𝑖𝑧𝑒)
{
𝑖𝑓 (𝑠𝑖𝑧𝑒 == 1)
𝑟𝑒𝑡𝑢𝑟𝑛 A[𝑠𝑡𝑎𝑟𝑡𝐼𝑑𝑥];
𝑛𝑢𝑚1 = 𝑠𝑒𝑎𝑟𝑐ℎMax(𝐴[], 𝑠𝑡𝑎𝑟𝑡𝐼𝑑𝑥, ⌊𝑠𝑖𝑧𝑒/2⌋);
𝑛𝑢𝑚2 = 𝑠𝑒𝑎𝑟𝑐ℎMax(𝐴[], 𝑠𝑡𝑎𝑟𝑡𝐼𝑑𝑥 + ⌊𝑠𝑖𝑧𝑒/2⌋, 𝑠𝑖𝑧𝑒 − ⌊𝑠𝑖𝑧𝑒/2⌋);
if (𝑛𝑢𝑚1 ≥ 𝑛𝑢𝑚2)
𝑟𝑒𝑡𝑢𝑟𝑛 𝑛𝑢𝑚1;
𝑒𝑙𝑠𝑒
𝑟𝑒𝑡𝑢𝑟𝑛 𝑛𝑢𝑚2;
}
T(n( = 2T(n/2( + c
时间复杂度 - O(n(
该函数对大小为 n/2 的子数组进行 2 次递归调用,并持续工作