数据结构基本知识点
具体内容包括：
大O记号（最常用）
T(n):表示算法执行时间。 注意：关心足够大的规模，注重考查成本的增长趋势。
T(n) = 需要执行的基本操作次数。 在满足一些条件后，将T(n)=表示为一个f(n)的函数。大O内用来近似的函数f(n)会更加简洁。同时依然能准确反映增长趋势。大O给出了增长的上界。可以认为大O是对T(n)的一个悲观的估计。
大Ω记号
大Ω给出了T(n)的增长的下界。
大θ记号
θ记号是没有大小之分的，可以认为是对T(n)的一个确切的描述。 图中的这个记号，表明这个的一个T(n)位于上确界和下确界之间，所以可以被视为一个准确的估计。
常数
不含循环和分支以及递归调用的可定时常数时间内能执行完成。
对数
需要注意的是，对数的底数和幂次都是无所谓的。因为一个以a为底的对数，完全可以通过在前面乘上一个系数转换成一个以b为底的。 
多项式
多项式级别的复杂度，使我们追求的一个目标。
指数
这类算法随着输入规模的增大，时间增长极快，通常被认为是不可忍受的。
最后给出一张图来，来直观认识下：
算法分析
级数
分析算法的时候，通过“不变性”和“单调性”证明算法的正确性是我们常用的办法。 三生三世中的一天，就类似于一天中的一秒。+
通过改进算法，可以极大地缩短运行时间：
通过硬件，将30年，变成了20分钟，但是通过算法的优化，直接将30年缩短到了30秒。
迭代与递归
对于迭代类型程序的时间复杂度分析，概括而言就是级数或者级数求和。这次我们关注重点是递归。
分析递归调用的时间复杂度的时候，我们可以把每一次递归实例中的递归调用忽略不计，视它为下一次递归调，以此类推。 divided and conquer 是我们今天介绍的主题。
我们讨论空间的时候，是把输入的参数所占用的空间排除之后程序中所占用的空间。
减而治之
递归跟踪：直观形象，仅适用简明的递归形式。 递推方程：间接抽象，更适用于复杂的递归形式。
递推方程
使用递推方程的时候，如何计算时间复杂度： 解方程
“递归基”.是递归函数的一种平凡情况，只有有递归基，递归才不会一直进行下去。
分析时间复杂度的时候，我们先把递归调用忽略不计，发现每次调用中也没有迭代的部分，所以，每一个递归实例所需要的时间是常数的。 
如何快速计算出时间呢？ 我们把递归跟踪清晰地展示在图中。因为每一个递归实例所需要的时间都是常数1，所以，计算整个递归调用需要的时间，其实就是计算有多少个递归调用实例。1+2+4+8，我们发现这是一个几何级数。所需时间是和最后一项同阶的。而最后一项的含义有多少个项，不难发现，有多少个元素，就有多少个项，所以很容易得到n.所以时间复杂度是O(n).
总结
本章我们介绍了： 迭代与递归的算法。 减而治之和分而治之的算法策略。 递归算法两种典型的常用的分析方法：递归跟踪和递归式。
动态规划
fib数列可以形象地描述为上台阶过程，你可以每次上一步，也可以每次上两步。比如你要上到第六个台阶。那么有两种走法，一种就是从第4级走两个过来，或者是从第5级走一个过来，而对应的，上到第4级也有很多种方法，上到第5级也有很多种方法。 排列组合公式：
递归可以帮我们找一个可行并且正确的解。但是如何将效率提高，使之变成一个使用算法的话，我们往往还需要进行近一步的调试。而在这个过程中，动态规划扮演着非常重要的角色。 动态规划：消除重复计算，提高效率。
第一章习题：
Resource Refernce
- https://lucky_echo.gitbooks.io/dsa-thu/content/chapter1.html
正文到此结束
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
