a=6,b=5,f(n)=n,logba=1,113,存在ε=0.113,使得,因此.
8皇后问题等价于要求在一个8×8格的棋盘上放置8个皇后,使得任意两个皇后不能放在同一行或同一列或同一斜线上。求解过程从空棋盘开始,设在第1行至第m行都已经正确放置了m个皇后的基础上,再在第m+1行上找合适的位置放置第m+1个皇后,直至第8行也找到合适的位置放置第8个皇后。在任一行上都有8种选择,开始时,位置在第1列,以后改变时,顺序选择第2列、第3列、…、第8列。当第8列也不是一个合适的位置时,就要回溯,去改变前一行的位置。分治法将复杂的大问题分解成规模小的问题以各个击破。归并排序等算法是采用分治法实现的。动态规划法与分治法类似,基本思想也是将待求解问题分解成若干子问题,先求解子问题,然后从这些子问题的解得到原问题的解,背包问题、LCS问题等是采用动态规划法实现的。贪心法跟动态规划法一样,也是用来解决最优问题的,但贪心法并不从整体最优考虑,它所做出的选择只是某种意义上的局部最优。
对于算法A,设a=7,b=2,f(n)=n2,则logba>2,因此存在常数ε,使得,因此。如果要使B渐进地快于算法A,则有,得log27a,求得a<49,因此a的最大整数为48。
本题需要用3个辅助变量n1、n2和n3来保存数组A中-1、0和1的个数,空间复杂度为Θ(1)。在统计时,需要使用一循环语句遍历数组A。统计完成后,再使用一次循环语句遍历数组A,并将A中的前n1个元素赋值为-1,第n1+1到n1+n2个元素赋值为0,最后n个元素赋值为1。数组A的元素个数为n,因此算法的时间复杂度为Θ(n)。
分治算法的设计思想是将一个难以直接解决的大问题分解成一些规模较小的相同问题,以便各个击破,分而治之。分治算法产生的子问题往往是原问题的较小模式。一般来说,分治算法分为三个步骤:将原问题分解成一系列子问题;递归求解各个子问题;将子问题的解合并成原问题的解。
分治算法的基本思想是将一个难以直接解决的大问题分解成一些规模较小的小问题以便各个击破,分而治之。分治算法的每一层都有3个步骤:分解、求解和合并。本题的查找算法,不断划分数组,缩小查找范围,可见该算法是基于分治策略的算法。