作为一名非科班出身的程序员，要修炼的内功其实挺多的。现在就开始记录自己修炼数据结构与算法的路程。
从数据结构与算法的字面意义上面来看，一方面是数据结构，另外一方面是算法。
一、算法
计算机处理信息的本质还是在于算法。算法是独立存在的一种解决问题的方法和思想。对于算法而言，语言并不重要，重要的是思想，语言只是去实现一个算法的载体而已。在LeetCode上面，我们可以看到能够刷题的语言有C、C++、Java、Python、Javascript等语言。
算法具有五个特性：
1、输入: 算法具有0个或多个输入
2、输出: 算法至少有1个或多个输出
3、有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
4、确定性：算法中的每一步都有确定的含义，不会出现二义性
5、可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成
时间复杂度和大"O"记法
常常我们会看到时间复杂度这概念，没有接触过数据结构与算法的话，可能会误以为是采用了代码运行的时间去衡量算法的有效性，但是这样的观念是不对的。因为同一种代码放到不同机器上去跑，得到结果所消耗的时间是不同的。但是我们换一种思路去看待这个问题，同样的代码，他运行的步骤肯定是相同的。即使在不同的机器上面，每一步运行所消耗的时间是不同的，但是对于算法进行多少个基本操作（即花费多少时间单位）在规模数量级上却是相同的，由此可以忽略机器环境的影响而客观的反应算法的时间效率。
三种时间复杂度
在进行算法时间复杂度分析的时候，存在如下几种时间复杂度
- 最优时间复杂度：完成task最少需要的操作数。
- 平均时间复杂度：完成task平均需要的操作数。
- 最坏时间复杂度：完成task最多需要的操作数。
我们最为关注的就是最坏的情况，也就是最坏时间复杂度。然后我们在一些排序算法里面可以看到它们三者分别的情况是什么。
常见的时间复杂度
我们需要记住这个时间复杂度的关系
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2) <O(n^3) <O(2^n) <O(n!)<O(n^n)
Python内置类型的性能分析
就列表而言
| 操作 | 时间复杂度 | 解释 |
|---|---|---|
| index[n] | O(1) | 索引一步就取到了 |
| index assignment | O(1) | 采用索引的方式赋值 |
| append | O(1) | 尾部追加 |
| pop() | O(1) | 尾部给弹出一个元素 |
| pop(i) | O(n) | 最坏情况就是从头部取 |
| insert(i, item) | O(n) | |
| del operator | O(n) | 代表了一个元素一个元素去删除 |
| iteration | O(n) | 遍历 |
| contains(in) | O(n) | 看元素是不是在list里面 |
| get slice[x:y] | O(k) | 定位到x为O(1)，一直取到y，跨度是k |
| del slice | O(n) | 中间元素给删掉，那么后面的元素就需要向前移动，补上空位置 |
| set slice | O(n+k) | 先是要删除一部分元素，然后再补充上 |
| reverse() | O(n) | |
| concatenante | O(k) | 两个列表相加，第二列表的元素为k个 |
| sort | O(nlogn) | 封装的sort |
| multiply | O(nk) | 一个列表可以去乘一个数，n是元素，k是个数 |
dict内置操作的时间复杂度
| 操作 | 时间复杂度 | 解释 |
|---|---|---|
| copy | O(n) | 就是复制一份 |
| get item | O(1) | 通过键可以立马拿到值 |
| set item | O(1) | |
| delete item | O(1) | |
| contains (in) | O(1) | |
| iteration | O(n) | 迭代肯定是O(n) |
二、数据结构
数据结构知识静态的描述了数据元素之间的关系。Python里面内置了挺多的数据结构，例如列表、元组、字典等等。
程序 = 数据结构+算法
三、时间复杂度实际分析
我们可以通过主定理来分析一下递归问题里面的算法复杂度。
持续更新中...
数据结构与算法系列博客：
一、数据结构与算法概述
二、数组及LeetCode典型题目分析
三、链表（Linked list）以及LeetCode题
四、栈与队列（Stack and Queue
五、树（Trees）
六、递归与回溯算法
七、动态规划
八、排序与搜索
九、哈希表
参考资料：
1、https://baike.baidu.com/item/%E4%B8%BB%E5%AE%9A%E7%90%86/3463232?fr=aladdin
网友评论