《算法图解》笔记
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了《算法图解》笔记，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2819字，纯文字阅读大概需要5分钟。
内容图文
C1 算法简介
1. 二分查找
如果数据的组织是有序的，那么从中间开始进行查找，每次判断可以排除一半的数据，可以极大的节省资源。对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步。
def binary_search(list, item):
low = 0
high = len(list)—1
while low <= high:
mid = (low + high)
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None
2. 大 O 表示法
大O表示法是一种特殊的表示法，指出了算法的速度有多快（大O表示法表示的是最慢的情形）。
- 假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作，这个运行时间为O(n)。
- 二分查找需要执行log n次操作，使用大O表示法，这个运行时间为O(log n)。
算法的速度指的并非时间，而是操作数的增速，随着输入的增加，其运行时间将以什么样的速度增加。
C2 选择排序
数组和链表
- 数组：占用连续地址的内存空间，如果内存不够大，是无法创建数组的。此外，数组也无法增加或减少数量。
- 链表：可以存储在内存的任意空间，链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。这样的存在一个问题，当我们要查找第n个元素的内容时，必须从第一个元素开始逐个读取，效率很低。
效率
| 数组 | 链表 | |
|---|---|---|
| 读取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 删除 | O(n) | O(1) |
- 数组读取时只需要读出对于地址的元素，但插入和删除时必须将元素后移。
- 链表读取时需逐个读取，插入和删除时只需要修改对应元素指向的地址即可。
选择排序
遍历所有数据，找到最大或最小的那个，存入新列表的第一个位置，再找出第二打或小的放入新列表，依此类推。
C3 递归
递归是指：在函数的定义中使用函数自身的方法。
每个递归函数都有两部分：
-
基线条件（base case）
-
递归条件（recursive case）：定义如何停止，避免死循环。
栈
栈是只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。
使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。
C4 快速排序
分而治之
工作原理：
- 找出基线条件，这种条件必须尽可能简单。
- 不断将问题分解（缩小规模），直到符合基线条件。
快速排序
快速排序使用了分而治之的思想。
- 基准条件：只包含一个元素的序列；
- 问题分解：找到一个基准值，将大于它的放一边，小于的放另一边；
def quicksort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print quicksort([10, 5, 2, 3])
算法效率
在平均情况下，快速排序的运行时间为O(n log n)，快速排序的性能高度依赖于基准值的选择。
最糟情况
基准值总是最边缘的元素，其中一个子数组始终为空，这导致调用栈非常长，最终效率为O(nlogn)
最佳情况
基准值总是中间的元素，因为你每次都将数组分成两半，所以不需要那么多递归调用，很快就到达了基线条件，因此调用栈短得多，最终效率为O(logn)。
（在调用栈的每层都涉及O(n)个元素）
值得注意的是，最佳情况也是平均情况。只要你每次都随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为O(nlog n)。
内容总结
以上是互联网集市为您收集整理的《算法图解》笔记全部内容，希望文章能够帮你解决《算法图解》笔记所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。