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

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;
Источник

4 ответа

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

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

Источник

Давайте проследим, сколько раз каждый цикл выполняется на каждой итерации.

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

        for j <- 1 to i do   // InnerLoop_1
            B[i] <- B[i] + A[i, j];

        for j <- n down to (i + 1) do   // InnerLoop_2
            C[i] <- C[i] + A[i, j]
    end
end;

В первой итерации OuterLoop (i = 1) выполняется InnerLoop_1. once.

Во второй итерации OuterLoop (i = 2) выполняется InnerLoop_1. twice.

В третьей итерации OuterLoop (i = 3) выполняется InnerLoop_1. thrice.

. . .

В последней итерации OuterLoop (i = n) выполняется InnerLoop_1. n times.

Таким образом, общее количество выполнений этого кода равно

+ + 3+ … +

знак равно (n(n + 1) / 2)(Формула суммы натуральных чисел)

знак равно

знак равно

В первой итерации OuterLoop (i = 1) InnerLoop_2 выполняется раз.

Во второй итерации OuterLoop (i = 2) InnerLoop_2 выполняется раз.

В третьей итерации OuterLoop (i = 3) InnerLoop_2 выполняется раз.

. . .

В й итерации OuterLoop (i = n - 2) InnerLoop_2 выполняется раз.

В й итерации OuterLoop (i = n - 1) InnerLoop_2 выполняет time.

Напоследок ( nth) итерация OuterLoop (i = n), InnerLoop_2 выполняется раз.

Таким образом, общее количество выполнений этого кода равно

+ + + … + + +

знак равно 0+ 1+ 2+ … + n - 3+ n - 2+ n - 1

знак равно (n - 1)((n - 1) + 1) / 2(Формула суммы натуральных чисел)

знак равно (n - 1)(n) / 2

знак равно

знак равно

Time Complexity

Количество раз InnerLoop_1выполняет:

Количество раз InnerLoop_2выполняет:

Добавляя, получаем

(((n^2) + n) / 2)+ (((n^2) - n) / 2)

знак равно ((((n^2) + n) + ((n^2) - n)) / 2)

знак равно (((n^2) + n + (n^2) - n) / 2)

знак равно (((n^2) + (n^2)) / 2)

знак равно ((2(n^2)) / 2)

знак равно (n^2)

знак равно O(n^2)

——————

Также взгляните на эти

  1. /questions/10543993/chto-takoe-big-o-vlozhennogo-tsikla-gde-chislo-iteratsij-vo-vnutrennem-tsikle-opredelyaetsya-tekuschej-iteratsiej-vneshnego-tsikla/62055626#62055626
  2. /questions/39522799/vremennaya-slozhnost-vlozhennogo-tsikla-for/61824023#61824023
  3. /questions/59462490/on-i-funktsiya-vremennoj-slozhnosti-dannogo-koda/59574440#59574440
  4. /questions/21671824/ispolzuya-big-o-notation-kakova-pravilnaya-metka-dlya-etogo-algoritma/62348199#62348199
  5. /questions/40379058/vlozheno-dlya-tsikla-v-big-oh-complexity/62358542#62358542
Источник

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

Самый внешний цикл for будет выполняться 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.

Источник

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

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

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

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

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

Источник
Другие вопросы по тегам