📖什么是数据结构？
数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素集合。
📖什么是算法？
算法(Algorithm)就是定义良好的计算过程，它取一个或一组良好的值作为输入，并产生出一个或者一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。
📖算法效率
通常我们会用复杂度去衡量一个算法的好坏。算法在编写成可执行程序后，运行时需要消耗时间资源和空间资源(内存资源)。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法的运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小，所以对空间复杂度要求很高，但是现在随着计算机行业的快速发展，计算机的存储容量已经达到了很高的程度，内存成本逐渐降低。所以我们如今已经不再需要特别关心一个算法的空间复杂度。
📖时间复杂度
定义：
在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所消耗的时间，从理论上来说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要算法都上机测试嘛？是可以都上机测试，但是这很麻烦，并且同一个程序在不同的机器上运行时间可能差异很大，所以我们有了时间复杂度的分析方法。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作执行的次数，为算法的时间复杂度。
即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。
🔖大O的渐进表示法
实际中我们计算时间复杂度的时候其实并不需要计算精确的执行次数，而只需要知道大概执行次数，所以这里我们引入了大O的渐进表示法。其中大O符号是用于描述函数渐进行为的数学符号。
推导大O阶的方法：
- 用常数1取代运行时间中的所有加法常数
- 在修改后的运行次数函数中，只保留最高阶项
- 如果最高阶项存在且系数是不唯1的常系数，则去除最高项的系数，得到的结果就是大O阶
- 如果最终结果是O(1)，则表示常数次，并不是代表一次
最坏情况：
任意输入规模的最大运行次数（上界）
平均情况：
任意输入规模的期望运行次数
最好情况
任意输入规模的最小运行次数（下界）
一般我们比较关心的是一个算法的最坏情况。
🔖常见时间复杂度计算举例
冒泡排序：
// 计算BubbleSort的时间复杂度？ void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i - 1] > a[i]) { Swap(&a[i - 1], &a[i]); exchange = 1; } } if (exchange == 0) break;//如果没有条语句，最好情况也是O(N*N) } }
最好情况：O ( N ) O(N)O(N)
最坏情况：O ( N 2 ) O(N^2)O(N 2 )
最好情况就是数组本身有序，虽然它有序，但是计算机最初并不知道它是有序的，仍需要遍历一遍数组才能知道它是有序的，因此冒泡排序的最好情况是：O ( N ) O(N)O(N)
冒泡排序一趟可以排好一个元素，最坏情况是数组完全逆序，则第一趟需要交换N − 1 N-1N−1次，第二趟需要交换N − 2 N-2N−2次…直到最后一趟只交换一次，把所有的交换次数加起来就得到了冒泡排序最坏情况下的时间复杂度，其实也就是一个等差数列求和，所以最会情况下的时间复杂度是O ( N 2 ) O(N^2)O(N 2 )
二分查找：
// 计算BinarySearch的时间复杂度？ int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n - 1; // [begin, end]：begin和end是左闭右闭区间，因此有=号 while (begin <= end) { int mid = begin + ((end - begin) >> 1); if (a[mid] < x) begin = mid + 1; else if (a[mid] > x) end = mid - 1; else return mid; } return -1; }
最好情况：O ( 1 ) O(1)O(1)
最坏情况：O ( l o g 2 N ) O(log_2N)O(log
2
N)
最好情况是第一次查找就找到目标值，此时时间复杂度就是O ( 1 ) O(1)O(1)
二分查找中每一次查找要么找到目标值，要么可以排除掉一半数据，因此最坏情况是执行到当区间只剩下一个值的时候，用数学语言来描述这个过程就是：每折半查找一次就会除一次二，一直到结果为1 11的时候，二分查找结束。N / 2 / 2 / 2..... / 2 = 1 N/2/2/2...../2=1N/2/2/2...../2=1。计算执行次数就是看除了多少次2。其结果是除了l o g 2 N log_2Nlog 2 N个2，所以最坏情况就是O ( l o g 2N)O(log_2N)O(log 2 N)，一般可以把简写成O ( l o g N ) O(logN)O(logN)（仅限于时间复杂度，且只有当底数是2的时候才能简化）
O ( N ) O(N)O(N)与O ( l o g 2 N ) O(log_2N)O(log 2 N)的对比：
可见O ( l o g 2 N ) O(log_2N)O(log 2 N)相较于O ( N ) O(N)O(N)在效率上有很大的提升，虽然二分查找的效率很高，但是他有一个致命的限制条件就是数组有序，对数组排序也是需要消耗时间的，因此二分查找在实际中使用的并不是很多，用的更多的是红黑树，它的时间复杂度也是O ( l o g 2 N ) O(log_2N)O(log 2 N)
递归阶乘
// 计算阶乘递归Fac的时间复杂度？ long long Fac(size_t N) { if (0 == N ) return 1; return Fac(N - 1) * N; }
时间复杂度：O ( N ) O(N)O(N)
这里涉及到了递归，Fac一共被递归调用了N次，且每一次Fac中的执行次数是1，所以总的执行次数就是N + 1 N+1N+1个1 11相加，因此时间复杂度就是O ( N ) O(N)O(N)
斐波那契数列
// 计算斐波那契递归Fib的时间复杂度？ long long Fib(size_t N) { if (N < 3) return 1; return Fib(N - 1) + Fib(N - 2); }
时间复杂度：O ( 2 N ) O(2^N)O(2 N )
用递归去求解斐波那契额数列，它的时间复杂度是等比数列求和，最终的时间复杂度就是O ( 2 N ) O(2^N)O(2 N )
常见时间复杂度关系
🔖面试题：消失的数字
题目出处：消失的数字
分析：
这道题大家很容易想到的方法就是先对数组进行排序然后再利用二分查找找到缺失的数字。但是注意题目限制了时间复杂度只能在O ( N ) O(N)O(N)，而我们常用的冒泡排序时间复杂度是O ( N 2 ) O(N^2)O(N
2 )，快排的时间复杂度是O ( N ∗ l o g N ) O(N*logN)O(N∗logN)，都不符合题目要求，因此这条路要被我们Pass掉。我们可以考虑异或来解决这个问题，异或有下面两条性质：a^a=0、a^0=a，并且异或满足交换律和结合律，所以我们可以先让0~N的所有数字进行异或，然后再和数组里面的所有元素进行异或，最终的结果就是缺失的那个数字,这种方法只需要遍历两边数组，时间复杂度是O ( N ) O(N)O(N)。下面来看一下这种思路的代码实现：
int missingNumber(int* nums, int numsSize){ int num = 0; for(int i = 0; i <= numsSize; i++) { num = num ^ i; } for(int i = 0; i < numsSize; i++) { num = num ^ nums[i]; } return num; }
处理上面的这种思路还可以直接利用求和公式算出0~N的总和，再减去数组中的所有元素，最终的结果就是缺失的数字，此种方法只需要遍历一遍数组，因此时间复杂度也是O ( N ) O(N)O(N)。
