算法是什么,算法就是解决问题的思路
这个是一个日积月累的过程
位运算,二进制
如果去验证一个数是否是2的次方
很简单就是一个数如果是2的次方那么他必然是形如10000的样子
那么n-1的话就会是形如01111的样子那么两个数字做与运算jiuhui=0
其他数字如果是超过两个一的话那么即便-1,高位的1也不会发生变化。所以这道题就很有意思
他们的复杂度是O(1),太快了,这就是优化
为什么大厂喜欢问算法与数据结构
+大企业看中的是什么?看中的是潜力,希望你能承担更多的责任,如果我一眼看得到潜力,我要你干什么,阿里巴巴是一个大公司一下又倒不了,那么他们面临的是复杂多样的环境,需要厉害的人去面对
还喜欢问技术
有很多工程师是CRUD工程师(业务工程师),没用。只需要去查API就好了
有很多人都用过Redis,但是你们知道他们的数据结构是怎么写的吗?,很多公司包括技术都会把CRUD给你封装好,如果你都不知道数据机构又怎么知道是否适合你受伤的业务,如果不去看又怎么知道。
如果做一个统计的功能,那么很多人会用一个循环都不会去想其他想法,如果并发一高就爆掉了
我们作为架构师最大的目标是要写出这种框架级开源级的代码,成为行业的精英,你怕什么中年危机,不被行业淘汰。
这个行业是一个迭代非常快的行业,技术是需要不断地更新的。努力学习,我们需要把最基础东西学会
底层是不会变的,万变不离其宗。B+tree发展了很多年才出现的
赵云推荐了四本书
数据结构严版
大话数据结构
算法竞赛入门经典
算法艺术信息学竞赛
算法特性
有穷性(有结束条件)、可行性(能够运行)、确定性(有确定的意义)、有输入、有输出
设计原则:正确性、可读性、健壮性(bug)、写出的代码很少有bug、而且系统比较稳定
高效率(运行时间要快,别人要求三秒我要一秒就解决出来)与低存储(内存解决有性能上的优越):内存+CPU
高效+低存储=开源级源码 (赵云说的)
内存占用最小:CPU占用最小,运算速度最快
评价算法的两个重要指标(时间复杂度(高效)+空间复杂度(低存储)):占据整个学习的半壁江山,接下来我们会重点学习时间复杂度的计算
时间复杂度运行一个程序所花费的时间O()(运行代码所需要的时间)
空间复杂度,运行程序所需要的内存OOM(运行代码所需要的内存)
离散数学里面有怎么去算以上两种复杂度,暑假再去学一遍离散数学
时间复杂度计算的意义:怎么测试接口的性能?压测、冒烟测试。要依赖测试环境吧,流程很长,如果测试人员对于你的程序不了解,给了一个很大的数据集就会容易出问题,还依赖机器。我们要学会自己判断这个就是时间复杂度
时间复杂度的表示方法用大O表示
时间复杂度来分析
+找for while 递归,而且要找循环量最大的那一段
+同级循环怎么算
时间复杂度
常数:O(1)
常数就是确定的次数
线性:O(n)
这不就是循环嘛 for(i=0 ; i<N ;i++ ){ N=N+1;//看复杂度其实是看语句执行力多少次而不是看上面的循环结束条件 } 运行了N次,N是未知的
对数:O(logn):log在算法里面是默认2为底。演变过来是2^x=n–>logn=x
所以在左右两条支路的树状结构中层数就是logn(x=log2n。在有三条支路的树状结构中是log3n,以此类推)
i=1; while(i<=n){ i=i*2; } 问?这里会执行多少次 答:log2^n i=1; while(i<=n){ i=i*3; } 问?这里会执行多少次 答:log3^n 这他妈就是逆推嘛 二分查找、二叉搜索树
线性对数:O(nlogn)
就是在上面对数的代码外面嵌套一层循环 i=1; for(j=0; j<n; j++){ while(i<=n){ i=i*3; } } 问?这里会执行多少次 答:nlog3^n
平方:O(n^2)
运行了多少次,时间复杂度多少就是看运行了多少次 平方就是两个for嵌套 三次方就是三分for嵌套 冒泡排序的时间复杂度就是平方
N次方:O()
计算时间复杂度的时候,计算的是执行的次数。最后的等式出来可以忽略常数再计算
其实最快的计算方法就是找最高阶,最高阶的结果就是结果:比如有加法的情况下.因为如果N是无穷大的话N^2和N差的数量级很多所以可以忽略
如果在工程代码里面我们怎么找时间复杂度
+首先找到有循环的地方
+找到有网络请求的地方(数据库请求、RPC:远程调用,在分布式中使用)
这两个地方是很耗时间的,以上基本就可以算出来工程的时间大概是怎么样的
测试:log打印,多搞点数据。就可以计算出平均时间
时间复杂度指的是某一段代码
写数据结构和算法我们的追求就是把代码优化到不能再优化
效率最高
O(1)–>O(logn)–>O(n)–>O(nlogn)–>O(n2)–>O(nx)–>
每次优化一个等级性能就会优化非常多
优化的时候我们要往O(1)优化
案例:登陆功能–判断用户名密码O(1)到数据库里查记录(假设这个接口出现性能问题,就是到数据库中查记录)如果达不到性能要求,可能要上分布式或者加缓存,这个时候已经不是代码的问题了是硬件的问题了
O(1)–>O(logn)–>O(n)–>O(nlogn)这几个效率都是很高的,优化的空间不是很大了
如果有个人写了一个冒泡排序那个很离谱的话,我们是不是就要用其他排序去优化
比如快速排序或者归并排序或者堆排序、桶排序
空间复杂度的话就是找花了内存的地方,看数据。看开了空间的地方。比如数组 、链表、缓存对象、递归。就差不多就是这样,具体往代码里套就是了
面对这么多知识点我们应该怎么学习
根据学习目的来
+提升能力(全学)
+突击面试的(数组、链表、排序、二叉树、红黑树、B(+ - *大家族)Tree)
+进阶(树轮+图论+赵云专项+每节课的理论部分)