递归时间复杂度主定理
assume that T(n) = aT(n/b) + n^k
T(n) = n^(log to the base b of a) if k<=logba
T(n) = n^k if k>logba
T(n) = n^klogn if k==log(b)a
我们先看下面这个例子
怎样才能知道它的递归次数呢，我们可以画一棵递归树，再把树的节点数出来
T(n)=2*T(n/2)+n
第一层n, 第二层2*(n/2), 第三层4*(n/4), 每层都有个n，高度Logn
分治的话：
assume that k linked-list, and length is N for each linked-list
T(kn) = 2T(k/2*n) + kn
高度log2(k),每层累加都是kn, 因此最终是log2(k) * kn
方法 1：暴力，k 个链表按顺序合并
时间复杂度：
(n+n)+(2n+n)+…+ ((k-1)n + n) = (1+2+…+k-1)n + (k-1)n = (1+2+…+k-1+k)n -n = (k^2+k-1)/2n = O(k^2n)
方法 2：将 k*n 个结点放到 vector,再将 vector 排序，再将结点顺序相连
设有 K 个链表，平均每个链表有 n 个结点，时间复杂度：
kNlogkN +kN = O(kNlogkN)
方法 3：对 k 个链表进行分治，两两进行合并
设有 k 个链表，平均每个链表有 n 个结点，时间复杂度：
第一轮：进行 k/2 次，每次处理 2n 个数字
第 2 轮，进行 k/4 次，每次处理 4n 个数字
…
最后一次，进行 k/(2^logk)次，每次处理 2^logk*n 个数
2nk/2+…+2^logkn * k/(2^logk)
常见算法时间复杂度
时间复杂度总结：
prim o(e+vlogv), 主要是优先队列 top v 次，每次 log(v), 然后边遍历总计 2e.
kruskal o(eloge), 主要是边的排序耗时上。
dijsktra o(e+vlogv), 边总计 e, 优先队列取了 v 次，每次 top log(v), 这里指的斐波那契堆，该堆 insert 为 o(1),其他和二叉堆一致。
floyd wallshal, o(n3)
bellman-ford, o(ve), 每个边松弛一次，共循环 v 次，o(ve);