在nxn的二维数组中，我试图找到一个比它的邻居大的数字。
我用分而治之的算法来解决这个问题。
接下来，我试图证明我的算法的正确性，通过展示一个合适的不变量，即我通过用随机数填充4x4网格来对其进行逼近，将其划分并找到所选择的每个列的全局最大值（不确定这是证明算法正确性的方法）。
我最困惑的是如何分析算法的运行时间，即在最坏的情况下需要访问nxn数组中的多少元素，最后是否有方法显示算法是否是渐近最优的。
最佳答案
你不能有比O（n ^ 2）更好的复杂度，因为你需要访问数组的每个元素。如果没有访问某个元素，它可能会发现，除了您没有访问的元素中的全局最大值外，您的数组没有任何局部极大值。蛮力算法（只要检查每个元素是局部最大值）就是O（n ^ 2），因此没有比这更好或更坏的空间。
重新分而治之的算法——对于给定的问题来说，这似乎过于工程化了。你从中什么也得不到，并且你引入了额外的复杂因素（你如何处理部件之间的边界？）