二维矩阵二分查找：O(logM+logN)与O(logM·logN)哪个更优？

• 结论先行：O(logM + logN)（等价于O(logMN)）的解法比O(logN·logM)的解法更优，耗时更少。

• 具体对比分析：
  从数学角度看，当M和N都大于2时，logM * logN 的值会明显大于 logM + logN。举个实际例子：
  假设M和N都是1024（2^10），以2为底的对数下，logM=logN=10：

  • O(logM·logN)的复杂度计算值为10*10=100
  • O(logM+logN)的复杂度计算值为10+10=20
    差距非常明显。即使M和N较小，比如M=N=4（log2值为2），两者相等（2*2=2+2=4）；但只要其中一个数大于2，比如M=8（log2=3），N=4（log2=2），乘积是6，和是5，乘积已经大于和了。

• 本质原因：乘法增长的速度远快于加法，哪怕是对数级的数值相乘，也会比相加更快达到更大的量级。所以O(logMN)的时间复杂度对应的算法执行步骤更少，自然耗时更短。

内容的提问来源于stack exchange，提问作者Mohit Ashliya