常數時間 90 度轉置一個矩陣
Feb 23, 2017 · 1 min read
一眼看到這個標題，腦中就立馬出現問號 "?" 怎麼可能? 但今天一早同事就說了個好想法，讓我們看下去~
一般來說轉置矩陣方法不外乎
- 開新的空間複製
- 四個四個轉
- 對角線翻轉後水平翻轉
但在怎麼快都要掃過整個矩陣一次，最少也要 O(m*n)
怎麼樣可以常數時間完成呢? 數學上聽起來就不太可能，但工程上，卻是有機會的。那就是根本不要轉，僅修改存取方式 (例如更換 oeprator[] 的實作)，在存取時當場計算應該存取的位置。
有種恍然大悟的感覺。
