4
三月 2015
source link: http://blog.kongfy.com/2015/03/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
三月 2015
三月 2015 发表了 2 篇文章
[转]Linux进程调度：CFS调度器的设计框架
一直计划要写一篇Linux内核中关于进程调度的文章，拖欠了很久，准备动手写的时候发现了此文，看过以后觉得着实没有自己重新写的必要了，转载于此。
分类： Linux, 操作系统 | 2015-03-18 | 2,050 个字 | 0 Comments
有向图强连通分支：Kosaraju’s algorithm
有向图强连通分支算是个基础算法，不过总是忘记，写下来备忘。
无向图强连通分支非常简单，使用图的遍历算法（DFS或BFS）即可，而有向图的强连通分支计算则要复杂一些，Kosaraju’s algorithm实现了O(n+m)时间复杂度的有向图强连通分支算法。
算法的核心思想在于：从有向图中任何一个点出发做DFS，必然能从图中“拖”出一个点集，和无向图中不同的是，这个点集不一定构成强连通分支，但是如果我们能通过一个合适的顺序进行DFS（“sink” vertex），则可以依次把每一个强连通分支“拖”出来，得到正确的结果，那么算法的要点则在于如何寻找这个合适的顺序。
分类： 算法 | 2015-03-16 | 485 个字 | 0 Comments
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK