简答题.txt

算法分析常见简答题与常见算法 简答题.txt 算法.txt

1.	什么是算法？
       算法是一系列解决问题的清晰指令，也就是对于符合一定规范的输入，能够在有限时间内获得所要求的输出
2.	分析非递归算法的效率的方案
      一，决定用哪个参数表示输入规模。二，找出算法的基本操作(作为一个规律，它总是位于算法的最内层循环中)，三，检查基本操作执行的次数是否只依赖输入规模，如果它还依赖其他的特性，则最差效率，平均效率，最优效率（如有必要）需要分别研究。四，建立一个算法基本操作执行次数来求和表达式。五利用求和运算的标准公式和法则来建立一个操作次数的闭合公式，或者至少确定它的增长次数
3.	分析递归算法时间效率的通用方案
        一，决定那个参数作为输入规模的度量。二找出算法的基本操作。三，检查一下对于相同规模的不同输入，基本操作的执行次数是否可能不同，如果有这种可能则必须对最差效率平均效率最优效率做单独研究。四，对于算法基本操作的执行次数建立一个递推关系以及相应的初始条件。五，解这个递推式，或者至少确定他的解的增长次数
4.	分治法的工作方案
        一，将问题的实例划分为几个较小的实例最好拥有的同样的规模，二，对这些较小的实例求解（一般使用递归方法，但在问题规模足够小的时候有时间也会利用另一个算法），三，如果必要的话合并这些较小的解以得到原始问题的解
5.	减治法
     减治技术利用了一个问题给定实例的解和同样问题较小实例的解之间的某种关系，一旦建立了这种关系，我们既可以从顶至下（递归的），也可以从底向上的来运用该关系，减治法主要有三种变种（1）减去一个常量（2）减去一个常量因子（3）减法的规模是可变的
6.	变治法的3种主要类型
         （1）变换为同样问题的一个更简单或者更方便的实例我们称之为实例化简（2）变换为同样实例的不同表现我们称之为改变表现（3）变换为另一个问题的实例这种问题的算法是已知的我们称之为问题化简
7.什么是AVL树
     一颗AVL树是一颗二叉查找树，其中的每个节点的平衡因子定义为该节点左子树和右子树的高度差，这个平衡因子要么是-1要么是0要么是1
7.	堆的概念
       堆的定义为一颗二叉树，树的节点中包含键并且满足下面两个条件（1）树的形状要求，这颗二叉树是基本完备的（或者简称为完全二叉树）这意味着树的每一层都是满的除了最后一层右边的元素有可能缺位（2）父母优势要求，每一个节点的键都要大于或等于它子女的键
8.	从堆中删除最大的键
        第一步，根的键和最后的一个键做交换，第二步，堆的规模减1，第三步，严格按照自底向上的算法，把K沿着树向下筛选来对这颗较小的树进行堆化，也就是说验证K是否满足父母优势，如果它满足，就完成了。如果不满足，K和他较大的子女做交换，然后重复这个操作，知道K在新位置中满足父母优势
9.	堆排序的做法
       第一步，为一个给定的数组构造一个堆（自底向上）第二步，（删除最大键）对剩下的堆应用n-1次根删除操作
10.	贪婪技术所做的每一步满足的条件
       （1）可行性：即他必须满足问题的约束（2）局部最优：它是当前步骤中所有可行选择中最佳的局部选择（3）不可取消：即选择一旦做出，在算法的后面步骤中就无法改变了
11.动态规划的思想
       如果问题是由交叠的子问题所构成的，我们就可以用动态规划技术来解决它，一般老说，这样的子问题出现在对给定问题求解的递推关系中，这个递推关系中包含了相同的类型的更小问题的解，动态规划是对交叠的子问题中每一个较小的子问题只求一次并把结果记录在表中，这样就可以得出原始问题的解


算法的特型：
一般性，简单性，正确性，效率性。