如何计算嵌套循环的时间成本

Question

是否有一个数学公式，我可以在我的Windows计算器中计算我的嵌套循环的时间成本？

从我读到的，我看到像O（n）这样的东西，但我不知道如何把它放在计算器中。

我有一个300级嵌套循环，每个循环级别将从0到1000

所以它就像：

for i as integer =0 to 1000
{
 //300 more nested loops, each goes from 0 to 1000
}

我假设1个完整循环将花费1秒（即从最顶部循环到最内循环的300个级别将花费1秒）。

如何确定完成整个循环操作需要多少秒？

谢谢

Answer 1

如果你有M个嵌套循环，每个循环有N个步骤，那么最内部代码运行的总次数是NM。因此，如果此代码执行t秒，则总运行时间将不小于NMt。

在你的情况下，N = 1001，M = 301.因此

NM = 135100613528332135681503965572936668434980383198873905324080191446595532995501031878568339038189302148003825909757155656839303362412566303902047481680713912312468768866711065155453645555498331353162205366660114289048545458602040997122042702307944960321744251085417246566965755119837462103571625353748368178996297989938179411759336616760215910287874166611018614081177115766185697572722701177493817368925785168451503363083820342899051998130399446052148665113120565144078901400413228703450167819489527676653322223864446371467671712248681551967500362321874751607483376225875087260250476394552381244390502211287798976517858528172200122908677767202230123538748625620714770240900391167175061613370018686399771746802721755073886060599525507236398391404895578​​6591110292838269781981812167453230775137941595147968127169264749956845265384891251656562329411331097495063637387550896404766837508698223985774995150301001。

另外，如果我们假设最内部代码非常快，例如t =1μs，则总运行时间将不小于NMt = 1.35 ...×10897 s。

当宇宙结束时，你的代码将完全接近0.0000000000000000000000000000％，假设当时硬件没有出现故障并且人类文明还没有结束（因此你很难找到电气你需要运行你的硬件的力量）。