algorithm - 在 O(p*log(5)) 中，我们可以忽略 log 5 作为常数吗？

Question

func(p) 的大 O 时间复杂度是多少？ C++ 代码如下。

int get_power(int a, int b)
{
   if(!b) return 1;
   if(b%2) return a * get_power(a, b/2);
   return get_power(a, b/2);
}
int func(int p)
{
   int sum = 0;
   for(int i = 1; i <= p; ++i) 
   {
      sum += get_power(i, 5);
   }
 return sum;
}

int main()
{
   int c;
   scanf("%d",&c); 
   func(c);
}

根据我的理解，复杂度为 O(p) !!这是对的吗？？？有可能是 O(p*log5)

Answer 1

抱歉我的英语不好；我以前从来没有用英语写过任何包括数学在内的帖子..

你好像误解了什么O()意味着。

“f(x) is O(g(x))”表示存在X这使得 f(x) <= N * g(x) 为真对于每个 x > X , 其中N是常数。

例如，假设f(x) = log2 * x .可以肯定的是 f(x) <= log2 * g(x)其中 g(x) = x .所以我们可以说“f(x) 是 O(x)”。 (我说 N 是常量；如你所知，log2 是常量。)

然而，当谈到f(x) = x^2时, f(x) 不是 O(x)，因为f(x) > N * x其中 x > N . 不可能存在X这使得 f(x) <= N * x 为真其中 X > x .

---

你问的是否复杂func是O(p)或 O(p * log5) .回答:都是真的。

...which makes it true that f(x) <= N * g(x) where N is constant...

从这句话可以知道，O(g(x) * log5)等于O(g(x)) .常数倍数对 O() 没有任何影响.