数据结构与算法分析收获总结第3章算法分析

92 阅读 0 评论 61 点赞

我是靠谱客的博主典雅大门，最近开发中收集的这篇文章主要介绍数据结构与算法分析收获总结第3章算法分析，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

看标题感觉这一章很重要，但其实教材也就十几页就结束了，主要内容还是上，下限，以及学会计算程序运行时间，也没涉及到敲代码，其他的了解一下就行了吧
正文：
1.算法的增长率是指当输入的值增长时，算法代价的增长速率。表达式为Cn（C为常数）的增长率称为线性增长率或者线性时间代价。含有n2次方的高次项，称为二次增长率，该曲线属于指数增长率。n方 n logn比较（注：数据结构中log一般默认以2为底）
2.最佳情况（如第一个元素恰恰就是所需），最差情况（如直到数组最后一个元素才找到所需的K）平均情况(如数组大小为n，平均要检查n/2个元素)。
3.如何更快的算法？log优于线性优于指数型
4.渐进分析（Asymptotic analysis）：忽略系数，注意集中在最重要的一点：增长率。能够简化算法分析
但也不一定一定是最好的，如对5个数排序的一种算法，如果用来给成千上万的数排序，算法就可能不是很适合，尽管它的渐进分析表明该算法性能良好。
5.上限：用来表示该算法可能有的最高增长率。大O表示法（读作大欧）: 如果某个算法增长率上限（在最差情况下）是f(n) <=> 最差情况下在集合O(f(n))中
给出O的定义：设T（n）表示算法的实际运行时间，f(n)则是上限的一个函数表达式。对于非负函数T(n)，如果存在两个正的常数c和n0，对于任意n>n0，有T(n)<=cf(n),则称T(n)在集合O(f(n)) 中
例：T(n)=c1n平方+c2n（c1,c2为正的常数），T(n)在O(n平方)中证明：c1n平方+c2n <= c1n平方+c2n平方 = （c1+c2）n平方，n>1时成立，再n=1时也满足
6.下限：用来描述算法在某类数据输入时所需要的最少资源。用符号Ω表示（读作欧米伽）
给出Ω的定义：设T（n）表示算法的实际运行时间，g(n)则是一个函数表达式。对于非负函数T(n)，如果存在两个正的常数c和n0，对于任意n>n0，有T(n)>=cg(n),则称T(n)在集合Ω(g(n)) 中
7.θ表示法：如果一个算法既在O(h(n))中，又在Ω(h(n))中，则称其为θ（h(n)）（读作西塔）
8.化简法则：有四条法则：
I.若f(n)在O(g(n))中，且g(n)在O(h(n))中，则f(n)在O(h(n))中；（这条很少用到）
II.若f(n)在O(kg(n))中，对于任意常数k>0成立，则f(n)在O(g(n))中；
III.若f(n)在O(g1(n))中，且f2（n）在O(g2(n))中，则f1(n)+f2(n)在O(max(g1(n),g2(n)))中；
IIII.若f1(n)在O(g1(n))中，且f2(n)在O(g2(n))中，则f1(n)f2(n)在O(g1(n)g2(n))中；
9.函数分类：判断两函数比值的极限来判断哪个增长率更快：比如给定f(n)和g(n)，lim f(n)/g(n) （n趋于无穷大），若极限趋于无穷大，则f(n)增长得更快，极限趋于0，则g(n)增长得更快
10.程序运行时间的计算
这是个重点!!!给出一个程序，学会判断运行时间，比如含有m层for(i=0;i<n;i++)循环，时间代价就为θ（n的m次方）。for中若（i=1；i<n；i*=2）则为logn。
for(i=0;i<n;i++)嵌套for(j=0;j<n;j++)
for(i=0;i<n;i++)嵌套for(j=0;j<i;j++)为1/2n平方,
for(i=0;i<n;i*=2)嵌套for(j=0;j<n;j++)为nlogn,
for(i=0;i<n;i*=2)嵌套for(j=0;j<i;j++)为2的logn次方，即为n
11.多参数问题，如有多个for循环，每个for循环中的参数不同，相加时候注意…（不怎么重要）
12.空间代价，如n*n数组，数组总规模就是n平方。如一个包含n个整数的一维数组，每个整数占用c字节，则整个数组需要cn字节的空间，即θ（n）