l算法考试重点.docVIP

算法考试重点 算法的概念 答：算法是求解一类问题的任意一种特殊的方法。较严格的说法是，一个算法是对特定问题求解的一种描述，它是指令的有限序列。 算法具有的五个特征：（1）输入（2）输出（3）确定性（4）能行性（5）有穷性 问题求解过程（1）理解问题（2）设计方案（3）实现方案（4）回顾复查 系统生命周期：一个计算机程序的开发过程就是使用计算机求解问题的过程。软件工程将软件开发和维护分成若干段，称为系统生命周期。通常把软件生命周期划分为分析、设计、编码、测试和维护等五个阶段。 算法问题的求解过程：（1）理解问题（2）选择求解方法确定数据结构（3）设计算法（4）正确性证明（5）分析算法（6）编写代码 递归定义是一种间接或直接引用自身的定义方法。一个合法的递归定义包括两部分基础情况和递归部分。 程序健壮性是指当输入不合法数据时，程序应能做适当处理而不至于引起严重后果。 影响程序运行时间的因素：（1）程序所依赖的算法（2）问题规模和输入数据·（3）计算机系统性能。 时间复杂度：一个算法的时间复杂度是指算法运行所需要的时间。 最好、最坏和平均时间复杂度 如果待查元素刚好是第一个元素，则所需的查找时间最短这就是算法的最好情况。 如果待查元素师最后一个元素，则所需的查找时间最长，则是算法执行时间的最坏情况。 11设函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数c和n0，使得当n≥n0时，有f(n)≤cg(n)，则记做f(n) = O(g(n))，称为大O记号（big Oh notation）。 O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n3 n0有：0 ￡ f(n) ￡ cg(n) } f(n)=O(g(n))表示所有增长阶数不超过g(n)的函数的集合。 g(n)的形式要比f(n)简单。如f(n)=2n+3=O(n), 称一个算法具有O(g(n))，指n足够大时，运行时间不会超过g(n)的某个常数倍，g(n)是上界。 12设有函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数 c和n0，使得当n≥n0时，有f(n)≥c g(n)，则记做f(n) = W (g(n))，称为W记号（omega notation）。 W(g(n)) = { f(n) | 存在正常数c和n0使得对所有n3 n0有：0￡ cg(n) ￡ f(n) }称一个算法具有W(g(n))，指n足够大时，运行时间至少需要g(n)的某个常数倍，g(n)是下界，可以认为是最小值。 13设有函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在正常数c1，c2和n0，使得当n≥n0时，有c1 g(n)≤f(n)≤c2 g(n)，则记做f(n) = Q(g(n))，称为Q记号（Theta notation）。 14定义2-4 小o记号f(n) = o(g(n))当且仅当f(n) = O(g(n))且f(n) 1 W(g(n)) 15渐近分析记号的若干性质 (1）传递性： f(n)= Q(g(n))， g(n)= Q(h(n)) T f(n)= Q(h(n))； f(n)= O(g(n))， g(n)= O (h(n)) T f(n)= O (h(n))； f(n)= W(g(n))， g(n)= W (h(n)) T f(n)= W(h(n))； f(n)= o(g(n))， g(n)= o(h(n)) T f(n)= o(h(n))； （2）反身性： f(n)= Q(f(n))；f(n)= O(f(n))；f(n)= W(f(n)). （3）对称性： f(n)= Q(g(n)) ? g(n)= Q (f(n)) （4）互对称性： f(n)= O(g(n)) ? g(n)= W (f(n)) （5）算术运算： O(f(n))+O(g(n)) = O(max{f(n),g(n)}) ； O(f(n))+O(g(n)) = O(f(n)+g(n)) ； O(f(n))*O(g(n)) = O(f(n)*g(n)) ； O(cf(n)) = O(f(n)) ； g(n)= O(f(n)) T O(f(n))+O(g(n)) = O(f(n)) 16最常见的多项式时间算法的渐近时间复杂度 O(1)＜O(log n)＜O(n)＜O(nlog n)＜O(n2)＜O(n3) 最常见的指数时间算法的渐近时间复杂度 O(2n)＜O(n！)＜O(nn) 16二叉有哪些信誉好的足球投注网站树是一棵二叉树，他要求的左子树上所有的结点的值都小于根节点，右子树上·所有节点的值都大于根节点。 17二叉平衡树：是一种平衡有哪些信誉好的足球投注网站树；即是任何结点的左子树和右子树高度最多相差1的二叉有哪些信誉好的足球投注网站树。每次插入或删除后，按规则重