我正在学习数据结构和算法。我参考的书(Sedgwick)使用“查找最大元素”来说明分治策略。该算法将一个数组中点分为两部分,递归地在这两部分中找到最大元素,并返回较大的那个作为整个数组的最大元素。
以下是一个练习问题:
修改用于查找数组中最大元素的分治程序(程序5.6),将大小为N的数组分成大小为k = 2 ^(lg N-1)和大小为N-k的另一部分(因此至少有一个部分的大小是2的幂次方)。
绘制相应的递归调用树形图,当数组大小为11时,类似于程序5.6所示的那个。
我看到这样一个二叉树的左子树是一个完美的二叉树,因为第一个子集的大小是2的幂次方。作者希望我从中得出什么意义?
以下是一个练习问题:
修改用于查找数组中最大元素的分治程序(程序5.6),将大小为N的数组分成大小为k = 2 ^(lg N-1)和大小为N-k的另一部分(因此至少有一个部分的大小是2的幂次方)。
绘制相应的递归调用树形图,当数组大小为11时,类似于程序5.6所示的那个。
我看到这样一个二叉树的左子树是一个完美的二叉树,因为第一个子集的大小是2的幂次方。作者希望我从中得出什么意义?