经典算法设计思想与程序设计方法

算法设计思想总结 本资源摘要信息将对算法设计思想进行总结，涵盖了算法设计的基本概念、算法设计的任务、算法分析、程序设计、结构化程序设计等方面的知识点。 一、算法设计的基本概念 算法是解决问题方法的精确描述，但是并不是所有问题都有算法。算法设计的任务是对各类具体问题设计良好的算法及研究设计算法的规律和方法。 二、算法设计的任务 算法设计的任务是对各类具体问题设计良好的算法及研究设计算法的规律和方法。常用的算法有：穷举搜索法、递归法、回溯法、贪心法、分治法等。 三、算法分析 算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论各种复杂度，以探讨某种具体算法适用于哪类问题，或某类问题宜采用哪种算法。算法的复杂度分时间复杂度和空间复杂度。时间复杂度是指在运行算法时所耗费的时间为f(n)（即n的函数）。空间复杂度是指实现算法所占用的空间为g(n)（也为n的函数）。称O(f(n))和O(g(n))为该算法的复杂度。 四、程序设计 程序是对所要解决的问题的各个对象和处理规则的描述，或者说是数据结构和算法的描述。程序设计就是设计、编制和调试程序的过程。结构化程序设计是利用逐步求精的方法，按一套程式化的设计准则进行程序的设计。由这种方法产生的程序是结构良好的。 五、结构化程序设计 结构化程序设计是利用逐步求精的方法，按一套程式化的设计准则进行程序的设计。所谓“结构良好”是指：（１）易于保证和验证其正确性；（２）易于阅读、易于理解和易于维护。按照这种方法或准则设计出来的程序称为结构化的程序。 六、逐步求精 逐步求精是对一个复杂问题，不是一步就编成一个可执行的程序，而是分步进行。第一步编出的程序最为抽象；第二步编出的程序是把第一步所编的程序（如过程、函数等）细化，较为抽象；……；第i步编出的程序比第i-1步抽象级要低；……；直到最后，第n步编出的程序即为可执行的程序。 七、抽象程序 抽象程序是指程序所描述的解决问题的处理规则，是由那些“做什么”操作组成，而不涉及这些操作“怎样做”以及解决问题的对象具有什么结构，不涉及构造的每个局部细节。