我已经知道部分旋转的大 O 是并且对于完全旋转保持不变。我也知道部分旋转的大 theta 复杂度是
我想知道在 big theta 中完全旋转的复杂性
我已经知道部分旋转的大 O 是并且对于完全旋转保持不变。我也知道部分旋转的大 theta 复杂度是
我想知道在 big theta 中完全旋转的复杂性
从您报告的数字中,我假设您将乘法或 FMA 计算为您的基本操作,这是计算“触发器”或浮点操作的可能方法之一。
在这种情况下,旋转需要零浮点运算,因此成本为零。GECP 的成本仍然 。触发器模型的一个弱点是它无法区分两者。
然而,在现实生活中,GECP 确实比 GEPP 花费更多:您需要更多的比较和内存读写来进行交换。应该如何计算这些操作?例如,它们需要多少个处理器周期?这很复杂:有缓存、管道、超线程和各种低级的东西。实际运行时间将取决于矩阵中的实际数据。在现实生活中的大多数计算机上,即使两次运行相同的代码也不会花费完全相同的时间。要了解预测 CPU 时间有多么棘手,请查看这个 SO question,例如。
许多科学计算领域的研究人员会告诉你,在某些时候,唯一的解决方案是忘记大θ运算计数,而只在样机上测量真实世界的挂钟时间。操作计数只是一个有用的近似模型,但只能以一定的精度预测现实。正如智者所说,所有模型都是错误的。