Вычислительная сложность алгоритма в Большой О, Большой Omega и Theta

Question

Я пытаюсь решить следующий вопрос о вычислительной сложности:

Compute вычислительная сложность следующего алгоритма и записать его сложность в Big O , Большой Омега и Тета

for i=1 to m { 
    x(i) =0; 
    for j=1 to n { 
     x(i) = x(i) + A(i,j) * b(j) 
    } 
} 

где A - это mxn, а b - nx1.

Я закончил с Big O O(mn^2) Big Omega(1) и Theta(mn^2).

Answer 1

Если предположить, что следующий оператор работает в постоянном времени:

x(i) = x(i) + A(i,j) * b(j) 

это таким образом сделано в O (1), и не зависит от значений для i и j. Так как вы итерацию над этим утверждением во внутреннем for цикле, ровно n раз, вы можете сказать, что следующий код работает в O (п):

x(i) =0; 
for j=1 to n { 
    meth1 
} 

(предполагая, что задание выполняется в постоянном времени, а также). Опять же, это не зависит от точного значения для i. Наконец, мы берем внешнюю петлю во внимание:

for i=1 to m { 
    meth2 
} 

Метод meth2 повторяются ровно m раз, таким образом, плотно верхняя границы для временной сложности в O (N м).

Поскольку нет никаких условных операторов, ни рекурсивных и структуры данных , б и х не изменяет выполнение программы, алгоритм также большие Омега (млн) и большой Theta (mn).

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

Answer 2

Напомните, что f = Theta(g) если и только если f=O(g) и f=Omega(g).

Матрица-векторное произведение может быть вычислено в Theta(mn) времени (при условии, наивные реализации) и суммой векторов в O(m), так что общее время работы является Theta(mn). Отсюда следует, что время также равно O(mn) и Omega(mn).