V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
qwerthhusn
V2EX  ›  算法

求 M 行 N 列矩阵,最大子矩阵和,有比 O(M×N²)时间复杂度更低的算法吗?

  •  
  •   qwerthhusn · 294 天前 · 625 次点击
    这是一个创建于 294 天前的主题,其中的信息可能已经有所发展或是发生改变。

    能不能达到更低的时间复杂度?

    实在想不出来了,感觉自己智商着实有点低啊。

    马上菊花外包机考,之前从没刷过题,这几天在临阵抱佛脚,遇到个最大子矩阵问题,由于涉及到动态规划:

    先看了看 0-1 背包问题,脑子烧了老半天,算是理解个大概了,但是还没有看各种变种背包问题,以及朴素 DP 解法的进一步优化。

    然后就去看了最大子数组和,暴力 O(N³),暴力暂存结果 O(N²),分治法 O(N×LOG₂N)都很好理解,最后一个 DP ,我本来想自己想一想看看能不能找到状态迁移方程,愣是没想到,然后看答案,还稍微费劲理解了一番终于算是明白了。

    现在扩充到二维数组,压缩到一维数组然后 DP 达到 O(M×N²)这个也没想到,最后看了答案还琢磨了很久算是搞明白了(其实本来算是比较好懂的,主要是我脑子一直在想找个状态迁移方程被绕进去,搞短路了),当 m<n 时也可以用行作为循环轴 O(N×M²)这个很好理解。目前网上的很多解都是这个版本的。但是昨天我好像刷到了 O(M×N)的解,但是找不到那个链接了。

    我自己想了半天也没能想出来什么好的状态迁移方程。

    2 条回复    2023-11-22 00:04:49 +08:00
    Abmcar
        1
    Abmcar  
       294 天前
    应该没了吧,而且你这考 od 又不是可信
    看 op 水平,不刷这种题闭着眼考也能过吧
    chaoxu
        2
    chaoxu  
       179 天前
    考虑 m=n ,则这个问题是 APSP-hard ,没人知道 O(n^{3-\epsilon})复杂度的算法。

    Backurs, Arturs; Dikkala, Nishanth; Tzamos, Christos (2016), "Tight Hardness Results for Maximum Weight Rectangles", Proc. 43rd International Colloquium on Automata, Languages, and Programming: 81:1–81:13, doi:10.4230/LIPIcs.ICALP.2016.81
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   887 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 20:46 · PVG 04:46 · LAX 13:46 · JFK 16:46
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.