algorithm - 如何计算算法的复杂度？

Question

我目前正在学习算法入门类(class)，我需要帮助来解决这个问题。如上所示，因为我持怀疑态度并且不太确定。 :) 我有两个问题:

问题一: 根据我从算法书中了解到的情况，我相信这个问题的运行时复杂度是 f(n) = 3n。为什么？好吧，因为 while 循环将继续运行 n 次，并且对于循环的每次迭代，您有 3 次操作(1 次减法、1 次乘法和 1 次加法)我的 though 过程是正确的还是错误的？由于赋值语句，它真的应该是 f(n) = 5n 吗？我知道两者的复杂性相同，但我真的很想明确地确认一下。

问题二: 至于显示算法是否找到多项式的值，足以让我举例说明它找到特定多项式的值，比如 3n^2 + 2n + 1 来证明算法有效或者是否有更好的这样做的方法。

Answer 1

第一个问题，复杂度确实是O(n)。

如果你想像你所要求的那样更精确地确定，在每个循环中，你的算法将需要一定数量的操作(我的复杂性类(class)有点陈旧，我希望我不会错过任何;) ):

1. 分析循环条件:i>=0
2. 计算x和y的乘积
3. 将结果添加到a[i]
4. 将结果存入y
5. 计算 i - 1
6. 将结果存入i

您的程序还将执行 3 个额外操作:

1. y = 0
2. 我=n
3. 上次比较i和0，不进入循环

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

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

为了证明你的算法，你首先必须写下你的前提条件(你应该在条目中有什么)。 然后你必须在你的 while 循环开始时指示你的程序应处于的状态，并在它结束时指示相同的状态。

例如: y=0 我=n 同时(我> = 0){ //y=Sum(a[j] + x^j, j>i) y=a[i] + x ^ i//我想应该是 x^i 而不是 x*y y=Sum(a[j] + x^j, j>i-1) 我=我-1 //y=Sum(a[j] + x^j, j>i)

我没有找到该程序的任何必要前提，我只是在前面提到它，因为它对其他类似作品的思考很重要。 如图所示，思路是显示程序在每一点的状态，这样我们就知道它到达终点时所处的状态。