01
局部性
刚被访问过的数据,极有可能很快地再次被访问,这一现象在信息处理过程中屡见不鲜。
例如,推荐系统topk项集的的每一项都有可能被重复地购买,排名靠前的网页被访问后,我们很可能很快就又去访问它。
再如去开学术会议时在012会议室遇到的同门师兄,可能明天又在餐厅相遇。
02
利用局部性
如下的ist,
访问效率关键取决于秩的位置,越靠前的元素,访问的效率越高,
假定的数据具有局部性,我们利用这个特性,访问过秩为i的元素后,将其移动到最前端,很可能紧接着,它有可能被访问到,等再访问时,它就很快被访问到了,
因此,使用一段时间后,最近被访问的元素都跑到list的前面,由于有局部性,因此接着要访问的元素很可能位于前端区域,所以会取得很高的访问效率,
类似地,在二叉树中,同样将刚访问的元素放到前头,
这种BST树就是伸展树,某个刚被访问的节点,通过左右摇摆,逐层伸展到树根位置...
03
伸展
节点v被访问后,立即移到树根位置,借助的手段依然是zig和zag操作,
04
Tarjan点睛
构思的精髓是向上追溯两层,而非一层。反复考察祖孙三代,经过两次旋转,使v上升两层。
向上伸展两层,看看最坏情况下,树的折叠效果,访问最下节点1,考虑祖孙三代,
当节点1达到树根时,树的高度差不多变为原来的一半,而逐层伸展的话,树高不变,所以tarjan的两层伸展是更好的。
《实例》阐述算法,通俗易懂,助您对算法的理解达到一个新高度。包含但不限于:基本算法,机器学习,深度学习,Kaggle实战,Spark和Tensorflow等。期待您的到来!