Algorithm

决策树与ID3算法

在机器学习和数据挖掘领域里,决策树是一种有效的归纳推理算法之一,它将训练样本抽象出多个特征函数,通过离散值的函数输出归纳成一个决策树,由于是有训练样本统计而来,它对样本噪声有一定的健壮性。 一、什么是决策树   直接看图说话: 一个母亲给女儿介绍相亲对象,女孩见不见呢?(图片剽窃自Coding...

比较排序的最优解

看内核代码内存部分时有红黑树的利用,顺便翻了一下经典的排序算法,比较笨的算法如插入排序、冒泡排序的时间复杂度到了θ(N^2)的程度,但诸如堆排序、归并排序和快速排序的复杂度优化到了θ(NlogN)的程度,其中快排成为均匀杂序里面最快的实践算法,自我YY想着排序算法难道不能优化了?一查阅果真如此:基于比较排序的一...

跳表SkipList的原理和C实现

跳表SkipList,顾名思义是链表的一种,或者说它是单链表的变异实现,使用跳表可以将查询操作的复杂度控制到θ(lg N),而普通的链表只能通过顺序查找,复杂度为θ(N),如此跳表的优势就很明显了,虽然它是通过以空间换时间搞定的。 先看一下普通的有序单链表: 要在里面查找一个值就需要顺序比较,复杂度大家都清...