伪代码算法：查找迭代次数 + best/worst 个案例场景

Question

给定以下伪代码，我应该找出最内层循环中的语句执行了多少次，作为 n 的函数，以及该算法的操作顺序的最佳和最差情况是什么是。

Algorithm What(A,n)
  A <-- new 2D array of n*n integers
  s <-- 0
  for I <-- 2 to n-2 do
     for j <-- I-2 to n-1 do
        s <--s + A[I][j]
     end for
   end for

我只是在概念化如何解决这些问题时遇到了麻烦。任何帮助将不胜感激:)

Answer 1

Algorithm What(A,n)
  A <-- new 2D array of n*n integers
  s <-- 0
  for I <-- 2 to n-2 do        
     for j <-- I-2 to n-1 do   ---> this executes (n-1)-(I-2)+1 times=n-I+2 times
        s <--s + A[I][j]
     end for
   end for

分析

所以 T(n)= 对 I ( n-I+2) = 0+1+2+...+n 次求和 [ for I= n-2 down to 2] =n(n+1)/2

T(n)= O(n^2)

参考：学习 Cormen 的书算法简介 或算法解锁（如果您是初学者）。您将熟悉分析过程。

伪代码算法：查找迭代次数 + best/worst 个案例场景

Pseudo Code Algorithm: finding number of iterations + best/worst case scenarios

algorithm

pseudocode

分析