这段短代码的运行时复杂度是多少？

我在编程练习网站上找到了这个解决方案，它说复杂性是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

这段短代码的运行时复杂度是多少？

回答

相关问题