数据结构笔记.doc

数据结构笔记数据结构算法 1. 算法有穷性: {1} n<=1 1. 序列 Hailstone(n)= {n} ∪ Hailstone(n/2) n偶{n} ∪ Hailstone(3n+1) n奇例: Hailstone(42)={42,21,64,32,...,1} 2.(1) 算数级数:与末项同阶 T(n)=1 +2+3+…+n =n(n+1)/2 = O(n2) (2) 幂方级数: 比幂次高出一阶:∑_(k=0)^n ? k^d =∫_0^n ?〖 x^(d+1) dx=1/(d+1) 〗|_0^n=1/(d+1) n^(d+1)=O(n^(d+1)) T2(n) = 12+22 +32 +…+ n2= n(n+1)(2n+1)/6 = O(n3) T3(n) = 13+23 +33+ …+ n3= n2(n+1)2/4 = O(n4) (3) 几何级数(a> 1) :与末项同阶 Ta(n) = a0+ a1 +a2 +a3 +…+an = O(an) (4) 收敛级数: 1/1/2 + 1/2/3 + 1/3/4 +…+ 1/n/(n+1) =1 -1/n+1 = O(1) (5) 长度有限: 1+ 1/2 + 1/3 +…+ 1/n =Θ(logn) 2. 起泡排序算法(1) 不变性:经过 K 轮扫描交换后,最大的 K 个元素必然就位(2) 单调性:经过 K 轮扫描交换后,问题规模缩至 n-k (3) 正确性: 至多经过 n 轮扫描交换,算法终止,且能给出正确答案。//#include<iostream> using namespace std; void bubblesort1A(int A [],int n){ //θ<n bool sorted = false; // 整体排序标志,首先假定尚未排序 while (!sorted){ // 在尚未确认已全局排序之前,逐趟进行扫描交换 sorted = true; // 假定已经排序 for(int i= 1;i < n; i++ ){ // 自左向右逐对检查当前范围 A[θ,n) if(A[i-1] > A[i]){ // 一旦 A[i-1] 与 A[i] 逆序,则 swap(A[i-1],A[i]); // 交换之,并 sorted = false; // 因整体排序不能保证,需要清除排序标志}}} n--; // 至此末元素必然就位,故可以缩短待排序序列的有效长度} //int main(){ int A[7] = {6,8,4,9,2,1,3}; bubblesort1A(A,7); for(int i= 0; i< 7; i++){ cout<<A[i]; } return 0; } 复杂度: T(n) = T(n-1)+O(1) T(n)-n = T(n-1)-(n-1)=...=T(2)-2=T(1)-1=T(0) T(n) = O(1)+n 2. 算法的时间复杂度 T(n)= 算法所执行基本操作的总次数。 (n) 的渐进上界 n>>2 ,T(n) <= c*f(n) //c 为常数, f(n) 为函数若n 足够大, f(n) 给出了 T(n) 的渐进上界,记为 T(n)= ó (f(n)), 大ó 记号的性质: ⑴对于任意常数 c ,均有ó (f(n))= ó (c*f(n)); ⑵对于任意常数 a>b> θ,有ó (n^a+n^b)= ó (n^a); 4. 算法复杂度的最好情况: n>>2 ,T(n) >= c*g(n) //c 为常数, g(n) 为函数 n>>2 ,n 足够大, T(n) =Ω(g(n)) //T(n) 的一个渐进下界与ó 刚好相反,大Ω记号是对算法执行效率的乐观估计??对于规模为n 的任意输入,算法的运算时间都不会低于Ω(g(n)) 。 5. 对算法复杂度做出定量的界定,大Θ记号, T(n) 介于ó (f(n)) 与Ω(g(n)) 之间,若ó (f(n))= Ω(g(n)) ,则用大Θ记号: c1*h(n)<=T(n)<=c2*h(n) //c1,c2 为常数, h(n) 为函数 n 足够大, h(n) 给出了 T(n) 的一个确界,T(n)=Θ( h(n) ), 对于规模为 n 的任何输入,算法的运行时间都与Θ( h(n) )同阶。 6. 时间复杂度本身就是空间复杂度的一个天然上界。 7. 常数复杂度: T(n)=O(1) 8. 对数复杂度: T(n)=O(log(n)) 对任意 n,logn = O(n^c) 复杂度无限接近于常数; 例1 :计算十进制对应二进制中数位 1 的总数//#include<iostream> //using namespace std; int countOnes(unsigned