常用算法设计方法5

发布时间：2006-07-25 12:02 点击：

分页:前10页 上一页 11 [12] 13 14 15 16 17 18 19 20 下一页 后10页

P的子问题

P₁、

P₂、…、

P_k的相应的解

y₁、

y₂、…、

y_k合并为

P的解。

    根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的

k个子问题的处理方法是行之有效的。许多问题可以取

k=2。这种使子问题规模大致相等的做法是出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。

    分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方法比较复杂，或者是有多种合并方案；或者是合并方案不明显。究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。

【问题】

       大整数乘法

问题描述：

    通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理，即将执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。

    请设计一个有效的算法，可以进行两个

分页:前10页 上一页 11 [12] 13 14 15 16 17 18 19 20 下一页 后10页

版权申明:未经书面授权请勿转载本站信息!!作品版权归所属媒体与作者所有!!

发表评论：

匿名发表

用户名:

查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任
留言板管理人员有权保留或删除其管辖留言中的任意内容
本站提醒：不要进行人身攻击。谢谢配合。