алгоритмической сложности triangularization кода

Question

У меня есть следующий (частичный) код для triangularization разреженной MXN матрицы А (п является четным числом, и т = 3n/2-2):

y=0; 
for k=1:n 
if(mod(k,2)==0) 
    y=y+1; 
end 
    for j=k+1:n 
     A(k,j)=A(k,j)-tau*U(k,k); 
     if (k<=n-2) 
      for i=n-1:n 
       A(i,j)=A(i,j)-tau*U(i,k); 
      end 
     end 
     for i=n+1:n-2+y 
      A(i,j)=A(i,j)-tau*U(i,k); 
     end    
    end 
end 

и я заинтересованный в поиске точной алгоритмической сложности (в большой записи O) как функции как m, так и n. Я получил разные результаты из-за ветвей if.

спасибо.

Answer 1

y=0; 
// n times 
for k=1:n 
    // some constant complexity stuff 
    // it basically sets y to floor(k/2) 
    if(mod(k,2)==0) 
     y=y+1; 
    end 
    // n-k times 
    for j=k+1:n 
     A(k,j)=A(k,j)-tau*U(k,k); 
     // executed everytime except the last few iteration of the outermost loop 
     if (k<=n-2) 
      // constant complexity 
      for i=n-1:n 
       A(i,j)=A(i,j)-tau*U(i,k); 
      end 
     end 
     // executes y-2 times 
     for i=n+1:n-2+y 
      // so we basically need to bound the number of times this is executed 
      A(i,j)=A(i,j)-tau*U(i,k); 
     end    
    end 
end 

В k -й итерации цикла средней повторяется n-k раз и последний внутренний цикл итерацию y-2 который является floor(k/2)-2 раз (независимо от j)

Таким образом, внутреннее назначение выполняет Sum (n - k)(k/2 - 2) для k=1:n раз, который составляет Θ(n^3).