14233. 珅泽教育CSP-J第一轮模拟考第二十套 第 13 题

珅泽教育CSP-J第一轮模拟考第二十套 第 13 题

假设 nn 是图的顶点的个数,mm 是图的边的个数,为求解某一问题有下面四种不同时间复杂度的算法。对于 m=Θ(n)m=\Theta(n) 的稀疏图而言,下面的四个选项,哪一项的渐近时间复杂度最小( )。

{{ select(1) }}

  • Θ ⁣(mlog⁡n⋅log⁡log⁡n)\Theta\!\left(m\sqrt{\log n\cdot\log\log n}\right)
  • Θ(n2+m)\Theta(n^2+m)
  • Θ ⁣(n2log⁡m+mlog⁡n)\Theta\!\left(\frac{n^2}{\log m+m\log n}\right)
  • Θ(m+nlog⁡n)\Theta(m+n\log n)