Дискретная математика Обозначение Big-O Сложность алгоритма

Я, вероятно, смогу понять часть б, если вы поможете мне сделать часть а. Я весь день смотрю на эту и подобные проблемы, и у меня просто проблемы с пониманием того, что делать с вложенными циклами. Для первого цикла n итераций, для второго n-1, для третьего n-1. Правильно ли я об этом думаю?

Рассмотрим следующий алгоритм,
который принимает на вход последовательность из n целых чисел a1, a2, ..., an
и выдает на выходе матрицу M = {mij}
, где mij — минимальный член< br> в последовательности целых чисел ai, a + 1, ..., aj для j >= i и mij = 0 в противном случае.

инициализировать M так, чтобы mij = ai, если j >= i и mij = 0

for i:=1 to n do
    for j:=i+1 to n do
        for k:=i+1 to j do
            m[i][j] := min(m[i][j], a[k])
        end
    end
end
return M = {m[i][j]}

(a) Покажите, что этот алгоритм использует сравнения Big-O(n^3) для вычисления матрицы M.
(b) Покажите, что этот алгоритм использует сравнения Big-Omega(n^3) для вычисления матрицы M.

Используя эту грань и часть (a), сделайте вывод, что алгоритм использует сравнения Big-theta(n^3).


algorithm matrix math big-o complexity-theory
person kkm    schedule 14.10.2012    source источник

Ответы (2)


arrow_upward
5
arrow_downward

В части A вам нужно найти верхнюю границу количества min операций.

Для этого ясно, что приведенный выше алгоритм имеет меньше min операций, чем следующий:

for i=1 to n
  for j=1 to n //bigger range then your algorithm
    for k=1 to n //bigger range then your algorithm
        (something with min)

Вышеприведенное имеет ровно n^3 min операций — таким образом, в вашем алгоритме меньше, чем n^3 минут операций.

Отсюда можно сделать вывод: #minOps <= 1 * n^3 (для каждого n > 10, где 10 произвольно).
По определению Big-O это означает, что алгоритм O(n^3)

Вы сказали, что можете вычислить B в одиночку, так что я позволю вам попробовать :)

подсказка: в среднем цикле больше итераций, чем for j=i+1 to n/2

person amit    schedule 14.10.2012
comment
Спасибо! Это имеет гораздо больше смысла, чем любой другой пример из учебника. Теперь о части б. Глядя на ваш намек, если я посмотрю только на первую половину терминов, количество операций будет меньше, но алгоритм все равно будет выполнять операции Cn ^ 3, где C ‹ = 1. Следовательно, алгоритм Big-Omega (n ^ 3). Это правильно? - person kkm; 14.10.2012
comment
@helmeplease: Идея правильная, но нужно сделать больше шагов, чтобы показать это, а затем прямо вперед, если вам это нужно формально. Попробуйте, используйте тот же подход, который я использовал, чтобы показать большое О, и после нескольких испытаний, я уверен, вы добьетесь своего. - person amit; 14.10.2012
comment
Должен ли я точно сказать, сколько операций имеет этот новый алгоритм, или я могу сказать Cn^3 операций, где C‹=1? Это то, с чем у меня самая большая проблема - подсчет количества операций, когда это не так просто, как в приведенном вами примере. - person kkm; 14.10.2012
comment
Если вы можете показать какое-то произвольное C*n^3, это нормально, но вам нужно указать конкретное C и показать, почему это C правильно. Если вы можете доказать, что такое C тоже существует, это тоже нормально. - person amit; 14.10.2012
comment
Как мне показать это для произвольного Cn^3, если я не знаю точного количества операций в моем алгоритме? Я не могу быть на 100% уверен, что minOps ›= Cn^3 для произвольного C, не так ли? - person kkm; 14.10.2012

arrow_upward
0
arrow_downward

Для каждой итерации внешнего цикла два внутренних вложенных цикла дадут n^2 сложность, если i == n. Внешний цикл будет выполняться i = 1 to n. Таким образом, общая сложность будет представлять собой ряд вроде: 1^2 + 2^2 + 3^2 + 4^2 + ... ... ... + n^2. Это суммарное значение равно n(n+1)(2n+1)/6. Игнорируя члены более низкого порядка этого члена суммирования, в конечном итоге порядок будет O(n^3)

person taufique    schedule 14.10.2012