Общая сложность сложного цикла while с внутренним шагом, который увеличивается с каждым циклом

Question

Я начинаю изучать анализ сложности, и я не могу понять общую сложность этой части алгоритма Big-O, как следует это будет рассчитано?

Code Fragment    Time Complexity 
1 - C = 0     O(1) 
2 - while C <= L   O(L) 
3 -  f(C += 1)   O(???) 

Шаг 3 фактически выполняет больше шагов, но может быть скомпонован как функция f, выполняющая шаги C.

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

Answer 1

Давайте подключим несколько номеров и посмотрим, что произойдет.

• Для L = 0 шаг 3 запускается один раз с шагом 0;
• Для L = 1 шаг 3 выполняется дважды с 0, а затем 1 шаг;
• Для L = 2 шаг 3 выполняется 3 раза с помощью 0, 1 и 2 шагов;
• Для L = 3 шаг 3 выполняется 4 раза с помощью 0, 1, 2 и 3 шагов;
  [...]
• Для L = C шаг 3 выполняется n раз с шагом 0, 1, ... и C = L.

Скажем "нулевой ступени" является постоянная времени и изменить его на 1. Таким образом, есть два способа ответить на это:

• Ваша функция работает 1 + 1 + 2 + 3 + .. + L шагов. Это 1 + серия элементов L, которая суммируется с 1 + L * (L + 1)/2, поэтому это O (L);
• Он выполняет L раз функцию, которая может быть ограничена O (L), поэтому это O (L).

Answer 2

Если f(C) принимает C шаги и C увеличивается в каждой итерации до значения L, то алгоритм O(L^2).

Answer 3

Если функция F() НЕ изменения C ... то общая сложность трех линий вы показали это O (N): Время будет увеличиваться линейно, как размер L - C растет. Ни строка 1, ни строка 3 не способствуют: они оба по существу «постоянны».

Если функция F() DOES изменения C (например, с использованием глобальной переменной), то обе линии 2 и 3 внести свой вклад и cjungel-х и ответы GIUSTI являются правильными O(L^2).

Вот большая статья:

https://justin.abrah.ms/computer-science/how-to-calculate-big-o.html