O(n^2) 与 O(n) 中的算法 [英] Algorithms in O(n^2) vs O(n)

问题描述

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

I'm new to computer science and just started with pseudocodes and I have some questions. It's my third week in the semester and majority is self-studying. I have some questions:

O(n^2) 与 O(n) 算法有什么区别?- 同样，什么是 O(n log n)?- 和Ω(n^2)?

What is the difference of an O(n^2) with an O(n) algorithm? - Similarly, what is O(n log n)? - and Ω(n^2)?

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

So far, I have written:

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

但发现它是O(n).我如何转换它?

But found out it is O(n). How do I transform it?

什么是运行时间?- 我知道第一行的分配是 1 个操作

What is the run time? - I know assignment on first line is 1 operation

它在一个实际的，比如说 C# 算法中是什么样子的?

And how does it look like in an actual, say C#, algorithm?

推荐答案

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

What you are asking about is a topic in computer science known as Algorithm Complexity Analysis. It is a very important topic to consider when writing algorithms, or solutions, in your programs because it relates to run-time, or how fast your computations will run.

Big-Oh 或 O(n) 与算法运行的上限运行时间有关.在这种情况下，O(n) 意味着对于 n 个元素，需要考虑所有 n 个元素以完成算法计算或线性计算.这个 Big-Oh 复杂度的范围是从常数时间 O(1) 到 O(n^n)，对于非常大且非常慢的计算.此外，请考虑以下等式:

Big-Oh, or O(n) relates to the upper-bound run-time for an algorithm to run. In this case, O(n) means for n-elements there will need to be all n-elements considered for the algorithms computation to complete, or linear. The range for this Big-Oh complexity is from constant time, O(1), to up O(n^n) for really large, and very slow computations. Also, consider equations such as the following:

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

这些都是 O(n) 复杂度，因为随着元素数量的增加，方程因此变得越来越大.我们忽略常数，因为方程会因变量而变大和变快，而不是由于永远不会改变的常数值.而等式如下:

These both are O(n) complexity because as the number of elements grow, the equation grows larger and larger because of it. We neglect the constants because the equation will grow larger and fast due to the variable, rather than due to the constant values which never change. Whereas, with equation as the following:

y=10n^2+5n+5 

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

The complexity is going to be O(n^2) due to the 10n^2 being the largest growing element contributing to the equation growing faster. We drop the constants and consider the largest growing components to equations to evaluate complexity.

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

For Big-Omega complexity, we consider this the lower bound for Algorithm Complexity Analysis. For example, an algorithm can run as quick as Omega(n) (best case) but take as long as O(n^2) (worst case) this is common in analysis of sorting algorithms or searching algorithms.

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

In some cases, we want to write programs with algorithms that are efficient and faster for optimization reasons, especially when we want a quicker program for faster solutions or quicker run times.

您提供的代码示例是 O(n)，因为它使用 for 循环遍历 n 个元素.考虑一个双 for 循环，其中当前 for 循环中有第二个循环.这是 O(n^2) 由于迭代，在最坏的情况下，n*n 个元素.

The code example you provided is O(n) because it uses a for loop to iterate over n-elements. Consider a double for loop, where there is a second loop within your current for loop. This is O(n^2) due to iterating over, in the worst case, n*n elements.

O(n^2) 运行时初始化空矩阵的 Java 伪代码:

Java pseudo-code for a O(n^2) run-time initializing an empty matrix:

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) 运行时间.

Notice, it uses two loops therefore inducing an O(n^2) run-time.

以下图表显示方程如何随时间增长:(以及它们增长的速度)

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

这篇关于O(n^2) 与 O(n) 中的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！