Плотно асимптотика алгоритма грубой силы для создания матрицы

Рассмотрим следующую задачу:Плотно асимптотика алгоритма грубой силы для создания матрицы

Дан массив R п элементов, построить матрицу М такое, что М [х, у] = S _{к = х .. .y} R [k]

Мне нужно рассчитать плотную асимптотическую границу ... например Θ (алгоритм)

Я считаю, что это O (n³), поскольку у вас есть два вложенных цикла, каждый с n операциями, а затем во внутреннем цикле for вы делаете до n дополнений по массиву R для генерации суммы который вставляется в M [x, y].

Является ли моя интуиция здесь правильной? Как я могу это доказать?

источник

2014-10-02 Sam Turani

Я не понимаю, что это сумма 'Σk = х ... у R [k] ', не могли бы вы подробно рассказать о том, что вам нужно включить в каждый индекс? –

Привет, Хави, простите, я не могу получить обозначение прямо на stackoverflow. Сумма начинается с k = x и поднимается до k = y и суммирует значение R [k] (значение элемента в R при индексе k). Это помогает? –

Да, вы суммируете все элементы R между индексами X и Y. Что происходит, когда Y> X? Сумма от индекса Y до индекса X? –

Вы можете сделать в O(n²) только два вложенных циклов, приняв запомнили решение ∑k=x…(y-1) в строке выше:

for x from 1 to n, y from 1 to n 
    if (y < x) 
     M[x,y] = 0 
    else if (y == x) 
     M[x,y] = R[y] 
    else 
     M[x,y] = M[x,y-1] + R[y]

источник

2014-10-02 00:51:43 Bergi

Или вас интересует только сложность немого алгоритма «грубой силы»? – Bergi

У меня было это в виду :) Я бы сказал, что if - это 'y

Ты прав! Я всегда делаю ошибки «один за другим», когда сталкиваюсь с математической суммой или одним индексированием: - / – Bergi

Плотно асимптотика алгоритма грубой силы для создания матрицы

ответ

Смежные вопросы