《算法图解》读书笔记6-图以及广度优先搜索

什么是图

图模拟一组链接,图由顶点和边组成。一个顶点可能与众多顶点直接相连,这些顶点被称为邻居

图通常表示为:G(V,E),其中,G表示一个图,V是图中顶点的集合,E是图中边的集合。

简单图

在图结构中,若不存在顶点到其自身的边,且同一条边不重复出现,则这样的图称之为简单图。

无向图

如果图中任意两个顶点之间的边都是无向边,则称该图为无向图。

无向边:若顶点M到顶点N的边没有方向,称这条边为无向边,用无序偶对(M,N)或(N,M)表示。

……

READ MORE

《算法图解》读书笔记5-散列函数及扩展

散列函数

散列函数就是一种映射,是从关键字到存储地址的映射。通常,包含散列函数的算法的算法复杂度都为O(1),对应到Python中的数据结构就是字典,给一个key可以得到一个固定的value值。散列函数必须满足一些要求:

  • 它必须是一直的。例如,假设输入apple时得到的是4,那么每次输入apple时,都必须是4,不然这个散列函数就是无意义的;
  • 散列函数应该将不同的输入值,对应到不同的值上。(虽然不同的key对应相同的value是允许的,但最理想的情况是不同的key,对应不同的value,这种称之为完美散列

……

READ MORE

《算法图解》读书笔记4-分治思想和快排

分而治之(Divide and Conquer)

所谓分而治之,分为分解问题,但我们目的是解决大问题,所有还有将分解后得到的结果贡献回大问题,最终使得我们解决大问题。

分而治之的思想是采用了递归的思想,将原问题分成几个规模较小但是类似于原问题的子问题, 通过递归的方式来求解这些小问题,最后将子问题的解合并来得到原问题的解。分治思想的本质是我们中学时候学的数学归纳法。

书上提到,使用分治思想解决问题的过程包括两个步骤,其实应该是三个步骤:

  1. 找出基线条件,这种条件必须尽可能简单。
  2. 不断将问题分解为子问题(或者说缩小规模),直达符合基线条件。
  3. 合并子问题的结果,得到最终问题的解(利用系统栈的特性实现过程状态的记录)

……

READ MORE

《算法图解》读书笔记3-递归

如果使用循环 ,程序的性能可能更高;如果使用递归,程序可能更容易理解。如何选择要看什么对你来说更重要。

递归函数

在一个函数中,可以调用另一个函数,如果调用的另一个函数是函数本身,这样的函数就是递归函数。如下示例:

def foo(x):
    if x == 0:
        return 'end'
    else:
        # 在函数中继续调用自己
        return foo(x-1)

……

READ MORE

《算法图解》读书笔记2-数组链表和选择排序

理解数组和链表

链表和数组是两种基本的数据结构,他们的区别在于数据在内存中的存储方式不同。

数组

数组在内存中是用一块连续的内存来存储数据的,数组中的每个数据地址是连续的。数组中的每个元素所占用的内存是相同的,所以,我们可以通过下标索引在常数数量级的时间内,迅速访问数组中的任何一个元素。但是要在数组中任意位置添加一个元素,就需要移动大量的元素,使得内存中空出一个位置来存放新插入的元素。同理,当删除一个元素的时候,也需要移动大量的元素,来使得删除元素以后的数组数据在内存中仍旧是连续的。

由此可见:当对于一组数据,读取操作频繁,写操作少的情况,应该使用数组数据结构。

……

READ MORE

Scroll to top