1.算法效率
1.1 如何衡量一个算法的好坏
如何衡量一个算法的好坏呢？比如对于以下斐波那契数列：
long long Fib(int N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }
斐波那契数列的递归实现方式非常简洁，但简洁一定好吗？那该如何衡量其好与坏呢？
1.2 算法的复杂度
算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。现在计算机的存储容量已经达到了很高的程度，所以我们如今已经不需要再特别关注一个算法的空间复杂度，有时还会用到用空间换时间
1.3 复杂度在校招中的考察
2.时间复杂度
2.1 时间复杂度的概念
时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。算法中的基本操作的执行次数，为算法的时间复杂度。
即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。
// 请计算一下Func1中++count语句总共执行了多少次？ void Func1(int N) { int count = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j)//嵌套循环是N*N { ++count; } } for (int k = 0; k < 2 * N; ++k) //2*N { ++count; } int M = 10; while (M--) //10 { ++count; } }
Func1 执行的基本操作次数 ： F（N）=N ^ 2 + 2 * N + 10
- N = 10 F(N) = 130
- N = 100 F(N) = 10210
- N = 1000 F(N) = 1002010
实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。
2.2 大O的渐进表示法
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后，Func1的时间复杂度为：
- N = 10 F(N) = 100
- N = 100 F(N) = 10000
- N = 1000 F(N) = 1000000
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。 另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)
2.3常见时间复杂度计算举例
经典的斐波那契
先往下调，不断建立栈帧
时间一去不复返，空间是可以重复利用的
函数所创见栈帧的思考：参数和套用的一样的 一样是一块栈帧，所以复调不会再额外创建空间
3.空间复杂度
空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度
空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因 此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定，即主要看malloc和递归
4. 常见复杂度对比
对斐波那契的探讨:
5. 复杂度的oj练习
一.消失的数字
二.旋转数组
方法一：
1. ++bigin --end 实现反转交换
2. 避免二重函数的灵魂就在于：三次逆转 两边往中间交换
优点： 无循环的嵌套 O(N）时间复杂度
代码如下：
方法二：
空间换时间 memcopy 时间O（N）
创建新数组，截断copy 再整体返回
~省流：
1. 时间复杂度 是算跑多少次的数学函数式 看循环次数 算的是量级
2.空间复杂度 所占存储空间 主要看malloc 和递归的次数
关注【扩容】 (int*) malloc (sizeof(int)*num) 和 递归（函数的栈帧创建）
3.都采用大O表示法 ，O（1）表示的是常数次
4.关注最坏的运行情况，O(N*N)一般就是底线了
~数据结构学习目标：
1. 死磕代码
2. 注意画图和思考
3. 数据结构学习得差不多了，推荐去看看《剑指offer》和《程序员代码面试指南》上的题 做一遍
4. 刷完上面的内容，去刷Leetcode 目标 刷题500+
努力成为一个优秀的程序员~
