Как определить временную сложность этого кода

Question

Предположим, у нас есть массив размера S и сумма элементов массива равна R. Какова будет временная сложность следующего кода? Спасибо.

T = 0;
for(int i=0; i<S; i++)
   for(int j=0; j<A[i]; j++)
         T++;

Answer 1

для общего назначения, мы можем вычислить сложность времени следующим образом:

внешний l oop будет работать n раз (учитывая n запросов) и снова для общего назначения , мы можем предположить, что массив может иметь n чисел. поэтому внутренняя l oop будет повторять от 0 до n раз, что составляет (n + 1).

, поэтому общая сложность времени составляет - O (N * N).

и для вашего кода Фрагмент, сложность будет: -

внешний l oop будет повторять S раз, а затем для каждого внешнего l oop внутренний l oop будет повторять A [i] раз (т.е. i-й элемент).

Итак, общая сложность времени - O (S * (A [i]).

Answer 2

сложность времени будет n ^ 2, поскольку есть два цикла. Здесь N - очень большое число, так что оно равно бесконечности, и в программировании нас интересует только худший случай, поэтому в худшем случае S будет очень большим, и каждое значение A [i] также очень большое. Таким образом, сложность времени будет O (n ^ 2)