Подсчет/вычисление примитивных операций цикла for внутри цикла for

У меня есть алгоритм: Вход: X, одномерный числовой массив размера n

Let A = an empty 1-D numerical array of size n
For i = 0 to n-1
    Let s = X[0]
    For j = 1 to i
       Let s = s + X[j]
    End For
    Let A[i] = s /(i+1)
End For

Выход: n-элементный массив чисел A, такой что A[i] является средним значением элементов X[0],X[1],…,X[i]

Я пытаюсь написать формулу T (n) и вычислить ее, как написать цикл for J = 1 для i в цикле for i = 0 для n-1.

что такое формула T(n)?

T(n) — время, необходимое для выполнения алгоритма. t(n) будет использоваться для вычисления большого O ( O(n) ). поэтому на данный момент у меня T(n) = 2n+2(n-1)+5i(n-1)+6(n-1)+1. поскольку я подсчитывал записи, чтения и операции в алгоритме. Я не знаю, есть ли формула записи.


loops for-loop algorithm primitive operations
person Z Software undergraduate    schedule 23.10.2014    source источник
comment
временная сложность рассчитывается не с использованием операций чтения и записи, а с использованием количества инструкций, которые будут выполнены.   -  person Haris    schedule 23.10.2014

Ответы (1)


arrow_upward
0
arrow_downward

Я не совсем понимаю ваш вопрос, но все же

как записать цикл for J = 1 в i внутри цикла for i = 0 в n-1?

То, как вы написали цикл, в порядке, он будет делать то, что вы хотите.

что такое формула T(n)?

Вы можете заметить, что алгоритм запустит второй цикл

0 раз, когда i=0,

1 время, когда i=1,

2 время, когда i=2, . . . и так далее..

Это будет продолжаться до n-1, поэтому сложность приближается к сумме 0 + 1 + 2 + .... + n-1, которая равна n*(n-1)/2. что асимтотически O(n^2)

person Haris    schedule 23.10.2014
comment
T(n) время, необходимое для выполнения алгоритма. t(n) будет использоваться для вычисления большого O ( O(n) ). поэтому на данный момент у меня T(n) = 2n+2(n-1)+5i(n-1)+6(n-1)+1. поскольку я подсчитывал записи, чтения и операции в алгоритме. Я не знаю, есть ли формула записи. - person Z Software undergraduate; 23.10.2014