lg*(n)的时间复杂度比lg(n)好吗？
在计算机科学中，时间复杂度是衡量算法执行时间随输入规模增长的增长率。lg(n)表示以2为底的对数函数，lg*(n)表示lg函数的迭代次数。
对于给定的n，lg(n)表示以2为底的对数函数的值。而lg*(n)表示对lg(n)进行迭代，直到结果不再变化为止的迭代次数。
lg(n)的时间复杂度比lg(n)要好。因为lg(n)表示对数函数的值，而lg(n)表示对数函数的迭代次数。迭代次数越少，算法执行的时间越短，时间复杂度越低。
lg*(n)常用于算法设计中，特别是在分析递归算法的时间复杂度时。它可以更准确地描述算法的执行时间，尤其是对于具有指数级增长的递归算法。
在云计算领域，lg(n)的应用场景相对较少，因为大多数云计算任务更关注实际的时间复杂度，而不是迭代次数。然而，在某些特定的算法设计和优化中，lg(n)可能会被用到。
腾讯云相关产品和产品介绍链接地址：
- 腾讯云计算服务：https://cloud.tencent.com/product
- 腾讯云数据库：https://cloud.tencent.com/product/cdb
- 腾讯云服务器：https://cloud.tencent.com/product/cvm
- 腾讯云人工智能：https://cloud.tencent.com/product/ai
- 腾讯云物联网：https://cloud.tencent.com/product/iot
- 腾讯云存储：https://cloud.tencent.com/product/cos
- 腾讯云区块链：https://cloud.tencent.com/product/baas
- 腾讯云元宇宙：https://cloud.tencent.com/product/vr
相关·内容
2回答
lg*(n)的时间复杂度比lg(n)好吗？
time-complexity、logarithm
我正在尝试理解lg*(n) log*(n)基数2与lg(n)相比的时间复杂度，我想知道他们中的哪一个是faster...can，有人能解释一下吗？提前谢谢。
浏览 74提问于2020-04-03得票数 0
回答已采纳
3回答
这个powerset算法的运行时间是多少？
algorithm、big-o、performance、powerset
我有一个算法，可以使用0到2^n之间的所有位来计算集合的幂集： index --; results.add(newSubset);我的问题是:这个算法的运行时间
浏览 0提问于2011-05-22得票数 5
回答已采纳
4回答
排序数组算法-重复值
sorting、array-algorithms
我有一个整数数组大小N，其中有重复的值，但我不知道值的范围。我在这个数组中有n/logn个不同的值，其余的都是重复的。
有没有办法以O(n)的时间复杂度和O(n/logn)的存储复杂度对其进行排序？
浏览 6提问于2014-12-23得票数 0
7回答
在数组中查找频率最高的元素的最快算法是什么
algorithm、sorting、search、complexity-theory
我有两个输入数组X和Y，我想返回数组X中出现频率最高的元素。 max_x = x End For由于有两个嵌套循环，该算法的时间复杂度为O(n^2)。我能用O(nlogn)或更快的速度来做这件
浏览 4提问于2013-03-24得票数 6
回答已采纳
1回答
如何确定以下代码的时间复杂度
algorithm、time-complexity、big-o、complexity-theory
public void test(int n) for(i=1;i<=n;i=i*2) for(j=1;j<n;j=j+(j*i)) //执行log(n)次的外部循环。我们如何计算内循环执行的次数？上面代码的时间复杂度是多少？
浏览 23提问于2020-04-04得票数 0
回答已采纳
2回答
查找此代码的大O
algorithm、big-o、complexity-theory
我需要一些帮助找到这个代码的复杂性或大O。如果有人能解释一下每个循环的大O是什么，那就太好了。我认为外循环应该是O(n)，但是内循环我不确定，*=2是如何影响它的？j *= 2;} while (k < n);
浏览 0提问于2015-10-09得票数 1
1回答
lg(n)是lg(N)的Omega吗？
algorithm、math、quicksort
我无法理解的地方是第3行到第4行。但我们能像第4行那样写吗？我不确定lg(n-i)是否是lg(n)的欧米茄。如果可能的话，我也想要直观的解释。
浏览 1提问于2021-12-19得票数 0
2回答
考虑以下职能：
algorithm、time-complexity
int unknown(int n){
for (i=n/2; i<=n; i++) k =k + n/2; 函数的返回值为Θ(n^2 2logn)。我的疑问是:函数的时间复杂性是Θ(nlogn)，我不知道它怎么会是Θ(nlogn)，因为外
浏览 1提问于2020-05-29得票数 0
回答已采纳
3回答
查找函数的大O值
algorithm、big-o
O(nlogn + n^1.01) O(nlogn + n^1.01) = O(nlogn)
请在这两个简化问题上帮助我
浏览 2提问于2010-02-07得票数 3
回答已采纳
2回答
确定算法的时间复杂度
algorithm、time-complexity
我正在解决一个问题，其中A在每次迭代中都会递减k的值。在每次迭代中，k也是加倍的。举个例子：如何评估此算法的时间复杂度？我认为由于增量的加倍，必须与O(logN)相关，但不确定如何直观/数学地得出结论。
浏览 13提问于2017-01-31得票数 1
3回答
大O代表最坏的运行时间，Ω是最好的情况，但是为什么有时在最坏的情况下使用Ω？
algorithm、data-structures、heap、complexity-theory、asymptotic-complexity
我很困惑，我以为在最坏的情况下运行时间使用Big，而最好的是使用Ω？谁能解释一下吗？
(lg n)不是最好的情况吗？(nlg n)是最坏的情况吗？还是我误会了什么？在大小为n的堆上，最大Heapify最坏的运行时间是Ω(lg n)。(提示:对于有n个节点的堆，给出节点值，使Max-Heapify在从根到叶<em
浏览 4提问于2013-03-14得票数 10
回答已采纳
3回答
"log*“是什么意思？
big-o、iterated-logarithm
我在读一本关于数据结构的书时偶然发现了术语O(log* N)。log*是什么意思？I cannot 和WolframAlpha 。
浏览 0提问于2010-09-26得票数 25
回答已采纳
3回答
寻找时间复杂度
c、algorithm、time-complexity
我试图理解下面每一个例子的复杂性之间的细微差别。:因此，复杂性必须是：因此，复杂性是n lg n。第一个for循环用于lg n次。那么，当没有内环执行依赖于外部循环时，如何计算复杂度<
浏览 0提问于2013-09-22得票数 2
回答已采纳
2回答
这个函数的时间复杂度是o(n)吗？
python、data-structures、big-o
我现在在一个数据结构类中，这个函数会被认为是O(N)吗？我的想法是因为while循环与for循环没有直接的关联，它仍然是O(N)？如果需要更多的信息/代码来获得更好的上下文，我不介意编辑这篇文章。我很感谢你的澄清。
浏览 14提问于2021-03-10得票数 1
1回答
在lg(n!)中运行的算法的时间复杂度时间
performance、time-complexity
在lg(n!)中运行的算法的大Θ(或最低大O)时间复杂度是多少？时间？
(其中lg ->日志基2)
浏览 2提问于2014-11-20得票数 1
回答已采纳
1回答
这个“计算所有回文子串”算法的运行时间是多少？
algorithm、priority-queue、palindrome
>(); for (int i = 0; i < string.length(); i++) { //n目前我不关心重复，但我不确定最坏的情况下运行时间的结果，从我的理解是这样的*
n (max poss
浏览 1提问于2016-08-31得票数 0
回答已采纳
1回答
subMethod(m)的复杂度为O(m)，下面代码的最坏情况复杂度是多少？
python、time-complexity
def func(n): for i in range(n//2, n+1): j = j * 2
浏览 0提问于2020-03-10得票数 0
1回答
当分析时间复杂性时，日志基2等于日志基3？
algorithm、big-o、time-complexity
大多数解决方案的练习4.4.6介绍。对于算法第3版，n*lg 3(N)= (n*lg(n))的大omega。谢谢
浏览 5提问于2014-05-25得票数 6
回答已采纳
3回答
选择比较算法求k值
algorithm、comparison、quicksort
假设我希望在n个元素数组中找到K值，并在排序后的输出中返回它们。K可能是-我考虑了一些有效的算法，但我所能想到的只是O(nlogn)的复杂性。我可以用“O(N)”来做吗？也许需要一些快速的修改？
谢谢!
浏览 6提问于2016-05-12得票数 0
回答已采纳
3回答
以下功能的时间复杂度是多少？
c++、c、algorithm
int func(int n){ return 0; return sqrt(n);其中sqrt(n)是Cmath.h库函数。O(1)
我认为运行时间完全取决于sqrt(n)。但是，我不知道这个函数是如何实现的。求出
浏览 2提问于2014-04-16得票数 7
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频活动推荐
腾讯云开发者
