一、数据结构与算法基础知识
从广义上讲，数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。从狭义上讲，就是指某些著名的数据结构和算法，比如队列、栈、堆、二分查找、动态规划等。数据结构和算法是相辅相成的，数据结构为算法服务，算法要作用在特定的数据结构之上。数据结构思维导图基础数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树基础算法：地柜、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
二、时间复杂度和空间复杂度
时间复杂度
1、概念
时间复杂度的全程是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。
2、时间复杂度分析
只关注循环执行次数最多的一段代码 我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数对多的那段代码即可加法法则：总复杂度等于量级最大的那段代码的复杂度 随着数据规模的增长，低阶和常量的量级就可以忽略，所以总的时间复杂度等于量级最大的那段代码的时间复杂度乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
3、几种常见时间复杂度实例分析
常量阶 O(1)
int i = 8;
int j = 6;
int sum = i +
// 只要代码的执行时间不随n的增大而增长，这样的代码的时间复杂度我们都记作 O(1)
// 或者说，一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，时间复杂度也是O(1)
指数阶 O(2^n)对数阶 O(logn)
int i = 1;
while (i <= n) {
i = i * 2;
}
线性对数阶 O(nlogn)
//这个方法循环执行n次，时间复杂度就是O(nlogn)
int i = 1;
while (i <= n) {
i = i * 2;
}
阶乘阶 O(n!)线性阶 O(n)平方阶 O(n^2) 、立方阶 O(n^3).... k次方阶O(n^k)-
空间复杂度
1、概念
空间复杂度全程是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
2、常见的空间复杂度
常量阶 O(1)对数阶 O(logn)线性阶 O(n)
// 只有第三行申请了一个大小为n的int类型的数组，其他的代码都没有占用更多的空间，所以这段代码的空间复杂度是O(n)
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}
for (i = n-1; i >= 0; --i) {
print out a[i]
}
}
线性对数阶O(nlogn)平方阶 O(n^2) 、立方阶 O(n^3).... k次方阶O(n^k)
三、时间复杂度分析
// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
1、最好时间复杂度
在最理想的情况下，执行完这段代码的复杂度。（上面代码中要查找的变量x正好是要数组的第一个元素）
2、最坏时间复杂度
在最糟糕的情况下，执行完这段代码的复杂度。（数组中没有要查找的变量x）
3、平均时间复杂度
最好时间复杂度和最坏时间复杂度都是比较极端的情况，平均时间复杂度表示的是在正常情况下可能的时间复杂度，用代码在所有情况下执行的次数的加权平均值标示
4、均摊时间复杂度
在代码执行的所有复杂度情况中绝大部分是最低级别的复杂度，个别情况是高级别复杂度切发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上，基本上均摊结果就等于低级别复杂度。它属于平均时间复杂度中的一种特殊的平均时间复杂度。
转载于:https://www.cnblogs.com/jakaBlog/p/11284504.html
相关资源：数据结构与算法分析—C语言描述 高清版
