算法考试重点算法的概念答:算法是求解一类问题的任意一种特殊的方法。较严格的说法是,一个算法是对特定问题求解的一种描述,它是指令的有限序列。算法具有的五个特征:(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记号(bigOhnotation)。O(g(n))={f(n)|存在正常数c和n0使得对所有n³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)≥cg(n),则记做f(n)=W(g(n)),称为W记号(omeganotation)。W(g(n))={f(n)|存在正常数c和n0使得对所有n³n0有:0£cg(n)£f(n)}称一个算法具有W(g(n)),指n足够大时,运行时间至少需要g(n)的某个常数倍,g(n)是下界,可以认为是最小值。13设有函数f(n)和g(n)是定义在非负整数集合上的正函数,如果存在正常数c1,c2和n0,使得当n≥n0时,有c1g(n)≤f(n)≤c2g(n),则记做f(n)=Q(g(n)),称为Q记号(Thetanotation)。14定义2-4小o记号f(n)=o(g(n))当且仅当f(n)=O(g(n))且f(n)¹W(g(n))15渐近分析记号的若干性质(1)传递性:f(n)=Q(g(n)),g(n)=Q(h(n))Þf(n)=Q(h(n));f(n)=O(g(n)),g(n)=O(h(n))Þf(n)=O(h(n));f(n)=W(g(n)),g(n)=W(h(n))Þf(n)=W(h(n));f(n)=o(g(n)),g(n)=o(h(n))Þf(n)=o(h(n));(2)反身性:f(n)=Q(f(n));f(n)=O(f(n));f(n)=W(f(n)
算法考试重点 来自淘豆网m.daumloan.com转载请标明出处.
