-
算法: 指解决问题的一种方式或一个过程,算法是若干指令的有穷序列。
-
满足性质: 输入、输出、确定性、有限性。
-
程序与算法之间的联系: 程序是算法用某种程序设计语言的具体实现。
-
计算机的两大资源: 时间、空间。
-
常用提升算法的效率的方式: 牺牲空间换时间。
-
- 问题求解的逻辑过程:
- 建模:对输入参数和解给出形式化或半形式化的描述。
- 设计算法: 采用什么算法设计技术,正确——是否对所有的实例都得到正确的解。
- 分析算法: ——效率
- 问题求解的逻辑过程:
-
常见排序算法的效率:
-
算法时间复杂度: 针对指定基本运算,计数算法所做的运算次数。
- 最坏情况下的时间复杂度:W(n);
- 平均情况下的时间复杂度 :A(n);
-
平均情况下的时间估计(顺序检索法):
-
函数的渐近的界:
-
相应定理:
- 同阶:
- 低阶:
- 高阶:
- 同阶:
-
阶的高低:
-
函数取整: ⌊X⌋ 向下取整,⌈x⌉ 向上取整;
-
主定理的应用:
-
公式:T(n)= aT(n/b)+f(n)
- a:归约后的子问题的个数
- n/b: 归约后子问题的规模
- f(n):归约过程及组合子问题的解的工作量
-
共有三种情况:此处省略;
-
常见的主定理
-
二分检索: T(n)= T(n/2)+1
-
二分归并排序: T(n)= 2T(n/2)+n-1
-
例:
-
T(n)= 9T(n/3)+n
-
a = 9
-
b = 3
-
f(n) = n
T(n) = O(n^2)
更多推荐
算法入门基础知识总结
发布评论