时间复杂度为O(n³)的算法在10倍速计算机上可处理的元素规模是多少

相同运行时长下的最大处理元素数 #

• 时间复杂度为O(n³)的算法，运行总运算量和元素规模的三次方成正比，关系可表示为：运算总量 = 常数系数 × n³
• 设备运算速度为10倍时，相同运行时长内能完成的总运算量也为原来的10倍，因此可建立等式：n_new³ = 10 × n_old³
• 计算可得新设备最大处理规模：n_new = n_old × ³√10 ≈ 2.15 × n_old，也就是约为旧设备可处理规模的2.15倍

直接将原规模乘以10的推算逻辑是否成立 #

• 该逻辑完全不成立
• 该推算方式仅适用于O(n)复杂度的线性算法，对于立方级复杂度的非线性算法，运算量随规模增长的速度远快于线性增长，不能直接按设备速度倍数缩放处理规模
• 以你给出的例子验证：旧设备可处理3个元素时，对应总运算量和3³=27成正比，10倍速设备相同时间可支撑270单位的运算量，对270开三次方得到约6.46，即最多只能处理6个元素，远低于推算的30个

内容的提问来源于stack exchange，提问作者GhettoThief