时间复杂度

可有人请向我解释如何计算下列递归代码的复杂性：时间复杂度

long bigmod(long b, long p, long m) { 
    if (p == 0) 
     return 1; 
    else 
    if (p % 2 == 0) 
     return square(bigmod(b, p/2, m)) % m; 
    else  
     return ((b % m) * bigmod(b, p - 1, m)) % m; 
}

来源

2011-04-19 station

这O（日志（P）），因为你是除以2每次或减去一个然后除以二，所以最坏的情况下会真的取O（2 * log（p）） - 一个用于除法，一个用于减法。

请注意，在这个例子中，最坏情况和平均情况应该是相同的复杂度。

来源

2011-04-19 04:45:31

它运行在O(log n)

没有昂贵的操作（通过我的价格比平方或改装，无循环等）的功能里面，所以我们可以非常简单，只是算函数调用。

最好的情况是两个幂，我们将需要完全的log（n）调用。

最糟糕的情况是，我们每隔一个电话会收到一个奇数。这只能做我们的呼叫的两倍。乘以一个常数因子，不会渐近地变坏。 2*f(x) is still O(f(x))

O(logn)

来源

2011-04-19 04:45:58

分割如果数字为负你从中减去1，它变得比除以2正，所以它不能被登录（ n）甚至在更糟糕的情况下。 – 2011-04-19 04:48:03

我没有遵循，你可以再试一次吗？如果哪个数字是负数？我认为我们的答案几乎是一样的东西，我没有看到差异 – 2011-04-19 04:52:43

因此，p是正数比我们除以2，或负数比我们减去一个，并且必须在之后除以两。 – 2011-04-19 04:55:11

如果你想更正式的关于它，那么你可以写一个递推关系，并使用主定理来解决它。 http://en.wikipedia.org/wiki/Master_theorem

来源

2011-04-19 04:51:12 Adam

它是为O（log（N））基体2，因为通过2

来源

2013-03-12 19:45:38

我认为你应该添加一个解释为什么这样。 – 2013-03-12 20:05:15

你能展示你是如何提出答案的？ – 2013-03-12 20:05:27

回答

相关问题