几个小问题求教

log2() 的时间复杂度是什么？网上似乎查不到（cpp reference不会看啊，直接百度似乎没有），自己测的不开O2的用时是相同次数加法不开O2的4倍左右，都开O2是3倍左右时间。（对比的是做 $10^8$ 次 log2(rand()) 和 x+=rand()）

prufer 序列生成 与 "对于 $2$ 到 $n$ 在 $[1,i-1]$ 中随机 fa 生成随机树的期望高度是什么？听说前者是根号的，后者是 log 的？怎么计算出来呢？

到处都说 spfa 随便卡，但是怎么卡 spfa 呢？有时候会看到题解说什么这个数据范围一看就不卡 spfa 之类的（好像是n、m范围相等还是啥的？可能记错了），稀疏图能卡 spfa 吗？