问答题

【简答题】求最大、最小元算法的时间复杂度（比较次数）下界是多少？分治算法在什么情况下可以达到下界？

答案：在规模为n的数据元素集合中找出最大元和最小元，至少需要3n/2-2次比较，即3n/2-2是找最大最小元算法的下界。当n=...

你可能感兴趣的试题

【简答题】分治法求最大、最小元算法的主要思想？

答案：当n=2时，一次比较就可以找出两个数据元素的最大元和最小元。当n>2时，可以把n个数据元素分为大致相等的两半，一半有n/...

【简答题】分治法的要领是什么？（分治法可分为哪三个主要步骤）

答案：分治法的要领
分治法是把一个规模较大的问题分解为若干个规模较小的子问题，这些子问题相互独立且与原问题同类；首先...