O（n ^ 2）vs O（n）中的算法

Question

我是计算机科学的新手，只是从伪代码开始的，所以我有一些疑问。这是我本学期的第三周，大部分时间都是自学的。我有一些问题：

O（n ^ 2）与O（n）算法有什么区别？-同样，O（n log n）是什么？-和？（n ^ 2）？

到目前为止，我已经写了：

horner = 0;
for( i = n; i >= 0; i ?? )
    horner = x * horner + a[i];

但是发现它是O（n）。如何转换？

运行时间是多少？-我知道第一行的分配是1个操作

在实际的C＃算法中，它看起来如何？

Answer 1

您要问的是计算机科学中一个称为算法复杂性分析的主题。在程序中编写算法或解决方案时，要考虑一个非常重要的主题，因为它与运行时间或计算运行的速度有关。

Big-Oh或O（n）与算法运行的上限运行时间有关。在这种情况下，O（n）表示对于n个元素，将需要考虑所有n个元素以使算法计算完成或呈线性。这种Big-Oh复杂性的范围是从常数时间O（1）到最大的O（n ^ n）（非常大且非常慢的计算）。另外，请考虑以下方程式：

y=10n+1
y=5n+10

两者都是O（n）复杂度，因为随着元素数量的增加，方程式也因此而变得越来越大。我们忽略常数是因为方程将由于变量而不是由于永不改变的常数值而变得更大，更快。而公式如下：

y=10n^2+5n+5 

由于10n ^ 2是使方程快速增长的最大增长元素，因此复杂度将为O（n ^ 2）。我们删除常数，并考虑方程中最大的增长成分来评估复杂性。

对于Big-Omega复杂度，我们认为这是算法复杂度分析的下限。例如，一种算法的运行速度可达到Omega（n）（最佳情况），而运行时间却长达O（n ^ 2）（最坏情况），这在排序算法或搜索算法的分析中很常见。

在某些情况下，出于优化的原因，我们希望使用高效且快速的算法编写程序，尤其是当我们需要更快的程序以实现更快的解决方案或更快的运行时间时。

您提供的代码示例为O（n），因为它使用for循环迭代n个元素。考虑一个double for循环，当前的for循环中有第二个循环。由于在最坏的情况下迭代n * n个元素，因此O（n ^ 2）。

用于初始化空矩阵的O（n ^ 2）运行时的Java伪代码：

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

请注意，它使用两个循环，因此产生了O（n ^ 2）运行时间。

这是一张图表，显示方程如何随着时间增长：（以及方程增长的速度）

Answer 2

O(n)表示算法达到其最终状态（即算法开始时给出的对象）最多（最坏情况）所需的迭代、计算或步骤的数量。n

\n\n

假设您有一个包含 5 个元素的数组，以及一个复杂度为 O(n^2) 的排序算法。您知道，如果对数组应用排序，最多需要 5^2=25 步才能达到最终状态。

\n\n

另请阅读：O、\xce\xa9 和 \xce\x98 之间有什么区别？

\n