如何计算算法的复杂度？

Question

我目前正在介绍算法课程，我需要帮助解决这个问题。由于我对此表示怀疑，因此不太确定。 :)我有两个问题：

问题1： 从我所了解的算法书中，我相信这个问题的运行时复杂度是f（n）= 3n。为什么？那么因为while循环将继续运行n次，并且对于循环的每次迭代，您有3次操作（1次减法，1次乘法和1次加法）是我的过程是正确还是错误？由于赋值语句，它应该是f（n）= 5n。我知道两者都是相同的复杂性，但我真的很想明确地确定。

问题2： 至于说明算法是否找到了多项式的值，我已经足够让我举一个例子来找到一个特定多项式的值，例如3n^2 + 2n + 1来证明该算法的工作原理还是有更好的方法来做到这一点。

Answer 1

对于第一个问题，复杂度确实是O（n）。

如果你想要更确切地确定你想要的东西，在每个循环中，你的算法将需要一定的操作量（我的复杂课程有点旧，我希望我不会错过任何; ））：

1. 判断循环条件：ⅰ> = 0
2. 计算x和y的乘积
3. 结果添加到A [1]
4. 将结果存储在y中
5. 计算我 - 1
6. 。结果存储在我

你的计划也将做3个额外的操作：

1. Y = 0
2. 我= N
3. 比较我到0的最后一次，不进入循环

你也可以考虑计算机必须为y和i等分配内存的事实。

对于第二个问题，如同在数学中一样，证明它在一种情况下是有效的，并不足以证明它在任何情况下都有效。

为了证明你的算法，你首先必须编写你的前提条件（你应该有什么入口）。 然后，你必须在你的while循环开始时指出你的程序应该处于的状态，并且在它的结尾处同样。

例如： Y = 0 i = N时 而（ⅰ> = 0）{// Y =总和（A [j]的+ X ^，j将>ⅰ） Y = A [1 ] + x^i //我假设它是x^i而不是x * y y = Sum（a [j] + x^j，j> i-1） i = i-1 // y = Sum（a [j] + x^j，j> i） }

我没有找到任何必要的程序前提条件，我刚才提到过它，因为重要的是要考虑它其他类似的作品。 如图所示，这个想法是在每个点显示程序的状态，所以我们知道它到达最后的状态。