最近看是看买了好久好久的数，名字叫做《数据结构与算法分析》
- 美国作者，国人的译本，所以有的句子读起来乖乖的，但是不重要，能学习思想和知识就很好。
- 不知道买了多久，好几年了吧，开始每天啃一点点
- 看到第二章看了五六页，然后突然发现看不懂了，所有字都认识，但是突然就不懂什么意思，怎么来的，就和大学高数一样，我特么蒙蔽了
- 所以绝顶回头再看，再学，再报哈哈哈哈，绝顶好好看懂了，再写篇博客记录一下
数学基础
- 估计算法资源消耗所需的分析是一个理论问题，因此需要一套正式的系统架构。先从某些数学定义开始。
定义一
- 如果存在常数c和n0使得当N>=n0时，T(N)<= cf(N),则记为T(N) = O(f(N))
- 这个定义大概意思是函数T(N)和cf(N)，存在一个交会的点，且这个点以后cf(N)总是会大于T(N)，这种情况就可以记为T(N) = O(f(N))
定义二
- 如果存在常数c和n0使得当N>=n0时，T(N)>= cf(N),则记为T(N) = Ω(f(N))
定义三
- T(N) = Θ(h(N))当且仅当T(N) = O(h(N))和T(N) = Ω(h(N))
- 说实话你这书写的屎一样，哈哈哈哈，这句我理解的就是前面成立，必须后面两个都满足，且只有后面两个满足，前面的式子才成立，是这个意思吧；
定义四
- 如果对每一正常数c都存在常数n0使得当N>n0时T(N)<cp(N),则T(N) = o(p(N))。有时也可以说，如果T(N) = O(p(N))且T(N) != θ(p(N)),则T(N)= o(p(N))
- 啊哈哈这都是书里的原文啊，感觉就听秃然的，确实很难理解。
- 这些定义的目的是要再函数见建立一种相对的级别。给定两个函数，通常存在一点，在这些点上一个函数的值小于另一个函数的值，因此，一般的宣称，比如说f(N)<g(N)是没有什么意义的。于是，我们比较他们的相对增长率。当将相对增长率应用到算法分析时，才能明白为什么它是重要的度量。
定义解释
- 对于较小的N，1000*N要比N²大，但N²的增速快，因此N²最终将是更大的。在这种情况下N = 1000是转折点。
- 第一个定义是说:最后总存在某个点n0，从他以后cf(N)总是至少与T(N)一样大，从而若忽略常数因子，则f(N)至少与T(N)一样大。这里的栗子T(N) = 1000*N,f(N) = N²，n0 = 1000,c = 1。可以说1000N=O(N²)。这种记法成大O标记法。
- 如果传统的不等式来计算增长率:
- 第一个T(N) = O(f(N))的定义是说T(N)的增长率小于等于f(N)；
- 第二个T(N) = Ω(f(N))定义是T(N)的增长率大于或等于g(N)；
- 第三个T(N) = Θ(h(N))定义是T(N)的增长率等于h(N)；
- 第四个T(N) = o(p(N))定义是T(N)的增长率小于p(N),这个不同于大O，因为大O包含增长率相同的情形；
- 记住O是小于等于，Ω是大于等于，θ是等于，o是小于(和大O差不多，知识不包含相等的情形)
- 当T(N) = O(f(N))时，我们是在保证T(N)实在一不快于f(N)的速度增长。因此你f(N)是T(N)的上界。那么反过来说T(N)是f(N)的下界即f(N) = Ω(T(N))
- 举个栗子:
N³比N²增长快，因此我们可以说N² = O(N³)或者N³ = Ω(N²)。
重要结论：
法则一
- 如果T1(N) = O(f(N))且T2(N) = O(g(N)),辣么:
a. T1(N) + T2(N) = O(f(N) + g(N))[ 这里书本还有一段，说可以更直观的表示为max(O(f(N)),O(g(N))) ,氮素我不敢苟同，在代码里max函数是取两值更大的值返回，然而前面的运算时相加。当作一个小疑问吧 ] 按照后文的意思确实是取更大值
b. T1(N) * T2(N) = O(f(N) * g(N))
法则二
- 如果T(N)是一个k次多项式，则T(N) = Θ(N^k)。意思就是取最大的次方的值，其他都可以忽略?
- 比如T(N) = N^4 + N³ + N²，这个可以习作T(N）= Θ(N^4)，大概是这个意思，只取影响怎张速率最大的部分。
法则三
- 对任意常数k,logkN = O(N)。
- 这个告诉我们对数增长得非常缓慢。
特别注意
- 首先将常数或者低阶项放入O中是很坏得习惯。比如不要写成T(N) = O(2N²)或T(N) = O(N²+2N),这两种都要写成T(N) = O(N²)。即在大O表示得任何分析中，各种简化都是可能发生得。低阶项和常数一般都会忽略和舍弃。此时，要求得精度是很粗糙得。
- 我们总能够通过计算极限limN->∞f(N)/g(N)来确定两个函数的相对增长率。该极限有四种可能:
- 极限是0，那么f(N) = O(g(N))
- 极限是c!=0,那么f(N) = Θ(g(N))
- 极限是∞，那么f(N) = Ω(g(N))
- 摇摆不定，不考虑，计算时间复杂度不会出现这种情况。
小总结
- 其实只要记住关键部分就好了
- O代表小于等于，Ω代表大于等于，Θ代表等于，o代表小于
- 大O的表达式中，常量和相对小的项可以丢弃和忽略
- 大O表达式符合乘法和加法运算
- logkN = O(N) 即任何对数函数增长缓慢
- 对数函数忘记了去看了一下 a的b次方=N 那么可以表示成 logaN = b; (性质 一般地，如果a（a>0，且a≠1）的b次幂等于N，那么数b叫做以a为底N的对数，记作logₐN=b)
- 今天就到这里了，明天继续加油啊。
模型
- emmm模型书本的意思就是一个理想状态的计算机。
- 它做任何简单的工作都恰好花费一个单位的时间
- 有无限的内存
要分析的问题
- 要分析的最重要的资源就是运行时间。
- 而影响时间的主要因素则是使用的算法和对该算法的输入(这里的意思应该是数量级吧)
- 分析所得到的界限是算法的界限，不是程序的界限，程序设计语言几乎不影响大O的答案
- 如果程序比算法分析提出的速度慢得多，那么可能存在低效率的实现(比如在C++中，数组当作整体来拷贝，而不是传递引用)
- 一般来说，如没有相反的指定，那么所需要的都是最坏情况的运行时间。
- 书里举了个栗子，求最大子序列和，针对不同的算法的时间梯度有一个表。这里没办法展示哈，反正传递了一个思想，小数据量输入，大家完成的都很快，O(N)是最好的，线性增长。
运行时间计算(感觉这个比较重要)
- 一段话大概意思是，针对算法分析时间，而且专注于大O，所以会抛弃一下常数和低阶项。
简单的栗子
//下面是一个求和公式，哈哈，虽然有点抽象，但是我只能做到这么多了；就是求i³的和，i ∈[1,n];
N
Σ i³
i=1
//求和算法
public static int sum(int n){
int sum;
sum = 0; //1
for(int i = 1;i<=n;i++){ //2
sum+= i * i * i; //3
}
return sum; //4
}
- 对上面的程序分析很简单。
- 所有声明不计时。；
- 1，4行个占用一个单位时间；
- 第三行做了四个操作，两次乘法，一次加法，一次赋值,而因为循环了N次，所以占用了4N个时间单位；
- 第二行再初始化i，判断i和N的大小和i自增运算有消耗；其中初始化一次消耗1时间单元，判断大小N+1次，所以消耗N+1个时间单位；自曾N次，消耗N个时间单位；一共是2N+2个时间单位；
- 总共加起来是6N + 4个时间单位；
- 同时因为大O会丢弃常数和交小的项，所以这个算法是O(N)
一般法则
法则一:for循环
- 一个for循环的运行时间至多是该for循环内部语句(包括测试)的运行时间乘以迭代次数；
法则二:嵌套的for循环
- 从里向外分析这些循环。再一组嵌套内部的一条语句总的运行时间为该语句的运行时间乘以该组所在所有的for循环的次数的乘积。
- 举个栗子,下面的片段为O(N²),和那个简单栗子一样，保留了最大项。
//就不写完整了
for(int i =0;i<n;i++){
for(int j =0;j<n;j++){
k++;
}
}
法则三:顺序语句
- 将格格语句的运行时间求和即可(这意味着，其中的最大值（这个最大值，改为更大的值比较合适）就是所得的运行时间)那么上面有一段就是我理解错了，确实是max(f(N),g(N))函数
- 举个栗子,下面的判断按顺序执行现时花费O(N),然后花费O(N²)，一次总量是max(O(N),O(N²))也就是O(N²)。
for(int i = 0;i<n;i++){
sum++;
}
for(int j = 0;j<n;j++){
for(int k = 0;k<n;k++){
sum++;
}
}
法则四:if/else语句
if(condition)
S1
else
S2
- 对于上述判断。一个if/else语句的运行时间从不超过判断的运行时间加上S1和S2中运行时间更大者的总和。
- 显然在某些情形下这么估计有点过头，但是决不会低估。
其他
- 其他法则都是显然的？？？这句话什么意思，哪里显然了。啊哈哈哈哈，感觉翻译是不是不那么准确哈。
- 分析的基本策略是从内部(或者深层部分)向外展开工作的。
- 如果有方法调用，那么要先分析调用。
- 如果有递归过程，那么存在几种情况。若递归实际上只是改头换面的for循环，则分析就比较简单。下面举个栗子
//其实就是一个for循环的工作，所以运行时间为O(N)
public static long fac(int n){
if(n <= 1){
return 1;
}else{
return n*fac(n-1);
}
}
- 实际上这个栗子对递归的使用并不好。当递归被正常使用时，将其转换成一个循环时相当困难的。这种情况下，分析将涉及求解一个递推关系。
- 为了观察到这种可能的发生情况，看看下面的栗子，实际上它使用递归的效率低的令人发指。
public static long fib(int n){
if(n<=1) return 1;
else return fib(n-1) + fib(n-2);
}
- 初看，程序没什么大病哈。但是如果将程序飙一下，N值设置为400，我奶奶都跑的比他快哈。
- 分析分析，什么是特码的运行时间。
- 令T(N)为调用函数fib(n)的运行时间。
- 如果N = 0 或者N = 1,则运行时间是个常数，即第一行上做判断以及返回的时间。因为常数并不重要，所以我们可以说T(0)=T(1)=1.
- 对于N的其他值的运行时间则相对与基准情形的运行时间来度量。
- 若N>2,则执行该方法的时间是第一行上的常数工作加第三行的工作。
- 第三行由一次加法和两次方法调用组成。
- 由于方法调用不是简单的运算给，因此必须用它们自己来分析它们。第一次调用时fib(n-1)，从而按照T的定义他们需要T(N-1)个时间单位。类似的第二次方法调用用时T(N - 2)，=。此时总时间为T(N-1) + T(N - 2) + 2，其中2时第一行的判断和第三行的加法。于是对于N>2,存在下列关系.
T(N) = T(N-1) + T(N-2) + 2
emmm,我逃课了？前面的数学相关的知识看得不仔细，这里用到了前面的理论和结论，我看不懂了。
- 但是fib(N) = fib(N-1) + fib(N-2),因此归纳法容易证明T(N) >= fib(N)，emmm哪里容易了。
- 前面的数学相关的章节证明过fib(N) < (5/3)n次幂，类似的计算可以证明(对于N>4)fib(N) >= (3/2)N次幂，从而这个程序的运行时间一指数级增长。这大致上时最坏的情况。
- 这个程序之所以运行缓慢，是因为存在了大量多余的工作。
- 在第三行调用fib(n-1)实际上在某处计算fib(n-2)。这个信息被抛弃了，在第三行的第二次调用又重新计算了一次。抛弃了已经处理过的信息，递归合成起来导致了巨大的运行时间。
- 这就是格言'计算任何事情不要超过一次'的有力佐证。
补充下前面的数据证明
- 归纳法证明
- 第一步证明基准情形。
- 第二部进行归纳假设。一般来说，它指的是假设定理对知道某个极限有限数k的所有情况都是成立的。然后使用这个假设证明对于下一个值(一般为k_+ 1)也是成立的。至此定理得证(在k是有限的情形下)；
- 举个栗子
//作为栗子，我们证明斐波那契数，F0 = 1,F1 = 1,F2=2,F3=3,F4=5,....Fi= Fi-1 + Fi-2,满足对i>=1,有Fi<(5/3)i次幂。
//首先确定基准情形，容易验证F1 = 1< 5/3 ; F2 = 2 < 25/9 ，这就证明了基准情形
//假设定理对于i=1,2....k成立，这就是归纳假设。为了证明定理，我们需要证明Fk+1 < (5/3)k+1次幂.
//根据定义得到Fk+1 = Fk + Fk-1
//下面的k要么是下标，要么是次幂
//Fk+1 = (5/3)k + (5/3)k-1
//(5/3)k + (5/3)k-1 = (3/5)(5/3)k+1 + (3/5)²(5/3)k+1 = (15/25 + 9/25)(5/3)k+1 = 24/25 * (5/3)k+1 < (5/3)k+1
//Fk+1 < (5/3)k+1
//所以就证明了（斐波那契数，F0 = 1,F1 = 1,F2=2,F3=3,F4=5,....Fi= Fi-1 + Fi-2,满足对i>=1,有Fi<(5/3)i次幂。）
- 上面递归的情况，也是使用相同的方法证明的(对于N>4)fib(N) >= (3/2)N次幂。最好的情况也是(3/2)N次幂，这种指数增长的情况确实烂透了(康熙怒斥群臣语气.jpg)。
最大子序列和问题的求解
加油！
网友评论