算法的大O复杂度
是衡量算法性能的一种指标，用于描述算法在最坏情况下的时间复杂度。它表示算法执行所需的时间或空间资源随输入规模的增长而增加的速度。
大O复杂度通常用大O符号表示，例如O(1)、O(log n)、O(n)、O(n log n)、O(n^2)等。其中，O(1)表示常数时间复杂度，即算法的执行时间不随输入规模的增长而增加；O(log n)表示对数时间复杂度，常见于二分查找等分治算法；O(n)表示线性时间复杂度，常见于遍历算法；O(n log n)表示线性对数时间复杂度，常见于排序算法；O(n^2)表示平方时间复杂度，常见于嵌套循环算法。
算法的大O复杂度对于评估算法的效率和性能非常重要。在实际开发中，我们需要根据具体的应用场景和数据规模选择合适的算法，以提高程序的执行效率和资源利用率。
以下是一些常见的算法的大O复杂度及其应用场景：
- O(1)：常数时间复杂度。适用于只需执行固定次数操作的算法，如常数级别的数学运算。
- O(log n)：对数时间复杂度。适用于二分查找、平衡二叉树等问题。
- O(n)：线性时间复杂度。适用于线性遍历、查找最大/最小值等问题。
- O(n log n)：线性对数时间复杂度。适用于排序算法（如快速排序、归并排序）和一些分治算法。
- O(n^2)：平方时间复杂度。适用于嵌套循环、简单排序算法（如冒泡排序、插入排序）。
- O(2^n)：指数时间复杂度。适用于穷举搜索等问题，随着输入规模增大，执行时间急剧增加。
- O(n!)：阶乘时间复杂度。适用于全排列等问题，随着输入规模增大，执行时间急剧增加。
腾讯云相关产品和产品介绍链接地址：
- 云函数（Serverless）：提供按需运行代码的计算服务，无需关心服务器管理和资源调度。详情请参考：https://cloud.tencent.com/product/scf
- 云服务器（CVM）：提供可扩展的云服务器实例，适用于各类应用场景。详情请参考：https://cloud.tencent.com/product/cvm
- 云数据库 MySQL：提供高性能、可扩展的云数据库服务，适用于各类应用场景。详情请参考：https://cloud.tencent.com/product/cdb_mysql
- 人工智能机器学习平台（AI Lab）：提供丰富的人工智能开发工具和服务，支持机器学习、深度学习等任务。详情请参考：https://cloud.tencent.com/product/ai
请注意，以上仅为腾讯云的一些相关产品示例，其他云计算品牌商也提供类似的产品和服务。
相关·内容
考虑到无碰撞的Hashtable。
如果我有这段代码
for(int i=0;i<jewels.length();i++) #step 1
jewelSet.add(jewels.charAt(i)); #step 2
第一步大O是O(n)。好吧，那没问题
步骤2没有循环的单独的大O是大(1)，这是正确的.
我的问题..。循环中的步骤2将导致O(1) *n。意思是..。O(n)
所以这整个代码张贴的大O将是O(2n) = O(n) ..is，对不对？
我是说..。什么时候
Loop :
O(1)
经过多次循环..。O(1)总金额将不再是O(1)。它将是n*
浏览 3提问于2021-09-03得票数 0
回答已采纳
1回答
我对big-o还很陌生，我想弄清楚这一小段代码的大o运行时间是多少。我知道通常情况下，如果有，但是整个数组的事情会改变什么吗？我很困惑，所以任何一点的输入都是很好的。提前感谢！
public apple(int n)
{
int n = 0;
int apple = 0;
a = apple + n;
}
浏览 0提问于2017-09-07得票数 0
我有一个问题，找到算法所需的内存的大O顺序意味着什么？
比如，这和大o操作有什么区别？
E.g
给出以下伪代码，并使用初始化的二维数组A，两维大小均为n：
for i <- 1 to n do
for j <- 1 to n-i do
A[i][j]= i + j
内存的大o符号不就是n^2，计算也是n^2吗？
浏览 0提问于2012-11-13得票数 12
2回答
我只是读了一个问题的答案，“大O”的简明英语解释，从中我知道，大-O表示法只是一个算法复杂性的“上限”？
但是，我们能否将它应用于算法的其他情况(即最佳和平均情况)？
浏览 0提问于2015-01-08得票数 0
回答已采纳
1回答
对于一个算法的平均时间复杂度，您使用了什么符号？在我看来，正确的方法是使用大θ来引用一组结果(即使特定的尝试可能不同)。例如，平均数组搜索将是n+1(Θ)/2。
是这样的吗？
对平均搜索时间的解释是/2:在n个第一个整数的访问时间和为n(n+1)/2的情况下，大量随机访问数组的平均时间为(n (n+1)/2 )/n =(n+1)/2，在这种情况下，我认为Θ(n+1)/2将是平均访问时间。这(对我来说)很有意义，但由于我对渐近符号(以及一般的编程)还不熟悉，我想知道这是否是一种常见的做法。
我之所以问这个问题，是因为我很困惑地发现，在像http://bigocheatsheet.com这样的页面
浏览 0提问于2013-05-11得票数 1
回答已采纳
3回答
对于下面的伪码，最糟糕的时间复杂度大O表示法是什么？(假设函数调用是O(1))，我对大O表示法非常陌生，所以我不确定答案，但我认为O(log(n))是因为while循环参数每次乘以2，还是仅仅是O(loglog(n))？还是我在这两方面都错了？任何输入/帮助都是值得赞赏的，我正试图掌握最糟糕的时间复杂度的大O表示法的概念，我刚刚开始学习。谢谢!
i ← 1
while(i<n)
doSomething(...)
i ← i * 2
done
浏览 4提问于2016-02-01得票数 2
回答已采纳
2回答
我正在学习大O符号，我想找到我从Project Euler中解决的一个数学问题的大O符号。
total
for x (0..9){
for y (0..9){
for z(0..9){
if(some_condition == true){
total = total + permute(x,y,z)
}
}
} }
print total
我的猜测是O(N^3)，因为有3个循环，但我不确定
浏览 1提问于2015-02-23得票数 1
8回答
问题
嗨，我试着理解大O符号的复杂性顺序是什么。我读过很多文章，至今还没有找到任何解释“复杂性顺序”的东西，甚至在这里对大O的有用描述也是如此。
我对大O的了解
我已经明白的部分。关于Big表示法，我们用输入大小n的增长来度量算法的时间和空间复杂度。我还了解到某些排序方法对大O有最好的、最坏的和平均的场景，例如O(n)、O(n^2)等，n是输入大小(待排序的元素数)。
任何简单的定义或例子都将不胜感激。
浏览 4提问于2013-12-19得票数 5
回答已采纳
1回答
给出了一个n个整数的未排序数组，您希望找到数组中是否有任何重复项(即任何整数出现不止一次)。
该算法基于大小为n个整数的未排序数组。使用嵌套循环来查找重复项，其复杂度为:O (N^2)
如果我们限制输入数据以实现一些最好的情况场景，那么如何限制输入数据以实现更好的大O复杂度？描述一种处理此有限数据的算法，以查找是否存在任何重复数据。什么是大O复杂性？
这些问题提出以下问题：
如何限制数据的一种方法。
这将如何改变您查找重复项的算法，以及更好的大O复杂度是什么。
我想出的答案是：
如果我们将数据限制在5 (n = 5)的数组大小上，我们可以将复杂度降低到O(N)。
如果数组是排序
浏览 1提问于2014-03-15得票数 0
2回答
例如，如果我在我的方法中有两个参数M和N，并且时间复杂度被证明是O(M+N)，为什么人们说O(M+N)而不是O(N)，O(N)是O(2N)的简化形式？什么时候我们应该在大O符号中使用多个变量？这背后有什么道理吗？传递给参数的不同变量将如何影响增长率，为什么不将它们组合成一个大O变量？我想不出哪一个实例中传入的不同变量参数会影响运行时。我刚开始接触数据结构和算法，所以我想知道。
浏览 1提问于2020-07-02得票数 1
2回答
我刚开始在一个数据结构课，教师已经张贴了10个问题，并询问其中一个大O。根据我读过的文章，我假设这段代码的大O将是O(1)，因为数据参数是单个数据元素。但是，它确实执行了多次，这取决于数字的大小，所以这会使它成为O(N)吗？
public class Main {
public static void main(String[] args) {
f(100000);
}
public static long f (int n) {
long sum = 0;
for (long i = 2; i < n; i =
浏览 4提问于2016-03-20得票数 0
回答已采纳
一位同事向我提到，SQL Server不像MySQL/PHP那样适用于Big O。
任何占用CPU时间的东西都有一个大O...
我是不是误解了什么？我的意思是，如果运行查询，总会有一个大O？SQL Server如何例外或不同？
浏览 2提问于2013-04-30得票数 0
回答已采纳
1回答
我有两个链接列表，表示非常大的数字(除了链接列表之外，它不能保存在其他任何东西中)。我有一个复杂度为O(n)的Add方法。我想知道，在不将整个列表转换为字符串/int/long(如果可能的话计算列表)的情况下，是否可以以任何方式将这两个数字相乘，并将其保持在O(n^2)的复杂性上。
现在，无论我尝试什么，我都会得到一个O(n^3)的复杂性，而且它还不够好。
谢谢你的帮助。
浏览 4提问于2014-01-31得票数 1
回答已采纳
1回答
如果一个算法最坏的运行时间是6n^4 + 2，其最佳运行时间是67+ 6n^3，那么最合适的渐近表示法是什么？
我在试着学习大O符号。
是Θ(n^2)吗？
浏览 1提问于2022-02-02得票数 -1
回答已采纳
1回答
我真的很难计算出这段代码的大O符号。 Boolean validInput = false;
while (validInput == false) {
System.out.println("Please input number of cards");
if (stdin.hasNextInt()) {
n = stdin.nextInt();
if (n > 0) {
validInput = true;
} else {
System.out.prin
浏览 19提问于2021-11-06得票数 0
5回答
我知道这个算法的大O复杂度是O(n^2)，但我不明白为什么。
int sum = 0;
int i = 1; j = n * n;
while (i++ < j--)
sum++;
即使我们在开始时设置了j = n * n，我们在每次迭代中递增i和递减j，因此产生的迭代次数不应该比n*n少得多
浏览 62提问于2015-11-23得票数 54
回答已采纳
1回答
我已经编写了这段代码，它可以完成我想要的工作。我想要做的是找出代码的大O符号。所以我想学习如何计算时间复杂度，并最终得到一个大的O符号结果。用外行的话说是怎么做的？ ""“ def treetocode(hTree):
code = dict()
def getCode(hNode, currentcode=""):
if (hNode == None): return
if (hNode.left == None and hNode.right == None):
code
浏览 22提问于2020-06-24得票数 0
大O和大欧米茄表示法是什么？
int temp = 0
for (i =0; i < 100000000; i++)
for (j = 0; j < N; j++)
temp = 0
while(temp < j)
{
temp++;
}
浏览 3提问于2020-01-28得票数 1
1回答
我有一个关于渐近复杂性的问题，特别是大O符号。 从数学上讲:我们有一个函数T(n)它的输出:我们的算法所花费的时间。 例如T(n) = 1000 + 10n。我们选择一个简单函数F(n) =n，并且对于一些大的自然数N和常数C，T(n) <= C.F(n)，它等价于T(n)属于O(f(n ) ) (其中T其中一个由C.F(n)控制的函数集)。 我的具体问题:我没有得到上界的点，从一个特定的输入N，所有的T(n)点都是F(n)点的上界。 在计算机科学和大O表示法中，这种数学近似和最坏-最好情况的复杂性之间有什么关系 ?
浏览 37提问于2021-07-15得票数 1
1回答
是否有可能用大O符号编写一个程序来确定算法最坏的运行时间？例如，它能够确定对数组中的每个元素进行迭代的单个for循环的时间复杂度为O(n)，其中n是数组的大小？
浏览 5提问于2022-05-26得票数 0
3回答
我有一个关于O-记法的问题。(大O)
在我的代码中，我使用了一个for循环来迭代一个用户数组。如果找到了正确的用户，则for循环具有if语句，该语句可使其脱离循环。
我的问题是如何测量O符号？
当我遍历数组中的所有用户时，O表示法是O(N)吗？或者是O符号O(1)，因为循环中断了，再也不会运行了？
浏览 0提问于2021-05-11得票数 2
1回答
static void coin(int[] d, int amount) {
int num_coin;
for (int i = d.length - 1; i >= 0; i--) {
num_coin = amount / d[i];
System.out.println("You should give " + num_coin + " coins of denomination " + d[i]);
amount = amount % d[
浏览 4提问于2019-06-27得票数 0
回答已采纳
假设我们使用O(n)、O(log n)或etc...使用X算法实现了一个问题。n的值什么时候足够大，以至于我们必须考虑另一种实现？让我看看我能不能解释得更清楚一点。
For n=10,000
O(n^2) = 100,000,000
O(n) =10 000
O(原木)=4
。。。
显然，最好的算法将是一个最低的“大o”。
假设我们用气泡排序对长度为5的数组进行排序，结果是25，这也没那么糟糕。但是，当O表示法太大时，我们必须使用另一个实现。
浏览 5提问于2010-11-24得票数 3
回答已采纳
2回答
我正在学习大O和递归。我遇到了上面提到的一个问题，
t = { 0, n =1 ; T(n-) , n > 1 }
谁能告诉我如何从这里到O(n^2)？
浏览 1提问于2012-02-25得票数 0
回答已采纳
问题
我想找出算法的复杂性。该算法通过递归求解size n的两个子问题n-1，然后将解与常数时间相结合，解决了size n-的问题。
因此，我写了一个重复：
T(n) = 2 * T(n-1) + 1 * O(1)
= 4 * T(n-2) + 3 * O(1)
= 8 * T(n-3) + 7 * O(1)
= 2^k * T(n-k) + ((2^k)-1) * O(1)
我停留在这一点上，所以我做了一些搜索谷歌。用n-1代替k，使T(n-k)变为T(1)。
T(n) = 2^(n-1) * T(1) + ((2^(n-1))-1) * O(1)
浏览 2提问于2017-10-03得票数 0
回答已采纳
2回答
理解渐近表示法的困难
、、、
据我所知和研究，
大-欧表示法描述了算法时间复杂度的最坏情况。
大Omega表示法描述了算法时间复杂度的最佳情况.
大- Theta表示法描述了算法时间复杂度的平均情况.
然而，最近几天，我看到了一场讨论，有些人说
最坏的情况是“可原谅”的误解。最好的Θ显然是错误的。最好的Ω也是可以原谅的。但他们仍然存在误解。
大-O表示法可以表示任何复杂性。实际上，它可以描述任何函数的渐近行为。
我还记得在我的大学课程中学到了前一个。我还是个学生，如果我错误地认识他们，请你解释一下好吗？
浏览 2提问于2018-08-25得票数 0
1回答
我试图找到一种方法，以尽可能最小的时间复杂度排序数组。我当时认为下面的是O(n)，但是对我来说似乎不太可能，因为现有的数组排序方法最多只有O(nlogn)。我的问题是，这个方法在java中的大O复杂度是什么，它是如何计算的？
public static void ArrSort(int[] arr){
int temp;
for(int j=0;j<arr.length;j++)
{
if(arr[j]>arr[j+1]) {
temp=arr[j];
浏览 2提问于2022-05-22得票数 -2
回答已采纳
def dividing(n):
while n!=1:
n=math.floor(n/2)
return True
有这段代码，我最初的想法是，它的复杂度只是n，因为它只是输入，没有方格，除了研究n/2时，我发现它的大O复杂度是Log(m)，所以我现在很困惑，这个大o复杂度是log(m)吗？若然，为甚麽会这样呢？
浏览 7提问于2021-03-29得票数 2
回答已采纳
可能重复：
很多时候，当讨论算法的时间复杂性时，也会考虑到内存问题。我想知道大-O(1)，大-O(N)，大-O(n*n)记忆的含义是什么？
它和时间的复杂性有什么关系？
浏览 9提问于2011-11-22得票数 30
回答已采纳
2回答
下面的陈述是正确的还是错误的？
使用预置的通用算法永远不会有比O(nlogn)更糟糕的效率。
我想这是真的。因为这个的大O是O(nlogn)
浏览 5提问于2017-03-01得票数 0
1回答
我们的老师给了我们大O表示法的以下定义
O(f(n)): A function g(n) is in O(f(n)) (“big O of f(n)”) if there exist
constants c > 0 and N such that |g(n)| ≤ c |f(n)| for all n > N.
我试着拆解这个定义的各个组成部分。首先，我对g(n)在O(f(n))中的含义感到困惑。这意味着什么？
接下来，我对声明的第二部分感到困惑。为什么说，对于所有n>N，g(n)的绝对值小于或等于f(n)，意味着关于大O表示法
我对大O表示法的一般直觉是，它是描述算法运行时
浏览 1提问于2014-10-28得票数 0
回答已采纳
3回答
我已开始阅读C++ STL，并为此找到了一本书！在我阅读复杂性时，它在选择算法和数据结构中起着重要作用，我一直在看到，大Oh表示法只用于不同的变量(O(N)，O(log(n). ))，通过进一步浏览，我发现大Oh表示f(x) = O(g(x))--(big-oh) means that the growth rate of f(x) is asymptotically less than or equal to to the growth rate of g(x)。
所以我的问题是，如果一个算法的时间复杂度总是等于g(x)的增长，为什么我们把这个复杂度作为f(x)=O(n)[Big oh of
浏览 5提问于2016-02-02得票数 2
回答已采纳
1回答
当人们谈论解决图问题的算法时，在运行时间中考虑了哪些输入--顶点数、边数，两者兼而有之？换句话说，O(|V|)、O(|E|)和O(|V||E|)是否都是图形算法的有效多项式运行时间？如果|V|或|E|中的一个比另一个大，这有关系吗？
浏览 2提问于2014-04-09得票数 0
回答已采纳
我需要帮助理解一个大O问题。我理解了这个概念，并且已经做了几道练习题，但这一道题把我难住了。
使用大O的定义，说明f(n)=anlogn+bn是O(nlogn). (a, b > 0)
我不知道如何找到C或N，因为如果常数A或B改变，那么C和N也必须改变？还是我看错了？
我马上就要考试了，我真的很想事先弄明白这点。
谢谢!
浏览 1提问于2013-09-18得票数 1
4回答
快速排序时间复杂度
、、、、
我最近读到了关于时间复杂性的文章，我发现快速排序的平均时间复杂度为O(nlog(n))。
问题1:我不明白的是，日志(N)是如何在时间复杂性方程中出现的？
问题2:为什么我们总是使用大O表示法来寻找算法的时间复杂性？我们为什么不用其他符号呢？
浏览 7提问于2012-08-15得票数 1
回答已采纳
1回答
我在Cormen书中所研究的二进制Saerch算法的时间复杂性是：
最佳案例-O (1) 最坏案例-O (log n)
我的疑问是，他们为什么直接用“大O”符号写出了这两种复杂性。我可以说最佳案例复杂性是Theta (1)和最坏情况复杂性是Theta (log n)吗？
浏览 2提问于2020-01-11得票数 1
3回答
这个代码的大O符号是什么？
for( int i=1; i<2n; i++)
x=x+1;
我的回答= O(2*n)是对的吗？
浏览 1提问于2015-05-16得票数 2
回答已采纳
7回答
我需要找到两个降序列表(list1和list2)的联合，其中联合将是两个列表中没有重复的每个元素。假设列表元素是整数。我使用大O表示法来确定解决此问题的最有效算法。我知道第一个的大O符号，但我不知道第二个的大O符号。谁能告诉我第二个算法的大O符号，这样我就可以决定实现哪个算法了？如果有人知道比这些算法更好的算法，你能帮我理解一下吗？提前谢谢。
Here are my two algorithms. . .
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
A
浏览 1提问于2013-03-18得票数 7
回答已采纳
1回答
我是一名教师，告诉我的学生，像y=15x+8这样的表达式的大O是O(1)，但是当我们学习前缀和后缀时，我们讨论了求这些表达式的值是O(N)，因为你必须遍历方程的每个字符(假设给你一个字符串)。
一名学生问，我们是如何说评估一个表达式是O(1)，如果在幕后必须有一个infix，后缀或前缀评估正在进行。
我不知道该回答什么。
浏览 1提问于2020-11-30得票数 0
回答已采纳
2回答
我理解了基本原理，如果我有一个这样的函数：
int sum(int x, int y, int z) {
int r = x + y + z;
return r;
}
它需要3个参数单位的空间和1个局部变量的空间，并且这永远不会改变，所以这是O(1)。
但是如果我有一个像这样的函数：
void add(int a[], int b[], int c[], int n) {
for (int i = 0; i < n; ++i) {
c[i] = a[i] + b[0]
}
}
这需要N个单位用于a，M个单位用于b，L个单位用于c，1个单位用于i和n
浏览 1提问于2015-05-14得票数 17
2回答
我想学习大o，我希望有人能帮助我计数运算符的方法，告诉我这个方法的时间复杂性是什么，并教我如何计算。我试着在Youtube上学习，但我有点困惑。
static void SelectionSort(int[] data)
{
int temp, min;
for (int i = 0; i < data.Length - 1 ; i++)
{
min = i;
for (int j = 0; j < data.Length; j++)
{
浏览 2提问于2022-04-13得票数 0
回答已采纳
2回答
复杂性..大O
、、
我必须确定以下函数的时间复杂度(大O)：
void BET::makeEmpty(BinaryNode* &n)
{
if(n != NULL)
{
makeEmpty(n->left);
makeEmpty(n->right);
delete n;
}
n = NULL;
}
我熟悉简单函数(循环、嵌套循环等)的时间复杂性，但我不确定如何确定递归函数的大O。
谢谢!
浏览 1提问于2014-03-30得票数 1
1回答
Big O描述了时间复杂性和空间复杂性的概念，但是有没有更通用的更高级别的类别来描述Big O符号所描述的复杂性的域？
例如，如果有人提出了应用程序中复杂性的主题，我可能会问“您是指圈复杂度还是大O复杂度？”然而，Big O是一种描述复杂性的符号，而不是一种实际的复杂性类型。
时间复杂性和空间复杂性的概念是否不同于它们没有归入更正式的一般类别的程度？如果这些概念通常被归入一个更一般的类别，那么该类别的名称是什么？
浏览 2提问于2016-06-01得票数 3
我很困惑，我以为在最坏的情况下运行时间使用Big，而最好的是使用Ω？谁能解释一下吗？
(lg n)不是最好的情况吗？(nlg n)是最坏的情况吗？还是我误会了什么？
在大小为n的堆上，最大Heapify最坏的运行时间是Ω(lg n)。(提示:对于有n个节点的堆，给出节点值，使Max-Heapify在从根到叶的路径上的每个节点上被递归调用。)
编辑:不，这不是作业。我正在练习，这有一个答案，键买我迷茫。问题4(6.2-6)
编辑2:所以我误解了这个问题，而不是关于大O和Ω？
浏览 4提问于2013-03-14得票数 10
回答已采纳
1回答
我想知道汉诺塔算法的最佳情况下的复杂度。我使用的算法是
我计算了时间复杂度，它是T(2^n -1)，大O是O(n)。但是，什么是最好的情况下的复杂性以及如何计算它？
浏览 0提问于2020-12-04得票数 0
8回答
帮助使用大O符号
、、
我在尝试理解大O符号的概念时遇到了一些问题。因此，大O的定义如下所示，T(n) ∈ O(G(n)) if T(n) <= G(n) * C。
既然常量"C“可以是大于0的任何整数，下面的例子不也是正确的吗？
示例：
n log n ∈ O(log n)
n log n <= log n * c
其中C等于n的值。
我知道答案是n log n ∉ O(log n)，但我不明白为什么，因为C可以是任何常数。
提前感谢您的帮助:D
浏览 1提问于2010-07-28得票数 9
1回答
三维矩阵遍历大O
、、、
我对这两种算法的大O的尝试.
1)算法threeD(矩阵，n)
//大小为n的三维矩阵
layer ← 0
while (layer < n)
row ← 0
while (row < layer)
col ← 0
while (col < row)
print matrix[layer][row][col]
col ← col + 1
done
row ← row + 1
done
layer ←
浏览 1提问于2014-07-11得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
