考点：
1、衡量一个算法好坏的标准是（C ）。
A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短
2、下面关于NP问题说法正确的是（B ）
A NP问题都是不可能解决的问题
B P类问题包含在NP类问题中
C NP完全问题是P类问题的子集
D NP类问题包含在P类问题中
3、算法是由若干条指令组成的有穷序列，而且满足以下性质（ D ）
（1） 输入：有0个或多个输入
（2） 输出：至少有一个输出
（3） 确定性：指令清晰，无歧义
（4） 有限性：指令执行次数有限，而且执行时间有限
A (1)(2)(3) B(1)(2)(4) C(1)(3)(4) D (1) (2)(3)(4)（再加可行性）
4、函数32n+10nlogn的渐进表达式是( B ).
A. 2n B. 32n C. nlogn D. 10nlogn
5、设f(N),g(N)是定义在正数集上的正函数,如果存在正的常数C和自然数N0,使得当N≥N0时有f(N)≤Cg(N),则称函数f(N)当N充分大时有下界g(N),记作f(N)∈○(g(N)),即f(N)的阶( A )g(N)的阶.
A.不高于 B.不低于 C.等价于 D.逼近
算法时间复杂性指算法中元运算的执行次数。
6、算法的复杂性有 时间 复杂性和 空间 复杂性之分。
7、程序是 算法 用某种程序设计语言的具体实现。
8、算法的“确定性”指的是组成算法的每条 指令 是清晰的，无歧义的。
9、算法是指解决问题的 一种方法 或 一个过程 。
11、数值概率算法常用于 数值问题 的求解。
12、计算一个算法时间复杂度通常可以计算 循环次数、 基本操作的频率 或计算步。
13、算法是由若干条指令组成的有穷序列，解决某类问题的一系列运算的集合，且要满足输入、输出、确定性、有穷性和可行性五条性质。
14、任何可用计算机求解的问题所需的时间都与其 规模 有关。
15、快速排序算法的性能取决于 划分的对称性 。
1.用计算机求解问题的步骤：
1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标
5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制
2. 算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程
3.算法三要素
- 操作
- 控制结构
- 数据结构
4.算法具有以下5个属性：
算法是解决某类问题的一系列运算的集合。
- 有穷性：一个算法总是在执行了有穷的运算之后终止。
- 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口。
- 可行性：可以通过已经实现的基本运算执行有限次来实现的。
- 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
- 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
5. 算法设计的质量指标：
- 正确性：算法应满足具体问题的需求；
- 可读性：算法应该好读，以有利于读者对程序的理解；
- 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。
- 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。
经常采用的算法主要有迭代法、分治法、贪婪法、动态规划法、回溯法、分支限界法
6. 衡量算法时间效率的方法有哪两种？请叙述。
答：有事前分析法和事后分析法两种。
- 事后分析法：先将算法用程序设计语言实现，然后度量程序的运行时间。
- 事前分析法：算法的时间效率是问题规模的函数，假如，随着问题规模n的增长，算法执行时间的增长率和函数f(n)的增长率相同，则可记作：T(n)=O(f(n))称T(n)为算法的渐进时间复杂度。简称时间复杂度。
7. 在算法复杂性分析中，O、Ω、Θ这三个记号的意义是什么？在忽略常数因子的情况下，O、Ω、Θ分别提供了算法运行时间的什么界？
如果存在两个正常数c 和N_0,对于所有的_N≥N_0，有|_f(N)|≤C|g(N)|，则记作：f(N)= O(g(N))。这时我们说f(N)的阶不高于g(N)的阶。
若存在两个正常数C和自然数N0，使得当N ≥ N_0时有|_f(N)|≥C|g(N)|，记为f(N)=Ω(g(N))。这时我们说f(N)的阶不低于g(N)的阶。
如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1|g(N)| ≤|f(N)| ≤ c2|g(N)|则记作 f(N)= Θ(g(N))
O、Ω、Θ分别提供了算法运行时间的上界、下界、平均
8．对下列各组函数f (n) 和g (n)，确定f (n) = O (g (n)) 或f (n) =Ω(g (n))或f(n) =θ(g(n))，说明理由。
解题思路：
比较阶数：同阶为θ，f(n)
(1) f(n)=2n； g(n)=n!
(2) f(n)=n1/2； g (n)=log n2
(3) f(n)=100； g(n)=log100
(4) f(n)=n3； g(n)= 3n
(5) f(n)=3n； g(n)=2n
答：
(1) f(n) = O(g(n)) 因为g(n)的阶比f(n)的阶高。
(2) f(n) = Ω(g(n)) 因为g(n)的阶比f(n)的阶低。 （有问题）
(3) f(n) = θ(g(n)) 因为g(n)与f(n)同阶。
(4) f(n) = O(g(n)) 因为g(n)的阶比f(n)的阶高。
(5) f(n) = Ω(g(n)) 因为g(n)的阶比f(n)的阶低。
9.简述：
（1） 什么是算法？算法的特征有哪些？
（2） 什么是 P 类问题？什么是 NP 类问题？请描述集合覆盖问题的近似算法的基本思想。
答案：
（1）算法是解决某类问题的一系列运算的集合【2 分】。
具有有穷行、可行性、确定性、0 个或者多个输入、1 个或者多个输出【8 分】。
（2）可以在多项式时间内可解的判定问题称为 P 类问题【2 分】。
在非确定多项式时间内可解的判定问题称为 NP 类问题。【2 分】
集合覆盖问题的近似算法采用贪心思想：对于问题
若有收获，就点个赞吧
0 人点赞
