通常,事件A在事件B(发生)的条件下的概率,与事件B在事件A的条件下的概率是不一样的;然而,这两者是有确定的关系,贝叶斯法则就是这种关系的陈述。
贝叶斯法则
作为一个规范的原理,贝叶斯法则对于所有概率的解释是有效的;然而,频率主义者和贝叶斯主义者对于在应用中概率如何被赋值有着不同的看法:频率主义者根据随机事件发生的频率,或者总体样本里面的个数来赋值概率;贝叶斯主义者要根据未知的命题来赋值概率。...
阅读全文
EM算法也称期望最大化(Expectation-Maximum,简称EM)算法,它是一个基础算法,是很多机器学习领域算法的基础,比如隐式马尔科夫算法(HMM),LDA主题模型的变分推断等等。本文就对EM算法的原理做一个总结。
EM算法要解决的问题
我们经常会从样本观察数据中,找出样本的模型参数。最常用的方法就是极大化模型分布的对数似然函数。
但是在一些情况下,我们得到的观察数据有未观察到的隐含数据,此时我们未知的有隐...
阅读全文
跳表概念
二分查找法依赖于数组的随机访问特性,只能用数组实现
跳表是基于链表实现类似于二分查找的算法
查找、插入、删除各方面性能都不错的动态数据结构,甚至可以替代红黑树
Redis中的有序集合(SortedSet)就是用跳表来实现的
跳表结构
对于一个有序的单链表,想在其中查找某个数据,只能从头到尾遍历链表。效率很低
对链表建立一级索引,每两个结点提取一个结点到上一级,抽出来的一级称为索引...
阅读全文
二叉树的基本概念
常见术语
结点:包含一个数据元素及若干指向子树的分支
结点的度:含有孩子结点的个数
结点的层次:由根结点开始,根结点层次为0
树的深度:由根结点开始,根结点深度为0
树的高度:由叶子结点向根结点,取最大值,叶子结点高度为0
叶子结点(终端结点):没有孩子结点
分支结点(非终端结点):有孩子结点
根结点:没有父亲结点
子树:一个分支结点及其后辈组成子...
阅读全文
字符串或串(String)是由数字、字母、下划线组成的一串字符。一般记为s=“a1a2···an”(n>=0)。它是编程语言中表示文本的数据类型。在程序设计中,字符串(string)为符号或数值的一个连续序列,如符号串(一串字符)或二进制数字串(一串二进制数字)。
通常以串的整体作为操作对象,如:在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。两个字符串相等的充要条件是:长度相等,并且...
阅读全文
Dijkstra算法只能求取边的权重为非负的图的最短路径,而Bellman-Ford算法可以求取边的权重为负的图的最短路径(但Bellman-Ford算法在图中存在负环的情况下,最短路径是不存在的(负无穷))。
算法原理
Dijkstra算法本质上是一种贪心算法,1959年,EdsgerDijkstra提出了该算法用于解决单源最短路径问题,即在给定每条边的长度ll,求取源节点s到其它所有节点的最短路径。Dijkstra算法维护一个节点集合S,S中的节点到源...
阅读全文
排序算法是我们编程中遇到的最多的算法。目前主流的算法有8种。
平均时间复杂度从高到低依次是:
冒泡排序(o(n2)),选择排序(o(n2)),插入排序(o(n2)),堆排序(o(nlogn)),
归并排序(o(nlogn)),快速排序(o(nlogn)),希尔排序(o(n1.25)),基数排序(o(n))
一、冒泡排序:
思想:从数组第一位开始,每个元素和它下一位比较,将大的换到后面,即每一轮循环之后可以确定一个位置。提高效率(...
阅读全文
Go语言内置运行时(就是runtime),不同于传统的内存分配方式,go为自主管理,最开始是基于tcmalloc架构,后面逐步迭新。自主管理可实现更好的内存使用模式,如内存池、预分配等,从而避免了系统调用所带来的性能问题。
基本策略
每次从操作系统申请一大块内存,然后将其按特定大小分成小块,构成链表(组织方式是一个单链表数组,数组的每个元素是一个单链表,链表中的每个元素具有相同的大小。);
为对象分配内存...
阅读全文