complexity-theory - 复杂性和运行时间

Question

我试着环顾四周，看看是否可以回答我的答案，但我没有偶然发现什么可以帮助我。

在处理运行时复杂性时，您是否考虑了操作数？根据我对处理运行时间的理解，每个不同的操作数都可能花费 x 时间，所以只计算循环给你下限？如果这是不正确的，请您向我解释我的逻辑错误的地方。

例如：

            for (i=0;i<n;i++)
               for (j=0;j<n;j++)
                 a[i,j]=b[i,j]+c[i,j]

只是 O(n^2) 对吗？还是因为加法操作数而成为 O(a*n^2) ？并且您使用“O”作为运行时间通常正确吗？

例如：

            for (i=0;i<n;i++)
               for (j=0;j<n;j++)
                 a[i,j] -= b[i,j] * c[i,j]

会再次成为 O(n^2) 对吗？还是会因为减法和乘法运算而成为 O(a^2*n^2) ？

谢谢堆栈！

score 0 · Accepted Answer

我建议您阅读 O 表示法的含义。但让我向您简要介绍一下：

当我们说时f(x)=O(g(x))，我们的意思是对于某个与输入大小无关的常数 c，

f(x)<=c.g(x) for all x>=k

换句话说，超过某个点 k，曲线 f(n) 总是以曲线 g(n) 为界，如图所示。

在此处输入图像描述

现在，在您考虑的情况下，加法和减法运算、乘法运算都是需要恒定时间（O(1)）的原始运算。假设两个数字相加需要“a”时间，而分配结果需要“b”时间。

所以对于这段代码：

  for (i=0;i<n;i++)
   for (j=0;j<n;j++)
     a[i,j]=b[i,j]+c[i,j]

让我们草率地忽略赋值和更新的for循环操作。运行时间T(n)=(a+b)n²。

请注意，这只是O(n ² )，为什么？

根据定义，这意味着我们可以识别出某个点 k，对于某个常数 c，曲线 T(n) 始终以 n ²为界。

意识到这确实是真的。我们总是可以选择足够大的常数，使 cn^2 曲线总是在给定曲线之上。

这就是为什么人们说：放弃常数！

底线： f(n) 的大 O 是 g(n) 意味着，在某条垂直线的右侧，曲线 f(n) 始终以 g(n) 为界。

1 回答 1