写在开头的话：
大家好我是笔者，是一个对IT行业很感兴趣的一个人，这是我在****写的第一篇博客。因为最近在学习的过程当中经常会参考到****的各种知识，所以说把笔记拿出来和大家分享！算是回报社会的一种方法吧。

咳（尴尬的咳嗽），废话不多说，这篇文章是面向对计算机有一点点了解的初中学历以上的朋友。

学习算法大纲

• 时间（渐进）复杂度
• 空间复杂度
• 时间与空间的取舍

时间（渐进）复杂度

算法的时间渐进复杂度也叫时间复杂度
假设设T(n)为执行n次某算法
如：
10cm的面包，3s吃1cm，则有：T(n)=3n
10cm的面包，3s吃一半，则有：T(n)=3logn
x cm的面包，3s吃完，则有：T(n)=3
10cm面包，1s吃1cm，2s吃2cm…则有：T(n)=(1+n)*n/2=0.5n^2+0.5n
这样，我们就有了T(n)这个函数，其中n为输入规模~

但是！如果要比较时间复杂度还需要一些东西。
例如算法A的函数为T(n)=100n，算法B的函数为T(n)=n^2，这时候要比较就要看n的取值了。
那么如何准确的推到出时间复杂度呢？有如下几个原则：
如果运行时间是常数级，统一化成1。
如果是多项式，只保留最高项。
省略最高项系数
结果用O()函数（渐进时间复杂度表示函数）表示
让我们回头看看上面提到的几个场景：
场景1：
T(n)=3n
省去系数后为
T(n)=n
用O()函数表示
T(n)=O(n)

（n的函数图像）
场景2：
T(n)=3log(n)
省去系数为
T(n)=log(n)

（n的函数图像）
场景3：
T(n)=3
常数级啊…
T(n)=O(1)

（n的函数图像）
场景4：
T(n)=0.5n^2+0.5n
保留最高次项
T(n)=0.5n^2
系数化为1
T(n)=n^2

（n的函数图像）
所以说我们可以比较了吧？

（时间渐进复杂度函数图像）
不难看出当n够大时：
O(1)< O(log(n))< O(n)< O(n^2)
是不是很厉害？
当然除了这些复杂度，还有很多诸如：
O(nlog(n))、O(n¹⁰）、O(mn)、O(2^n)、O(n!)
之类的。所以说，加油吧！

新的问题：

如今，计算机硬件性能越来越强了，为什么还这么注意时间复杂度呢？
举个例子：

执行同样的操作：
某Z算法的执行次数是T(n)=100n
Z算法时间复杂度是O(n^2)
某S算法的执行次数是T(n)=5n^2
S算法时间复杂度是O(n)
Z算法运行的机器比S算法要快100倍，那么随着n的增长，谁的运行速度快呢？
T(n)=100n*100
n=1 10 000 5
n=5 50 000 125
n=10 100 000 500
n=1 000 10 000 000 5 000 000
n=100 000 1 000 000 000 50 000 000 000
n=1 000 000 10 000 000 000 5 000 000 000 000

T(n)=100n*100	T(n)=5n^2
10 000	5
50 000	125
100 000	500
10 000 000	5 000 000
1 000 000 000	50 000 000 000
10 000 000 000	5 000 000 000 000

当n=1 000 000时，
就算你比我快100倍，
我有算法我所用的时间比你快——
500倍~~~~~
所以说学好算法很重要呢！

空间复杂度

在运行程序时，会使用许多的中间数据，如变量、链表、数组等。
程序占用空间的大小计算公式记做S(n)=O(f(n))
其中f(n)是算法所占空间的计算函数。
不说多的，直接上例子

• 当算法所需要的储存空间大小固定，和输入规模没有直接关系时，，空间复杂度记为O(1)
• 当算法分配的是一个线性的集合，并且集合大小和输入规模n成正比时，空间复杂度记为O(n)
• 当算法分配的是一个二维集合，并且集合的长度和宽度和n成正比时，空间复杂度记为O(n^2)
• 当算法分配的是一个递归空间，就需要自己判断了！嗯！
  

时间与 空间的取舍

正所谓鱼和熊掌不可兼得。很多时候，我们需要在时间复杂度和空间复杂度之间进行取舍。
很多时候，时间复杂度更为重要一些，我们宁可多分配一些内存空间，也要提升程序的执行速度。