algorithm - C++代码的指令执行

Question

您好，我有一个 C++ 算法，我想找到执行的指令。代码如下

cin >> n;   
for(i=1;i<=n;i++)
     for (j = 1; j <= n; j ++) 
     A[i][j] = 0;

for(i=1;i<=n;i++) 
A[i][i] = 1;

现在，经过我的计算，我得到了这个T(n) = n^2+8n-5。我只需要其他人来验证我是否正确。谢谢

Answer 1

好，我们一步一步来分析。

第一条指令

cin >> n

算作一次操作：1。

然后循环

for(i=1;i<=n;i++)
     for (j = 1; j <= n; j ++) 
     A[i][j] = 0;

让我们从里到外。该j循环执行 n 次数组赋值 ( A[i][j] = 0)、(n + 1)次j <= n比较和 n次j ++赋值。它也执行一次赋值j = 1。所以总共给出：n + (n +1) + n + 1 = 3n + 2。

然后外i循环执行 (n + 1)次i <= n比较、ni ++次赋值并执行 n 次j循环。它还执行一项i = 1任务。这导致： n + (n + 1) + n * (3n + 2) + 1 = 3n^2 + 4n + 2。

最后，最后一个 for 循环执行 n 次数组赋值、(n + 1) 次i <= n比较和 n次i ++赋值。它还执行一项任务i = 1。这导致： n + (n + 1) + n + 1 = 3n + 2。

现在，将三个操作相加，我们得到：

(1) + (3n^2 + 4n + 2) + (3n + 2) = 3n^2 + 7n + 5 = T(n)次操作。

时间函数是等价的，假设赋值、比较、加法和cin都是在恒定时间内完成的。这将产生一个复杂度为 O(n^2) 的算法。

假设 n >= 1，这是诅咒。