数据结构与算法入门基础
第一个简单的算法题
题目描述
给定一个整数，判断是否是2的N次方？
示例1:
输入: 1输出: true解释: 2^0 = 1
示例2:
输入: 16输出: true解释: 2^4 = 16
示例3:
输入: 218输入: false
解题
方案1:
class Solution {public boolean isPowerOfTwo(int n) {if(n == 0) {return false;}while(n%2 == 0){n = n/2;}return n == 1;}}
方案2 ：
转换为2进制,按位与运算
2===>10
1===>01
10 & 01 =00
4===>100
3===>011
100 & 011=000
8====>1000
7===>0111
1000 & 0111 = 0000
16===>10000
15===>01111
10000&01111=00000
class Solution {public boolean isPowerOfTwo(int n){if(n == 0){return false;}if(n&(n-1) == 0){return true;}return false;}}
对比两种方案，方案1需要运行很多次，方案2只需要运行一次。显然方案2是更好的解决方案，更高效。
什么是数据结构与算法
首先数据结构与算法很重要很重要——就好像我们人类离不开氧气，绿色植物离不开二氧化碳一样！！！
数据是一切能输入到计算机中的信息综合，结构是指数据之间的关系，数据结构就是将数据和它们之间的关系存储到计算机当中。
算法是为了更有效的处理数据，提高数据运算效率。是为数据结构服务的，例如：数据结构通常伴随有查找算法、排序算法等
为什么学习数据结构与算法
BATJ一线互联网公司面试必问技术
为什么必问？数据结构与算法是所有计算机类的基础，基础要扎实。大企业看中的是潜力。可以承担更多的责任。
如果你不想做一辈子的CRUD工程师：业务工程师，CRUD工程师。
架构师必备，写出框架级的代码。
提升自己的能力，不被行业淘汰。
书籍推荐
数据结构与算法
数据结构与算法分析：Java语言描述
刷题网站
力扣 https://leetcode-cn.com/problemset/all/
算法的特性
五个特征
有穷性、确定性、可行性、有输入、有输出
设计原则
正确性、可读性、健壮性
高效率与低内存
内存占用最小，CPU占用最小，运算速度最快。
评估算法的两个重要指标
时间复杂度：运行一个程序所花费的时间。O()
空间复杂度：运行程序所需要的内存
时间复杂度
时间复杂度计算的意义
怎么测试接口的性能？通过压测，冒烟。但是要依赖测试环境，流程很长，而且搞的规模或者数据不准确。比如排序算法: 1 2 3 /3 2 1，你应该用代码分析。也就是时间复杂度。
时间复杂度表示方法
大O表示法：O(1)、O(n)、O(nlogn)、O(n^2)、O(logn)
几种常见的时间复杂度分析:指的是某一段代码运行的次数。
计算时间复杂度往往是计算比较大的而且是不确定的数，如果已经确定了，那么就不用计算了，也就是我们说的常量。
常数：O(1) 1表示的是常数，所有能确定的数字我们都用O(1)
对数：O(logn)、O(nlogn)
线性：O(n)
线性对数：O(nlogn)
平方：O(n^2)
N次方：O(n^n)
我们怎么找时间复杂度
找到有循环的地方。用时间复杂度分析。
找到有网络请求的地方。(PRC、数据库请求) 。就是测试时间log打印，计算平均时间。
时间复杂度如何分析
public class BigO {public static void main(String[] args) {/***********************O(1)************************/int a = 1; //1次 O(1)for(int i = 0 ;i < 3;i++){//这里会运行几次？4次 在第4次的时候结束 跳出 i=3 (0 1 2 3)a = a + 1; //这里运行几次？3次 O(1)? n+1 n 1 O(3)? => O(1)}int n = Integer.MAX_VALUE; //表示n是未知/***********************O(logn)************************/int i = 1;for(int j = 0 ; j < n ;j++){while ( i <= n){i = i * 2;}}while( i <= n){i = i * 3; //O(logn)}//i的值：2 4 8 16 32,=》2^0,2^1,2^2,2^3,.....2^n//===> 2^x=n =>求出x就是我们运行的次数 => x=log2n =>计算机忽略掉常数 => x = logn =>O(logn)//二分查找 为什么是logn的算法？//1~100 找69这个数//50:(1+100)/2 = 50/***********************O(n)************************/for(i = 0 ; i < n;i++){a = a +1; //运行了多少次？O(n) n一定是一个未知的，如果n是已知6的}/***********************O(n^2)************************/for(i = 0 ; i < n;i++){ // 乘法 n次for(int j = 0 ; j < n ;j ++){ //n次a = a +1; //运行了多少次？O(n^2)}}for(i = 0 ; i < n;i++){ // 乘法 n次for(int j = i ; j < n ;j ++){ //n次a = a +1; //运行了多少次？n*(n+1)/2 => O(n^2); => (n^2+n)/2 => 注意有个规律，有加减法的时候，找次数最高的那个}}/** 外面的循环次数是确定的 O(n) n次，1 2 3 4 。。。n** i=n 运行1次* i=n-1 运行2次* .* .* .* i=1 运行n次** 1,2,3 …… n次 最后里面这层要运行多少次？1+2+3+……+n=n*(n+1)/2**/}}
空间复杂度
空间复杂度分析的意义
找消耗内存的地方
如何找出成效的空间复杂度
使用了内存空间的地方，比如数组、链表、缓存对象
几种常见的时间复杂度分析：指的是某一段代码s
几种常见的时间复杂度分析：指的是某一段代码。
几种常见的时间复杂度分析：指的是某一段代码。几种常见的时间复杂度分析：指的是某一段