这是为这种算法的最坏情况下的时间复杂？ [英] What is the worst case time complexity for this algorithm?

问题描述

 程序matrixvector（n为整数）;
变种I，J：整数;
开始
  对于i＆LT; -1到n也开始
    乙[I] = 0;
    C [i]于= 0;
    为J＆LT; -1到我这样做
      B〔1]  - ;  -  B [I] + A [I，J]。
    为J＆LT; -n到I + 1做
      C [1]  - ;  -  C [I] + A [I，J]
  结束
结束;
 

解决方案

为O（n ^ 2），如果我没有看错！

为什么你需要两个内环是超越我。为什么不总结B和C在同一个循环？

procedure matrixvector(n:integer);
var i,j:integer;
begin
  for i<-1 to n do begin
    B[i] = 0;
    C[i] = 0;
    for j<-1 to i do 
      B[i]<- B[i]+ A[i,j];
    for j<-n down to i+1 do
      C[i]<-C[i] + A[i,j]
  end
end;

解决方案

O(n^2), if I read it right.

Why you need two inner loops is beyond me. Why not sum B and C in the same loop?

这篇关于这是为这种算法的最坏情况下的时间复杂？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！