算法设计题目

第2章

1、大整数乘法的O(nmlog(3/2))算法

给定2个大整数u和v,它们分别有m位和n位数字,且m≤n。用通常的乘法求uv的值需要O(mn)时间。可以u和v均看作是有n位数字的大整数,用教材第2章介绍的分治法,在O(nlog3)时间内计算uv的值。当m比n小得多时,用这种方法就显得效率不够高。试设计一个算法,在上述情况下用O(nmlog(3/2))时间求出uv的值。

2、O(1)空间子数组换位算法

设a[0:n-1]是一个有n个元素的数组,k(1≤k≤n-1)是一个非负整数。试设计一个算法将子数组a[0:k-1]与a[k+1:n-1]换位。要求算法在最坏情况下耗时O(n),且只用到O(1)的辅助空间。

3、√段合并排序算法

如果在合并排序算法的分割步骤中,将数组a[0:n-1]划分为 √ 个子数组,每个子数组中有O(√)个元素。然后递归地对分割后的子数组进行排序,最后将所得到的 √ 个排好序的子数组合并成所要的排好序的数组a[0:n-1]。设计一个实现上述策略的合并排序算法,并分析算法的计算复杂性。

4、合并排序算法

对拨给元素存储于数组和存储于链表中的2种情形,写出合并排序算法。

5、非增序快速排序算法

如何修改QuickSort才能使其将输入元素按非增序排序?

你可能喜欢

  • 数字滤波算法设计
  • 数据结构算法设计
  • 算法设计与分析
  • 算法设计论文
  • 算法设计课程设计
  • 算法和程序设计

算法设计题目相关文档

最新文档

返回顶部