algorithm - 为数字供电的时间复杂度

Question

学习 MIT Opencourseware 的算法类(class)，一位教授谈到了对数字的幂及其时间复杂度。

x^n 简单地计算为 x*x*x...... n 次(想象一个简单的 for 循环，其中执行乘法)

他说这种方法的时间复杂度是 theta(n)。

这是我的分析:

设 N(x) 是一个给出 x 中位数的函数。然后，复杂度:

x*1 = N(x)

x*x = N(x)*N(x)

x*x*x = N(x^2) * N(X)

x*x*x*x = N(x^3) * N(x)

等等……

综上所述，T(x^n) = N(x) + N(x)*N(x) + N(x^2)*N(x) + N(x^3)*N( x) + ............ N(x^(n-1))*N(x)

T(x^n) = N(x)[1 + N(x) + N(x^2) + N(x^3) + ...... N(x^n-1 )]

但是，我无法进一步解决。它最终如何产生 theta(n)？

Answer 1

可以这样想。

如果您将两个数字之间的乘法视为需要单位时间的运算。然后 2 数乘法的复杂性在 theta(1) 时间内完成。 现在，在一个 for 循环中，它为 n 个数字运行 n-1 次。您应用此操作 n-1 次。所以 theta(1) 成本操作发生 N-1 次，这使得操作 theta(n-1) 的总成本在渐近术语中是 theta(n)

乘法是这样的

• x=x
• x^2 = x*x
• x^3 = (x^2)*x
• x^4 = (x^3)*x
• ................
• .....................
• .....................
• x^(n-1) =(x^(n-2))*x
• x^n = (x^(n-1))*x

它是每个步骤的 theta(1)，因为您可以使用上一步的结果来计算整体产品。例如，当您计算 x^2 时。您可以存储 x^2 的值并在计算 x^3 时使用它。同样，当您计算 x^4 时，您可以使用 x^3 的存储值。

现在所有单独的操作都需要 theta(1) 时间。如果做n次，总时间就是theta(n)。现在计算 x^n 的复杂度。

• 对于 x^2，T(2) = theta(1)
  这是我们归纳的基本情况。
  
• 让我们假设 x^k，T(k) = theta(k) 为真
  
• x^(k+1) = (x^k)*x, T(k+1)= theta(k)+theta(1)

因此，对于 x^n，时间复杂度为 T(n) = theta(N)

如果你想总结复杂性。你总结错了。

我们知道T(2) = theta(1)，两个数相乘的时间复杂度。

• T(n) = T(n-1)+T(2)(两个数相乘的时间复杂度和(n-1)个数相乘的时间复杂度)
• T(n) = T(n-2)+T(2)+T(2)
• T(n) = T(n-3)+T(2)+T(2)+T(2)
• ......................
• ......................
• T(n) = T(3) + (n-3)*T(2)
• T(n) = T(2) + (n-2)*T(2)
• T(n) = (n-1)*T(2)
• T(n) = (n-1)*theta(1)
• T(n) = theta(n)

如您所知，C 是您将如何编写幂(朴素)函数的示例。

 int power(int x,int n)
 {
     int powerVal=1;
     for(int i=1;i<=n;++i)
     {
          powerVal=powerVal*x;
     }
     return powerVal;
 }

现在，正如您所看到的，每次两个整数相乘都只需要 theta(1) 时间。你运行这个循环 n 次。所以总复杂度是 theta(n)