سوال ۷۲ کنکور ارشد علوم کامپیوتر ۱۳۹۸

طراحی الگوریتممتوسطپیچیدگی مجانبی و نرخ رشد

اهمیت

۰/۵

فرض کنید در برنامه زیر C = aux(A,B) دو ماتریس A و B با اندازه n×n را در هم ضرب کرده و نتیجه را در C برمی‌گرداند. مقدار برگشتی تابع زیر برای ماتریس M کدام است؟

Mat(M)
{
  P = M ; Q = M
  for i = ۱ to n-۱ do{
    P = aux(P,M)
    Q = aux(Q,P)
  }
  return(Q)
}

#loop-analysis#summation#arithmetic-series#matrix-power#accumulator#update-rule