0%

关于树的算法及其复杂度和适用场景分析

$HuffmanTree$(哈夫曼树)

小知识点

  1. 因为哈夫曼树除了叶子结点外,其他节点都是两个结点合并构成的,所以不存在度为1的结点。
  2. 因为$n_{sum}=n_0+n_1+n_2$,并且$n_1=0$。
  3. 且总的分支数加根结点就是总的结点个数,所以$n_{sum}=2n_2+1$。
  4. 综上可得$n_{sum}=2n_0-1$。
Read more »

关于图的算法及其复杂度和适用场景分析

最小生成树

$prim$算法(普里姆算法)

  • 时间复杂度$O(N^2)$
  • 适用场景:稠密图
  • 又叫加点法
Read more »

欧拉函数

euler

在数论中,对正整数$n$,欧拉函数$\phi(n)$是小于或等于$n$的正整数中与$n$互质的数的数目。

求单个数的欧拉函数值时间复杂度可以为$Olog_2n$,代码如下:

Read more »