[其他] SMAWK algorithm中的monotone定義
大家好 最近在看SMAWK algorithm, 其中定義了monotone matrix跟
totally monotone matrix. 在原始定義中, montone matrix的定義是:
假設 i 為row index, 令J(i)為row i的leftmost minimum value的column index
則monotone matrix是指有 J(i1) <= J(i2), if i1 < i2特性的matrix
問題來了 我看到一個網頁:
https://medium.com/@shahh8138/smawk-algorithm-242fa751baab
這個網頁裡面用的定義不大一樣: 摘錄如下
Monotone : Formally, an (n x n) matrix M is said to be a monotone
matrix if for every pair of indices i1 i2 and j1 j2 such that,
1 <= i1 < i2 <= n and 1 <= j1 < j2 <= n, the following conditions hold:
1. m(i1, j1) <= m(i1, j2) and m(i2, j1) <= m(i2, j2)
(non-decreasing columns)
2. m(i1, j1) <= m(i2, j1) and m(i1, j2) <= m(i2, j2)
(non-increasing rows)
那我的想法是 是否上面兩個性質可以推得原始定義的性質 但嘗試了一下發現好像
找不出證明路徑, 所以想在此請教大家要怎麼證明呢? 若是跟原始定義不等價,
是否有相似的條件可以推得原始定義的性質?
我是感覺上面兩個條件其中一個寫錯了 第二個條件是不是要變成大於?
也有可能我誤解了整個東西 思路完全錯誤 也請大家幫忙指正 ORZ
謝謝大家
(真的好好奇是為什麼得出上面兩個條件的.........)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.96.239 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1730221080.A.3C0.html
→
10/30 03:23,
1年前
, 1F
10/30 03:23, 1F
→
10/30 03:23,
1年前
, 2F
10/30 03:23, 2F
→
10/30 03:23,
1年前
, 3F
10/30 03:23, 3F
→
10/31 00:50,
1年前
, 4F
10/31 00:50, 4F
→
10/31 00:52,
1年前
, 5F
10/31 00:52, 5F
→
10/31 00:53,
1年前
, 6F
10/31 00:53, 6F
→
10/31 00:53,
1年前
, 7F
10/31 00:53, 7F
→
10/31 00:57,
1年前
, 8F
10/31 00:57, 8F
→
10/31 00:58,
1年前
, 9F
10/31 00:58, 9F
→
10/31 00:58,
1年前
, 10F
10/31 00:58, 10F