gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:38:34 32 4
gpt4 key购买 nike

学习 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)?

最佳答案

可以这样想。

如果您将两个数字之间的乘法视为需要单位时间的运算。然后 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)

关于algorithm - 为数字供电的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20828489/

32 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com