时间复杂度的计算合法吗？

文章/答案/技术大牛

发布

1回答

c、time-complexity

i>2; i = sqrt(i))void f1(int n){aux(n*n); aux(n*n*n);} 我可以假设sqrt(i)的时间复杂度是log(n) = 2^k 现在： k = log(1/log(n)) = log((log(n))^(-1)) = -1*log(log(n)) =Theta(log(log(n)) 我确实知道最终的解决方案是Theta(log(log(N)，但我想知道我的<

浏览 14提问于2020-09-10得票数 0

回答已采纳

1回答

如何在代数库中求代数运算的时间复杂度

algebraixlib

如何使用数学或大O表示法计算数据代数中使用的代数操作的时间复杂度。我将用书中的例子来解释我的问题。考虑一下书中给出的例子。B 在上面的例子中，我想计算转置和合成操作的时间复杂度。如果可能的话，我还想找出其他代数数据操作的时间复杂度。如果你需要更多的解释，请告诉我。 @wesholler我编辑了我的

浏览 0提问于2015-10-06得票数 0

1回答

计算密码散列函数/随机预言的时间复杂度是多少？

hash、complexity

我想知道在进行复杂性分析时计算哈希函数/随机预言的计算复杂度是多少。例如，计算H(b\|r)的计算复杂度是多少？其中b是位，而r是安全参数\lambda长度的随机字符串。如果b是字符串(即字符串消息)，那么计算复杂度是多少？在我看来，我们可以把它看作是占用poly(\lambda)时间，但是我们能把它当作恒定时间内的计算</em

浏览 0提问于2019-02-20得票数 1

1回答

在不同的编程语言中实现算法的时间复杂度是否有所不同？

algorithm、language-agnostic、time-complexity、big-o、clrs

不是假设算法在任何编程语言中都具有相同的时间复杂度吗?那么当我们计算算法的总时间复杂度时，为什么我们要考虑这种编程语言在时间复杂度上的差异，例如在参数中通过值传递或通过引用传递？或者，当我们发现算法的时间复杂性时，我们不应该在实现中考虑这种编程语言差异，这是错误的吗？到目前为止，我想不出任何其他的实例，但是例如

浏览 7提问于2020-12-09得票数 0

2回答

模运算的时间复杂度

math、matlab、time-complexity

假设我想要计算a (mod )。它的时间复杂度是多少？我正在使用Matlab，但不确定Matlab是如何计算它的。是否将a除以n，减去整数部分，然后再乘以n？问“这件事的时间复杂度是多少”有意义吗？

浏览 6提问于2012-01-10得票数 4

1回答

低复杂度DCT

algorithm、matlab、math、dct

我成功地计算了一幅图像的二维离散余弦变换( dct )，使用了经典的算法，并将其作为一维阵列的组合。这两种方法的时间复杂度分别为n^4和n^3。在图像上实现时，需要很长时间才能计算。使用n^3复杂度的图像，就像对512 x 512图像的7分钟。

浏览 0提问于2017-08-07得票数 0

1回答

移位加乘法的时间复杂度

time-complexity、multiplication

我试图计算出计算机移位的时间复杂度，并根据下面的图像添加乘法算法：那么，如果一个整数是A位宽的，并且操作的每一步都是B时间单位，并且总是完成一个加法步骤，那么这个算法的时间复杂度会是O(n*n)吗?它的每次移位和加起来都是O(n)吗？

浏览 0提问于2014-11-20得票数 1

回答已采纳

2回答

计算代码段的时间复杂度

algorithms、complexity、big-o、algorithm-analysis

我正在试图计算以下代码段的时间复杂度{ { {print("hello") }我就是这样计算的--变量i的第一个for循环执行n时间。内部for循环依赖于i，变量j按如下方式递增：1 + 2 + 3 + ... + k，当它比n大的时

浏览 0提问于2021-05-27得票数 0

2回答

输入的时间复杂度和大小

algorithm、time-complexity

我正在为一次考试做准备，考试的主要内容是时间的复杂性。我在解决这四个问题时遇到了一个问题。1)如果我们证明了一个算法的时间复杂度为θ(n^2)，那么对于所有的输入，它是否可能需要O(n)的时间计算？2)如果我们证明了一个算法的时间复杂度为θ(n^2)，那么它是否可能需要某些输入的O(n)的时间计算？3)如果我们

浏览 4提问于2013-06-11得票数 3

回答已采纳

1回答

算法复杂度渐近图

c++、algorithm、time-complexity、curve、asymptotic-complexity

我正在准备一个C++项目，我必须计算出许多算法复杂度big-O，并将其与图上的理论值进行比较。我做了一个时间函数来计算算法的执行时间，但我没有找到一种方法来计算复杂度，并使用时间T和输入N绘制曲线。有什么想法吗？

浏览 4提问于2016-04-22得票数 0

3回答

广度优先和深度优先遍历树的时间和空间复杂度是多少？

algorithm

有人能举例说明我们如何计算这两种遍历方法的时间和空间复杂度吗？另外，深度优先遍历的递归解决方案如何影响时间和空间复杂度？

浏览 1提问于2012-03-24得票数 76

回答已采纳

0回答

具有字符串键的HashMap真的比Trie具有更低的时间复杂度吗？

algorithm、data-structures

HashMap的时间复杂度为O(1)，概率很高，而Trie在这种情况下的时间复杂度为O(k)，其中k是字符串的长度。现在我的问题是:计算字符串的散列值的时间复杂度不是O(k)，从而使HashMap的复杂度相同吗？若否，原因为何？在我看来，这里的Trie查找字符串的时间

浏览 4提问于2016-07-15得票数 6

回答已采纳

1回答

for循环的时间复杂度

time-complexity、big-o

我需要计算以下循环的时间复杂度： for (i = 1; i < n; i++) } 假设n= 10，i < n;控制语句运行n次，i++;语句运行n-1次吗？并且知道i = 1;语句将运行一段时间。计算for-loop中三个语句的总时间复杂度得到1+n+n-1 = 2n，而循环及其语句得到2n+n-1 = 3n-1 = O(n)。我的计算<

浏览 25提问于2019-02-12得票数 1

1回答

审判庭的时间复杂性

factoring、complexity

在trail除法中，我们检查n \mod i从2到\sqrt{n}之间的i值，找出p的值，然后计算\dfrac{n}{p}来得到q。通常，时间复杂度是(假设在恒定时间内找到余数和除法) \sqrt{n}。如何计算密码的时间复杂度？假设b是以二进制格式表示n的位数，那么我可以直接在\sqrt{n}中替代，这样就可以得到2^{\frac{b}{2}}。还是应该将其计算为模块化操作所需

浏览 0提问于2015-11-16得票数 1

回答已采纳

5回答

算法的时间复杂度:如何在计算时间后决定哪一种算法

java、algorithm、time-complexity

今天，我在msdn中看到了博客，我注意到了如何计算算法的时间复杂度。我完全理解如何计算算法的时间复杂度，但在最后，作者提到了以下几行 (N+4)+(5N+2)+(4N+2) = 10N+8 因此，上述算法的渐近时间复杂度为O(N)，这意味着上述算法是线性时间复杂度算法为什么说它是基于线性时间复杂度

浏览 11提问于2012-05-11得票数 0

回答已采纳

2回答

使用像zip()和join()这样的内置python函数对我的函数的性能有什么影响？

python、python-3.x、time-complexity、big-o

下面我提供了计算LCF (最长公共前缀)的函数。我想知道大O的时间复杂度和空间复杂度。我能说它是O(n)吗？或者zip()和join()会影响时间复杂度吗？我想知道空间复杂度是O(1)。函数的输入是一个包含字符串的列表，例如["flower","flow","flight"]。

浏览 0提问于2020-05-20得票数 1

2回答

如何计算kurskal算法的时间复杂度: O(E log E) = O(E log V)？

algorithm、sorting、time-complexity

请告诉我如何计算Kruskal定理的时间复杂度的步骤？我知道Kruskal算法的算法，但不知道伪码和时间复杂度的计算。Kruskal算法的复杂度为O(E log E) = O(E log V) (维基百科)。但我不知道如何计算..

浏览 1提问于2014-04-14得票数 0

1回答

找到第i个最大的元素

algorithm、divide-and-conquer、recurrence

我想使用分而治之的过程来计算一行整数的第i个最大元素，并分析算法的渐近时间复杂度。if (high-i+1==q) return A[q]; else ith(A,q+1,high);是对的吗如果是这样，我们如何才能找到它的时间复杂度？时间复杂度由以下递归关系描述：

浏览 1提问于2015-03-29得票数 1

2回答

实体视图/纯函数可以任意复杂吗？

solidity、web3js、gas、contract-invocation、json-rpc

非常数函数在计算复杂度上受到块气体限制.我假设，但不确定，这不适用于view/pure函数。view/pure函数在计算复杂度上是否有任何限制，除了我要等很长时间才能执行长循环的事实吗？

浏览 0提问于2016-11-04得票数 16

回答已采纳

2回答

当内部循环用于不同的数组时，嵌套for循环的时间复杂度是多少？

java、arrays、time、complexity-theory

如果我们测量一个数组的时间复杂度，我们可以在时间复杂度计算中忽略不同的数组吗？(即如果我们只关心外部数组的增长，我可以说是O(N)，还是必须给出总的时间复杂度O(N*M)。

浏览 0提问于2020-09-22得票数 0

点击加载更多