当前位置：文江博客话题详情

在哪里可以找到 O(n^2) 和 O(n) 等的含义？

发布于 2024-09-15 05:50:26 字数 64 浏览 3 评论 0原文

我一直在注意到有关堆栈溢出的答案使用此类术语，但我不知道它们的含义。它们叫什么？有没有好的资源可以简单地解释它们？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

过期以后 2024-09-22 05:50:27

该表示法称为 Big O 表示法，并用作表达算法复杂性的简写（基本上是随着输入大小 (n) 的增长，给定算法需要运行多长时间）

一般来说，您将遇到以下主要类型的算法：

O(1) - 常量 - 的长度该算法完成所需的时间不取决于该算法必须处理的项目数量。
O(log n) - 对数 - 该算法完成所需的时间长度取决于该算法必须处理的项目数量。随着输入大小变大，每个新输入所需的时间会减少。
O(n) - 线性 - 该算法完成所需的时间长度直接取决于算法必须处理的项目数量。随着输入大小的增加，所需的时间也会相应增加。
O(n^2) - 多项式 - 随着输入大小的增加，处理输入所需的时间也会越来越大 - 这意味着大输入大小变得非常难以解决。
O(2^n) - 指数 - 最复杂的问题类型。处理时间会根据输入大小而极大程度地增加。

一般来说，您可以通过查看算法的使用方式来粗略地衡量算法的复杂性。例如，查看以下方法：

function sum(int[] x) {
    int sum = 0;
    for (int i = 0; i < x.length; i++) {
        sum += x[i];
    } 
    return sum;
}

这里必须完成一些操作：

初始化一个名为 sum 的变量
初始化一个名为 i 的变量
对于 i 的每次迭代：将 x[i] 添加到 sum，将 1 添加到 i，检查if i 小于 x.length
返回总和

这里有一些操作在恒定时间内运行（前两个和最后一个），因为 x 的大小不会影响它们运行的时间。此外，还有一些操作以线性时间运行（因为它们针对 x 中的每个条目运行一次）。使用 Big O 表示法，算法被简化为最复杂的算法，因此该求和算法的运行时间为 O(n)

That notation is called Big O notation, and is used as a shorthand to express algorithmic complexity (basically how long a given algorithim will take to run as the input size (n) grows)

Generally speaking, you'll run into the following major types of algorithims:

O(1) - Constant - The length of time that this algorithim takes to complete is not dependent on the number of items that the algorithim has to process.
O(log n) - Logarithmic - The length of time that this algorithim takes to complete is dependent on the number of items that the algorithim has to process. As the input size becomes larger, less time is needed for each new input.
O(n) - Linear - The length of time that this algorithim takes to complete is directly dependent on the number of items that the algorithim has to process. As input size grows, the time it takes grows in equal amounts.
O(n^2) - Polynominal - As input size grows, the time it takes to process the input grows by a larger and larger amount - meaning that large input sizes become prohibitively difficult to solve.
O(2^n) - Exponential - The most complicated types of problems. Time to process increases based on input size to an extreme degree.

Generally you can get a rough gauge of the complexity of an algorithim by looking at how it's used. For example, looking at the following method:

function sum(int[] x) {
    int sum = 0;
    for (int i = 0; i < x.length; i++) {
        sum += x[i];
    } 
    return sum;
}

There's a few things that have to be done here:

Initialize a variable called sum
Initialize a variable called i
For each iteration of i: Add x[i] to sum, add 1 to i, check if i is less than x.length
Return sum

There's a few operations that run in constant time here (the first two and the last), since the size of x wouldn't affect how long they take to run. As well, there are some operations that run in linear time (since they are run once for each entry in x). With Big O notation, the algorithim is simplified to the most complex, so this sum algorithim would run in O(n)

回复收藏 0 原文

微暖i 2024-09-22 05:50:27

首先阅读计算复杂性，然后尝试一些有关算法的书籍，例如算法简介。

来自维基百科页面：

大 O 表示法根据函数的增长率来表征函数

如果您不愿意深入研究细节，您通常可以通过分析其代码来近似算法复杂性：

void simpleFunction(arg); // O(1) - if number of function instructions is constant and don't depend on number of input size

for (int i=0;i<n;i++) {simpleFunction(element[i]);} // O(n)

for (int i=0;i<n;i++) { // this one runs O(n^2)
    for (int j=0;j<n;j++) {
        simpleFunction(element[i]);
    }
}

for (int i=0;i<n;i*=2) {  // O(lgn)
    simpleFunction(element[i]);
}

有时，估计函数/算法大 O 表示法复杂性并不那么简单在这种情况下，使用摊销分析。上面的代码只能作为快速入门。

Read about Computational Complexity first, then try some books about algorithms like Introduction to Algorithms.

From Wikipedia page:

Big O notation characterizes functions according to their growth rates

If you don't won't to drill into details you can very often approximate algorithm complexity by analizing its code:

void simpleFunction(arg); // O(1) - if number of function instructions is constant and don't depend on number of input size

for (int i=0;i<n;i++) {simpleFunction(element[i]);} // O(n)

for (int i=0;i<n;i++) { // this one runs O(n^2)
    for (int j=0;j<n;j++) {
        simpleFunction(element[i]);
    }
}

for (int i=0;i<n;i*=2) {  // O(lgn)
    simpleFunction(element[i]);
}

Sometimes it is not so simple to estimate function/algorithm big O notation complexity in such cases amortized analysis is used. Above code should serve only as quickstarter.

回复收藏 0 原文

琉璃繁缕 2024-09-22 05:50:27

这称为Big O 表示法，用于量化算法的复杂性。

O(1) 意味着无论要处理多少数据，算法都需要恒定的时间。

O(n)表示算法速度随着数据量的增加呈线性增长。

等等...

因此，O 表示法中 n 的幂越低，算法解决问题的效果就越好。最好的情况是 O(1) (n=0)。但许多问题都有其固有的复杂性，因此几乎在所有情况下您都找不到如此理想的算法。

回复收藏 0 原文

原来是傀儡 2024-09-22 05:50:27

到目前为止，答案都很好。网络搜索的主要术语是“Big O notation”。

“someformula is O(someterm)”数学背后的基本思想是，当变量趋向无穷大时，“someterm”是公式中占主导地位的部分。

例如，假设您有 0.05*x^3 + 300*x^2 + 200000000*x + 10。对于非常小的 x 尺寸（x==1 或 x==2），200000000*x 将是迄今为止最大的部分。此时，公式图将看起来呈线性。随着您的继续，在某些时候 300*x^2 部分会更大。但是，如果您继续使 x 变得更大，无论您想要多大，0.05*x^3 部分将是最大的，并且最终将完全超过公式的其他部分。从图中可以清楚地看出您正在查看一个立方函数。所以我们可以说公式是O(x^3)。