Какова сложность времени наихудшего случая для этого алгоритма?

Question

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;

Answer 1

O (n ^ 2), если я правильно прочитал.

Зачем вам нужны две внутренние петли, мне не под силу. Почему бы не суммировать B и C в одном цикле?

Answer 2

наихудший случай - O (n²).

действительно есть три цикла, но не все внутри друг друга, что дает O (n²).

также вы можете ясно видеть, что внутренние циклы не будут идти от 1 до n (как это делает внешний цикл). Но поскольку это только изменит сложность времени на некоторую константу, мы можем игнорировать это и сказать, что это всего лишь O (n ^ 2).

Это показывает, что временная сложность является мерой, говорящей: ваш алгоритм будет масштабироваться с этим порядком, и это больше не займет времени. (однако всегда возможно быстрее)

для получения дополнительной информации о "вычислении" сложности наихудшего случая любого алгоритма, я могу указать вам на связанный с вопрос, который я задавал ранее

Answer 3

Просто объясню подробно для начинающих:

Наружный цикл будет выполняться n раз (от 0 до n) Тогда есть два цикла for в самом крайнем цикле for. Сначала цикл for будет идти от 1 до n (1 + 2 + 3 + 4 + ..... + n) И второй цикл for перейдет от n к 1 (n + n-1 + n-2 + .... + 1)

Формула суммирования для (1 + 2 + 3 + 4 + 5 + .... + n) равна n (n + 1) / 2

, поэтому общее время работы может быть вычислено как n + n (n + 1) / 2 + n (n + 1) / 2

Соблюдайте самый высокий многочлен в этом уравнении, это n ^ 2.

Мы можем еще больше упростить это уравнение, отбросить константы и проигнорировать линейную часть, что даст нам время выполнения n ^ 2.