big-o - 在分析 PSRS 为什么 O(p^2 log p^2) = O(p^2 log p)？

Question

PSRS分析(通过定期抽样进行平行排序) 在计算部分。 为什么 Big-o 对常规样本进行排序: O(p^2 log p^2) = O(p^2 log p) ? 谢谢你的回答。

Answer 1

因为 log p² = 2 log p(这是对数的一个属性)并且使用大 O 表示法可以让您忽略乘法常数。