前言：📫 作者简介：小明java问道之路，专注于研究计算机底层，就职于金融公司后端高级工程师，擅长交易领域的高安全/可用/并发/性能的设计和架构📫
🏆 Java领域优质创作者、阿里云专家博主、华为云享专家🏆
🔥 如果此文还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦
本文导读
本文介绍了学习算法和数据结构的方法和准备工作，介绍了学习算法的一些必要的专业名词，时间复杂度、空间复杂度的代码案例
一、训练准备-怎么学？学到什么程度？
1、怎么学？
第一遍：读题和思考5-15分钟，如果有思路的话自己开始做和写代码（思考所有的可能解法）；
如果没思路看题解，前提是读题思考15分钟（理解题目的意思），看题解默写背诵（思考所有的可能解法）、熟练（分析每种解法的思路），然后开始自己写（闭卷）
第二遍：默写程序、调试（先在头脑里面调试，实在不行再在编译器里调试），这一遍一定要弄会，会写，哪怕时间长（刻意练习、分解—构建知识树、知识模型）
第三遍：隔一天再写一遍程序，思考那里写错了，为了记忆
第四遍：一周后再写一遍，思考和其他的知识模型的关联，建立知识模型！
第五遍：面试前写一遍，复习
2、学到什么程度？
可以构件知识树（知识模型、思维导图），做过的题有多种解法，讲出来举一反三
二、复杂度原理
衡量代码的好坏，包括两个非常重要的指标：1.运行时间；2.占用空间。衡量标准有个度就是时间复杂度和空间复杂度
时间复杂度：算法的时间复杂度表示为，若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度，简称时间复杂度。
空间复杂度：算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。
如何推导出时间复杂度呢，有如下几个原则：
1、如果运行时间是常数量级，用常数1表示；
2、只保留时间函数中的最高阶项；
3、如果最高阶项存在，则省去最高阶项前面的系数。
如何影响空间复杂度的三个方面：
一个算法在计算机存储器上所占用的存储空间，包括
1、存储算法本身所占用的存储空间
2、算法的输入输出数据所占用的存储空间
3、算法在运行过程中临时占用的存储空间
三、复杂度算法分析
（一）几种时间复杂度的代码示例
O(1) 算法
一种算法的运算次数与数据规模无关，那么它的时间复杂度是常数级别的，写成 O(1)，哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标。
int fun(int key) { return -key; }
O(logn) 算法
时间复杂度O(logn)对数阶，当数据增大n倍时，耗时增大logn倍，二分查找就是O(logn)的算法，每次排除一半的可能
int fun(int a[], int key) { int low = 0; int high = a.length - 1; while (low <= high) { int mid = low + (high - low) / 2; if (a[mid] > key) high = mid - 1; else if (a[mid] < key) low = mid + 1; else return mid; } return -1; }
O(n) 算法
线性阶，就代表数据量增大几倍，耗时也增大几倍，比如常见的遍历算法
void fun(int i) { for (int a = 0; a < i; a++) }
O(nlogn)算法
线性对数，就是n乘以logn（遍历的同时内部可以排除一半数据），当数据增大256，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。
public void mergeSort(int[] arr, int p, int q) { if (p >= q) return; int mid = (p + q) / 2; mergeSort(arr, p, mid); mergeSort(arr, mid + 1, q); merge(arr, p, mid, q); } private void merge(int[] arr, int p, int mid, int q) { int[] temp = new int[arr.length]; int i = p, j = mid + 1, iter = p; while (i <= mid && j <= q) { if (arr[i] <= arr[j]) temp[iter++] = arr[i++]; else temp[iter++] = arr[j++]; } while (i <= mid) { temp[iter++] = arr[i++]; } while (j <= q) { temp[iter++] = arr[j++]; } for (int t = p; t <= q; t++) arr[t] = temp[t]; }
O(n²)算法
void fun(int i) { for (int a = 0; a < i; a++) for (int b = a; a < i; a++) }
对比O(n³) 算法、 O(n²)算法、O(nlogn) 算法、O(n) 算法、O(logn) 算法
（二）几种空间复杂度的代码示例
常量空间
类似于时间复杂度 O(1)，当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记作O(1)
int a = 0;
线性空间
当算法分配的空间是一个线性的集合（如数组），并且集合大小和输入规模 n 成正比时，空间复杂度记作 O(n)
int[] a = new int[n];
二维空间
当算法分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模 n 成正比时，空间复杂度记作 O(n^2)
int[][] arr = new int[i][j];
递归空间
在操作系统执行程序时，会专门分配一块内存，用来存储“方法调用栈”。此时栈空间复杂度就是 O(n)。
方法调用栈包括入栈和出栈两个操作：当进入一个新方法时，执行入栈操作，把调用的方法和参数信息压入栈中。当方法返回时，执行出栈操作，把调用的方法和参数信息从栈中弹出
void fun(int i) { fun(i); }
小结：本文介绍了学习算法和数据结构的方法和准备工作，介绍了学习算法的一些必要的专业名词等等
