c++ - 大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) 作为执行时间增长 我得到它的方式是:

MAX [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;   

Big O 仍然是 O(n2) 对吗？ 那么这是否意味着 Big 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-Oh 的想法，即排除那些“相对不重要”的速度差异，并能够从更一般/理论上的意义上了解给定算法在给定输入大小上所做的工作量。

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