大O计算

Question

int maxValue = m[0][0];         
for (int i = 0; i < N; i++) 
{               
    for (int j = 0; j < N; j++) 
    {                   
        if ( m[i][j] >maxValue )        
        {                   
            maxValue = m[i][j];     
        }                       
    }                   
}                   

cout<<maxValue<<endl;           

int sum = 0;                
for (int i = 0; i < N; i++)     
{                   
    for (int j = 0; j < N; j++)     
    {                   
        sum = sum + m[i][j];            
    }                   
} 

cout<< sum <<endl;

对于上面提到的代码，我得到了O(n2)，因为我得到的执行时间增长方式是：

最大O(1)，O(n2)，O(1)，O(1)，O(n2)，O(1)

两个O(n2)都是for循环。这个计算正确吗？

如果我将此代码更改为：

int maxValue = m[0][0]; 
int sum = 0;
for (int i = 0; i < N; i++)         
{                       
    for (int j = 0; j < N; j++)         
    {                       
    if ( m[i][j] > maxValue )       
        {                   
        maxValue = m[i][j];     
        }               
        sum += m[i][j];
    }                   
}   

cout<<maxValue<<endl;   
cout<< sum <<endl;   

大O仍然是O(n2)，对吗？那么，这是否意味着大O仅仅是一个关于时间将如何根据输入数据大小增长的指示？而不是算法是怎么写的？

Answer 1

这对我来说有点像家庭作业的问题，但是...

Big-Oh是关于算法的，特别是算法执行的步骤数(或使用的内存量)如何随着输入数据的增长而增长。

在您的示例中，将N作为输入的大小，这很令人困惑，因为您有一个二维数组NxN。实际上，由于您的算法只对此数据进行一次或两次遍历，您可以将其称为O(n)，在本例中，n是二维输入的大小。

但是为了回答问题的核心，您的第一个代码对数据进行了两次传递，而第二个代码在一次传递中完成了相同的工作。然而，Big-Oh的想法是，它应该给出增长的顺序，这意味着独立于特定计算机的确切运行速度。所以，我的计算机可能比你的快两倍，所以我可以运行你的第一个代码，和你运行第二个代码的时间大致相同。因此，我们希望忽略这些差异，并假设两种算法在数据上进行固定次数的传递，所以为了“增长顺序”，一次传递，两次传递，三次传递，都无关紧要。这一切都和一次传球一样。

在不考虑NxN输入的情况下考虑这一点可能更容易。只需考虑一个包含N个数字的列表，并假设您想要对其执行某些操作，例如查找最大值，或对列表进行排序。如果你的列表中有100个项目，你可以在100个步骤中找到最大值，如果你有1000个项目，你可以在1000个步骤中找到最大值。因此，增长的顺序与输入的大小是线性的: O(n)。另一方面，如果你想对它进行排序，你可能会编写一个算法，每次找到下一个要插入的项时，都会对数据进行一次完整的遍历，并且它必须为列表中的每个元素大致执行一次，所以这就是在长度为n的列表上进行n次遍历，所以这是O(n^2)。如果列表中有100个项目，大约需要10^4个步骤；如果列表中有1000个项目，大约需要10^6个步骤。所以我的想法是，与你的输入大小相比，这些数字增长得非常快，所以即使我有一台速度更快的计算机(例如，一台比你的好10年的型号)，我也可能在最大问题上击败你，即使列表长度是你的2倍或10倍，甚至100倍或1000倍。但是对于O(n^2)算法的排序问题，当我尝试处理一个100或1000倍长的列表时，即使计算机比您的好10年或20年，我也无法击败您。这就是Big的想法--哦，排除那些“相对不重要”的速度差异，并能够看到在更一般的/理论意义上，给定的算法对给定的输入大小做了多少工作。

当然，在现实生活中，一台计算机比另一台计算机快100倍，这可能会对你产生巨大的影响。如果你试图用一个固定的最大输入大小来解决一个特定的问题，你的代码以老板要求的1/10的速度运行，而你得到了一台运行速度快10倍的新计算机，那么你的问题就解决了，而不需要编写更好的算法。但重点是，如果你想处理更大(更大)的数据集，你不能只是等待一台速度更快的计算机。

Answer 2

big O表示法是基于输入大小执行算法所需的最大时间的上限。因此，基本上两种算法的最大运行时间可能略有不同，但big O表示法相同。

您需要了解的是，对于运行时间函数，基于输入大小的线性函数将具有大的o表示，即o(n)，而二次函数将始终具有大的o表示，即o(n^2)。

因此，如果你的运行时间是n，也就是一次线性遍历，大o记法就是o(n)，如果你的运行时间是6n+c，也就是6次线性遍历和一个常数时间c，那么它仍然是o(n)。

现在，在上面的例子中，第二个代码得到了更多的优化，因为您需要跳到循环的内存位置的次数更少。因此，这将提供更好的执行。但是这两个代码仍然会有o(n^2)的渐近运行时间。

Answer 3

是的，在这两种情况下都是O(N^2)。当然，O()时间复杂度取决于您如何编写算法，但上面的两个版本都是O(N^2)。但是，请注意，实际上N^2是输入数据的大小(它是一个N x N矩阵)，因此最好将其描述为线性时间算法O(n)，其中n是输入的大小，即n=N x N。