O(n^2) 与 O(n) 中的算法 [重复]

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

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#）算法中是什么样子的？

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

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 

复杂度将为 O(n^2)，因为 10n^2 是最大的增长元素，有助于方程增长更快。我们放弃常数并考虑方程中最大的增长分量来评估复杂性。

对于 Big-Omega 复杂性，我们认为这是算法复杂性分析的下限。例如，算法可以像 Omega(n)（最好情况）一样快地运行，但需要长达 O(n^2)（最坏情况），这在排序算法或搜索算法的分析中很常见。

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

您提供的代码示例的时间复杂度为 O(n)，因为它使用 for 循环来迭代 n 个元素。考虑一个双 for 循环，其中当前的 for 循环中有第二个循环。这是 O(n^2)，因为在最坏的情况下需要迭代 n*n 个元素。

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)。

Here is a graph to show how equations grow over time: (and how fast they grow)