我有一个关于表示n个数的乘积的算法的运行时间的问题。我认为最好的解决方案是分而治之，它是基于递归地将n个元素除以2，再乘以2个元素令人困惑的是简单操作的数量。在分而治之的情况下，复杂性应该是O（Logn），所以如果我们有8个数字乘以，我们应该有3个基本步骤。例如，我们有8个数字…我们可以把8减半，直到达到2，然后开始乘以（A1 A2 A3 A4 A5 A6 A7 A8）……（a1*a2=b1）（a3*a4=b2）（a5*a6=b3）（a7*a8=b4）（b1*b2=c1）（b3*b4=c2）（c1*c2=final result）……然而，在这个结果中，我们需要7个简单乘法。有人能给我澄清一下吗。。？
最佳答案
分而治之是指当你可以将你的原始集合划分成多个子集合时，在你识别并创建它们之后，它们就不再相互作用了（或者只以一种与每个子集上的操作相比微不足道的便宜的方式）。在您的情况下，您违反了“子集在标识它们之后不交互”规则。
此外，O（x）并不意味着操作数小于x，它只是意味着，对于x大小的任何具体数据集，都有一个有限值d，因此所需的操作数小于d*x（我的母语是德语，希望我在翻译时没有改变其含义）因此，事实上，在8个数据项上需要8个操作本身并不意味着复杂性大于O（log n）。
关于algorithm - n个数乘积的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20592751/