分析时间复杂度的算法

Question

我正在分析算法,我只是想知道我是否在正确的轨道上.

对于这个算法,我只计算行中有***的乘法.

这是算法:

1. 所以我从内线开始,我可以看到那里有2个操作(两个乘法).
2. 现在我正在查看2个最内部的循环,所以我可以告诉它p=p*20*z执行完全正确的(j) + (j-1)+(j-2)+(j-3)...1次数.这碰巧等于j(j+1)/2.
3. 所以总的来说,由于有两次乘法,所以它会发生2 * (j(j+1)/2).
4. 最后,"i"循环恰好发生了n次,所以,总的来说,它是n(2 * (n(n+1)/2)).

这是我背后的思考过程.我对么？谢谢.

Answer 1

你的思考过程是正确的.你需要用n替换j项(n是j可以假设的最大值),但这可能是一个错字.

此外,您可以从以下位置进一步简化:

n(2*(n(n+1)/2))
2*n*(n^2+n)/2
n^3+n^2

=> O(n^3)

最后一步是因为n立方项将以比n平方项大得多的速度增长,我们可以说它将主导大n的运行时间.我要提到的另一点是,你应该考虑将存储作为一个操作以及两个乘法,尽管显然这不会改变简化的大运行时.