一、时间复杂度和空间复杂度
1.时间复杂度和空间复杂度统称为算法效率
时间复杂度主要衡量一个算法的运算速度
空间复杂度主要衡量一个算法需要的额外空间
注：以前的时候比较注重空间效率，因为存储容量很小。但是现如今计算机行业发展迅速，存储容量已经达到了很高的程度，所以现在更重视时间效率。
2.算法中的基本操作的执行次数，为算法的时间复杂度
算法在运行过程中临时占用存储空间的量度，为算法的空间复杂度
时间复杂度并不是看时间的长短，而是看执行的次数
空间复杂度并不是看空间的大小，而是看执行的个数
3.时间复杂度、空间复杂度表示法
4.常见的时间复杂度
//请计算一下Func1基本操作执行了多少次 void Func1(int N) { int count = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { ++count; } } for (int k = 0; k < 2 * N; ++k) { ++count; } int M = 10; while (M--) { ++count; } printf("%d\n", count); }
综上可以看出来：其关键作用的是：n*n，故时间效率为：O（n^2）
注：大O的渐进表示法去掉了那些对结果影响不大的项
常见的时间复杂度：O( 1 ) O( n ) O( n^2 ) O( logn )
注：O（logn）：二分查找法
5.推导大O阶方法
用常数1取代运行时间中的所有加法常数。
在修改后的运行次数函数中，只保留最高阶
如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大0阶。
6.另外有些算法的时间复杂度存在最好、平均和最坏情况
最坏情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期望运行次数
最好情况:任意输入规模的最小运行次数(下界)
注：在实际中一般情况关注的是算法的最坏运行情况
7.常见的空间复杂度
占用了5个空间，使用了常数个额外空间，所以空间复杂度为O（1）
二、OJ题
消失的数字OJ链接：https://leetcode-cn.com/problems/missing-number-lcci/
1.消失的数字
数组 nums 包含从 0 到 n 的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。
你有办法在 O(n) 时间内完成吗？
例：输入：【3，0,1】
输出：2
2.轮转数组
旋转数组OJ链接：https://leetcode-cn.com/problems/rotate-array/
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
首先一起来分析三种算法：
NONONO思路一效率太低了吧！
