标签 c# c++ algorithm pseudocode
<分区>
我是计算机科学的新手，刚开始接触伪代码，我有一些问题。这是我本学期的第三周，大部分时间是自学。我有一些问题:
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) 运行时间。
这是一个图表，显示方程式如何随时间增长:(以及它们增长的速度)
关于c# - O(n^2) 与 O(n) 中的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27750064/