数据结构复习巩固（1.2）时间空间复杂度

一.分析时间复杂度

首先，写下推导大O阶的方法：

1.用1取代运行时间中的所有加法常数
2.只保留最高阶项
3.去掉最高阶项的系数，若有最高阶项且不是1

1 ) 为何用“1”取代加法常数？

无论输入数据增大多少倍，执行的时间、消耗的空间与输入数据大小无关。
则规定它的时间复杂度表示为O(1)，

不能以O(3)等其他数字来表示。

2 ) 分析时间复杂度时，为什么忽略常数项？为什么只保留最高次项？为什么要去掉最高次项系数？

为了让自己加快进度，就不以图画的方式表示了。

• 比如有三个算法： A（4n+8）； B（2n^2+10）；C （2n^2+9n+1）
  1.在n<=3的时候，A算法的执行次数要多于B
  2.假设n很大时，比如1000：
  A算法执行4008次，B算法却执行了2000010次；
  很明显A的效率远好于算法B。并且去掉常数项 与 其最高项系数，也不会有明显变化。所以，我们在分析时间复杂度时，可以忽略常数项 与 最高次项系数。

  同理，算法B与算法C，在n=1,000,000时：
  B执行2 000 000 000 010次，C执行200 000 9000 001次
  可以说，随着n的增大，算法B在趋近与算法C，
  所以，判断一个算法得效率时，要关注最高阶项的阶数，可以忽略掉函数中的常数项与次要项。

二.常见的时间复杂度

耗费时间从多到少排列：

自己在这里标记一下O(logn)是如何分析的，我总是不会立马反应出相关情景：

• 比如有序数组{4,5,5,6,8,7,9,10}，使用二分法找到10(最坏的情况)：
  1.第一次找到分量6，比10小，包括6和其左边剩下的一半就不用再判断了
  2.这样一半一半地去找，N折半后是N/2，再次是N/4……直到二分到N/N=1
  3.进而想出算式 N*（1/2）^x=1，x=log(2)N
  4.log(2)8最多可以分割3次,即执行3次

简单的的说，就是2^x = N，所以x=log2N

三.算法空间复杂度

1.通常，使用“空间复杂度”表示空间需求。使用“时间复杂度”表达时间的需求。
2.直接讲“复杂度”，一般是指“时间复杂度”。
3.若输入数据所占空间只取决于问题本身，与算法无关，一般所讨论的是除正常占用内存开销外的辅助存储单元规模。
4.若算法执行时所需的辅助空间，相对于数据量来说是个常数，则空间复杂度为O(1)，称为原地工作。

假设原始数据大小为n，一个算法需要m大小的内存才能运行，那么我们就有一个函数f(n)=m。
比如说，如果用冒泡排序对数据排序，如果直接在原始数据上排，那么根本不需要额外的存储空间，而只需要定义几个变量，那么复杂度就是1。

如果排序产生一个新的数组，不修改原来的数组，那么对于排序n个数据，就需要n个新的存储空间，那么复杂度就是n。

再比如，对于两个数组，求它们的笛卡儿积（比如a=1,2,3 b=a,b，结果是1a 1b 2a 2b 3a 3b），那么它的复杂度就是n^2

算法空间复杂度的计算公式：S（n） = O（f(n)）

n为问题的规模
f(n)为语句关于n所占存储空间的函数

还需要注意:
1.递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间
2.对于单线程来说，递归有运行时堆栈，求的是递归最深的那一次压栈所耗费的空间的个数，因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。

四.算法的相关概念

1.算法的定义：算法是解决特定问题的求解步骤的描述。 在计算机中为指令的有限序列，并且每条指令表示一个或多个操作。

2.算法的特性：有穷性、确定性、可行性、输入、输出。

3.算法的设计要求：正确性、可读性、健壮性、高效率和低存储量需求。

4.算法的度量方法：事后统计方法（不科学，不准确）、事前分析估算方法。

再举例理解一个概念：渐进增长

判断一个算法好不好，只通过少量的数据是不能做出准确判断的；我们可以比对算法的关键执行次数函数的渐进增长性来判断：

渐进增长的概念：

• 给定两个函数F(n)与G(n)，如果存在一个整数num，使得所有的 n>num，且F(n)总比G(n)大，
  那么函数F(n)的增长渐进快于G(n)

通过比对算法的关键执行次数函数渐进增长性，判断某个算法A随n的增大，会优于算法B

假设有 算法A（2n^2） 算法B（3n+1）。可以理解为
算法A 要进行两次循环，3次赋值操作；
算法B 也类似地进行 3n+1 次操作：

可以看出：
n=1时，算法B比A少操作一次
n=2时，二者的效率相同
之后随n的增大，算法A的优势越来越明显

• 并且可得出结论：n没有限制的情况下，在n超过2后，算法B的渐进增长快于算法A。