0 
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) 对吗？那么这是否意味着 Big O 只是一个关于时间将如何根据输入数据大小增长的指示？而不是算法怎么写？

4

3 回答 3

2

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

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) 算法的排序问题，我不会 即使我的计算机比你的好 10 年或 20 年，当我尝试列出一份长度为 100 或 1000 倍的列表时，我也无法击败你。这就是 Big-Oh 的想法，将那些“相对不重要”的速度差异分解出来，并能够在更一般/理论上的意义上看到给定算法在给定输入大小上所做的工作量。

当然，在现实生活中，一台计算机比另一台快 100 倍可能对您产生巨大影响。如果您尝试使用固定的最大输入大小来解决特定问题，并且您的代码以您老板要求的速度的 1/10 运行，并且您获得了一台运行速度快 10 倍的新计算机，那么您的问题无需需要写一个更好的算法。但关键是，如果您想处理更大（更大）的数据集，您不能只等待更快的计算机。

于 2012-04-29T09:31:03.843 回答
1

该big O符号是基于输入大小执行算法所花费的最大时间量的上限。所以基本上两种算法的最大运行时间可能略有不同，但big O表示法相同。

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

因此，如果您的运行时间仅为 n，即一次线性传递，则大 o 符号保持 o(n)，如果您的运行时间为 6n+c，即 6 次线性传递和恒定时间 c，它仍然是 o(n)。

现在在上述情况下，第二个代码更加优化，因为您需要为循环跳转到内存位置的次数更少。因此这将提供更好的执行。但是这两个代码的渐近运行时间仍然是o(n^2).

于 2012-04-29T09:12:39.307 回答
0

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

于 2012-04-29T09:09:01.000 回答