剑指Offer--算法与数据结构（时间复杂度和空间复杂度）

本文主要是介绍剑指Offer--算法与数据结构（时间复杂度和空间复杂度），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

算法是什么，算法就是解决问题的思路

这个是一个日积月累的过程

位运算，二进制

如果去验证一个数是否是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=log2^{n。在有三条支路的树状结构中是log3}n,以此类推)

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（n^{2）–>O（n}x）–>

每次优化一个等级性能就会优化非常多

优化的时候我们要往O（1）优化

案例：登陆功能–判断用户名密码O（1）到数据库里查记录（假设这个接口出现性能问题，就是到数据库中查记录）如果达不到性能要求，可能要上分布式或者加缓存，这个时候已经不是代码的问题了是硬件的问题了

O（1）–>O（logn）–>O（n）–>O（nlogn）这几个效率都是很高的，优化的空间不是很大了

如果有个人写了一个冒泡排序那个很离谱的话，我们是不是就要用其他排序去优化

比如快速排序或者归并排序或者堆排序、桶排序

空间复杂度的话就是找花了内存的地方，看数据。看开了空间的地方。比如数组 、链表、缓存对象、递归。就差不多就是这样，具体往代码里套就是了

面对这么多知识点我们应该怎么学习

根据学习目的来

+提升能力（全学）

+突击面试的（数组、链表、排序、二叉树、红黑树、B（+ - *大家族）Tree）

+进阶（树轮+图论+赵云专项+每节课的理论部分）

这篇关于剑指Offer--算法与数据结构（时间复杂度和空间复杂度）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！