как вычислить худший случай временной сложность алгоритма

Question

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

for j = 1 to i do 
    for k = 1 to j do 
     print(i,j,k) 

Answer 1

Поскольку у нас нет никаких условий, которые влияют на время выполнения этого алгоритма сложность оставалась бы то же самое: всегда есть такая же сложность времени.

Давайте будем простыми.

Если мы рассмотрим только семантическую важные инструкции во внутреннем цикле мы можем вычислить сложность, как следует:

Каждый внешний запуск цикла увеличивает следующий внутренний цикл запуска счетчика на единицу.

У нас было бы 1 + 2 + 3 + 4 + 5 + ... + i-1 + i циклов, каждый раз, когда внешний контур завершен, внутренний цикл будет выполнен еще один раз, чем раньше.

Теперь мы попытаемся обобщить это выражение.

Мы удвоим первоначальный термин, чтобы представить его в альтернативной форме, вы поймете, почему.

2 * (1 + 2 + 3 + 4 + 5 + ... + i-1 + i) = (1 + 2 + 3 + 4 + 5 + ... + i-1 + i) + (1 + 2 + 3 + 4 + 5 + ... + i-1 + i) 

2 * (1 + 2 + 3 + 4 + 5 + ... + i-1 + i) = (1+i) + (2 + (i-1)) + (3 + (i-2)) + ... + ((i-1) + 2) + (i+1) 

Теперь мы можем видеть, что в этом представлении мы имеем кратное одному и тому же термину.

2 * (1 + 2 + 3 + 4 + 5 + ... + i-1 + i) = (1+i) + (1+i) + (1+i) + ... + (1+i) + (1+i) 

2 * (1 + 2 + 3 + 4 + 5 + ... + i-1 + i) = i*(1+i) 

Поскольку у нас еще есть двойник нашей первоначальной сложности, нам нужно разделить на 2, что приводит к выражению замкнутой формы.

1 + 2 + 3 + 4 + 5 + ... + i-1 + i = (i*(1+i))/2 

в результате нашей сложности O(i(i+1)/2) =>O(i^2)

Мы можем сделать это из-за того, что данный многочлен внутри O(), вы можете просто заменить его x^highest_power

Мы не» t соблюдать инструкции, которые обязательно обрабатываются самими контрольными структурами; Я не думаю, что это задача. Если вы этого хотите, сообщите мне.