所以,这不是我的家庭工作问题,而是取自关于算法和数据结构(现已完成)课程的未分级作业.
您将获得一个n×n个不同数字的网格.如果数字小于其所有邻居,则该数字是局部最小值.(一个数字的邻居是紧靠上方,下方,左侧或右侧的一个.大多数数字有四个邻居;侧面的数字有三个;四个角有两个.)使用分而治之的算法设计用于计算局部最小值的范例,仅对数字对进行O(n)比较.(注意:由于输入中有n 2个数字,因此您无法查看所有数字.提示:考虑哪种类型的重复会为您提供所需的上限.)
由于数字不是任何顺序,我不知道除了O(n 2)比较之外我们怎么能逃脱任何事情.