n×n矩阵二分查找最大宝藏函数的时间复杂度计算疑问

时间复杂度结论 #

你的推导是正确的，这段代码的时间复杂度确实是O(nlogn)，具体分析如下：

• 递归层数量：代码采用列二分的逻辑，每一次递归都会把待搜索的列范围缩小一半，n×n矩阵初始有n列，最多递归log₂n次就会终止，递归深度为O(logn)
• 单层递归开销：每一次递归都会先遍历目标中间列的所有n行元素，找出该列的最大值，单次遍历的时间复杂度为O(n)
• 总时间复杂度：两层开销相乘，得到总复杂度为n * logn = O(nlogn)

对应代码 #

void findMaxTreasureAux(vector<vector<int>>& map, int columns, int& index_row, int& index_column, int limitsx) {
    
    int med = columns/2;
    int max = 0;
    
    for (int i = 0; i < map.at(0).size(); i++) {
        if (map[i][med+limitsx] > max) {
            index_row = i;
            max = map[i][med+limitsx];
        }
    }
    
    if (med+1+limitsx < map.at(0).size() && map[index_row][med+1+limitsx] > max) 
        findMaxTreasureAux(map, med, index_row, index_column, med+1);
    else if (med - 1 >= 0 && map[index_row][med-1] > max)
        findMaxTreasureAux(map, med, index_row, index_column, limitsx);
    else index_column = med+limitsx;
    
}

void findMaxTreasure(vector<vector<int>>& map, int columns, int& index_row, int& index_column) {
  
  if (map.empty()) return;
  index_column = 0;
  index_row = 0;
  findMaxTreasureAux(map, columns, index_row, index_column, 0); 
}

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