计算C中给定函数的时间复杂度
大卫
我需要计算f3函数的时间复杂度： 
我的问题是，我无法成功计算在n上的applet sqrt（）函数直到其小于1n^0.5^k < 1的时间是多少，我可以假设sqrt（）的时间复杂度为1。 k值超出n^0.5^k < 1？如果我成功了，那么我认为该系列的总和是n/2, (n^0.5)/2, (n^0.5^2)/2,...很容易的。
补助金
我将显示上下限。
首先，我们计算的成本g3。
例如，n = 2^16。
我们在for循环中进行了多少次迭代？
i=2^0, i=2^1, i=2^2, i=2^3... < 2^16
或多或少，这将是16个步骤。因此，g3的成本为O(log(n))。
现在让我们尝试计算f3。由于它g3在循环内使用，因此将如下所示：
log(n) + log(n^(1/2)) + log(n^(1/4)) + log(n^(1/8)) + ...
这肯定大于log(n)，因此我们可以将其log(n)作为下限。
现在，为了计算上限，我们必须考虑，循环执行了多少次迭代？
再举2^16一个例子：
2^16, 2^16^(1/2), 2^16^(1/4), 2^16^(1/8), 2^16^(1/16),
原来是：
2^16, 2^8, 2^4, 2^2, 2^1
在下一次迭代中，由于sqrt(2)四舍五入，我们将停止。
因此，通常，如果n=2^2^k，我们将进行k次迭代。那是log(log(n))。这意味着我们可以说log(n)*log(log(n))是上限。
可能有一个更调整的解决方案，但这应该是非常准确的。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
c循环函数计算时间复杂度
- 2
如何计算我的C函数的时间复杂度
- 3
计算嵌套循环在C中的时间复杂度
- 4
C ++中strstr（）函数的时间复杂度，空间复杂度和算法是什么？
- 5
计算代码中的时间复杂度
- 6
在C中此函数的时间复杂度是多少？
- 7
计算函数的复杂度，在python中
- 8
给定代码段计算时间复杂度的问题
- 9
如何计算给定代码的时间复杂度？
- 10
时间复杂度计算
- 11
如何计算递归函数的时间复杂度？
- 12
如何计算以下函数的时间复杂度？
- 13
如何计算此函数的时间复杂度？
- 14
计算内部有循环的递归函数的时间复杂度
- 15
给定嵌套循环的时间复杂度
- 16
给定代码场景的时间复杂度
- 17
heapq库中的函数的时间复杂度是多少
- 18
Linux中crypt函数的时间复杂度是多少？
- 19
我的算法的时间复杂度计算
- 20
算法的时间复杂度计算
- 21
计算迭代算法的时间复杂度
- 22
计算动态数组的时间复杂度
- 23
计算大阶乘时间复杂度
- 24
如何计算时间复杂度？
- 25
计算内循环的时间复杂度
- 26
简单的时间复杂度计算
- 27
如何计算时间复杂度？
- 28
计算算法的时间复杂度
- 29
计算递归算法的时间复杂度
我来说两句