数据结构与算法篇 之复杂度分析（上）
一直以来都想把数据结构和算法学好，可是老是学到一半就放弃了，哈哈这次买了一个课程王争老师学习
这次要用博客把这个过程记录下来
第一步先来普及一下数据结构的概念。。。。。。
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为：
Data_Structure=(D,R)
其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。
算法（Algorithm）是指解题方案的准确而完整的描述，就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
对于数据结构和算法来说，时间复杂度和空间复杂度就是对应着“快“和”省“
大O复杂度表示法使我们最常用的的分析方法：
我们来看一下下面这一段代码
1 int cal(int n) {
2 int sum = 0; 1 unit time
3 int i = 1; 1+1 unit time
4 for (; i <= n; ++i) { 1+1+n unit time
5 sum = sum + i; 1+1+n+n unit time
6 }
7 return sum;
8 }
其中这里用到的是 (2n+2) unit time
1 int cal(int n) {
2 int sum = 0; 1
3 int i = 1; 1
4 int j = 1; 1
5 for (; i <= n; ++i) {
6 j = 1; 2n
7 for (; j <= n; ++j) {
8 sum = sum + i * j; 2n*n
9 }
10 }
11 }
所以这里用到了 （2n*n+2n+3）uint time
T（n） = O（f（n）） T表示的是代码执行的时间，然后f表示是上面的哪条公式
第一条 T（n）= O（2n+2） = O（n）
第二条 T（n）= O（2n*n+2n+3）=O（n*n）
这就是大O的时间复杂度，为什么系数和常熟会被去掉？
当n很大，公式里的低阶和常量和系数对增长趋势影响并不大，所以我们只需要记录一个最大的量级
上面大概的讲清楚了大O的复杂度表示方法
接下来就来介绍三种最常用的分析方法：
1 只关心循环执行次数最多的一段代码
根据上面的代码我们一眼就可以看出，第一段代码是O（n），因为它只有一段
然后到了第二段代码呢？就是两层循环两个n，那么很自然就是O（n*n）
2 加法法则：总复杂度等于量级最大的那段代码
int cal(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
sum_1 = sum_1 + p;
}
int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum_3 = sum_3 + i * j;
}
}
return sum_1 + sum_2 + sum_3;
}
第一段代码的时间复杂度是100（无论这个常数是多少，10000还是1000000跟n都没关系，所以被忽略），
第二段代码的时间复杂度是O（n），第三段代码是O（n*n）
所以答案是O（n*n）
3 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
1int cal(int n) {
2 int ret = 0;
3 int i = 1;
4 for (; i < n; ++i) {
5 ret = ret + f(i);
6 }
7 }
8
9 int f(int n) {
10 int sum = 0;
11 int i = 1;
12 for (; i < n; ++i) {
13 sum = sum + i;
14 }
15 return sum;
16 }
第一段代码的时间复杂度是O（n），第二段代码的时间复杂度也是O（n）
所以时间复杂度等于O（n*n）
是不是觉得你所有代码都知道了，时间复杂度就是这么简单。。。。。。
时间复杂度可不只是这些喔
复杂度量级
一般分成两种，第一种是多项式和非多项式量级
非多项式量级只有O（2^n）和O（n！），当n的规模越大，算法时间会急剧增加，所以是非常低效的算法
看图就知道了
O（1） 常量级的时间复杂度，无乱常量是但是，1000？100000？都是1，谢谢
O（logn）和O（nlogn）
这是我最讨厌的分析的，真的，当初就是搞不懂这个
哈哈现在嘛
1 i=1;
2 while (i <= n) {
3 i = i * 2;
4 }
什么意思也就是 求2^x = n
也就是 x=log2n
1 i=1;
2 while (i <= n) {
3 i = i * 3;
4 }
什么意思也就是 求3^x = n
也就是 x=log3n
log3n = log3 2 * log2 n哈哈记忆中高中还是大学是有这么一条公式的
log3 2是常数，所以选择忽略。。。。。。凄惨啊
所以啊。。。最后连数字都忽略掉了。。。更加惨无人道了
O（logn），那吗另外一个O（nlogn）呢，执行n次O（logn）就有了
O（m+n）
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
还有。。。这代码一看怎么这么熟悉。。。当初面试的时候考过。。。。。。O（m+n）谢谢。。。哈哈
这个跟上面有点不一样，不是两个n+n，m和n的值谁大并不知道，所以啊就是O（m+n）
好了讲了一大堆的时间复杂度，总该讲一下空间复杂度吧，不然也太不公平了。。。。。。
int i；
int j；
int a[n];......这样好像不对的。。。。。。。
好的，不管了，那么它的空间复杂度是多少呢？O（n+2）常量去掉，那么就是O（n）
常用的空间复杂度有O（1），O（n），O（n*n）
好了，空间复杂度讲完了。。。。。。。就是这么不公平了。。。