Big O表示法:O(n ^ 2)和O(n.log(n))之间的差异？
在计算机科学中，Big O表示法是一种描述算法时间复杂度的方法。时间复杂度是指执行算法所需的时间与输入数据规模之间的关系。Big O表示法通常用来评估算法的效率。
O(n^2)和O(n.log(n))是两种不同的时间复杂度表示方法。
O(n^2)表示算法的时间复杂度是输入数据规模n的平方。当n较大时，算法执行的时间会呈平方增长。O(n^2)通常表示嵌套循环的算法，例如冒泡排序和选择排序。
O(n.log(n))表示算法的时间复杂度是输入数据规模n乘以n的对数。当n较大时，算法执行的时间会呈线性增长。O(n.log(n))通常表示分治算法，例如归并排序和快速排序。
因此，O(n^2)和O(n.log(n))之间的差异在于它们的时间复杂度增长速度不同。当n较大时，O(n^2)的算法执行时间会远远超过O(n.log(n))的算法。因此，在选择算法时，应尽量避免使用O(n^2)的算法，而是选择更高效的O(n.log(n))算法。
相关·内容
2回答
大O符号-请解释O(log2n)
java、for-loop、big-o
我很难理解为什么这段代码的大O符号是O(log2^n)： sum = i+j;我想应该是O(n)。
浏览 0提问于2017-10-29得票数 3
回答已采纳
3回答
了解大O符号O(2^N)
algorithm、time-complexity、big-o
我正在尝试理解以下用于计算斐波那契级数的递归函数是如何落入符号O(2^N)的。} 例如，如果我们考虑寻找数字"5“的斐波纳契数列，则fibo方法被调用15次。如何说它属于符号O(2^N)？fibo(1) fibo(3) fib0o(2)
---------------- ---------- -请认为我是一个新手
浏览 64提问于2019-09-18得票数 1
1回答
根据增长率排列渐近函数
algorithm、complexity-theory
按递增顺序排列以下增长率 O(n3)，O(1)，O(n2)，O(nlogn)，O(n2logn)，Ω(nlogn)，Θ(Nlogn)，Θ(n0.5)
浏览 17提问于2020-03-23得票数 0
回答已采纳
3回答
Big-O符号代码算法分析作业
big-o、time-complexity
for(int i=N; i>0; i=i/2) 我被要求找到complexity类，我不确定我应该使用Big-Omega表示法还是Big-O表示法但我假设它是O(N/2)，然后是O(N)，如果我去掉常量。for (int i=0; i<N;
浏览 2提问于2010-10-17得票数 1
5回答
算法，大O表示法:这是函数O(n^2)吗？还是O(n)？
java、algorithm、big-o
这是一本算法书“Java中的数据结构和算法，第6版”中的代码。作者: Michael . GoodRich，Roberto Tamassia和Michael H.n; j++) answer += c; return answer;作者认为，这个算法的大O表示法是O(n^2)，理由是：“答案+= c是答案第一次通过这个循环
浏览 0提问于2018-07-30得票数 2
回答已采纳
2回答
快速排序omega表示法
time-complexity、big-o、quicksort
快速排序的最佳情况是n log(n)，但每个人都使用Big-O表示法将最佳情况描述为O(n log (n))。根据我对符号的理解，Quicksort有Big-Omega(n log (n))和O(n^2)。这是正确的，还是我误解了Big-O
浏览 2提问于2018-05-22得票数 0
2回答
何时使用大O表示法以及何时使用大Theta表示法
algorithm、analysis
例如，当我们考虑函数f(n)=O(g(n))或类似于Big Theta时，我知道Big O是一个上界，Big Theta是一个紧界。但是，我们如何知道使用Big theta表示法而不是Big O表示特定的算法会更好呢？
例如，选择排序的时间复杂度是N^2的Big</e
浏览 0提问于2017-02-02得票数 0
1回答
基于python函数的大O符号的确定
python、big-o
我有一个学校作业，我需要确定两个函数的大O符号。问题是我们还没有真正的Big O课程，更不用说Python了。有人能解释一下如何确定大O，给定这些函数吗？谢谢!def my_func1(inputs): result = 0 j = 1while j < n:
result += inputs[i
浏览 3提问于2021-05-12得票数 0
1回答
渐近分析与大O
java、time-complexity、big-o、complexity-theory
让我们考虑以下功能： int x = 0; for(int j = 0; j < n; j++根据Big表示法，这个函数的运行时复杂性将是(我将非常精确)：N</
浏览 1提问于2018-09-20得票数 0
2回答
求素数算法的时间复杂度
python、algorithm、primes、sieve-of-eratosthenes
我对素数很好奇，我想知道找出相对较小的素数的最有效的方法，范围可达1,000万。我读到，筛子的埃拉斯托塞尼(SOE)是寻找较小的素数最有效的方法。我使用python实现了SOE，但有一些问题：
我的算法最坏的运行时间似乎是O(n^2)。我还在学习，所以我知道这个算法可以提高效率。在寻找素数时，最有效的数学方法和最有效的编程方法有区别吗？从数学
浏览 3提问于2014-08-06得票数 2
2回答
如何理解给定示例中的Big符号
algorithm、time-complexity、big-o、complexity-theory
表示T(n)是O(n^4)。但我想知道为什么不是O(n^3)？它包含n^3，如果省略20n和1，则应该是O(n^3)而不是O(n^4)。为什么是这样？
浏览 0提问于2019-02-27得票数 0
回答已采纳
1回答
O(n) + O(n^2) = O(n^2)？
time-complexity、big-o、complexity-theory
我们知道的O(n) + O(n) = O(n)，甚至的O(n) + O(n) +.+ O(n) = O(n^2)。是O(n</
浏览 3提问于2022-09-18得票数 0
1回答
这个递归代码的运行时是什么？
recursion、big-o
我想知道下面的递归函数的运行时是什么： if (n <= 1) { } }
如果你把它想象成一个调用树，那么每个节点都会有2个分支。该调用树中的节点数为2^n + 2²+2²+ 2³+ ... +2^n</em
浏览 10提问于2018-08-29得票数 0
回答已采纳
4回答
使用分离过程的大O表示法
algorithm
今天是我开始学习算法和算法分析的第一天。更具体地说，渐近分析。但在我开始之前，我有一个简单的问题需要澄清，我似乎在其他地方找不到。给出下面的代码片段，在Big O表示法中，算法的复杂度是多少？// Linear Computation: O(n)
浏览 25提问于2020-08-24得票数 0
回答已采纳
5回答
我一直在研究Big表示法，并遇到了一个运算计数2^n+n^2。我理解大O表示法的做法是删除常量和低阶项，但是我不知道要生成哪一个O(n)。我想可能是2^n，但没有找到任何线索。
浏览 7提问于2016-01-08得票数 7
回答已采纳
1回答
大O符号求和混淆
big-o
我希望使用Big表示法来说服其他人代码增强--这是为了提高效率和可读性。但我不确定我是否错了。for(var i=0;i<n;i++) doA
浏览 3提问于2017-01-18得票数 0
回答已采纳
4回答
数据库索引及其大O表示法
sql、database、sqlite、indexing、big-o
我试图从Big-O表示法的角度来理解数据库索引的性能。在对此了解不多的情况下，我会猜测：这通常是正确的吗？查询主键的</e
浏览 82提问于2011-01-15得票数 34
回答已采纳
2回答
符号T(n)是什么意思？
notation
我们学习了大O符号，但我也经常看到T(n)。mergeSort(A, low, mid); //cost = T(n/2) + e return merge(A1,A2);
浏览 1提问于2012-11-29得票数 12
3回答
大O表示法中的O(m+n)和O(m*n)是什么？
algorithms、big-o
据我所知，O(n)描述了一种算法，其性能将与输入数据集的大小成正比地线性增长。这方面的一个例子是for循环： puts nO(m+n)和O(m*n)是什么意思？我在网上找不到这方面的任何明确的例子。请提供例子！谢谢!
浏览 0提问于2015-09-07得票数 3
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
活动推荐
腾讯云开发者
