宝安建网站外包,做网站销售的,网站一级域名和二级域名,修改wordpress用户名第一章 算法概述
1.1算法性质#xff1a;
输入、输出、确定性、有限性
1.2时间复杂度 上界记号O#xff1a;如果存在正的常数C和自然数N0#xff0c;使得当N≧N0时有f(N)≦Cg(N)#xff0c;则f(N)有上界函数g(N)#xff0c;记为f(N) O(g(N))。 同阶记号θ#xff1a;…第一章 算法概述
1.1算法性质
输入、输出、确定性、有限性
1.2时间复杂度 上界记号O如果存在正的常数C和自然数N0使得当N≧N0时有f(N)≦Cg(N)则f(N)有上界函数g(N)记为f(N) O(g(N))。 同阶记号θf(N)θ(g(N))表示f(N)和g(N)同阶 。 下界记号Ω如果存在正的常数C和自然数N0使得当N≧N0 时有f(N)≧Cg(N)则f(N)有下界函数g(N)记为f(N) Ω(g(N))。 1.3NP完全性理论
P类问题是指一类能够用确定性算法在多项式时间内求解的判定问题。其实在非正式的定义中我们可以把那些在多项式时间内求解的问题当作P类问题。
NP类问题是指一类可以用不确定性多项式算法求解的判定问题。不确定性算法非确定(“猜想”)阶段确定(“验证”)阶段 第二章 递归与分治策略
2.1 递归
递归算法是一个直接或间接地调用自己的算法。
例1阶乘函数 int fac(int n)
{ if (n0) return 1;return n*fac(n-1);
}例2Hanoi塔问题。
汉诺塔问题可以通过以下三个步骤实现
1将塔A上的n-1个碟子借助塔C先移到塔B上。
2把塔A上剩下的一个碟子移到塔C上。
3将n-1个碟子从塔B借助塔A移到塔C上。 void move(char x,char y)
{printf(%c-%c\n,x,y);
}void hanoi(int n, char a, char b, char c){if (n 1) move(a,c);else { hanoi(n-1, a, c, b); move(a,c); hanoi(n-1, b, a, c);
}例3多变元递归——整数划分问题
例整数划分问题将一个正整数n表示为一系列正整数之和n n1 n2 …nk 其中n1≥n2≥…≥nk≥1, k≥1。 例如 p(6) 11 即整数6的划分数为11种
6, 51, 42, 411, 33, 321, 3111, 222, 2211, 21111, 111111
最简单情形(1) q(n, 1)1q(1, m) 1 n, m≥1;
递归关系 (2) q(n, n) 1 q(n, n–1)n1;
产生的新情况 (3) q(n, m) q(n, m–1) q(n–m, m), nm1
划分中不含m的情况 划分中含m的情况 (4) q(n, m) q(n, n), nm。
例4多步递归——Fibonacci数列 2.2分治法
解型为T(n)aT(n/b)O(nd)的递归方程
设a1和b1是常数f(n)是一个函数
T(n)是定义在非负整数集上的函数T(n)aT(n/b) O(nd) 。 例1二分搜索技术
int BinarySearch(Type a[ ], const Type x, int n)
{int left0;int rightn-1;while (left right ){ int middle (leftright)/2;if (x a[middle]) return middle;if (x a[middle]) right middle-1; else left middle1;}return -1;
}例2大整数的乘法
