大O符号Python函数

-2

foo（A）函数（其中n等于A的长度）的大O是什么？据我所知，foo（4）语句对于递归的每次迭代都是O（1）。我也理解foo（A // 8）语句的运行时间将是对数的。大O符号Python函数

因此，程序的运行时间是否会是bigO（log（n））？

此功能用于练习测试的运行时间。

def foo(A): 
    if A <= 6: 
     return 7 
    return foo(A//8) + foo(4)

来源

2017-08-10 Roy Levy

是的，它会... –

你的分析是正确的。 foo(4)需要一定的时间，并且您必须执行关于log n（基数8）次的操作 - 当然是O(log n)。

如果使用公式是更加舒适，验证与Master Theorem（A = 1，B = 8，K = 1 = 0）。

来源

2017-08-10 05:49:27 perigon

你的程序可以被写成如下recurrsion：

T(n) = T(n/8) + C

应用Master theorem其中一个= 1和B = 8

我们落入第二种情况：

n^(log(1) base 8) = n^0 = 1 
C = ϴ(1). 
==> T(n) = O(n^(log(a) base b) * log(n)) = O(n^(log(1) base 8) * log(n)) 
     = n^0 * log(n) = 1*log(n) = O(log(n))

来源

2017-08-10 06:11:15

A不是一个向量，而是一个整数，因此有n N在这个问题中，复杂性必须用A来表示。

让我们模拟的执行与A=1000：

foo(1000) 
    calls foo(125) and foo(4), i.e. 
    calls foo(15) and foo(4), and foo(4), i.e. 
    calls foo(1) and foo(4), and foo(4), and foo(4).

你得到的格局。因此，对foo的间接呼叫总数等于您可以将A除以8，直到它小于或等于6加上最终呼叫的次数。

这正是Floor(Log8(Ceil(A/7)))+1，这确实是O(Log(A))。

只是为了好玩：

如果你写的八进制A（基数为8），该函数foo计算的八进制数字7时间的总和，但最右边，加上7或14（如果最后数字是7）。

来源

2017-08-10 07:15:13

请注意解释downvote。 –

我没有投票给你。但我可以想，也许这是因为你的回答不明确。（即使它是正确的）。也许是因为已经有答案，你的没有添加任何东西。 –

@TonyTannous：我写了一个具体的答案（即显示在特定情况下采取的确切步骤，然后推广）。我还提供了呼叫次数的确切公式，并修正了OP的概念错误。我认为这不值得赞扬。 [但感谢您留心评论。] –

大O符号Python函数

回答

相关问题