根據我的研究，我獲得了關于這個簡單演算法的相互矛盾的資訊。該演算法是一個基本的矩陣轉置，它轉置了一個 nxn 矩陣 A。
我目前的理解是該演算法將在 O(n^2) 時間運行，并且空間復雜度為 O(1)，因為我們操作的矩陣與我們處理的矩陣相同。
但是-我也被告知它實際上會運行 O(n) 時間并且也具有 O(n) 的空間復雜度。這意味著它不會就地，因為它需要額外的空間來進行操作。
對于下面的轉置演算法，哪個思維程序是正確的？
Transpose(A)
1. for i = 1 to n -1
2. for j = i 1 to n
3. exchange A[i, j] with A[j,i]
uj5u.com熱心網友回復：
由于作業量與陣列中元素的數量成正比，并且這些元素占據了它們自己的空間，因此可能會產生一些混淆。因此，由于某些符號濫用或疏忽，兩者都會被稱為“O(n)”。
但這是錯誤的，因為
n 顯然不是元素的數量，而是陣列的行/列數；
根據定義，空間復雜度不包括輸入和輸出資料，而是任何所需的輔助空間。
因此，我們可以確認時間復雜度 O(n2) - 實際上是 Θ(n2) - 和空間復雜度 O(1)。該演算法是就地的。
最后的評論：
如果我們將元素個數表示為m，則時間復雜度為O(m)，不存在矛盾。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424316.html