почему временная сложность умножения квадратных матриц определяется как O (n ^ 3)?

Я сталкивался с этим в нескольких источниках (в Интернете и в книгах). Время выполнения умножения квадратных матриц составляет O (n ^ 3) для матриц размера nXn. (пример - сложность алгоритма матричного умножения)

Это утверждение указывает на то, что верхняя граница времени выполнения этого процесса умножения равна C.n^3, где C — некоторая константа, а n>n0, где n0 — некоторый вход, за пределами которого эта верхняя граница остается истинной. (http://en.wikipedia.org/wiki/Big_O_notation и В чем разница между Θ(n) и O(n)?) Проблема то есть я не могу вывести значения констант C и n0.

Мои вопросы -

  1. Может ли кто-нибудь предоставить математическое доказательство утверждения «большое О умножения квадратных матриц равно O (n ^ 3)»?

  2. каковы значения C и n0 ?


matrix-multiplication big-o
person Quest Monger    schedule 22.11.2012    source источник
comment
Для каждой ячейки (n ^ 2) вы пройдете по n ячейкам в соответствующих строках и столбцах и перемножите их вместе, так что это O (n ^ 3).   -  person nhahtdh    schedule 22.11.2012
comment
поэтому, если у нас есть 2 матрицы A и B, каждая из них равна nXn. а их произведение — матрица X размера nXn. вы подразумеваете, что для каждого значения в X (в X есть n ^ 2 значений) вам нужно пройти всего n элементов в A и B? или это больше похоже на n элементов в A и n элементов в B, что сделало бы это n ^ 4, а не n ^ 3.   -  person Quest Monger    schedule 22.11.2012
comment
n элементов в A и n элементов в B, да, но в сумме получается 2n, а не n^2. Таким образом, конечный результат O (n ^ 3).   -  person nhahtdh    schedule 22.11.2012

Ответы (1)


arrow_upward
8
arrow_downward

  1. Есть 3 цикла for друг в друге, от 0 до n-1 (или от 1 до n) каждый (как можно увидеть в предоставленной вами ссылке, хотя это и не совсем правильно), это дает O(n3). Формализовать его в правильное доказательство должно быть достаточно легко.

  2. а) Для формального доказательства время выполнения должно быть определено в терминах некоторого набора операций, обычно принимаемых за любую арифметическую операцию. Внутри 3 циклов for есть 2 арифметические операции (1 умножение, 1 сложение), таким образом, мы получаем 2.n3, таким образом, C = 2.

    б) n0 = 0, так как это верно начиная с n = 1

Обратите внимание, что, поскольку big-O — это всего лишь верхняя граница, мы также можем сказать, что сложность этого алгоритма равна O(nk) для любого k ›= 3 (то же самое было бы неверно, если бы мы используйте обозначение big-Theta). Мы также можем взять C и n0 как любое значение больше 2 и 0 соответственно (поскольку требование не состоит в том, чтобы найти наименьшие возможные значения).

person Bernhard Barker    schedule 22.11.2012
comment
Спасибо! и спасибо за исправление моей ошибки, я имел в виду асимптотическую верхнюю границу. Извините за недопонимание. актуально - mathforum.org/library/drmath/view/51904.html - person Quest Monger; 25.11.2012
comment
@QuestMonger большое спасибо за ссылку на mathforum... это был самый простой для понимания ответ, который я еще не встречал! - person Titus; 28.08.2014