這段短代碼的運行時複雜度是多少？

我在編程練習網站上找到了這個解決方案，它說複雜性是O（N）。但是，它對我來說更像O（N^2）。有人可以告訴我爲什麼這是O（N）嗎？這段短代碼的運行時複雜度是多少？

public static void transposeMatrix(int[][] matrix) { 
    int n = matrix.length - 1; 
    int temp = 0; 
    for(int i = 0; i <= n; i++){ 
     for(int j = i+1; j <= n; j++){ 
      temp = matrix[i][j]; 
      matrix[i][j] = matrix[j][i]; 
      matrix[j][i] = temp; 
     } 
    } 
}

來源

2017-09-11 olu

你說得對。該來源錯了。 –

您可能正在使用不同的N. – user2357112

的定義是什麼來源？ –

什麼是N？

如果N是max(matrix.length, matrix[0].length)，那麼算法就是O（N^2），就像你說的那樣。

如果N是矩陣的總大小，那麼算法是O（N）。

準確定義N的大O符號總是非常重要。在學習Big-O時，大多數討論圍繞單維輸入進行，人們假設您不必定義N。在現實世界中，事情很骯髒，我們處理多維輸入，而且你必須非常清楚N是什麼。

來源

2017-09-11 21:17:36

這不是O（n）。這是O（n^2）。具體來說，它將執行0≤i≤n的n-i交換。因此它將執行0 + 1 + 2 + ... + n交換= n（n + 1）/ 2交換，即O（n^2）。

來源

2017-09-11 21:11:41

n = matrix.length - 1;

時間複雜度：O（N^2）

空間複雜：O（1）

解釋：在第一個for循環我會從去（0 - - N）。並且在秒循環中，j將從（i + 1 --- N）開始。對於i = 0，您重複執行 N-1個元素。對於i = 1，你迭代N-2個元素。同樣，對於i = N-1，你迭代的最後一個元素

In total, T = (N-1) + (N-2) + (N-3) + ... + 2 + 1 

T ~ N * (1+2+3+...+N) 

T ~ O(N^2)

來源

2017-09-12 03:49:11 sarjit07

這段短代碼的運行時複雜度是多少？

回答

相關問題