JML系列 优化及时间复杂度可行性证明

符号定义

优化方法与复杂度分析

queryBlockSum

并查集

• 由于不需要删除操作，故采用并查集实现
• 并查集单次操作的均摊复杂度为
  $O(alpha(n))$

  O(α(n))，其中
  $alpha$

  α为一个Ackerman函数相关的，这里可以认为小于常数
  $4$

  4

• 每次查询时需遍历每个Person，时间复杂度
  $O(alpha p)$

  O(αp)

• 动态维护加边的复杂度
  $O(alpha r)$

  O(αr)

• 总时间复杂度
  $O(alpha p q_b+alpha r)$

  O(αpqb​+αr)上限小于
  $1times10^7$

  1×107，稳妥

bfs/dfs

• 考虑到有同学使用bfs实现qbs，故补充对其时间复杂度的讨论
• 做法大致为 从每个Person作为入口进行Floodfill，对于已经有标记的不再进入，没有标记的则将所有连通的节点做一个新标记，最后统计标记的数量
• 时间复杂度
  $O(q_b (p+r))$

  O(qb​(p+r))，上限小于
  $1times10^7$

  1×107，稳妥

queryAgeSum

• 采用直接暴力枚举Person进行计数的方法
• 时间复杂度为
  $O(q_a p)$

  O(qa​p)，上限
  $2.4times10^6$

  2.4×106，稳妥

queryNameRank

• 采用每次查询直接暴力统计的方法
• 时间复杂度
  $O(q_r p)$

  O(qr​p)，上限
  $8times10^5$

  8×105，稳妥

queryMinPath

• 采用堆优化Dijkstra算法，因为不需要处理负环
• 单次单源最短路径时间复杂度
  $O((p+r)logr)$

  O((p+r)logr)

• 总体时间复杂度为
  $O(q_m (p+r)logr)$

  O(qm​(p+r)logr)，上限较大，但由于总指令数限制，还满足关系
  $q_m+p+rle3000$

  qm​+p+r≤3000，求极值可估计真实复杂度上限小于
  $2.5times10^7$

  2.5×107

• 注意此题不写堆优化上限可达
  $1times10^9$

  1×109大概率被卡

• 另外spfa已死，不卡是情分，卡是本分，参考NOI2018Day1T1，这本来也是一种及其不稳定的算法

queryStrongLinked

暴力枚举

• 这种做法需要两步bfs/dfs
• 第一次判断连通后，枚举去掉所有割点再次bfs判断是否仍然联通，如果都能联通，说明这两个点点双连通
• 这里的枚举割点是准确条件，但实现的时候如果不想再写一个找割点的算法（还是Tarjan），可以用枚举所有点替代
• 第二次bfs采用MASK的方法加速，不需要修改原图
• 总时间复杂度
  $O(q_s p(p+r))$

  O(qs​p(p+r))时间复杂度上限可达
  $4.8times10^7$

  4.8×107，应该能过，但有些小小的危险，如果具体实现太丑有可能被卡常，不过相信课程组是善良的

• 【更新20200515-10:46】 各位大佬所说的两次bfs/dfs的方法是有巨大bug的，MASK第一次的路径有可能把第二次的路径堵了，但第一次的路径如果换一条，就不会堵第二次的路径，建议不要使用这种方法 建议不要使用这种方法 建议不要使用这种方法，另外，上述
  $4.8times10^7$

  4.8×107的复杂度课程组很善良！

点双连通分量

• 大致思路采用Tarjan找点双连通分量，再判断两个点是否具有相同编号（只是大致思路）
• 单次Tarjan就是dfs的复杂度
  $O(p+r)$

  O(p+r)

• 判断是否双连通复杂度
  $O(p)$

  O(p)

• 时间复杂度
  $O(q_s (2p+r))$

  O(qs​(2p+r))上限小于
  $1times10^5$

  1×105，稳妥

• 需要注意这种做法一定要多做测试！！！

其他

• 前两次作业的此处省略，没必要写的也省略
• 如有错误还请指正